Algorithms and data structures · Intermediate

A* search: combine path cost and a lower-bound estimate

Use g+h priorities to guide shortest-path search, distinguishing admissibility, consistency and reopening requirements.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Keep accumulated and estimated cost separate
  2. Compare two candidate branches
  3. Distinguish admissibility from consistency
  4. Useful guidance is not free
  5. Ask Logeia about this articleCheck your understanding

Keep accumulated and estimated cost separate

A* prioritizes a candidate vertex v using f(v)=g(v)+h(v), where g is the best path cost discovered from the source and h estimates the remaining cost to a goal. Here the setting is a finite graph with nonnegative edge weights. Setting every h to zero recovers Dijkstra-style priorities. An estimate is not a replacement for the actual accumulated cost. Similarly, discovering a goal as a neighbor is different from taking it from the priority queue under the algorithm’s proper termination condition. The distinction affects which path can safely be reported.

Compare two candidate branches

Let S→A cost 2, S→B cost 4, A→G cost 5 and B→G cost 1. With h(A)=5 and h(B)=1, the candidates have priorities 7 and 5, so the search favors B and finds a goal route costing 5. With zero estimates, A may be expanded earlier, but the correct final minimum is unchanged. If h(B) is instead an overestimate of 100, the cheaper branch can be deferred while a cost-7 goal is selected. Guidance can save exploration only under conditions compatible with the desired correctness guarantee.

Distinguish admissibility from consistency

An admissible heuristic never exceeds the true remaining optimal cost. Consistency additionally requires h(u)≤w(u,v)+h(v) for every edge and a zero estimate at a goal. A consistent heuristic supports the standard argument that a vertex removed with its best priority can be finalized. With an admissible but inconsistent heuristic, a better g may require reopening a vertex already considered closed. Do not attach an admissibility-only optimality claim to a graph-search implementation that permanently discards such later improvements. The algorithm and its assumptions must be described together.

Useful guidance is not free

A helpful estimate can reduce expansions, but does not promise that every instance will be faster than Dijkstra’s algorithm. Include the cost of evaluating h, maintaining visited states and ignoring outdated queue entries. On a four-neighbor unit-cost grid, Manhattan distance is a lower bound obtained by ignoring obstacles. Adding diagonal moves or changing move costs requires reevaluating that bound. Infinite state spaces require additional completeness conditions beyond this finite-graph discussion. Benchmark expanded states and memory as well as elapsed time, and verify path cost against a known-correct baseline before interpreting a speed improvement.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 11

Choose a learning path