Simple Algorithm
Artificial Intelligence · Hidden Layer · 24 min

Heuristic Search & A*

Admissible heuristics and the optimality of A*.

Uniform-cost search finds the cheapest route by exploring every state that is cheaper to reach than the goal, in all directions at once. A* adds one number per node, an estimate of the cost still to go, and aims the exploration at the goal. If the estimate never overestimates, the guarantee survives, and on the 8-puzzle a good estimate cuts the work a hundredfold.

What you’ll learn

  • Implement A* as best-first search on f(n)=g(n)+h(n)f(n)=g(n)+h(n), with the goal test on expansion and a table of best-known path costs.
  • Prove that A* tree search is optimal with an admissible heuristic, and that a consistent heuristic makes ff nondecreasing, so graph search never needs to reopen a state.
  • Characterize A*'s work by the states with g∗+h<C∗g^*+h<C^*, and compare heuristics by dominance and the effective branching factor.
  • Derive admissible heuristics as exact costs of relaxed problems, and bound the cost returned by weighted A* by w C∗w\,C^*.

Best-first search on f = g + h

Every algorithm in this lesson is best-first search: keep the frontier in a priority queue ordered by an evaluation function ff, and always expand a node with the smallest value. Choosing ff is the whole design:

  • f(n)=g(n)f(n)=g(n), the cost of the path found to nn: uniform-cost search (UCS).
  • f(n)=h(n)f(n)=h(n), a heuristic estimate of the cheapest cost from nn to a goal: greedy best-first search.
  • f(n)=g(n)+h(n)f(n)=g(n)+h(n): A* (Hart, Nilsson & Raphael, 1968).

Write h∗(n)h^*(n) for the true cost of a cheapest path from nn to a goal, and C∗C^* for the optimal solution cost. If hh were h∗h^*, then f(n)f(n) would be the cost of the best solution through nn. A* always expands the node whose estimated solution cost is smallest.

Think first The frontier holds three nodes: XX with g=1, h=9g=1,\ h=9; YY with g=6, h=1g=6,\ h=1; ZZ with g=3, h=3g=3,\ h=3. Which node does UCS expand next, which does greedy search, and which does A*?

UCS orders by gg and takes XX; greedy orders by hh and takes YY; A* orders by g+hg+h, with f(X)=10f(X)=10, f(Y)=7f(Y)=7 and f(Z)=6f(Z)=6, and takes ZZ. YY looks closest to the goal, but reaching it already cost 6. A* picks the most promising total, which neither of the other two looks at.

