# Is there an error in A* optimality proof Russel-Norvig 4th edition?

In "AI: A Modern Approach", 4th edition, by Russell and Norvig, they give a purported proof that A* is cost-optimal for any admissible heuristic. The given proof seems most certainly wrong. They want to show that all nodes on the optimal path are expanded. Towards a contradiction, they consider a node n on the optimal path that is not expanded, and say that its evaluation f(n) must be strictly greater than the optimal cost C*, for "otherwise, n would have been expanded".

In other words, they claim that a node n with f(n) less or equal than C* will be expanded. That claim is obviously not true in general? Take the heuristic that is identically zero; it is trivially admissible. Now consider a model with initial state A, which can transition to states B, C and D with costs 1, 2 and 3, respectively. Then B, C and D all transition to the goal state E, all with cost 3. The A* algorithm will simply expand B, then E. So it certainly finds an optimal path. Note that states C and D have no chance to be expanded. Nevertheless, they have evaluations 2 and 3, which are both less than 4, the optimal cost. So the claim does not hold.

I would like confirmation of my analysis - is the proof given in the book incomplete?

Just to be clear, I am not saying that A* is not always cost-optimal for any admissible heuristic, although I would love to see a reference (I've found research papers but they are about other notions of optimality, such as number of nodes expanded.) I am just saying that the proof given in the book is wrong.

• Could you be clearer about what your question is please. It appears you want a critique of whether your counter-example is valid, but you don't actually say. Feb 4, 2022 at 21:57
• Indeed I just want confirmation that the proof given in the book is incomplete. In the meantime I understood that the cost-optimality (confusingly also called admissibility) of A* under an admissible heuristic is quite easy to see, and outlined on this forum by John Doucette Feb 5, 2022 at 9:53
• I have folded that into your question. You can treat it as a suggestion of how to phrase "It (doesn't) work this way - am I right?" questions on the site. Feel free to roll back if you think it changes the question too much. I am keen though that you use question phrasing and not a general "looking for comments" ending (whcih would be more appropriate on a forum) Feb 5, 2022 at 12:32

You did not compute $$g(n)$$ correctly.

A* expands according to the evaluation function $$f(n) = g(n) + h(n)$$, where $$g(n)$$ is the cost of the path from the start node to $$n$$. Initially, you add $$A$$ to the frontier $$F = \{A \}$$. Then you pop from the frontier according to $$f(n)$$, so you pop $$A$$, and add its children to the frontier, which are $$B$$, $$C$$ and $$D$$, i.e. $$F = \{B, C, D \}$$. Now, you have

1. $$f(B) = g(B) + 0 = 1$$
2. $$f(C) = g(C) + 0 = 2$$
3. $$f(D) = g(D) + 0 = 3$$

So, you pop $$B$$ from the frontier and explore it, i.e. add $$E$$ to the frontier, so $$F = \{C, D, E \}$$. Now, you have

1. $$f(C) = g(C) + 0 = 2$$
2. $$f(D) = g(D) + 0 = 3$$
3. $$f(E) = g(E) + 0 = 1 + 3 = 4$$

So, you pop $$C$$. And so on.

(I didn't want to give more answers, but, hey, I like A*)