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 , 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 nondecreasing, so graph search never needs to reopen a state.
- Characterize A*'s work by the states with , 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 .
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 , and always expand a node with the smallest value. Choosing is the whole design:
- , the cost of the path found to : uniform-cost search (UCS).
- , a heuristic estimate of the cheapest cost from to a goal: greedy best-first search.
- : A* (Hart, Nilsson & Raphael, 1968).
Write for the true cost of a cheapest path from to a goal, and for the optimal solution cost. If were , then would be the cost of the best solution through . A* always expands the node whose estimated solution cost is smallest.
Think first The frontier holds three nodes: with ; with ; with . Which node does UCS expand next, which does greedy search, and which does A*?
UCS orders by and takes ; greedy orders by and takes ; A* orders by , with , and , and takes . 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.
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 failureRussell & Norvig's best-first search specialized to . With 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
An optimal-path node is always waiting. Fix an optimal solution path. Until A* returns, the shallowest unexpanded node 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, , and . Admissibility gives
No costlier goal is popped first. Suppose A* pops a goal node with . Because ,
So the frontier node has a strictly smaller than , contradicting the choice of as the minimum. The first goal popped costs exactly .
Termination. The frontier minimum never exceeds , so every expanded node has , hence and depth at most . With branching factor there are finitely many such nodes:
Think first The proof used and for the waiting node . What breaks if overestimates at a single node on the optimal path?
Then can exceed , and even exceed for a costlier goal on the frontier, so A* may pop 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 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.
Consistent implies admissible. Induct on the number of steps of a cheapest path from to a goal. With zero steps, . Otherwise let be the next node on that path:
never decreases along a path. For any successor of :
A state is first expanded along a cheapest path. Suppose A* pops a node for state with . Some node on a cheapest path to is on the frontier with , and monotonicity along the rest of that path gives
So would have been popped before , a contradiction. With a consistent heuristic, A* expands states in nondecreasing order of , each at most once and with its optimal cost, and graph search never needs to reopen anything.
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?
- 5
- 6
- 4
- It finds no path
Show the answer
B. 6
Expand : and . Pop : gets , . Pop : gets , . Pop (): it offers with , but is closed, so the cheaper path is discarded. Pop : cost 6. With reopening, returns with and A* finds the optimal cost 5.
How much does A* expand?
The proof is the monotonicity of : the goal leaves the frontier at , and every state with a smaller , together with a cheapest path to it, leaves earlier. So a heuristic saves work only by being large. If for all , then dominates , and every state that A* must expand with (where ) is also expanded with .
Among admissible heuristics, larger is better, and itself is best: with it, 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 . If A* generates nodes and finds a solution at depth , then is the branching factor that a uniform tree of depth would need in order to contain nodes:
A good heuristic keeps close to 1. Within one domain is fairly stable across nontrivial instances, so measuring it on small problems predicts the cost of large ones.
A* finds a solution at depth 5 after generating 52 nodes. What is the effective branching factor ?
Show the answer
1.92
Solve . At the right side is about , at about , so (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 rule | Exact cost of the relaxed problem | Heuristic |
|---|---|---|
| A tile moves from X to Y if X is adjacent to Y | each tile walks to its goal square independently | : Manhattan distance |
| A tile moves from X to Y if Y is blank | moves of a sort by swaps with the blank | Gaschnig's heuristic |
| A tile moves from X to Y | one move per misplaced tile | : misplaced tiles |
The differences matter. On this puzzle, A* graph search expands about 171,700 states with (nearly all 181,440 reachable states), about 31,800 with and about 1,480 with , counting with ties broken toward smaller ; other tie-breaking rules shift these numbers slightly.
You have three admissible heuristics , , , and none dominates the others. Which combination is guaranteed to be admissible and to dominate each of them?
Show the answer
B.
Each , 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 , 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,
which interpolates between A* () and greedy best-first search (). The price in solution quality is bounded:
Let be admissible, and let A* on (with reopening) pop a goal . As before, an optimal-path node with is on the frontier, and was popped first:
Use and admissibility:
So the returned cost lies within a factor of optimal, on every problem:
Key takeaways
- A* is best-first search on ; with it is uniform-cost search, and it must apply the goal test when a node is popped.
- An admissible heuristic () makes A* tree search optimal; a consistent one () makes nondecreasing, so graph search expands each state once, along a cheapest path.
- With a consistent heuristic, A* expands exactly the states with 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 .
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
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?
- An optimal solution, because admissibility is all A* needs
- A solution if one exists, but not necessarily an optimal one
- Nothing: it may loop forever
- 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 , which returns 6 instead of 5. Optimality needs consistency, or reopening.
Heuristics are both consistent. Compared with A* using , A* using ...
- returns a cheaper solution
- expands every state that A* with expands, and possibly more
- may lose optimality, because larger estimates are riskier
- never has to expand a state that A* with leaves unexpanded, apart from ties at
Show the answer
D. never has to expand a state that A* with leaves unexpanded, apart from ties at
A* must expand the states with . Since , the set for is contained in the set for . Both runs return cost ; only the work differs.
The Manhattan-distance heuristic for the 8-puzzle is the exact solution cost of which relaxed problem?
- Tiles may move to any adjacent square, even an occupied one
- Tiles may jump to any square in one move
- Tiles may move into the blank square from anywhere
- 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.
Weighted A* with and an admissible heuristic returns a path of cost 120. What can you conclude about the optimal cost ?
- Nothing: an inflated heuristic voids all guarantees
Show the answer
C.
The path found is a solution, so , and the bound gives , so .
Why must A* apply the goal test when a node is popped from the frontier rather than when it is generated?
- Generating a node costs more than popping it
- The goal test is only defined for expanded nodes
- When a goal is first generated, a cheaper route to it may still be waiting on the frontier
- 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 than other frontier nodes that lead to it more cheaply. When the goal is popped, its is the frontier minimum, and the optimality proof shows that no cheaper solution remains.
Go deeper
- Designing Heuristics · Relaxed problems, pattern databases and dominance.
- A* Optimality & Efficiency Proofs · Consistency, optimal efficiency and tie-breaking.
- Weighted, Anytime & Real-Time Search · Trading optimality for speed with guarantees.
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.