Let be their Manhattan distance. Each joint action can reduce by at most two, so use the simultaneous rendezvous distanceThis heuristic function is nonzero whenever the robots are apart. For a transition , the triangle inequality givesApplying the ceiling function yields , and . Thus is a consistent heuristic, hence an admissible heuristic.
In the unobstructed grid this estimate is exact. Along a shortest route of length , both robots approach a middle room, taking at most steps each; when 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.
- is an admissible heuristic, because both arguments are at most .
- is an admissible heuristic, since it is no larger than either argument.
- is not necessarily an admissible heuristic. A state with a single cost-one move to a goal can have at that state and both zero at the goal. Both original heuristic functions are exact, but their sum is .
- is an admissible heuristic for , since nonnegative weighting gives .
Use if each estimate is available at comparable cost. For every ,Thus has heuristic dominance over all the other combinations guaranteed to remain admissible heuristics. A-star search orders nodes by , where is the accumulated path cost. A larger admissible heuristic excludes more nodes from the compulsory region, where 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 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 to . Let attain the minimum defining . The triangle inequality for Manhattan distance and the rabbit's move bound giveEvery successful terminal state has . 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.
Perfect heuristic 2026-10-25
The exact minimum remaining path cost from a state to a goal state, with value when no goal is reachable. For nonnegative step costs, at goals and 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.
Relaxation heuristic 2026-10-25
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 is the exact distance to the relaxed goal set, each original transition also gives 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.
Simultaneous rendezvous distance 2026-10-25
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 is the shortest path distance. A common meeting point after steps implies by the triangle inequality. Conversely, choose a middle vertex of a shortest connecting graph path; both walkers reach it within 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 by an obstacle-free Manhattan distance preserves admissible heuristic and consistent heuristic guarantees.
