# Why is A* optimal if the heuristic function is admissible?

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:

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 this answer.

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.

• Free PDF of the book "Artificial Intelligence: A Modern Approach": https://www.cin.ufpe.br/~tfl2/artificial-intelligence-modern-approach.9780131038059.25368.pdf. Jan 16, 2019 at 21:40
• Your definition of tree search is not correct and the link you provide agrees. It does not depend on the problem structure. It depends on the algorithm. The only difference between a tree search and a graph search is that in graph search, we save the explored nodes so we don't visit them again while in a tree search we do not. So, in a tree search, we can visit the same node multiple times. Feb 17, 2020 at 16:42
• @MrGreen My definition does say that it is an algorithm for a certain kind of problem structure. It is true that the difference between the algorithms is whether they store visited states. The definitions I provide (which say when these algorithms should be applied, not what they are) are also correct. Feb 17, 2020 at 21:06
• @JohnDoucette You might have a graph that is too big to fit in memory. In that case, one might go with a tree search approach rather than a graph search. Feb 18, 2020 at 12:26
• I don't understand why you claim that your definition of tree search is correct (at least according to Norvig and Russell's definition). The tree search could, in principle, be applied to graphs (that are not trees), but that would cause problems. Maybe you should rephrase your answer and say that the tree search assumes that the search space is a tree? Maybe that's what you meant? In any case, I changed the link to the answer that describes the relationship between tree search and graph search. You also contributed to that answer.
– nbro
May 15, 2021 at 12:35