2
$\begingroup$

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?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
2
$\begingroup$

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})$$

Improve this answer
$\endgroup$
5
  • 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 at 18:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .