Heuristics, Greedy search & A*

Invent a heuristic for a problem you have never seen, hand-trace Greedy and A*, say exactly when A* is optimal and when it silently is not — and prove the blocking argument the slides leave as “TODO”.

This page assumes Chapter 1: the frontier, nodes, $g(n)$ and the explored set. UCS is complete and optimal and has exactly one flaw — it has never heard of the goal. This chapter gives search a nose.

1. What UCS is missing

The professor's framing, taken literally: Donuts ASAP! Uniform-cost search's plan for reaching a specific shop is to walk one block in every direction, then two blocks in every direction, until a ring happens to contain it. Provably correct, and wasteful in a fixable way.

Informed search is not free: you have to write the heuristic.

2. What a heuristic is

The two the course gives, both for pathing problems:

• Manhattan distance between $(x_1,y_1)$ and $(x_2,y_2)$: $|x_1-x_2| + |y_1-y_2|$. The distance if you may only move along grid lines — the right estimate for a Pacman maze, where diagonal moves do not exist.
• Euclidean distance: $\sqrt{(x_1-x_2)^2 + (y_1-y_2)^2}$. The as-the-crow-flies distance — the right estimate when you can move in any direction, or when you are on a road map and want the straight-line distance between two towns.

The slide's triangle: a state 10 across and 5 up from the goal is $10+5=15$ away in Manhattan terms and $\sqrt{100+25} \approx 11.2$ in Euclidean terms. Same quantity, different movement rules.

The running example: straight-line distance to Bucharest

The running example is the Romania road map: drive from Arad to Bucharest, states are cities, actions are roads, step costs are kilometres. The heuristic $h_{\text{SLD}}(n)$ is the straight-line distance from city $n$ to Bucharest — a ruler on the map, ignoring that roads exist. No search needed, and never an overestimate, because no road is shorter than the straight line. That last clause becomes admissible in §7.

In that figure the number on a road is its real length, the thing $g$ accumulates; the number under a city is $h_{\text{SLD}}$, the guess about everything ahead. One is measured, one is imagined — and the idea of this page is that you add them anyway.

The effect of a heuristic

In the slide's words: guide search towards the goal instead of all over the place. UCS in Arad ranks Zerind (75 km) ahead of Sibiu (140 km), and Zerind is the one unambiguously wrong direction; Sibiu's $h=253$ against Zerind's $374$ says “this way is 120 km more promising”, so the search leans east before spending a kilometre finding out.

3. Greedy best-first search

The most obvious way to use a heuristic is also the most reckless one.

Case 1 — where Greedy wins big

Arad → Bucharest. Greedy expands Arad, sees $\{$Zerind 374, Sibiu 253, Timisoara 329$\}$ and pops Sibiu; from Sibiu, $\{$Arad 366, Oradea 380, Fagaras 176, Rimnicu Vilcea 193$\}$ and pops Fagaras; from Fagaras it pops Bucharest, $h=0$. Three expansions, zero wasted nodes, for a usable 450 km route — where UCS expands Zerind, Timisoara, Sibiu, Rimnicu Vilcea, Fagaras, Pitesti, Craiova and more. When you need a route rather than the route, an excellent trade.

Case 2 — where Greedy returns a worse path

But 450 km is not optimal — 418 km exists through Rimnicu Vilcea and Pitesti, and Greedy lost it at Sibiu:

Fagaras is closer in a straight line and further by road: its only exit is a single 211 km haul. The estimate was not even bad — it ranked two options in the wrong order, which is all it takes.

Case 3 — where Greedy thrashes, or never terminates

Now put Greedy in Iasi and ask for Fagaras. Neamt is geometrically closer, so Greedy drives to Neamt — a dead end whose only road returns to Iasi. In graph search it backs out, expands Vaslui and arrives, having wasted the detour. In tree search it goes Iasi → Neamt → Iasi → Neamt → … forever. That is the technical meaning of “Greedy is not complete”.

4. A*: combining UCS and Greedy

Put the two failures side by side.

• UCS orders by backward cost $g(n)$ — the money already spent reaching $n$. A fact, blind to the future.
• Greedy orders by forward cost $h(n)$ — the money still to spend. A guess, blind to the past.

Each throws away the half of the problem the other keeps. So keep both.

The slide's worked example, in full

