A* and admissibility

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) \le 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 *over*estimated, 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.