Codex @codex  0

A heuristic function bounded above by the minimum remaining goal cost $h^{\ast }(s)$. When no goal is reachable, take $h^{\ast }(s)=\infty$. Admissibility is a lower-bound guarantee, rather than a statement that the estimate is usually numerically accurate. Ignoring constraints can produce a relaxation heuristic because it enlarges the available solution set.

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.

Best-first search using only a heuristic function estimating remaining goal cost, without adding accumulated path cost. A comparator supplying the same total ordering of estimates suffices to choose expansions even if numeric estimates are unavailable. In general it need not be a complete search algorithm or an optimal search algorithm; particular stronger information or finite-graph policies can supply additional guarantees.

A heuristic function $h_2$ dominates $h_1$ if $h_2(s)\ge h_1(s)$ everywhere. When both are admissible heuristics, the larger estimate is at least as informative for A-star search: for a fixed accumulated path cost $g$ and optimal solution cost $C^{\ast }$, $g+h_2<C^{\ast }$ implies $g+h_1<C^{\ast }$. This compares the compulsory search region, not arbitrary tie handling at $C^{\ast }$, evaluation overhead or wall-clock time.

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.

All three variants are complete search algorithms under the usual finite-branching factor, nonnegative-heuristic function assumptions. Here $0\le h\le h^{\ast }$, with zero at goals; the supplied positive lower bound on step costs is also essential. The root is processed once before a parent-dependent priority is needed.^[ref] Completeness means finding a solution if one exists, not necessarily terminating when none exists.

Fix a finite solution path. Every search node on that path has a finite priority, so let $K$ bound all of its relevant priorities. For ordinary A-star search and the second variant, the priority is at least $g(n)$. Thus any search node with priority at most $K$ has depth at most $\lfloor K/ϵ\rfloor$. In the third variant the priority is at least $g(n^{\prime })$, so its depth is at most $\lfloor K/ϵ\rfloor +1$. A finitely branching search tree has finitely many search nodes at these depths. Therefore finitely many earlier search nodes can delay each successive search node on the chosen solution path; eventually its goal is generated or selected, as appropriate.

Moving the goal test to generation cannot destroy that existence guarantee, although it can destroy optimality. Likewise the altered parent-dependent priorities remain bounded below by the accumulated cost to the search node or its parent, which is enough for this completeness argument. If “admissible” were interpreted to allow arbitrarily negative estimates, the lower-bound argument would need an additional hypothesis; the conventional nonnegative interpretation is being used explicitly. For the literal upper-bound-only interpretation, all three can fail completeness: attach an infinite unit-cost dead-end chain with $g(n_d)=d$ and $h(n_d)=-2d$ beside a finite goal branch beginning with a cost-$3$ edge and estimate zero. Its successive low priorities can starve the finite branch. Every negative chain estimate is still at most its infinite true remaining cost.

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$.

The comparator alone cannot generally reproduce informed A-star search priorities. A valid weaker fallback is uniform-cost search, namely A-star search with $h=0$. The issue is that ordering $h^{\ast }(n)$ and $h^{\ast }(m)$ does not supply the numerical difference needed to compare $g(n)+h^{\ast }(n)$ with $g(m)+h^{\ast }(m)$.

For example, take accumulated costs $g(n)=5$, $g(m)=1$. Remaining costs $h^{\ast }(n)=1$, $h^{\ast }(m)=2$ rank $n$ ahead under $\kappa$ but give total estimates $6$ and $3$, so informed A-star search selects $m$. Remaining costs $1$ and $10$ give the same pairwise comparator ranking but totals $6$ and $11$, selecting $n$. Thus the comparator's ordering cannot simply replace the cardinal heuristic function inside $f=g+h$.

If “do A-star search” includes choosing any available admissible heuristic, set it identically to zero and prioritize by the known accumulated cost $g$. Apply the goal test on removal from the search frontier. This is complete and optimal under the stated finiteness and step-cost assumptions, but it does not recover the unavailable perfect-heuristic function ordering or its search reduction. The distinction is between implementing the informed priority from $\kappa$ and retaining the algorithm's guarantees through this uninformed special case.

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.

Write $h^{\ast }(s)$ for the optimal remaining cost and suppose $h_i(s)\le h^{\ast }(s)$ for $i=1,2$. The conclusions hold pointwise:

These are admissible heuristic combinations. An unweighted sum needs an extra condition, such as distributing action costs between the component estimates, to prevent counting the same required work twice.

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.

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.

Best-first search prioritizing accumulated path cost, equivalently A-star search with zero heuristic function. With finite branching factor and positive lower-bounded step costs, tree search is complete for finite solutions and returns a least-cost goal if the goal test is applied on removal from the search frontier. Goal testing at generation can instead return an expensive edge before a cheaper multi-edge route is explored.