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

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.

Author-provided chapter: aima.cs.berkeley.edu/4th-ed/pdfs/newchap04.pdf

Printed section 4.1, especially pp. 97–100, discusses greedy best-first search, A-star search, admissible heuristics and the finite-branching factor/positive-cost completeness conditions. The printed chapter identity is used without inferring an edition from its host directory.

The first assertion is false. Give the root a first child that is a goal state of cost ten and another child leading to many cheaper non-goal search nodes. Depth-first search can take the first child and stop immediately. A-star search with the admissible heuristic $h=0$ behaves as uniform-cost search and expands the cheaper non-goal search nodes before selecting that goal. Thus an admissible heuristic does not make A-star search expand fewer nodes than every possible depth-first search ordering. The latter need not return an optimal solution.

The second assertion is true under the usual finite-branching factor assumption. Breadth-first search orders by search depth, not path cost. Every finite depth contains finitely many search nodes, so a goal at finite depth is eventually reached even if some steps cost zero. Zero-cost steps can affect cost optimality, but do not obstruct this completeness argument. An infinite branching factor would invalidate the argument irrespective of step costs.

The third assertion is true as a worst-case black-box requirement, with a finite optimum assumed. If outgoing actions are known only by expanding a state, an unexamined reachable branch can conceal a sufficiently negative-cost action followed by a route to a goal. Its total cost can beat the current solution by an arbitrarily large amount. Without additional lower bounds or structural information, finding one cheap solution cannot justify stopping; exhaustive examination can be necessary. This does not assert that every already-described irrelevant state must be visited on every input. Moreover, a reachable negative-cost cycle in a graph that can still reach a goal can make costs unbounded below, in which case no finite-cost optimal solution exists at all.

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.

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.

Maintain a certified solution-cost ceiling and prune only search nodes whose lower bound strictly exceeds it. Initially let $B=\infty$, or set $B=u(r)$ at the root $r$ when that value is finite. Whenever a search node $n$ is generated, updateRun ordinary A-star search with $f(n)=g(n)+h(n)$ and a goal test when removing a search node from the search frontier. Discard a generated search node, or a queued search node encountered after a later bound improvement, ifThis is branch and bound using a lower bound $f$ and an upper bound $B$. A finite $u(n)$ certifies that some goal is reachable from $n$ within that remaining-cost ceiling; for a dead end, $h^{\ast }(n)=\infty$ forces $u(n)=\infty$ too. Every finite quantity $g(n)+u(n)$ is consequently at least the global optimum $C^{\ast }$.

On an optimal solution path, admissible heuristic estimates ensure $f(n)\le C^{\ast }\le B$. Hence no search node of that path is pruned. The finite-branching factor and positive step-cost hypotheses from (a) still ensure completeness, and the usual A-star search argument makes the first selected goal optimal. A smaller bound can remove branches earlier; it need not improve every instance.

The strict inequality matters: $u$ is only a numerical bound and need not provide an actual stored solution path. If $B=C^{\ast }$, pruning at $f(n)\ge B$ could remove every optimal continuation. Nor may the algorithm return a path merely because its lower bound meets $B$ when no witnessing path has been constructed. With an actual incumbent solution, the familiar equality-pruning variant can instead retain and return that incumbent.

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.

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.