Heuristics and Their Guarantees

1What a heuristic is

Uninformed search ranks frontier nodes by what a path has already cost; nothing in it looks ahead. A heuristic adds the look-ahead: h(n) is a function that returns an estimate of what remains, produced without computing any actual path to the goal. Write h^*(n) for the true cost of the cheapest path from n to the nearest goal — the quantity the heuristic stands in for and the search cannot afford to compute at every node.

A useful heuristic holds three properties in tension: it is cheap to evaluate, because it runs on every node the search generates; it is informative, sitting closer to h^* than a shrug; and it is honest in the one direction that matters, which the next two concepts make precise. The classic instance is route-finding: the straight-line distance from a city to the destination costs one square root to compute, and it can never exceed the road distance, because no road is shorter than a straight line.

The estimate is allowed to be wrong — every guarantee in this lesson and the next is a statement about the direction in which it is wrong. An estimate that only ever errs low can be trusted with optimality; one that errs high, even once, cannot.

Figure. The real route costs 4 + 3 + 4 = 11; the dashed straight line guesses 7 without computing any path. Because a straight line can never beat the road, this h never overestimates - that is admissibility, the property A*'s optimality proof leans on. Edge lengths are schematic; the numbers carry the costs.

Coding lab. Compute Manhattan distance heuristic runs in the app, with checks on your output.

2Admissibility, formalised

A heuristic is admissible when it never overestimates: h(n) \le h^*(n) at every node n. The bound is one-sided by design. Wildly low is legal; slightly high anywhere is not. Since h^* is zero at a goal, an admissible heuristic must also report zero there.

Admissibility is exactly optimism, and optimism is what a stopping rule can trust. A* will halt the moment a goal looks at least as cheap as everything still waiting, and that halt is only safe if 'looks' never flatters what actually remains — the optimality proof in the next lesson uses the inequality at precisely that step and nowhere else.

Checking admissibility in general is as hard as the search itself, because h^* is a shortest-path quantity. On a graph small enough to solve by hand, though, you can compute h^* outright and put a proposed heuristic on trial — the ledger below does exactly that for the weighted graph carried over from the cost-aware search lesson.

Figure. At every node the estimate stands beside the true remaining cost and never rises above it — h(B) touching h*(B) is legal. A single estimate poking above its neighbour anywhere on the graph would end the property.

3Consistency (monotonicity)

Consistency — also called monotonicity — is the stronger, local property: along every edge from n to a successor n' with step cost c(n, n'), the estimate may not drop by more than the step costs, h(n) \le c(n, n') + h(n'), and h is zero at the goal. Read it as a triangle inequality: estimating straight from n can never beat stepping to n' first and estimating from there.

Its consequence is the one A* graph search runs on. Along any path, g grows by exactly the edge cost while h may fall by at most that much, so the sum f never decreases. Chaining the same inequality edge by edge all the way to a goal collapses it to h(n) \le h^*(n) — consistency implies admissibility. The implication does not run back, and the next concept constructs the counterexample.

Consistency is also the checkable property. Admissibility quantifies over all remaining paths — h^* is itself a shortest-path problem — but consistency is one inequality per edge, something a unit test can sweep exhaustively. The table below is that sweep for the lesson graph.

Figure. The dashed estimate straight from n may not exceed the solid step to n′ plus the dashed estimate from there: h(n) ≤ c(n, n′) + h(n′). A heuristic obeying this on every edge of the graph cannot drop faster than costs are paid — which is what keeps f from ever falling.

4Admissible but not consistent

The two properties are not the same, and the gap between them is small enough to build by hand. Take three nodes: S→A costs 1, A→G costs 1, and a direct edge S→G costs 3. The true remaining costs are h*(S) = 2 and h*(A) = 1. Now set h(S) = 2 and h(A) = 0. Both estimates sit at or under the truth, so this heuristic is admissible.

Check the edge S→A: consistency demands h(S) \le c(S, A) + h(A) = 1 + 0 = 1, and h(S) is 2. The inequality fails — the estimate drops by 2 across an edge that costs only 1. Admissible, not consistent.

The symptom shows up in f. Walking S→A, f falls from 2 to 1: for a moment the frontier believed the start looked dearer than a node beyond it. On a tree that is a curiosity; on a graph it is exactly the disorder that lets a node be expanded before its cheapest route has been found — the reopening problem, next.

Figure. Both estimates sit at or under the truth (2 ≤ 2 at S, 0 ≤ 1 at A), yet across the cost-1 edge S→A the estimate falls from 2 to 0 — faster than the cost is paid. Admissibility checks nodes against the goal; consistency checks neighbours against each other, and it is the neighbour check that fails.

5Reopening, and why consistency removes it

Graph search remembers where it has been: an expanded node goes into the explored set and is not expanded again. Reopening is the repair that breaks that promise — pulling a node back out of the explored set because a cheaper route to it turned up after it was already expanded.

With a consistent heuristic the repair is never needed. Because f never decreases along any path, the moment a node is popped with the smallest f on the frontier, no route still waiting can reach it more cheaply — its first expansion already carries its final, cheapest g. This is the same argument that lets Dijkstra's algorithm settle every node exactly once; consistency is precisely the condition that transfers it to A*.

With a heuristic that is admissible but not consistent, the argument breaks: a node can be popped early on a flattering estimate, and its cheaper route arrives later. The implementation then chooses its poison — reopen closed nodes (correct, and in the worst case expensive, since expansions can multiply) or refuse to (fast, and the returned path may no longer be optimal). Consistent heuristics are prized in practice precisely because they dissolve this choice.

Why one expansion suffices

1. Cheapest f popsThe node leaves the frontier carrying the smallest f = g + h anywhere in the search.
2. No path undercutsConsistency keeps f non-decreasing along every extension, so every waiting route into this node finishes at an f at least as large.
3. Settled for goodIts g is final — the explored set can be trusted, exactly as in Dijkstra's algorithm.