text
function A-STAR(problem, h):
    node ← NODE(state = problem.INITIAL, g = 0)
    frontier ← priority queue ordered by f(n) = n.g + h(n.state), holding node
    reached ← {problem.INITIAL: node}           # best path found so far to each state
    while frontier is not empty:
        n ← POP-MIN(frontier)
        if n.g > reached[n.state].g: continue   # stale entry: a cheaper path exists
        if problem.IS-GOAL(n.state): return n   # goal test on expansion
        for each action a in problem.ACTIONS(n.state):
            s' ← problem.RESULT(n.state, a)
            g' ← n.g + problem.COST(n.state, a, s')
            if s' not in reached or g' < reached[s'].g:
                reached[s'] ← NODE(s', parent = n, g = g')
                add reached[s'] to frontier      # may reopen an expanded state
    return failure

Russell & Norvig's best-first search specialized to f=g+hf=g+h. With h=0h=0 it is uniform-cost search, Dijkstra's algorithm with an early exit. Re-adding a state that is reached more cheaply keeps it correct even for heuristics that are admissible but not consistent.

Admissibility makes A* tree search optimal

DerivationProof
  1. f(n)=g∗(n)+h(n) ≤ g∗(n)+h∗(n)=C∗f(n)=g^*(n)+h(n)\ \le\ g^*(n)+h^*(n)=C^*

    An optimal-path node is always waiting. Fix an optimal solution path. Until A* returns, the shallowest unexpanded node nn of that path is on the frontier: at first it is the start node, and when it is expanded its successor on the path is generated. Its cost so far is optimal, g(n)=g∗(n)g(n)=g^*(n), and g∗(n)+h∗(n)=C∗g^*(n)+h^*(n)=C^*. Admissibility gives

  2. f(G2)=g(G2) > C∗ ≥ f(n)f(G_2)=g(G_2)\ >\ C^*\ \ge\ f(n)

    No costlier goal is popped first. Suppose A* pops a goal node G2G_2 with g(G2)>C∗g(G_2)>C^*. Because h(G2)=0h(G_2)=0,

  3. g(first goal popped)=C∗g(\text{first goal popped})=C^*

    So the frontier node nn has a strictly smaller ff than G2G_2, contradicting the choice of G2G_2 as the minimum. The first goal popped costs exactly C∗C^*.

  4. #{ n: f(n)≤C∗ } ≤ ∑k=0⌊C∗/ε⌋bk < ∞\#\{\,n:\ f(n)\le C^*\,\}\ \le\ \sum_{k=0}^{\lfloor C^*/\varepsilon\rfloor} b^k\ <\ \infty

    Termination. The frontier minimum never exceeds f(n)≤C∗f(n)\le C^*, so every expanded node has f≤C∗f\le C^*, hence g≤C∗g\le C^* and depth at most C∗/εC^*/\varepsilon. With branching factor bb there are finitely many such nodes:

Think first The proof used h(G2)=0h(G_2)=0 and h(n)≤h∗(n)h(n)\le h^*(n) for the waiting node nn. What breaks if hh overestimates at a single node on the optimal path?

Then f(n)f(n) can exceed C∗C^*, and even exceed g(G2)g(G_2) for a costlier goal G2G_2 on the frontier, so A* may pop G2G_2 first and return it. One overestimate in the wrong place is enough. Overestimates at nodes that lie on no optimal path never break the argument, which only needs f(n)≤C∗f(n)\le C^* along one optimal path.

Consistency and graph search

Tree search pays again for every repeated state. Graph search remembers the states it has reached and expands each one once, but then the first path to reach a state is the one that gets expanded, and with a merely admissible heuristic that path need not be the cheapest. Unless the algorithm reopens states, as the pseudocode above does by re-adding a state reached more cheaply, graph search can return a suboptimal solution.

DerivationWhat consistency buys
  1. h(n) ≤ c(n,a,n′)+h(n′) ≤ c(n,a,n′)+h∗(n′)=h∗(n)h(n)\ \le\ c(n,a,n')+h(n')\ \le\ c(n,a,n')+h^*(n')=h^*(n)

    Consistent implies admissible. Induct on the number of steps of a cheapest path from nn to a goal. With zero steps, h(G)=0=h∗(G)h(G)=0=h^*(G). Otherwise let n′n' be the next node on that path:

  2. f(n′)=g(n)+c(n,a,n′)+h(n′) ≥ g(n)+h(n)=f(n)f(n')=g(n)+c(n,a,n')+h(n')\ \ge\ g(n)+h(n)=f(n)

    ff never decreases along a path. For any successor n′n' of nn:

  3. f(m) ≤ g∗(s)+h(s) < g(n)+h(s)=f(n)f(m)\ \le\ g^*(s)+h(s)\ <\ g(n)+h(s)=f(n)

    A state is first expanded along a cheapest path. Suppose A* pops a node nn for state ss with g(n)>g∗(s)g(n)>g^*(s). Some node mm on a cheapest path to ss is on the frontier with g(m)=g∗(m)g(m)=g^*(m), and monotonicity along the rest of that path gives

  4. f(1st expansion) ≤ f(2nd expansion) ≤ ⋯ ≤ C∗f(\text{1st expansion})\ \le\ f(\text{2nd expansion})\ \le\ \cdots\ \le\ C^*

    So mm would have been popped before nn, a contradiction. With a consistent heuristic, A* expands states in nondecreasing order of ff, each at most once and with its optimal cost, and graph search never needs to reopen anything.

Check your understanding

Run A* graph search without reopening on this example: once a state has been expanded, later paths to it are discarded. What cost does it return?

  1. 5
  2. 6
  3. 4
  4. It finds no path
Show the answer

B. 6

Expand SS: f(A)=1+4=5f(A)=1+4=5 and f(B)=1+1=2f(B)=1+1=2. Pop BB: CC gets g=3g=3, f=4f=4. Pop CC: GG gets g=6g=6, f=6f=6. Pop AA (f=5f=5): it offers CC with g=2g=2, but CC is closed, so the cheaper path is discarded. Pop GG: cost 6. With reopening, CC returns with f=3f=3 and A* finds the optimal cost 5.

How much does A* expand?

The proof is the monotonicity of ff: the goal leaves the frontier at f=C∗f=C^*, and every state with a smaller ff, together with a cheapest path to it, leaves earlier. So a heuristic saves work only by being large. If h2(s)≥h1(s)h_2(s)\ge h_1(s) for all ss, then h2h_2 dominates h1h_1, and every state that A* must expand with h2h_2 (where g∗+h2<C∗g^*+h_2<C^*) is also expanded with h1h_1.

Among admissible heuristics, larger is better, and h∗h^* itself is best: with it, g∗(s)+h∗(s)≥C∗g^*(s)+h^*(s)\ge C^* everywhere, with equality exactly on optimal paths, so A* expands nothing else.

To compare heuristics across problem sizes, Russell and Norvig use the effective branching factor b∗b^*. If A* generates NN nodes and finds a solution at depth dd, then b∗b^* is the branching factor that a uniform tree of depth dd would need in order to contain N+1N+1 nodes:

N+1=1+b∗+(b∗)2+⋯+(b∗)d.N+1=1+b^*+(b^*)^2+\cdots+(b^*)^d.

A good heuristic keeps b∗b^* close to 1. Within one domain b∗b^* is fairly stable across nontrivial instances, so measuring it on small problems predicts the cost of large ones.

Predict before you look

A* finds a solution at depth 5 after generating 52 nodes. What is the effective branching factor b∗b^*?

Show the answer

1.92

Solve 53=1+b+b2+b3+b4+b553=1+b+b^2+b^3+b^4+b^5. At b=1.9b=1.9 the right side is about 51.251.2, at b=1.92b=1.92 about 53.453.4, so b∗≈1.92b^*\approx1.92 (Russell & Norvig's example). The search behaved like a tree with fewer than two children per node, however many moves each state really offers.

Where heuristics come from: relaxed problems

Good heuristics are rarely guessed. They are computed as exact solution costs of a relaxed problem: the original problem with some rules removed. In the 8-puzzle, a tile can move from square X to square Y if X is adjacent to Y and Y is blank. Removing conditions gives three classic heuristics:

Relaxed ruleExact cost of the relaxed problemHeuristic
A tile moves from X to Y if X is adjacent to Yeach tile walks to its goal square independentlyh2h_2: Manhattan distance
A tile moves from X to Y if Y is blankmoves of a sort by swaps with the blankGaschnig's heuristic
A tile moves from X to Yone move per misplaced tileh1h_1: misplaced tiles
Removing more rules can only lower the cost: h2h_2 and Gaschnig's heuristic both dominate h1h_1, and all three are at most h∗h^*.
7245 6831→ 26 moves  12345678\begin{array}{|c|c|c|}\hline 7&2&4\\\hline 5&\ &6\\\hline 8&3&1\\\hline\end{array}\quad\xrightarrow{\ 26\text{ moves}\ }\quad\begin{array}{|c|c|c|}\hline \ &1&2\\\hline 3&4&5\\\hline 6&7&8\\\hline\end{array}
Russell & Norvig's example: h1=8h_1=8 (every tile is misplaced), h2=3+1+2+2+2+3+3+2=18h_2=3+1+2+2+2+3+3+2=18 (tiles 1 to 8), and the true cost is h∗=26h^*=26.

The differences matter. On this puzzle, A* graph search expands about 171,700 states with h=0h=0 (nearly all 181,440 reachable states), about 31,800 with h1h_1 and about 1,480 with h2h_2, counting with ties broken toward smaller hh; other tie-breaking rules shift these numbers slightly.

Check your understanding

You have three admissible heuristics hah_a, hbh_b, hch_c, and none dominates the others. Which combination is guaranteed to be admissible and to dominate each of them?

  1. ha+hb+hch_a+h_b+h_c
  2. max⁡(ha,hb,hc)\max(h_a,h_b,h_c)
  3. 13(ha+hb+hc)\tfrac13(h_a+h_b+h_c)
  4. min⁡(ha,hb,hc)\min(h_a,h_b,h_c)
Show the answer

B. max⁡(ha,hb,hc)\max(h_a,h_b,h_c)

Each hi(n)≤h∗(n)h_i(n)\le h^*(n), so their maximum is too, and it is pointwise at least each of them. If all three are consistent, so is the maximum. It costs three evaluations per node, a price that is usually worth paying.

The Deep Layer lesson Designing Heuristics turns relaxation into a method: abstractions, pattern databases that store exact costs of subproblems, and ways to add heuristics without losing admissibility.

Inadmissible on purpose: weighted A*

Optimality is expensive. A* must expand every state with g∗+h<C∗g^*+h<C^*, and in hard problems that set grows exponentially. Often a slightly worse solution found much sooner is the better deal. Weighted A* (Pohl, 1970) inflates the heuristic,

fw(n)=g(n)+w h(n),w≥1,f_w(n)=g(n)+w\,h(n),\qquad w\ge1,

which interpolates between A* (w=1w=1) and greedy best-first search (w→∞w\to\infty). The price in solution quality is bounded:

DerivationWeighted A* costs at most w times the optimum
  1. g(G)=fw(G) ≤ fw(n)=g∗(n)+w h(n)g(G)=f_w(G)\ \le\ f_w(n)=g^*(n)+w\,h(n)

    Let hh be admissible, and let A* on fwf_w (with reopening) pop a goal GG. As before, an optimal-path node nn with g(n)=g∗(n)g(n)=g^*(n) is on the frontier, and GG was popped first:

  2. g∗(n)+w h(n) ≤ w (g∗(n)+h∗(n))=w C∗g^*(n)+w\,h(n)\ \le\ w\,\big(g^*(n)+h^*(n)\big)=w\,C^*

    Use w≥1w\ge1 and admissibility:

  3. C∗ ≤ g(G) ≤ w C∗C^*\ \le\ g(G)\ \le\ w\,C^*

    So the returned cost lies within a factor ww of optimal, on every problem:

Key takeaways

  • A* is best-first search on f=g+hf=g+h; with h=0h=0 it is uniform-cost search, and it must apply the goal test when a node is popped.
  • An admissible heuristic (h≤h∗h\le h^*) makes A* tree search optimal; a consistent one (h(n)≤c(n,a,n′)+h(n′)h(n)\le c(n,a,n')+h(n')) makes ff nondecreasing, so graph search expands each state once, along a cheapest path.
  • With a consistent heuristic, A* expands exactly the states with g∗+h<C∗g^*+h<C^* plus some ties: larger admissible heuristics dominate smaller ones, and the effective branching factor measures the savings.
  • Exact costs of relaxed problems, such as misplaced tiles and Manhattan distance, are admissible and consistent, and the maximum of admissible heuristics is admissible.
  • Weighted A* trades optimality for speed with a guarantee: the cost it returns is at most w C∗w\,C^*.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

A* graph search that never reopens a closed state runs on a finite graph with an admissible heuristic that is not consistent. What is guaranteed?

  1. An optimal solution, because admissibility is all A* needs
  2. A solution if one exists, but not necessarily an optimal one
  3. Nothing: it may loop forever
  4. An optimal solution, found more slowly than with a consistent heuristic
Show the answer

B. A solution if one exists, but not necessarily an optimal one

On a finite graph each state is expanded at most once, so the search terminates with a solution if one exists. But the first path to reach a state may not be its cheapest, and without reopening the cheaper path is discarded, as in the example S,A,B,C,GS,A,B,C,G, which returns 6 instead of 5. Optimality needs consistency, or reopening.

Question 2

Heuristics h1≤h2h_1\le h_2 are both consistent. Compared with A* using h1h_1, A* using h2h_2...

  1. returns a cheaper solution
  2. expands every state that A* with h1h_1 expands, and possibly more
  3. may lose optimality, because larger estimates are riskier
  4. never has to expand a state that A* with h1h_1 leaves unexpanded, apart from ties at f=C∗f=C^*
Show the answer

D. never has to expand a state that A* with h1h_1 leaves unexpanded, apart from ties at f=C∗f=C^*

A* must expand the states with g∗+h<C∗g^*+h<C^*. Since h2≥h1h_2\ge h_1, the set for h2h_2 is contained in the set for h1h_1. Both runs return cost C∗C^*; only the work differs.

Question 3

The Manhattan-distance heuristic for the 8-puzzle is the exact solution cost of which relaxed problem?

  1. Tiles may move to any adjacent square, even an occupied one
  2. Tiles may jump to any square in one move
  3. Tiles may move into the blank square from anywhere
  4. Only half of the tiles need to reach their goal squares
Show the answer

A. Tiles may move to any adjacent square, even an occupied one

Dropping "the target square must be blank" lets every tile walk to its goal square independently, one step per move, so the exact cost is the sum of the tiles' grid distances.

Question 4

Weighted A* with w=1.5w=1.5 and an admissible heuristic returns a path of cost 120. What can you conclude about the optimal cost C∗C^*?

  1. C∗=120C^*=120
  2. 120≤C∗≤180120\le C^*\le180
  3. 80≤C∗≤12080\le C^*\le120
  4. Nothing: an inflated heuristic voids all guarantees
Show the answer

C. 80≤C∗≤12080\le C^*\le120

The path found is a solution, so C∗≤120C^*\le120, and the bound gives 120≤1.5 C∗120\le1.5\,C^*, so C∗≥80C^*\ge80.

Question 5

Why must A* apply the goal test when a node is popped from the frontier rather than when it is generated?

  1. Generating a node costs more than popping it
  2. The goal test is only defined for expanded nodes
  3. When a goal is first generated, a cheaper route to it may still be waiting on the frontier
  4. Popping order guarantees that the heuristic is admissible
Show the answer

C. When a goal is first generated, a cheaper route to it may still be waiting on the frontier

A goal generated through an expensive last step can have a larger ff than other frontier nodes that lead to it more cheaply. When the goal is popped, its f=gf=g is the frontier minimum, and the optimality proof shows that no cheaper solution remains.

Go deeper

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.
  • S. Russell & P. Norvig, Artificial Intelligence: A Modern Approach, 4th ed. (Pearson, 2020), chapter 3.
  • J. Pearl, Heuristics: Intelligent Search Strategies for Computer Problem Solving (Addison-Wesley, 1984).
  • I. Pohl, "Heuristic search viewed as path finding in a graph," Artificial Intelligence 1 (1970), 193–204.