A heuristic is admissible if it never overestimates the true cost to reach the goal node from $n$. If a heuristic is consistent, then the heuristic value of $n$ is never greater than the cost of its successor, $n'$, plus the successor's heuristic value.

Why is A*, using tree or graph searches, optimal, if it uses an admissible heuristic?


This is well covered in the corresponding chapter of Russell & Norvig (chapter 3.5, pages 93 to 99 (Third Edition)). Check that out for more details.

First, let's review the definitions:

Your definitions of admissible and consistent are correct.

An admissible heuristic is basically just "optimistic". It never overestimates a distance.

A consistent heuristic is one where your prior beliefs about the distances between states are self-consistent. That is, you don't think that it costs 5 from B to the goal, 2 from A to B, and yet 20 from A to the goal. You are allowed to be overly optimistic though. So you could believe that it's 5 from B to the goal, 2 from A to B, and 4 from A to the goal.

A tree search is a general search strategy for searching problems that have a tree structure: that is, it's never possible to "double back" to an earlier state from a later state. This models certain types of games, for instance, like Tic-Tac-Toe. The tree search does not remember which states it has already visited, only the "fringe" of states it hasn't visited yet.

A graph search is a general search strategy for searching graph-structured problems, where it's possible to double back to an earlier state, like in chess (e.g. both players can just move their kings back and forth). To avoid these loops, the graph search also keeps track of the states that it has processed.

For more on tree vs. graph search, see the good answers on this Stack Overflow question.

Okay, now let's talk through the intuition behind the proofs.

We first want to show that

If $h(n)$ is admissible, A* using tree search is optimal.

The usual proof is by contradiction.

  1. Assume that A* with tree search and an admissible heuristic was not optimal.

  2. Being non-optimal means that the first complete path from the start to the goal discovered by A* (call this $q$) will be longer than some other path $p$, which A* explored up to some state $s$, but no further.

  3. Since the heuristic is admissible, the estimated cost of reaching the goal from $s$ must be smaller than the true cost.

  4. By 3, and the fact that we know how much it costs to reach $s$ along $p$, the estimated total cost of $p$, and thus the cost to expand $s$ must be smaller than the true cost of $p$.

  5. Since the true cost of $p$ is smaller than the cost of $q$ (by 2), the estimated cost to expand $s$ must be smaller than the true cost of $q$.

  6. A* always picks the path with the most promising total cost to expand next, and the cost of expanding the goal state is given by the total path length required to reach it.

  7. 5 and 6 form a contradiction, so our assumption in 1 must have been incorrect. Therefore A* must be optimal.

The graph search proof uses a very similar idea, but accounts for the fact that you might loop back around to earlier states.


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.