# Admissibility of heuristic in the $A^*$ algorithm

The CS188 course from Berkeley goes to great length in explaining why the optimality of $A^*$ algorithm is conditioned by the admissibility of heuristic.

Note: admissibility of heuristic means that:

$$\forall n, 0 \leq h(n) \leq h^*(n)$$

With $h^*(n)$ being the true optimal distance of $n$ to the goal.

The course's proof reasoning is sound and makes perfect sense.

However, this example uses a heuristic that is not admissible. For instance, the distance between the start state and the goal state is only $h^* = 2$ while the heuristic of the start state is $h = 17$ (see the example with the 8-puzzle, using Nilsson heuristic). Obviously, $17 \gt 2$ and therefore the heuristic is not admissible.

However, after having implemented the algorithm and tested it, it seems that it is able to find the optimal solution each time. Trying to alter the heuristic function only makes it worse than optimal.

So, if the admissibility of the heuristic a necessary condition for the guaranteed optimality of $A^*$, how comes that this example seems to refute this?

Did I miss something? Or perhaps, does the condition on the admissibility means that sometimes, the algorithm will be optimal even with an unadmissible heuristic, but only an admissible one guarantees the optimality?

I'd be curious to hear any thought about that.

• Hmm. Beware of tutorials about A* from people who think that A* with a constant-zero heuristic is just breadth-first search. It isn't: it's uniform-cost search. – David Richerby Dec 10 '16 at 8:51