Informed Search & the A* Algorithm

A first heuristic: "most wins" in tic-tac-toe

Consider the first move in tic-tac-toe. Brute force says there are 9 opening moves, 9×8 replies, and so on — but by symmetry there are really only three distinct first moves: a corner, a side, or the center. Now apply a simple heuristic: move to the square through which the most winning lines pass.

The center sits on 4 winning lines, each corner on 3, each side square on only 2. Applied at every turn, this "most wins" heuristic collapses the symmetric 9-move opening space to 3 options, immediately picks one, and prunes so aggressively that almost no search remains. That is exactly what a good heuristic buys you: drastically less search for a small cost in evaluation.

The fatal weakness: local maxima

A local maximum is a state that looks better than all of its children — yet is not the goal. Hill climbing arrives there, sees no improving move, and simply halts. In the 8-puzzle it is common to reach a configuration where every single move temporarily worsens the heuristic (e.g. a tile must move out of its goal position to let another tile pass). To reach the goal you must go downhill first — and hill climbing, by design, refuses.

Two relatives of the same disease: on a plateau all children evaluate the same, so there is no gradient to follow; on a ridge the summit is reachable only by a sequence of individually unimpressive moves that the one-step lookahead never sees.

A full worked trace

Here is a small hypothetical state space in the style of Luger's Figure 4.4. Each state is labeled with its heuristic value h (lower = closer to the goal, so lower is better). State O is a dead end — a trap the heuristic makes look attractive.

We run best-first search from A, always expanding the state on OPEN with the lowest h, breaking ties leftmost. Watch how the algorithm chases the false lead O, hits the dead end, and calmly falls back to P:

Solution path (recovered by following parent links back from the goal): A → C → H → P → GOAL.

h₁ — number of misplaced tiles

Count the tiles not in their goal position (the blank doesn't count). Checking tile by tile: 2 is at top-left but belongs top-middle (misplaced); 8 is at top-middle but belongs middle-left (misplaced); 3 is correct; 1 is at middle-left but belongs top-left (misplaced); 6 is at the center but belongs bottom-middle (misplaced); 4, 7, 5 are all correct. Four misplaced tiles → h₁ = 4.

h₂ — sum of Manhattan (city-block) distances

For each tile, count the grid moves (horizontal + vertical) from its current square to its goal square, then sum. Misplaced tiles only: tile 2 needs 1 move, tile 8 needs 2 (one down, one left), tile 1 needs 1, tile 6 needs 1. Total → h₂ = 1 + 2 + 1 + 1 = 5.

h₃ — 2 × number of direct tile reversals

A direct reversal is a pair of adjacent tiles that must swap places (each sits in the other's goal square) — expensive to fix, so weight it by 2. In our start state no two adjacent tiles are exact swaps of each other, so h₃ = 0: the heuristic can't even tell this state from the goal!

Adding the path cost: f = g + h₁

Now fold in g(n) = depth of the state in the search. The start's three successors (slide a tile into the blank) each have g = 1:

Moving tile 6 into place drops h₁ from 4 to 3, so its f stays at 4 while the alternatives jump to 6 — the search correctly prefers real progress and correctly penalizes moves that displace already-correct tiles (7 or 5).

The greedy trace

Greedy finds Arad → Sibiu → Fagaras → Bucharest = 140 + 99 + 211 = 450 km after expanding only three nodes. Impressively fast — and wrong. The optimal route is Arad → Sibiu → Rimnicu Vilcea → Pitesti → Bucharest = 140 + 80 + 97 + 101 = 418 km. Greedy never considered Rimnicu Vilcea (h = 193) because Fagaras (h = 176) looked closer, even though the Fagaras road is much longer.

A* from Arad to Bucharest, step by step

Same map, same heuristic as before — but now every frontier entry carries f = g + h. Follow the lowest f at each step (all arithmetic shown):

Arithmetic check: g(Sibiu)=140; g(Rimnicu)=140+80=220; g(Fagaras)=140+99=239; g(Pitesti)=220+97=317; Bucharest via Fagaras g=239+211=450; Bucharest via Pitesti g=317+101=418. All f values above follow by adding h_SLD.

Admissible heuristics

Let h*(n) be the true cost of the cheapest path from n to a goal. A heuristic is admissible if for every node n:

Admissible heuristics never overestimate — they are systematically optimistic. h_SLD is admissible because no road can be shorter than the straight line. Both 8-puzzle heuristics qualify too: every misplaced tile needs at least one move (h₁), and each tile needs at least its Manhattan distance in moves since one move shifts one tile one square (h₂).

Proof sketch. Let C* be the optimal solution cost, and suppose a suboptimal goal G₂ appears on the frontier. Since G₂ is a goal, h(G₂) = 0, so f(G₂) = g(G₂) > C*. Meanwhile some node n on the optimal path is always on the frontier, and by admissibility f(n) = g(n) + h(n) ≤ C*. Therefore f(n) ≤ C* < f(G₂), so A* always expands n before G₂ — it can never select a suboptimal goal. This is exactly what happened in the Romania trace: Pitesti (f = 417 ≤ 418 = C*) was expanded before Bucharest-via-Fagaras (f = 450). ∎

Consistent (monotone) heuristics

A heuristic is consistent if for every node n and every successor n′ reached by action a:

This is a triangle inequality: the estimate from n can't exceed the cost of one step plus the estimate from where that step lands. Key facts:

• Consistency ⇒ admissibility (the converse is not true, though most natural admissible heuristics happen to be consistent).
• With a consistent h, f is non-decreasing along every path, so the first time A* expands a node it has already found the cheapest path to it — which makes graph-search A* optimal (no reopening of closed nodes needed).
• h_SLD is consistent: the straight line from n to Bucharest is never longer than the road to n′ plus the straight line from n′ (general triangle inequality of geometry).