A* and admissibility

◈ 3 cards

A* is best-first with f = g + h; an admissible heuristic (never overestimates) guarantees an optimal path, and BFS is A* with h = 0.

A* = best-first with f = g + h

Algorithm A is best-first search using the full evaluation function $f (n) = g (n) + h (n)$ . When the heuristic $h$ obeys one extra condition, algorithm A becomes A\, and A\ comes with a guarantee.

Admissibility

A search algorithm is admissible if it is guaranteed to find a minimal-cost path whenever a path to the goal exists. The key result:

> A\* is admissible whenever $h (n) \leq h^{*} (n)$ for every state $n$ , where $h^{*} (n)$ is the true minimal cost from $n$ to the goal.

In words: an admissible heuristic never overestimates the remaining cost. The intuition behind the proof: if $h$ ever overestimated, it could make the optimal path look more expensive than it is and the search might commit to a cheaper-looking but actually-worse path. Bounding $h$ from above by the true cost means no state on the optimal path is ever wrongly skipped.

Two consequences worth memorizing:

BFS is A\* with $h (n) = 0$ . Zero never overestimates, so it is (trivially) admissible — which is exactly why BFS already finds shortest-in-moves paths. The power of A\* is using a non-trivial admissible $h$ to prune work without losing the guarantee.
A\* with an informed $h$ expands a subset of the states BFS would expand — same optimal answer, less work.

Worked example (exam Q4: the best-first principle in A\*)

A road map S→{A,B} with S→A=2, A→G=4, S→D=1, D→E=1, E→G=8, and a straight-line-style heuristic $h (S) = 6, h (A) = 4, h (D) = 9, h (E) = 8, h (G) = 0$ . The two routes cost: S→A→G $= 2 + 4 = 6$ ; S→D→E→G $= 1 + 1 + 8 = 10$ .

A\* orders open by $f = g + h$ . From S it sees $f (A) = 2 + 4 = 6$ and $f (D) = 1 + 9 = 10$ . It expands the cheaper-looking A first, reaches G with $f = 6$ , and never expands E because $f (D) = 10$ already exceeds the solution it found. Uniform-cost search ( $h = 0$ ) has no such foresight and expands the D-branch too. Result: A\* returns the optimal path S → A → G, cost 6, expanding 3 nodes where uniform-cost expands 5. That is the best-first heuristic principle: an admissible estimate lets you reach the cheapest goal while expanding strictly fewer states.

Edge labels are real costs, node plates are f = g + h. A* pops S, sees f(A) = 6 against f(D) = 10, commits to A, and reaches G at f = 6 — three expansions. D stays on open (its f already exceeds the solution) and E is never generated at all. Uniform-cost search, which is this same picture with every h set to 0, has no reason to prefer A and expands all five.

Only the last row carries a guarantee, and it buys it with one condition: h ≤ h*. Drop h and you are in row one — still optimal, but expanding far more; drop g and you are in row two, fast and unsafe. Algorithm A becomes A* the moment its heuristic is admissible.