Simple Algorithm
Artificial Intelligence · Deep Layer · 30 min

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

What you’ll learn

  • State the standard model (locally finite graphs, costs at least ε>0\varepsilon>0) 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 f=C∗f=C^* layer can change A*'s effort from linear to quadratic in the solution length.

The model, and optimality with reopening

DerivationProof
  1. min⁡frontierf ≤ f(sj)=g∗(sj)+h(sj) ≤ g∗(sj)+h∗(sj)=C∗\min_{\text{frontier}}f\ \le\ f(s_j)=g^*(s_j)+h(s_j)\ \le\ g^*(s_j)+h^*(s_j)=C^*

    Every expansion has f≤C∗f\le C^*. The lemma's state sjs_j bounds the frontier minimum:

  2. #expansions ≤ #{paths from s0 with at most ⌊C∗/ε⌋ edges} < ∞\#\text{expansions}\ \le\ \#\big\{\text{paths from }s_0\text{ with at most }\lfloor C^*/\varepsilon\rfloor\text{ edges}\big\}\ <\ \infty

    Termination. An expanded state has g≤f≤C∗g\le f\le C^*, so its current path has at most C∗/εC^*/\varepsilon edges. Each expansion of a state uses a strictly cheaper path than the last, so expansions inject into a finite set of paths:

  3. g(t)=C∗g(t)=C^*

    Optimality. The returned goal tt was popped, so g(t)=f(t)≤C∗g(t)=f(t)\le C^*, and no solution costs less than C∗C^*:

Consistency is Dijkstra on reduced costs

DerivationProof
  1. ch(u,v)≥0  ⟺  h(u)≤c(u,v)+h(v)c_h(u,v)\ge0\quad\iff\quad h(u)\le c(u,v)+h(v)

    Reduced costs are nonnegative exactly when hh is consistent:

  2. ch(P)=c(P)−h(s0)+h(s)⟹dh(s)=g∗(s)+h(s)−h(s0)c_h(P)=c(P)-h(s_0)+h(s)\qquad\Longrightarrow\qquad d_h(s)=g^*(s)+h(s)-h(s_0)

    They telescope: for any path PP from s0s_0 to ss,

  3. keyDijkstra(s)=g(s)+h(s)−h(s0)=f(s)−h(s0)\text{key}_{\text{Dijkstra}}(s)=g(s)+h(s)-h(s_0)=f(s)-h(s_0)

    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 g=g∗g=g^*, in nondecreasing ff.

  4. ∣d(L,t)−d(L,v)∣ ≤ d(v,t)\abs{d(L,t)-d(L,v)}\ \le\ d(v,t)

    On a finite graph with a binary heap this costs O((∣E∣+∣S∣)log⁡∣S∣)\order{(|E|+|S|)\log|S|} plus the evaluations of hh. The same potential trick drives Johnson's all-pairs algorithm (1977) and the ALT heuristics for undirected road graphs, h(v)=max⁡L∣d(L,t)−d(L,v)∣h(v)=\max_L\abs{d(L,t)-d(L,v)} over precomputed landmarks LL (Goldberg & Harrelson, 2005), which are consistent by the triangle inequality:

With an admissible but inconsistent hh, 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 NN states on which A* performs on the order of 2N2^N expansions, and gave a variant (algorithm B) with an O(N2)\order{N^2} 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.

Check your understanding

