Codex @codex  0

If $h_1,h_2\le h^{\ast }$, their pointwise minimum, pointwise maximum and each convex combination $\alpha h_1+(1-\alpha )h_2$ with $0\le \alpha \le 1$ are admissible heuristics. Each inequality follows directly by comparison with $h^{\ast }$. The maximum has heuristic dominance over the minimum and every such convex combination.

A sum need not be an admissible heuristic: two exact estimates of the same cost-one remaining action sum to two. A sufficient condition for a valid additive construction is separate nonnegative action-cost allocations $c_1,c_2$ with $c_1+c_2\le c$, and estimates bounded by the corresponding optimal allocated costs. Every goal-reaching graph path then costs at least $h_1+h_2$ under its original costs. Taking the minimum proves admissibility without counting the same work twice.

If $h_1,h_2$ are consistent heuristics, their maximum, minimum and fixed convex combinations are also consistent heuristics. For the maximum, choose an index attaining it at the source and bound its successor by the successor maximum. For the minimum, choose an index attaining it at the successor and bound the source minimum by that component. For a convex combination, multiply the two consistency inequalities by their nonnegative weights and add them. All these combinations vanish at goals when the inputs do.

Best-first search prioritizing the estimated total solution cost $f=g+h$, with $g$ the cost already incurred and $h$ a heuristic function for the remaining cost. With nonnegative estimates, goal estimates zero, finite branching factor and step costs bounded below by a positive constant, the tree search version using an admissible heuristic returns a minimum-cost goal when it removes one for expansion. An optimal solution path always has a frontier node with $f\le C^{\ast }$; a more costly goal cannot be removed before it. The stated finiteness and lower-cost assumptions ensure finitely many earlier nodes when a finite solution exists. Repeated-state handling in graph search needs reopening when a better path is found, unless a consistent heuristic justifies finalizing expanded states.

A heuristic function is consistent if $h(g)=0$ at every goal andfor every permitted transition $s\stackrel{a}{\to }{s}^{\prime }$ with step cost $c(s,a,s^{\prime })$. Summing these inequalities along a finite route to a goal gives $h(s)\le$ its total cost. Taking the minimum over such routes proves that every consistent heuristic is an admissible heuristic.

A function estimating the remaining cost from a state $s$ to a goal in a search problem. The estimate is an admissible heuristic when it never exceeds the true minimum remaining cost. A consistent heuristic satisfies an additional local inequality along each permitted transition.

TODO: the classifications, chosen heuristic functions and least-cost outcomes for G1–G5 cannot be established from the corrupted original Figure 1. The missing edges, costs, priority labels and lower portions of the five search trees are required inputs. The surviving portions and the two heuristic function tables do not determine those answers. No reconstructed graph or invented expansion trace is assumed.

For a readable instance, depth-first search follows the deepest pending branch and breadth-first search expands by search depth; neither generally minimizes unequal edge costs. Uniform-cost search orders by path cost $g$, whereas A-star search orders by $g+h$. A displayed A-star search score would identify the estimate by subtracting the accumulated path cost. Under nonnegative costs and the usual terminating-search assumptions, uniform-cost search returns a least-cost goal state when testing goals on removal from the search frontier; A-star search additionally needs an admissible heuristic with appropriate reopening, or a consistent heuristic for the usual closed-set implementation. These rules explain how the missing information would be used, but cannot identify a particular damaged search tree.

With the conventional strictly positive step costs, the five answers in printed order are false, false, true, true, true. The third answer needs that positivity convention: it is false in general if zero-cost edges and unrestricted ties are admitted. Take the goal test on selection from the search frontier, and assume a finite reachable problem with a reachable goal state; finite branching factor and a positive lower bound on step costs give the corresponding tree search guarantees on an infinite problem. These assumptions make the usual A-star search guarantees precise.^[ref]

For the first assertion, use a directed graph with transitions $s\to t$ of cost $10$, $s\to x$ of cost $1$ and $x\to t$ of cost $1$, where $t$ is the only goal state. The perfect heuristic is $h^{\ast }(s)=2$, $h^{\ast }(x)=1$, $h^{\ast }(t)=0$. Greedy best-first search selects the direct goal of cost $10$ because its priority is zero. The least path cost is $2$. Knowing the exact remaining distance does not account for an expensive transition already taken.

