3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – David Richerby Dec 10 '16 at 8:51
3
$\begingroup$

It's exactly as you suspected:

Sometimes, the algorithm will find an optimal solution even with an unadmissible heuristic... only an admissible heuristic guarantees the optimality of the solution returned.

If you use an unadmissible heuristic, there's no guarantee what will happen. The solution you get back might be the best one; or it might not be. And, you probably won't have any way of telling whether the solution you got back was optimal or not, so you won't even know for sure when this is a problem and when it isn't.

If you use an unadmissible heuristic, you'll often (but not always) get sub-optimal solutions.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.