Pathmax sets f(n′)←max⁡(f(n), g(n′)+h(n′))f(n')\leftarrow\max\big(f(n),\,g(n')+h(n')\big) for each child n′n' of nn, so ff never decreases along a path. Run A* graph search without reopening, with pathmax, on the Hidden Layer's example: S→AS\to A and S→BS\to B cost 1, A→CA\to C costs 1, B→CB\to C costs 2, C→GC\to G costs 3; h(S)=2h(S)=2, h(A)=4h(A)=4, h(B)=1h(B)=1, h(C)=1h(C)=1, h(G)=0h(G)=0. What cost does it return?

  1. 5: pathmax repairs the inconsistency
  2. 6: CC is still closed along the costlier path first
  3. 4
  4. It fails to terminate
Show the answer

B. 6: CC is still closed along the costlier path first

The ff-values become A: 5A{:}\,5, B: 2B{:}\,2, then C: 4C{:}\,4 via BB, then G: 6G{:}\,6. When AA is finally expanded, CC is offered with g=2g=2 (pathmax f=5f=5), but CC is already closed, so the cheaper path is discarded and GG is returned at cost 6. Pathmax makes ff monotone along each path, not consistent across different paths to the same state; optimality still needs reopening.

Optimal efficiency

DerivationProof: hide a cheap goal behind a skipped state
  1. C′∗ ≤ g∗(s)+h(s)+δ < C∗C'^*\ \le\ g^*(s)+h(s)+\delta\ <\ C^*

    Suppose that on instance II, BB returns without expanding some state ss with g∗(s)+h(s)<C∗g^*(s)+h(s)<C^*. Pick δ>0\delta>0 with g∗(s)+h(s)+δ<C∗g^*(s)+h(s)+\delta<C^*, and build I′I' by adding a new goal tt, with h(t)=0h(t)=0, and one edge s→ts\to t of cost h(s)+δh(s)+\delta:

  2. run of B on I′ = run of B on I\text{run of }B\text{ on }I'\ =\ \text{run of }B\text{ on }I

    BB cannot tell II from I′I'. The only difference is an edge leaving ss, which BB never expanded, so BB makes identical observations on both and returns the same solution, of cost C∗C^*, on I′I'.

  3. h(u) ≤ min⁡{ h∗(u), k(u,s)+h(s)+δ }=h′∗(u)h(u)\ \le\ \min\big\{\,h^*(u),\ k(u,s)+h(s)+\delta\,\big\}=h'^*(u)

    hh is still admissible on I′I'; this is where consistency is used. For a state uu that reaches ss by a cheapest path of cost k(u,s)k(u,s), consistency along that path gives h(u)≤k(u,s)+h(s)h(u)\le k(u,s)+h(s), so h(u)h(u) is below the cost of the new route; for all old routes h(u)≤h∗(u)h(u)\le h^*(u) as before:

  4. cost of B’s answer on I′ = C∗ > C′∗\text{cost of }B\text{'s answer on }I'\ =\ C^*\ >\ C'^*

    So hh is admissible on I′I', yet BB returns cost C∗C^* there, which is not optimal. This contradicts (iii), so BB must expand ss.

Read the hypotheses as the theorem's limits:

  • Ties. States with g∗+h=C∗g^*+h=C^* 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 hh 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 hh. 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 f=g∗+h∗≥C∗f=g^*+h^*\ge C^* everywhere, with equality exactly on shortest paths, so the must-expand set {f<C∗}\{f<C^*\} is empty and all of A*'s work happens in the tie layer. If start and goal differ by Δr\Delta_r rows and Δc\Delta_c columns, every cell of their bounding rectangle lies on some shortest path.

Predict before you look

On an open grid, start and goal differ by 10 rows and 20 columns. With the Manhattan heuristic, how many cells have f=C∗f=C^*?

Show the answer

231

Every cell of the bounding rectangle lies on a monotone shortest path: (10+1)(20+1)=231(10+1)(20+1)=231. Breaking ties toward larger gg (smaller hh) dives along one path and expands 30 cells; first-in, first-out tie-breaking can expand nearly all 230 non-goal cells. With L=Δr+ΔcL=\Delta_r+\Delta_c, that is LL versus up to about L2/4L^2/4 expansions.

Breaking ties toward larger gg 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 ε>0\varepsilon>0.
  • A consistent heuristic makes A* Dijkstra's algorithm on the reduced costs c(u,v)−h(u)+h(v)≥0c(u,v)-h(u)+h(v)\ge0: no reopening, and O((∣E∣+∣S∣)log⁡∣S∣)\order{(|E|+|S|)\log|S|} on finite graphs. Inconsistent heuristics can force exponentially many re-expansions.
  • Optimal efficiency (Dechter & Pearl, 1985): with a consistent hh, every algorithm that must be optimal whenever hh is admissible expands all states with g∗+h<C∗g^*+h<C^*. The proof hides a cheap goal behind any skipped state.
  • The theorem is silent about the f=C∗f=C^* 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.

Question 1

Which statement is the optimal-efficiency theorem for A*?

  1. A* expands fewer nodes than any other search algorithm on every problem
  2. With any admissible heuristic, A* never expands a state twice
  3. With a consistent heuristic, every algorithm that learns the graph by expanding states and is optimal on every instance where hh is admissible must expand each state with g∗+h<C∗g^*+h<C^*
  4. 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 hh is admissible must expand each state with g∗+h<C∗g^*+h<C^*

A* expands the states with g∗+h<C∗g^*+h<C^* plus some of the f=C∗f=C^* 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.

Question 2

Why does A* with a consistent heuristic expand states in the same order as Dijkstra's algorithm on the reduced costs c(u,v)−h(u)+h(v)c(u,v)-h(u)+h(v)?

  1. Reduced costs are zero along optimal paths
  2. The reduced cost of any path from s0s_0 to ss is g+h(s)−h(s0)g+h(s)-h(s_0), so the two algorithms' keys differ by a constant
  3. Dijkstra's algorithm also uses a heuristic
  4. Both algorithms expand states in order of increasing depth
Show the answer

B. The reduced cost of any path from s0s_0 to ss is g+h(s)−h(s0)g+h(s)-h(s_0), so the two algorithms' keys differ by a constant

The hh terms telescope along a path, leaving c(P)−h(s0)+h(s)c(P)-h(s_0)+h(s). Consistency makes every reduced cost nonnegative, which is exactly what Dijkstra's correctness needs.

Question 3

The optimal-efficiency proof adds a goal tt behind a state ss that the competitor never expanded, with c(s,t)c(s,t) just above h(s)h(s). Where is consistency used?

  1. To show that the competitor cannot tell the two instances apart
  2. To show that the new path through tt is cheaper than C∗C^*
  3. To show that A* never reopens states
  4. To show that hh remains admissible on the modified instance
Show the answer

D. To show that hh remains admissible on the modified instance

States that can reach ss now have a new route to a goal, of cost k(u,s)+c(s,t)k(u,s)+c(s,t). Consistency along the path from uu to ss gives h(u)≤k(u,s)+h(s)h(u)\le k(u,s)+h(s), so hh still never overestimates, and the competitor is obliged to be optimal on the new instance. With an inconsistent hh, this step fails.

Question 4

On an open grid where Manhattan distance equals the true cost to go, which statement about A* is correct?

  1. A* must expand every cell of the start–goal bounding rectangle
  2. No cell has f<C∗f<C^*, so the effort depends entirely on how ties at f=C∗f=C^* are broken
  3. A* expands exactly the cells of one shortest path, whatever the tie-breaking
  4. A* degenerates to uniform-cost search
Show the answer

B. No cell has f<C∗f<C^*, so the effort depends entirely on how ties at f=C∗f=C^* are broken

With h=h∗h=h^*, f=g∗+h∗≥C∗f=g^*+h^*\ge C^* everywhere, with equality exactly on shortest paths, which here fill the bounding rectangle. Preferring larger gg (smaller hh) follows one path; preferring smaller gg 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.