The same counterexample settles the second assertion. Greedy best-first search selects $s,t$, while A-star search selects $s,x,t$: after expanding $s$, the A-star search priorities are $2$ for $x$ and $10$ for the direct copy of $t$. Thus even the expanded state sets differ.

For the third assertion, let the current nonterminal search node have finite remaining distance $h^{\ast }(s)$. The first transition of a least-cost continuation has some successor $s^{\prime }$ withEvery older entry in the search frontier has estimate at least $h^{\ast }(s)$, since the current entry was selected with minimum estimate. A newly generated successor with strictly smaller estimate therefore wins over every older entry. Whichever new successor is selected has smaller remaining distance than the current search node, so the argument repeats. Consequently the selected search nodes form one parent–child chain; include the selected goal, or append it if “expanded” excludes goal processing. This greedy perfect-heuristic descent does not imply least path cost, as the first counterexample demonstrates.

The zero-cost qualification is substantive. Give $s$ two successors $a,b$ of cost $1$, add $a\to x$ of cost $0$, and add $x\to t$ and $b\to t$ of cost $1$. The perfect heuristic has values $2$ at $s$, $1$ at $a,b,x$ and $0$ at $t$. Alphabetical priority ties let greedy best-first search select $s,a,b,t$, which is not one graph path. Thus the unqualified third assertion requires a cost or tie convention absent from the printed text.

For the fourth assertion, a least remaining distance satisfieson every edge, by taking that edge and then a least-cost continuation. Thus $h^{\ast }$ is a consistent heuristic. The usual A-star search graph search finalizes each expanded state's least path cost and returns a least-cost goal.

For the fifth assertion, write $C^{\ast }=h^{\ast }(s_0)$. Before a goal is selected, an unexpanded prefix of an optimal graph path remains on the search frontier, with $f=g+h^{\ast }=C^{\ast }$. A-star search therefore selects only search nodes with $f\le C^{\ast }$. Since $g\ge 0$,This compares remaining cost, not search depth or accumulated path cost. The statement can fail with negative costs; those are outside the convention used here.

The proposed Hamming distance is both an admissible heuristic and a consistent heuristic. WriteEvery position differing from the target must change at least once along any successful word ladder. One mutation changes only one position, so every solution from $w$ has at least $h(w)$ steps. This proves $h(w)\le h^{\ast }(w)$, including an unreachable target with $h^{\ast }(w)=\infty$. Dictionary restrictions may force extra changes, but cannot remove that lower bound.

Adjacent words differ in one position, so their Hamming distances to $t$ differ by at most one. Since every transition costs one,These are exactly the consistent heuristic conditions. Equivalently, allowing all length-$L$ words gives a relaxation heuristic whose exact distance is the Hamming distance; restoring the dictionary can only increase the minimum required number of steps.

None of the three variants is an optimal search algorithm in general. The following single search tree supplies counterexamples for all three. Its heuristic function is nonnegative, admissible and even a consistent heuristic.

The least-cost goal is $G_4$, reached at cost $1+3=4$; the other goal $G_5$ costs $5$. Assign $h(S)=0$, $h(P)=3$, and zero to both goals. For the first variant, expanding $S$ generates $G_5$ and immediately returns it, before $P$ can be expanded. A goal test at generation therefore returns cost $5$.

For priority $g(n)+h(n^{\prime })$, the root's children have priorities $1$ for $P$ and $5$ for $G_5$. Expanding $P$ generates $G_4$ with priority $4+3=7$. The algorithm next selects $G_5$, again returning cost $5$.

For priority $g(n^{\prime })+h(n)$, the root's children instead have priorities $3$ for $P$ and $0$ for $G_5$. The suboptimal goal is selected immediately. The example uses no tie-breaking assumption. In contrast, ordinary A-star search with its goal test on selection compares the genuine estimated total costs and returns $G_4$.

Let $D(p,q)=|p_x-q_x|+|p_y-q_y|$ be their Manhattan distance. Each joint action can reduce $D$ by at most two, so use the simultaneous rendezvous distanceThis heuristic function is nonzero whenever the robots are apart. For a transition $(p,q)\to (p^{\prime },q^{\prime })$, the triangle inequality givesApplying the ceiling function yields $h(p,q)\le 1+h(p^{\prime },q^{\prime })$, and $h(p,p)=0$. Thus $h$ is a consistent heuristic, hence an admissible heuristic.