The “Combining UCS and Greedy” graph (originally Teg Grenager's): seven states, $S$ through $G$, with $h$ printed under each.

Expanding from $S$ without regenerating a node's own parent gives the slide's search tree:

The expansion order, pop by pop

Four expansions, and the answer is optimal. The other two on the identical graph:

The middle row is the clearest picture of greedy failure in the course. After expanding $a$, Greedy holds $b$ at $h=6$, $d$ at $h=2$ and $e$ at $h=1$, and pops $e$: to buy a one-unit improvement in the estimate it paid eight units of real cost (the $a\!-\!e$ edge) and never noticed, because 8 appears nowhere in its priority. UCS, seeing only $g$, wanders into $b$ and $c$ first — cheap, useless.

5. Watch all three run on the same maze

6. Why A* can still be wrong: a bad heuristic

A* is not magic. The slide's three-node graph:

Exactly what A* does here

1. Pop $S$, $f = 0+7 = 7$. Not a goal. Children: $A$ with $g=1$, $h=6$, $f(A) = \mathbf{7}$; $G$ by the direct road with $g=5$, $h=0$, $f(G) = \mathbf{5}$.
2. Frontier $\langle G,5\rangle, \langle A,7\rangle$: the minimum is $G$. Pop it, goal test passes, return $S\!-\!G$ at cost 5. $A$ is never expanded, so A* never discovers that going through $A$ costs 4.

$f(A) = 7$ claims “any plan through $A$ costs about 7”, and that claim is a lie — the best plan through $A$ costs 4. The lie came from $h(A) = 6$ against a true $h^*(A) = 3$. A* trusted it, concluded $A$ was a bad neighbourhood, and stopped looking.

7. Admissibility

The course's word for this is optimistic: an admissible heuristic always says “only about twenty minutes away” — sometimes right, never pessimistic. $h \equiv 0$ is the most optimistic of all, and admissible for every problem, which is why UCS is a special case of A*. A* only ever discards a plan by saying “its $f$ is too big”; if every $f$ underestimates the truth, a plan whose $f$ is too big has a truth that is bigger still, so discarding it was safe. That is the licence to trust A*'s dismissals.

Two sanity conditions fall out of the definition; check them reflexively:

• $h(\text{goal}) = 0$. At a goal, $h^*=0$, so $0 \le h \le 0$ forces $h = 0$. Every proof below uses this line.
• Admissibility is a claim about every state, not most states. One overestimating node is enough to destroy optimality, as Figure 4 shows with exactly one guilty node.

From the slides: “coming up with admissible heuristics is most of what's involved in using A* in practice.” The algorithm is twenty lines; the heuristic is where the work is (§14).

8. The optimality of A* tree search — the full blocking argument

The slides state the theorem, draw the picture, and write “TODO” where the three steps go. Here are the three steps, with every justification spelled out.

Setup, exactly as on the slide. Assume:

• $A$ is an optimal goal node — a node whose state is a goal, reached along a cheapest possible path, so $g(A) = C^*$, the optimal solution cost;
• $B$ is a suboptimal goal node — its state is a goal too, but $g(B) > C^*$;
• $h$ is admissible.

Claim: $A$ will be chosen for expansion (popped off the frontier) before $B$.

Why the claim suffices: A* returns the first goal node it pops, so if every optimal goal beats every suboptimal goal to the front of the queue, the first goal popped cannot be suboptimal.

The picture: blocking

Why there is always such an $n$

The slide compresses this into one parenthesis — “(maybe the start state; maybe $A$ itself!)” — and the whole proof rests on it. Fix an optimal path $S = n_0 \to n_1 \to \dots \to n_k = A$. I claim that at every moment before $A$ is popped, at least one $n_i$ on that path is sitting on the frontier. Induct on time:

• Initially the frontier is $\{S\} = \{n_0\}$, and $n_0$ is on the path. ✔
• Inductively, suppose some $n_i$ is on the frontier. The only way it leaves the frontier is by being popped and expanded. But expanding $n_i$ generates all its children, one of which is $n_{i+1}$ — which is therefore pushed onto the frontier at that very moment. So the property is restored immediately, with $i$ increased by 1. ✔
• The index can only climb to $k$, at which point the frontier node is $A$ — and we have stopped, because popping $A$ is the event we were waiting for. ✔

So the frontier always holds an unexpanded “front” of the optimal path: the frontier separates explored from unexplored, and you cannot get from $S$ to $A$ without crossing it.

Step 1: $f(n) \le f(A)$

Step 2: $f(A) < f(B)$

Step 3: therefore $n$ — and then $A$ — is expanded before $B$

9. A* graph search, and why admissibility is not enough

Everything above was tree search: no explored set, states re-generated freely. Real implementations use graph search — keep an explored set, never expand a state twice — or a cycle drowns you:

• A* tree search = the tree search algorithm from Chapter 1, frontier = priority queue keyed by $f(n) = g(n)+h(n)$.
• A* graph search = the UCS graph search algorithm from Chapter 1, frontier = priority queue keyed by $f(n) = g(n)+h(n)$.

One word changed, and the optimality theorem broke:

The two traces, side by side

The slide's summary of the bug, worth memorising: “$C$ (specifically $S\!-\!C$) is no longer on the frontier, so it can't be replaced with the better $S\!-\!A\!-\!C$ option.”

Why this is not the same bug as Chapter 1's

The replacement rule only works on nodes still on the frontier. Once a state is popped into the explored set, graph search treats it as settled — and for UCS that belief is true: UCS pops in increasing $g$, so a state's first pop carries its minimum possible $g$. A* pops by $f$, which mixes in a guess. Here A* popped $C$ with $g=3$ because $h(C)=1$ made that route look finished ($f=4$), while the genuinely better route to $C$ hid behind $A$, whose $h(A)=4$ made it look expensive ($f=5$). The heuristic told A* to settle $C$ too early.

beyond syllabus Two other repairs: reopening a closed state when it is rediscovered with smaller $g$, or running tree search and eating the duplicates. The course fixes the heuristic instead.

10. Consistency (the triangle inequality)

Admissibility constrains $h$ at each node relative to the goal. Consistency constrains $h$ across each edge, so that the estimate cannot drop faster than you can actually travel.

Consequence 1 — $f$ never decreases along a path

Why that matters: if $f$ never decreases along a path, the $f$ of the node A* pops never decreases over time either. A* sweeps outward in bands of increasing $f$, exactly as UCS does in bands of increasing $g$, so the first time a state is popped its $g$ is already optimal — anything arriving later arrives with an $f$ at least as large. That is the bet the explored set makes:

Consistency implies admissibility

11. The optimality summary you must memorise

Four things to carry away:

1. UCS is not a different algorithm. It is A* with the laziest heuristic; every A* theorem specialises to UCS by substituting $h = 0$, including Chapter 1's optimality proof — the blocking argument with the $h$'s crossed out.
2. The requirement gets stronger when you add the explored set. Graph search buys memory and time, and pays with a stronger obligation on $h$.
3. Consistency implies admissibility (§10), so the graph-search row implies the tree-search row: a consistent $h$ is safe everywhere, an admissible $h$ only in a tree.
4. And the slides' reassurance: “in general, most natural admissible heuristics tend to be consistent, especially if from relaxed problems.” An observation, not a theorem — and the reason nobody worries much in practice.

12. The two algorithms, written out

Both blocks from the slides. Read them together: the only textual difference is the priority-queue key.

function UNIFORM-COST-SEARCH(problem) returns a solution, or failure
   initialize the explored set to be empty
   initialize the frontier as a priority queue using g(n) as the priority
   add initial state of problem to frontier with priority g(S) = 0
   loop do
         if the frontier is empty then
              return failure
         choose a node and remove it from the frontier
         if the node contains a goal state then
              return the corresponding solution
         add the node state to the explored set
         for each resulting child from node
              if the child state is not already in the frontier or explored set then
                   add child to the frontier
              else if the child is already in the frontier with higher g(n) then
                   replace that frontier node with child

function A-STAR-SEARCH(problem) returns a solution, or failure
   initialize the explored set to be empty
   initialize the frontier as a priority queue using f(n) = g(n) + h(n) as the priority
   add initial state of problem to frontier with priority f(S) = 0 + h(S)
   loop do
         if the frontier is empty then
              return failure
         choose a node and remove it from the frontier
         if the node contains a goal state then
              return the corresponding solution
         add the node state to the explored set
         for each resulting child from node
              if the child state is not already in the frontier or explored set then
                   add child to the frontier
              else if the child is already in the frontier with higher f(n) then
                   replace that frontier node with child

Five lines worth annotating — each is an exam question waiting to happen:

• choose a node and remove it from the frontier — “choose” means the minimum-priority node. The only place the priority is consulted, which is why swapping the key is the only edit needed.
• if the node contains a goal state then return sits after the pop and before the expansion. Move it into the child loop and both algorithms lose optimality.
• add the node state to the explored set makes these graph search. Delete it and its membership check and you have tree search, which is what §8 proves about.
• if the child state is not already in the frontier or explored set — state, not node. Two nodes with the same state are what we are policing.
• else if the child is already in the frontier with higher f(n) then replace — the repair branch, and it handles only the frontier case. There is deliberately no branch for “already explored with higher $f$”, and that missing branch is the bug in Figure 6. Replacement must rewrite the parent pointer too, or the recovered path will not match the recovered cost.

13. UCS vs A* contours

The heuristic's quality is now a geometric parameter:

• $h \equiv 0$: minor axis as long as major — the ellipse is the circle, and A* is UCS.
• A weak but admissible $h$: a fat ellipse. Fewer nodes than UCS, still a lot.
• A strong admissible $h$: a thin cigar hugging the straight line between start and goal.
• $h = h^*$: the ellipse collapses onto the segment — A* expands only nodes on optimal paths. The best any heuristic can do.

The slide's word hedges matters: A* does not expand only the straight line, and must not — the sideways bulge is the set of alternatives it has to rule out before it can honestly claim optimality. Greedy skips the bulge, which is why it is faster and why it can be wrong. The bulge is the price of the proof.

14. Creating heuristics: relaxed problems

Where do you get a heuristic? The slides' recipe:

The Romania heuristic is exactly this: relax “stay on roads” to “drive straight across fields”, and the relaxed optimum is the straight-line distance — 366 km from Arad, Pythagoras instead of search. Relax just enough that the easier problem becomes trivial while still capturing something real about the difficulty.

Example: the 8-puzzle

The slide's five questions about the 8-puzzle, answered:

8-puzzle heuristic I — misplaced tiles

Why is it admissible? Each move slides exactly one tile into a new cell. So every misplaced tile requires at least one move of its own before the puzzle can be solved, and no single move can fix two tiles at once. Therefore the number of remaining moves is at least the number of misplaced tiles: $h_{\text{TILES}} \le h^*$. ✔

Which relaxation? Delete both rules about where a tile may go: a tile may be teleported to its goal square in one move. The optimal solution to that fantasy puzzle is one teleport per misplaced tile = 8, and that relaxed cost is $h_{\text{TILES}}$ — which is why admissibility never had to be argued case by case.

8-puzzle heuristic II — total Manhattan distance

Now relax only one rule — the one that says a tile may move only into the blank — and keep the rule that a tile moves one square at a time, orthogonally. The slide's phrasing: any tile could slide any direction at any time, ignoring other tiles.

Why is it admissible? A tile at Manhattan distance $d$ from its home needs at least $d$ moves of its own, because one move changes one of its coordinates by one. Summing over tiles, and using again that each move moves only one tile, gives $h_{\text{MANHATTAN}} \le h^*$. ✔ Note both facts are needed: “$\ge d$ moves per tile” and “no move helps two tiles”. Drop the second and you could double-count.

And $h_{\text{MANHATTAN}} \ge h_{\text{TILES}}$ always, because a misplaced tile contributes at least 1 to the sum and a correctly placed one contributes 0 — which is dominance, §15.

The statistics table, and what it is really saying

Statistics from Andrew Moore, as given on the slide.

Along the UCS row: $112 \to 6{,}300 \to 3{,}600{,}000$ — every 4 extra steps of depth multiplies the work by roughly 56, then 570, which is what $O(b^d)$ feels like. At depth 12, 3.6 million nodes is twenty times the entire reachable state space of 181,440, so these are tree-search counts, re-expanding states over and over. Along the A*_MANHATTAN row: $12 \to 25 \to 73$ — a factor of 49,000 less work than UCS at depth 12, purely because somebody decided which rule to delete.

Down the depth-12 column: $3.6\times10^6 \to 227 \to 73$ — the same algorithm with $h = 0$, then $h_{\text{TILES}}$, then $h_{\text{MANHATTAN}}$. The table is not a comparison of algorithms; it is a measurement of heuristic quality. A better heuristic does not trim a constant factor — it lowers the effective branching factor, which changes the exponent, which is why the gaps widen with depth.

15. Dominance, and combining heuristics

The slide's summary: roughly speaking, larger is better — as long as both are admissible. Why, precisely:

The two extremes named in the slides:

• The zero heuristic is pretty bad. A* with $h=0$ is uniform-cost search ($g + 0 = g$): complete, optimal, dominated by every other admissible heuristic, so it does the most work any admissible A* can. The floor.
• The exact heuristic is pretty good, but too expensive. $h = h^*$ dominates everything admissible and expands only nodes on optimal paths — but computing $h^*(n)$ means solving the problem from $n$. The ceiling, unreachable by construction.

Every useful heuristic lives between the two, and the trade is always the same: closer to $h^*$ prunes more nodes but costs more per node. A heuristic that halves the node count and triples the per-node cost is a loss.

When neither dominates: take the max

16. Recap

The Essentials box at the top is the recap. Take the two checks above cold — and if any line in the box is not yet obvious, that is the section to reread.

Next: Chapter 3 keeps the tree but takes away the assumption that you control every move. With an opponent picking half the branches, “cheapest path” stops meaning anything and we need minimax — and pruning returns, sharper, as $\alpha$-$\beta$.