Heuristics & Admissibility

Last lesson left every search blindfolded, thrashing through regions nowhere near the goal because none could look ahead. The cure was a whisper: at every node, a rough estimate of how far the goal still is. Picture it literally — you are driving between two cities, and at each intersection a friendly voice says, “you’ve still got roughly 40 km to go.” You don’t know it is exact — the road may bend, traffic may snarl — but the estimate is honest: it never claims the rest of the trip is shorter than it truly is. That honesty is the whole point of a heuristic in search.

A heuristic need not be perfect. It only has to point you the right way without lying about how close the goal is — and when it obeys that one rule, the informed-search algorithm riding on top of it (A*) is guaranteed to find the cheapest solution, not merely a solution. This is precisely the knob engineers tune in real route planners and game AI: a sharper honest heuristic explores far fewer states, which is what lets a maps app hand back a route in milliseconds instead of seconds.

The heuristic h(n)

Formally, h(n) takes a state and returns an estimate of the cost to reach the goal from there. The true optimal cost is written h*(n), and the relationship between h and h* is what everything hinges on.

• Greedy best-first search expands by smallest h(n).
• A* expands by smallest f(n) = g(n) + h(n) — actual cost so far plus estimated cost-to-go.

A* is only as good as its heuristic, so we need a way to tell which heuristics behave well. Two properties do it.

Admissible — “never overestimates”

A heuristic is admissible if, for every state n,

  h(n) ≤ h*(n)         (h*(n) is the true optimal cost from n to a goal)

That is the entire definition. It may under-estimate freely — even all the way down to 0; yes, h(n) = 0 is admissible, and A* then degrades to UCS. What it may never do is overestimate, at any single state, ever.

Why does this matter? Because A*‘s optimality proof rests on it. If h is admissible, then any path A* commits to at the goal has f = g + h = g + 0 = g, and no other partial path on the frontier carries a smaller f — so the goal really is reached by the cheapest route. Overestimate at even one node and A* can be fooled into committing to a worse path.

Consistent — “the triangle inequality”

A heuristic is consistent (or monotone) if for every state n and every successor n' reached by an action of cost c(n, n'),

  h(n) ≤ c(n, n') + h(n')

Read it plainly: my estimate from n should not exceed the cost of one step plus my estimate from where I land. If it did, the estimate would have to jump up by an impossible amount in a single move.

Consistent ⇒ admissible. Walk an entire optimal path applying the inequality step by step, and h(n) ends up bounded by the true cost-to-goal. The converse fails: there are admissible heuristics that violate the triangle inequality at some edge. And it matters in practice — with a consistent heuristic, f is non-decreasing along any path and A* never re-opens a closed node; with merely admissible, A* still finds the optimum, but its graph-search version may have to re-open nodes.

The largest admissible heuristic IS the true cost-to-goal

A neat squeeze. Admissibility says h(n) ≤ h*(n), so the largest value h can take at state n without overestimating is exactly h*(n). Anything larger breaks admissibility at that one node. That is also why the true cost is itself an admissible heuristic — it sits right on the boundary — and it is the perfect one: A* with h = h* expands only the nodes on the optimal path.

Worked example — GATE DA 2024

A search problem has a state n whose true optimal cost to the goal is h*(n) = 10. Candidate heuristic values at n are 0, 5, 8, 10, 12. Which are admissible at n? Which is the largest admissible value?

Apply h(n) ≤ 10 to each:

  h = 0   →  0 ≤ 10 ✓ admissible (always — h = 0 makes A* into UCS)
  h = 5   →  5 ≤ 10 ✓ admissible
  h = 8   →  8 ≤ 10 ✓ admissible
  h = 10  → 10 ≤ 10 ✓ admissible — and this is the largest possible
  h = 12  → 12 ≤ 10 ✗ NOT admissible (overestimates)

So all values up to and including 10 are admissible; h = 10 is the largest. Use h(n) = 12 inside A* and the algorithm can be tricked: a partial path with a true cost-to-go of 10 looks worse than an alternative whose g + h is lower, and A* may commit to the wrong path — losing its optimality guarantee.

A companion 2024-style check: a graph has h(A)=4, h(B)=2, h(C)=1, h(D)=0 with D the goal, and true costs h*(A)=5, h*(B)=2, h*(C)=1, h*(D)=0. Is h admissible? Test h(n) ≤ h*(n) at every node — 4 ≤ 5, 2 ≤ 2, 1 ≤ 1, 0 ≤ 0 — all four hold, so yes, h is admissible.

In one breath

A heuristic h(n) estimates the cost from a node to the goal and powers informed search (greedy expands by h, A* by f = g + h); it is admissible when it never overestimates — h(n) ≤ h*(n) at every node, the exact condition A* needs to stay optimal — and consistent (monotone) when h(n) ≤ c(n,n') + h(n') for every successor, a stricter triangle inequality that implies admissibility but is not implied by it; the largest admissible value at any state is its true cost-to-goal h*(n), and h = 0 is the trivially admissible heuristic that turns A* back into UCS.

Practice

A question to carry forward

So we have the honest estimate h(n), and two ways to use it. Greedy best-first grabs whichever node looks closest to the goal — but looks can deceive, and greedy will happily charge down a short-looking corridor that dead-ends miles away, because it ignores how far it has already travelled. The fix is to weigh both: the cost already spent and the cost still estimated to go.

That balance is the famous f(n) = g(n) + h(n), and the algorithm built on it is A*. Here is the thread onward: how does A* actually expand the tree by smallest f, why does adding the known g to the estimated h rescue greedy search from its blunders, and — the crux — why does an admissible h make A* provably return the cheapest path every time? Trace it on a small graph and watch f = g + h steer it home.