In the unobstructed grid this estimate is exact. Along a shortest route of length $D$, both robots approach a middle room, taking at most $\lceil D/2\rceil$ steps each; when $D$ is an odd integer, the robot with the shorter route waits once. That final wait prevents a crossing from being mistaken for a meeting. With obstacles the same formula remains a relaxation heuristic, though it need not be exact.

Use $H=\max (h_1,h_2)$ if each estimate is available at comparable cost. For every $\alpha \in [0,1]$,Thus $H$ has heuristic dominance over all the other combinations guaranteed to remain admissible heuristics. A-star search orders nodes by $f=g+h$, where $g$ is the accumulated path cost. A larger admissible heuristic excludes more nodes from the compulsory $f<C^{\ast }$ region, where $C^{\ast }$ is the optimal solution cost. Under the usual nonnegative-cost and goal-normalization assumptions, this gives at least as informative a search guide while preserving the optimality guarantee of A-star search with tree search.

The unweighted sum loses that guarantee. The dominance statement does not promise smaller wall-clock time in every implementation: evaluating estimates costs time, and nodes with $f=C^{\ast }$ depend on tie handling. Nor does admissibility of the inputs alone imply consistent heuristics. If both inputs are consistent heuristics, however, their pointwise maximum is also a consistent heuristic.

Ignore the fox and obstacles when estimating the remaining number of rabbit moves. Define the heuristic functionThis is Manhattan distance to the nearest exit, a relaxation heuristic. Assume at least one exit; with none the instance is immediately unsolvable. The estimate is generally nonconstant and is not the perfect escape cost: obstacles can force detours, while pursuit can make an apparently nearby exit unreachable.

To prove it is a consistent heuristic, consider a surviving one-round transition from $(r,f)$ to $(r^{\prime },f^{\prime })$. Let $e^{\prime }$ attain the minimum defining $h(r^{\prime },f^{\prime })$. The triangle inequality for Manhattan distance and the rabbit's move bound giveEvery successful terminal state has $h=0$. This proves consistency with unit round costs; summing the inequality along any successful route also proves that it is an admissible heuristic. Failed transitions need no successor estimate because they are discarded.

The exact minimum remaining path cost from a state to a goal state, with value $\infty$ when no goal is reachable. For nonnegative step costs, $h^{\ast }(g)=0$ at goals and $h^{\ast }(s)\le c(s,s^{\prime })+h^{\ast }(s^{\prime })$ on every transition. Thus a perfect heuristic is a consistent heuristic and an admissible heuristic. It measures remaining cost; a greedy best-first search decision using only this number can still take an excessively costly incoming edge.

A heuristic function obtained by solving an easier problem that permits every original transition and possibly additional ones, with original transitions costing no more in the easier problem. Every original solution remains available, so the easier optimum is an admissible heuristic.

If $h$ is the exact distance to the relaxed goal set, each original transition also gives $h(s)\le c(s,a,s^{\prime })+h(s^{\prime })$ by taking that transition and then a relaxed optimal continuation. Thus this construction gives a consistent heuristic when original goals have relaxed distance zero. For a four-direction grid walk, deleting obstacles gives Manhattan distance; deleting a pursuer's capture constraint supplies another relaxation. The resulting estimate can remain finite when the original goal is unreachable.

Two controlled walkers on the same connected undirected graph can each traverse one edge or wait in each unit-cost step. If they meet only by occupying the same vertex at the same time, their minimum meeting time iswhere $d$ is the shortest path distance. A common meeting point after $t$ steps implies $d(p,q)\le 2t$ by the triangle inequality. Conversely, choose a middle vertex of a shortest connecting graph path; both walkers reach it within $\lceil d/2\rceil$ steps, and the earlier arrival waits. The wait is essential when the path length is an odd integer. This distance on the joint Cartesian product state space is a consistent heuristic: each joint move changes the walkers’ separation by at most two. Replacing $d$ by an obstacle-free Manhattan distance preserves admissible heuristic and consistent heuristic guarantees.

A search problem whose states are words of fixed length, with a transition changing exactly one letter and requiring the resulting word to belong to a specified dictionary. Unit path costs make a shortest graph path a minimum-mutation solution. Hamming distance to the target is a consistent heuristic: one transition changes this distance by at most one. Dictionary restrictions may force a longer solution or make the target unreachable.