A* Optimality & Efficiency Proofs
Consistency, optimal efficiency and tie-breaking.
"A* is optimally efficient" is one of the most quoted results in AI, and one of the most misquoted. It does not say that A* is fast, and it does not hold for every admissible heuristic. This lesson states it precisely, proves it with an adversary argument, and shows where the fine print bites: inconsistency, ties and the last -layer.
What you’ll learn
- State the standard model (locally finite graphs, costs at least ) and prove that A* with reopening is complete and optimal for any admissible heuristic.
- Prove that A* with a consistent heuristic is Dijkstra's algorithm on reduced costs, and explain what inconsistency costs.
- Prove the optimal efficiency of A* for consistent heuristics (Dechter & Pearl, 1985), and locate exactly where consistency is needed.
- Quantify how tie-breaking in the final layer can change A*'s effort from linear to quadratic in the solution length.
The model, and optimality with reopening
Every expansion has . The lemma's state bounds the frontier minimum:
Termination. An expanded state has , so its current path has at most edges. Each expansion of a state uses a strictly cheaper path than the last, so expansions inject into a finite set of paths:
Optimality. The returned goal was popped, so , and no solution costs less than :
Consistency is Dijkstra on reduced costs
Reduced costs are nonnegative exactly when is consistent:
They telescope: for any path from to ,
So Dijkstra's keys are A*'s keys minus a constant. Dijkstra on nonnegative costs settles each state once, at its true distance, in nondecreasing order; translated back, A* expands each state once, with , in nondecreasing .
On a finite graph with a binary heap this costs plus the evaluations of . The same potential trick drives Johnson's all-pairs algorithm (1977) and the ALT heuristics for undirected road graphs, over precomputed landmarks (Goldberg & Harrelson, 2005), which are consistent by the triangle inequality:
With an admissible but inconsistent , some reduced costs are negative, and Dijkstra's invariant fails: a state can be expanded and later reached more cheaply. A* with reopening stays optimal, but the price can be steep. Martelli (1977) built graphs with states on which A* performs on the order of expansions, and gave a variant (algorithm B) with an worst case.
Inconsistent heuristics are not exotic: they arise from taking the maximum over a random subset of lookups, compressed pattern databases, or learned estimates. In undirected graphs, bidirectional pathmax propagates values between neighbors, and Felner et al. (2011) showed that such heuristics can pay off in practice.
Pathmax sets for each child of , so never decreases along a path. Run A* graph search without reopening, with pathmax, on the Hidden Layer's example: and cost 1, costs 1, costs 2, costs 3; , , , , . What cost does it return?
- 5: pathmax repairs the inconsistency
- 6: is still closed along the costlier path first
- 4
- It fails to terminate
Show the answer
B. 6: is still closed along the costlier path first
The -values become , , then via , then . When is finally expanded, is offered with (pathmax ), but is already closed, so the cheaper path is discarded and is returned at cost 6. Pathmax makes monotone along each path, not consistent across different paths to the same state; optimality still needs reopening.
Optimal efficiency
Suppose that on instance , returns without expanding some state with . Pick with , and build by adding a new goal , with , and one edge of cost :
cannot tell from . The only difference is an edge leaving , which never expanded, so makes identical observations on both and returns the same solution, of cost , on .
is still admissible on ; this is where consistency is used. For a state that reaches by a cheapest path of cost , consistency along that path gives , so is below the cost of the new route; for all old routes as before:
So is admissible on , yet returns cost there, which is not optimal. This contradicts (iii), so must expand .
Read the hypotheses as the theorem's limits:
- Ties. States with may or may not be expanded, depending on tie-breaking, and no rule is best on every instance. Dechter and Pearl develop a hierarchy of optimality notions to handle this.
- Inconsistency. For admissible but inconsistent heuristics, step 3 fails: on the modified instance may overestimate, so a competitor owes nothing there. A* can then be beaten, for example by Martelli's algorithm B on instances that force A* into exponentially many re-expansions.
- Expansions, not time. The comparison counts expansions among algorithms that use the same . It says nothing about the time per expansion, or about how large the must-expand set is.
Think first Does optimal efficiency imply that A* with a consistent heuristic beats every bidirectional search?
No. A bidirectional algorithm violates condition (i): it also expands states backward from the goal, so the adversary argument does not apply to it. The right lower bound for bidirectional search concerns pairs of states, one from each side, and on some problems bidirectional search needs fewer expansions than A*, for instance when the heuristic is weak and the two searches can meet in the middle.
Ties, the last f-layer, and the frontier
On an open 4-connected grid with unit costs, Manhattan distance is the true cost to go. Then everywhere, with equality exactly on shortest paths, so the must-expand set is empty and all of A*'s work happens in the tie layer. If start and goal differ by rows and columns, every cell of their bounding rectangle lies on some shortest path.
On an open grid, start and goal differ by 10 rows and 20 columns. With the Manhattan heuristic, how many cells have ?
Show the answer
231
Every cell of the bounding rectangle lies on a monotone shortest path: . Breaking ties toward larger (smaller ) dives along one path and expands 30 cells; first-in, first-out tie-breaking can expand nearly all 230 non-goal cells. With , that is versus up to about expansions.
Breaking ties toward larger is the usual default. In planning tasks with many zero-cost actions, the final plateau can hold most of the search, and how to explore it is studied in its own right (Asai & Fukunaga, 2016).
Key takeaways
- With reopening, an admissible heuristic suffices: by the frontier lemma, A* is complete and optimal on locally finite graphs with costs at least .
- A consistent heuristic makes A* Dijkstra's algorithm on the reduced costs : no reopening, and on finite graphs. Inconsistent heuristics can force exponentially many re-expansions.
- Optimal efficiency (Dechter & Pearl, 1985): with a consistent , every algorithm that must be optimal whenever is admissible expands all states with . The proof hides a cheap goal behind any skipped state.
- The theorem is silent about the layer, where tie-breaking can change the effort from linear to quadratic in the solution length, and about running time and the size of the must-expand set.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
Which statement is the optimal-efficiency theorem for A*?
- A* expands fewer nodes than any other search algorithm on every problem
- With any admissible heuristic, A* never expands a state twice
- With a consistent heuristic, every algorithm that learns the graph by expanding states and is optimal on every instance where is admissible must expand each state with
- With a consistent heuristic, A* runs in time polynomial in the solution length
Show the answer
C. With a consistent heuristic, every algorithm that learns the graph by expanding states and is optimal on every instance where is admissible must expand each state with
A* expands the states with plus some of the layer, and the adversary argument shows that every competitor in that class must expand the former. The comparison is with algorithms using the same heuristic, modulo ties, and it counts expansions, not time.
Why does A* with a consistent heuristic expand states in the same order as Dijkstra's algorithm on the reduced costs ?
- Reduced costs are zero along optimal paths
- The reduced cost of any path from to is , so the two algorithms' keys differ by a constant
- Dijkstra's algorithm also uses a heuristic
- Both algorithms expand states in order of increasing depth
Show the answer
B. The reduced cost of any path from to is , so the two algorithms' keys differ by a constant
The terms telescope along a path, leaving . Consistency makes every reduced cost nonnegative, which is exactly what Dijkstra's correctness needs.
The optimal-efficiency proof adds a goal behind a state that the competitor never expanded, with just above . Where is consistency used?
- To show that the competitor cannot tell the two instances apart
- To show that the new path through is cheaper than
- To show that A* never reopens states
- To show that remains admissible on the modified instance
Show the answer
D. To show that remains admissible on the modified instance
States that can reach now have a new route to a goal, of cost . Consistency along the path from to gives , so still never overestimates, and the competitor is obliged to be optimal on the new instance. With an inconsistent , this step fails.
On an open grid where Manhattan distance equals the true cost to go, which statement about A* is correct?
- A* must expand every cell of the start–goal bounding rectangle
- No cell has , so the effort depends entirely on how ties at are broken
- A* expands exactly the cells of one shortest path, whatever the tie-breaking
- A* degenerates to uniform-cost search
Show the answer
B. No cell has , so the effort depends entirely on how ties at are broken
With , everywhere, with equality exactly on shortest paths, which here fill the bounding rectangle. Preferring larger (smaller ) follows one path; preferring smaller can expand nearly the whole rectangle, quadratically many cells in the path length.
Further reading
- P. E. Hart, N. J. Nilsson & B. Raphael, "A Formal Basis for the Heuristic Determination of Minimum Cost Paths," IEEE Transactions on Systems Science and Cybernetics 4(2) (1968), 100–107.
- R. Dechter & J. Pearl, "Generalized best-first search strategies and the optimality of A*," Journal of the ACM 32(3) (1985), 505–536.
- A. Martelli, "On the complexity of admissible search algorithms," Artificial Intelligence 8 (1977), 1–13.
- A. Felner, U. Zahavi, R. Holte, J. Schaeffer, N. Sturtevant & Z. Zhang, "Inconsistent heuristics in theory and practice," Artificial Intelligence 175 (2011), 1570–1603.
- S. Russell & P. Norvig, Artificial Intelligence: A Modern Approach, 4th ed. (Pearson, 2020), section 3.5.