I don't understand the proof that $A^*$ is optimal.

The proof is by contradiction:

Assume $A^*$ returns $p$ but there exists a $p'$ that is cheaper. When $p$ is chosen from the frontier, assume $p''$ (Which is part of the path $p'$) is chosen from the frontier. Since $p$ was chosen before $p''$, then we have $\text{cost}(p) + \text{heuristic}(p) \leq \text{cost}(p'') + \text{heuristic}(p'')$. $p$ ends at goal, therefore the $\text{heuristic}(p) = 0$. Therefore $\text{cost}(p) \leq \text{cost}(p'') + \text{heuristic}(p'') \leq \text{cost}(p')$ because heuristics are admissible. Therefore we have a contradiction.

I am confused: can't we also assume there's a cheaper path that's in a frontier closer to the start node than $p$? Or is part of the proof that's not possible because $A^*$ would have examined that path because it is like BFS with lowest cost search, so, if there's a cheaper path, it'll be at a further frontier?


The key phrase here is

because heuristics are admissible

In other words, the heuristics never overestimate the path length:

$$cost(n) + heuristic(n) \le cost(\text{any path going through n})$$

And since the frontier is ordered by $\textbf{cost + heuristic}$, when a completed path $p$ is dequeued from the frontier, we know that it must necessarily be $\le$ any path going through some other frontier node $q$, because

$$cost(p) = cost(p) + heuristic(p) \le cost(q) + heuristic(q) \le cost(\text{any path going through q})$$

  • 1
    $\begingroup$ However, $p'$ in the proof is not any path, it is a path assumed to be cheaper than $p$. So, how do you explain the conclusion "Therefore $\text{cost}(p) \leq \text{cost}(p'') + \text{heuristic}(p'') \leq \text{cost}(p')$"? By assumption, $\text{cost}(p') < \text{cost}(p)$. How come that you can conclude the opposite only because you say, in the proof, that you remove $p$ before $p''$ from the frontier? Even if the frontier is ordered, it does not imply that you have not removed $p'$ before $p$. I think this is what is confusing in the provided proof. $\endgroup$ – nbro Jun 27 '19 at 18:22
  • 2
    $\begingroup$ @nbro: It is a proof by contradiction. That is the contradiction. You can in fact assume that $p'$ has not been dequeued yet, because if it had, the algorithm would have terminated and returned $p'$ $\endgroup$ – BlueRaja - Danny Pflughoeft Jun 27 '19 at 18:32
  • $\begingroup$ I think that's the actual answer to the original question "can't we also assume there's a cheaper path that's in a frontier closer to the start node than $p$?". $\endgroup$ – nbro Jun 27 '19 at 18:36
  • 1
    $\begingroup$ I mean, the answer to that question is really the proof given by OP. My answer is simply an alternative proof that more directly answers his question, hopefully in a way that makes more intuitive sense. Neither of these are the same as your original question, which should technically be a separate question on this site, but is easily answered in a comment. $\endgroup$ – BlueRaja - Danny Pflughoeft Jun 27 '19 at 18:47
  • $\begingroup$ How is my question different than "can't we also assume there's a cheaper path that's in a frontier closer to the start node than 𝑝?", which, I suppose, it means "can't we also assume that $p'$ is dequeued before $p$"? The proof simply tells you, in an intricate way, that you remove $p$ before $p'$, hence $p'$ cannot be cheaper. By the way, how is yours an alternative proof? You just rephrased parts of the proof. $\endgroup$ – nbro Jun 27 '19 at 18:49

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.