Answers.Body: <p>The key phrase here is</p>
  <blockquote>
  <p>because heuristics are admissible</p>
  </blockquote>
  <p>In other words, the heuristics never <em>overestimate</em> the path length:</p>
  <p><span class="math-container">$$cost(n) + heuristic(n) \le cost(\text{any path going through n})$$</span></p>
  <p>And since <strong>the frontier is ordered by <span class="math-container">$\textbf{cost + heuristic}$</span></strong>, when a completed path <span class="math-container">$p$</span> is dequeued from the frontier, we know that it must necessarily be <span class="math-container">$\le$</span> any path going through some other frontier node <span class="math-container">$q$</span>, because</p>
  <p><span class="math-container">$$cost(p) = cost(p) + heuristic(p)$$</span>
  <span class="math-container">$$\le cost(q) + heuristic(q)$$</span>
  <span class="math-container">$$\le cost(\text{any path going through q})$$</span></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-06-27T18:22:01.287Z
Answers.Text: 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.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-06-27T18:32:47.647Z
Answers.Text: @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'$
Answers.UserDisplayName: BlueRaja - Danny Pflughoeft
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-06-27T18:36:44.383Z
Answers.Text: 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$?_".
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-06-27T18:47:32.780Z
Answers.Text: 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.
Answers.UserDisplayName: BlueRaja - Danny Pflughoeft
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-06-27T18:49:51.960Z
Answers.Text: 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.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-06-27T17:34:01.540Z
Answers.LastActivityDate: 2022-02-18T21:44:33.193Z
Answers.LastEditDate: 2022-02-18T21:44:33.193Z
Answers.UserDisplayName: BlueRaja - Danny Pflughoeft
Body: <p>I don't understand the proof that <span class="math-container">$A^*$</span> is optimal. </p>
  
  <p>The proof is by contradiction:</p>
  
  <blockquote>
    <p>Assume <span class="math-container">$A^*$</span> returns <span class="math-container">$p$</span> but there exists a <span class="math-container">$p'$</span> that is cheaper. When <span class="math-container">$p$</span> is chosen from the frontier, assume <span class="math-container">$p''$</span> (Which is part of the path <span class="math-container">$p'$</span>) is chosen from the frontier. Since <span class="math-container">$p$</span> was chosen before <span class="math-container">$p''$</span>, then we have <span class="math-container">$\text{cost}(p) + \text{heuristic}(p) \leq \text{cost}(p'') + \text{heuristic}(p'')$</span>. <span class="math-container">$p$</span> ends at goal, therefore the <span class="math-container">$\text{heuristic}(p) = 0$</span>. Therefore <span class="math-container">$\text{cost}(p) \leq \text{cost}(p'') + \text{heuristic}(p'') \leq \text{cost}(p')$</span> because heuristics are admissible. Therefore we have a contradiction.</p>
  </blockquote>
  
  <p>I am confused: can't we also assume there's a cheaper path that's in a frontier closer to the start node than <span class="math-container">$p$</span>? Or is part of the proof that's not possible because <span class="math-container">$A^*$</span> 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?</p>
  
Tags: <search><proofs><heuristics><a-star><admissible-heuristic>
Title: Understanding the proof that A* search is optimal
UserDisplayName: Gooby
ThreadText: # Understanding the proof that A* search is optimal
  
  (Asked by: username_0 on 2019-06-27)
  
  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?
  
  **Tags:** search, proofs, heuristics, a-star, admissible-heuristic
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-06-27. Score: 2
  
  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})$$
  
  > **Comments:**
  > **username_2**: 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.  
  > **username_1**: @username_2: 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'$  
  > **username_2**: 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$?_".  
  > **username_1**: 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.  
  > **username_2**: 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.  
  
  ---
  
  