Heuristics & Admissibility

Imagine you’re driving from one city to another, and at every intersection a friendly voice whispers, “you’ve still got roughly 40 km to go.” You don’t know if it’s exact — maybe the road bends or there’s traffic — but the estimate is honest: it never tells you the rest of the trip is shorter than it really is. That honesty is the whole point of a heuristic in search.

A heuristic doesn’t have to be perfect. It just has to point you in the right direction without lying about how close the goal is. When it satisfies that one rule, the informed-search algorithm sitting on top of it (A*) is guaranteed to find the cheapest solution. This is exactly the knob engineers tune in real route planners and game AI: a sharper admissible heuristic explores far fewer states, so the same idea is what makes a maps app return a route in milliseconds instead of seconds.

The heuristic h(n)

Formally, h(n) is a function that takes a state and returns an estimate of the cost to reach the goal from there. The true cost is usually written h*(n). The relation between h and h* is what matters.

• 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.

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’s it. It’s allowed to under-estimate (even all the way down to 0 — yes, h(n) = 0 is admissible; A* then degrades to UCS). It is not allowed to overestimate, ever, at any single state.

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 has a smaller f — so the goal really is reached by the cheapest path. 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 as: my estimate from n shouldn’t be more than the cost of one step plus my estimate from where I land. (If it were, the estimate would jump up by an impossible amount.)

Consistent ⇒ admissible. Walk an entire optimal path applying the inequality step by step and the estimate 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.

When you implement A* with a consistent heuristic, f values along any path are non-decreasing, and you never need to re-open a closed node. With merely admissible, A* still finds the optimum, but the graph-search version may need to re-open nodes.

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

A neat squeeze argument. The admissibility condition is h(n) ≤ h*(n). So the largest value h can take at state n without violating admissibility is exactly h*(n). Any larger value would overestimate at that one node — making the heuristic inadmissible.

That’s also why “the true cost is itself an admissible heuristic” — it sits right on the boundary. (And it’s the perfect heuristic: A* with h = h* expands exactly the nodes on the optimal path.)

Worked example

Based on the 2024 paper, Q27. 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.

If you used h(n) = 12 inside A*, the algorithm could be tricked: a partial path with true cost-to-go of 10 would look worse than an alternative whose g + h was lower, and A* might commit to the wrong path — losing the optimality guarantee.

Based on 2024 Q46-style. A graph has h-values h(A)=4, h(B)=2, h(C)=1, h(D)=0 with D the goal. The true costs-to-goal are h*(A)=5, h*(B)=2, h*(C)=1, h*(D)=0. Is h admissible? Is it consistent?

Admissible: check h(n) ≤ h*(n) at every node — 4 ≤ 5, 2 ≤ 2, 1 ≤ 1, 0 ≤ 0. Yes, all four hold. So h is admissible. Consistency would require checking the triangle inequality on every edge; given just node-values, the per-node admissibility test is the conservative answer.

How GATE asks this

Two recurring shapes — both appeared in 2024. MSQ: a list of candidate heuristics with their values at each state, plus the true costs-to-goal; pick the ones that are admissible / consistent. MCQ or NAT: given a state with a known true cost h*(n) = k, the largest admissible value at that node is k. Both reduce to the same test: write down h(n), write down h*(n), check h(n) ≤ h*(n) at every node.

Quick check