Admissible Heuristics and Optimality of A*

In A*, nodes are popped from the open list in order of $f(n) = g(n) + h(n),$ where $g(n)$ is the cost from the start to $n$ and $h(n)$ is a heuristic estimate of the remaining cost from $n$ to the goal. Whether A* returns an optimal path depends on the quality of $h.$

Let $h^*(n)$ denote the true optimal cost from $n$ to the goal. A heuristic $h$ is admissible if, for every node $n,$

$$h(n) \leq h^*(n).$$

In words: an admissible heuristic never overestimates the remaining cost. It is always an optimistic lower bound on the true cost-to-go.

Since $h^*(\text{goal}) = 0,$ an admissible heuristic must also satisfy $h(\text{goal}) = 0.$

For example, suppose the true remaining costs from four nodes to goal $G$ are

$$h^*(A) = 12,\quad h^*(B) = 7,\quad h^*(C) = 4,\quad h^*(G) = 0.$$

The heuristic $h(A)=10,\ h(B)=7,\ h(C)=3,\ h(G)=0$ is admissible: every value satisfies $h(n) \leq h^*(n).$ The heuristic $h(A)=10,\ h(B)=9,\ h(C)=3,\ h(G)=0$ is not admissible because $h(B) = 9 > 7 = h^*(B).$