Answers.Body: <p>This is well covered in the corresponding chapter of <a href="http://aima.cs.berkeley.edu/" rel="nofollow noreferrer">Russell &amp; Norvig</a> (chapter 3.5, pages 93 to 99 (Third Edition)). Check that out for more details.</p>
  <p>First, let's review the definitions:</p>
  <hr />
  <p>Your definitions of admissible and consistent are correct.</p>
  <p>An <strong>admissible heuristic</strong> is basically just &quot;optimistic&quot;. It never overestimates a distance.</p>
  <p>A <strong>consistent heuristic</strong> 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 <em>are</em> 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.</p>
  <p>A <strong>tree search</strong> is a general search strategy for searching problems that have a tree structure: that is, it's never possible to &quot;double back&quot; 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 &quot;fringe&quot; of states it hasn't visited yet.</p>
  <p>A <strong>graph search</strong> 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.</p>
  <p>For more on tree vs. graph search, see <a href="https://ai.stackexchange.com/a/9554/2444">this answer</a>.</p>
  <hr />
  <p>Okay, now let's talk through the intuition behind the proofs.</p>
  <p>We first want to show that</p>
  <blockquote>
  <p>If <span class="math-container">$h(n)$</span> is admissible, A* using tree search is optimal.</p>
  </blockquote>
  <p>The usual proof is by contradiction.</p>
  <ol>
  <li><p>Assume that A* with tree search and an admissible heuristic was not optimal.</p>
  </li>
  <li><p>Being non-optimal means that the first complete path from the start to the goal discovered by A* (call this <span class="math-container">$q$</span>) will be longer than some other path <span class="math-container">$p$</span>, which A* explored up to some state <span class="math-container">$s$</span>, but no further.</p>
  </li>
  <li><p>Since the heuristic is admissible, the estimated cost of reaching the goal from <span class="math-container">$s$</span> must be smaller than the true cost.</p>
  </li>
  <li><p>By 3, and the fact that we know how much it costs to reach <span class="math-container">$s$</span> along <span class="math-container">$p$</span>, the estimated total cost of <span class="math-container">$p$</span>, and thus the cost to expand <span class="math-container">$s$</span> must be smaller than the true cost of <span class="math-container">$p$</span>.</p>
  </li>
  <li><p>Since the true cost of <span class="math-container">$p$</span> is smaller than the cost of <span class="math-container">$q$</span> (by 2), the estimated cost to expand <span class="math-container">$s$</span> must be smaller than the true cost of <span class="math-container">$q$</span>.</p>
  </li>
  <li><p>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.</p>
  </li>
  <li><p>5 and 6 form a contradiction, so our assumption in 1 must have been incorrect. Therefore A* must be optimal.</p>
  </li>
  </ol>
  <p>The graph search proof uses a very similar idea, but accounts for the fact that you might loop back around to earlier states.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-01-16T21:40:15.890Z
Answers.Text: Free PDF of the book "Artificial Intelligence: A Modern Approach": [https://www.cin.ufpe.br/~tfl2/artificial-intelligence-modern-approach.9780131038059.25368.pdf](https://www.cin.ufpe.br/~tfl2/artificial-intelligence-modern-approach.9780131038059.25368.pdf).
Answers.UserDisplayName: DukeZhou
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-02-17T16:42:33.070Z
Answers.Text: 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.
Answers.UserDisplayName: MrGreen
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-02-17T21:06:08.230Z
Answers.Text: @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.
Answers.UserDisplayName: John Doucette
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-02-18T12:26:07.043Z
Answers.Text: @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.
Answers.UserDisplayName: MrGreen
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-02-18T22:52:41.580Z
Answers.Text: @MrGreen that's true, but I'm not sure it is relevant to this question.
Answers.UserDisplayName: John Doucette
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-05-15T12:35:13.320Z
Answers.Text: 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.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-08-08T15:04:47.190Z
Answers.LastActivityDate: 2021-05-15T12:32:28.280Z
Answers.LastEditDate: 2021-05-15T12:32:28.280Z
Answers.UserDisplayName: John Doucette
Body: <p>A heuristic is <strong>admissible</strong> if it <em>never overestimates</em> the true cost to reach the goal node from <span class="math-container">$n$</span>. If a heuristic is <strong>consistent</strong>, then the heuristic value of <span class="math-container">$n$</span> is never greater than the cost of its successor, <span class="math-container">$n'$</span>, plus the successor's heuristic value. </p>
  
  <p>Why is A*, using tree or graph searches, optimal, if it uses an admissible heuristic?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-09-15T22:50:29.503Z
Comments.Text: See also [How does an admissible heuristic ensure an optimal solution?](https://cs.stackexchange.com/q/16065/20691) at Computer Science SE.
Comments.UserDisplayName: nbro
Tags: <search><proofs><heuristics><a-star><admissible-heuristic>
Title: Why is A* optimal if the heuristic function is admissible?
UserDisplayName: Wizard
ThreadText: # Why is A* optimal if the heuristic function is admissible?
  
  (Asked by: username_0 on 2018-04-13)
  
  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?
  
  **Tags:** search, proofs, heuristics, a-star, admissible-heuristic
  > **Comments:**
  > **username_1**: See also [How does an admissible heuristic ensure an optimal solution?](https://cs.stackexchange.com/q/16065/20691) at Computer Science SE.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2018-08-08. Score: 14 | Accepted answer
  
  This is well covered in the corresponding chapter of [Russell & Norvig](http://aima.cs.berkeley.edu/) (chapter 3.5, pages 93 to 99 (Third Edition)). Check that out for more details.
  
  First, let's review the definitions:
  
  ---
  
  Your definitions of admissible and consistent are correct.
  
  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](https://ai.stackexchange.com/a/9554/2444).
  
  ---
  
  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.
  
  > **Comments:**
  > **username_3**: Free PDF of the book "Artificial Intelligence: A Modern Approach": [https://www.cin.ufpe.br/~tfl2/artificial-intelligence-modern-approach.9780131038059.25368.pdf](https://www.cin.ufpe.br/~tfl2/artificial-intelligence-modern-approach.9780131038059.25368.pdf).  
  > **username_4**: 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.  
  > **username_2**: @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.  
  > **username_4**: @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.  
  > **username_2**: @MrGreen that's true, but I'm not sure it is relevant to this question.  
  > **username_1**: 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.  
  
  ---
  
  