Answers.Body: <p><strong>TL;DR</strong>: All A* requires to find the <em>optimal path</em> is an admissible heuristic</p>
  <p>I'll read that section of the book for more clarity and extend this answer; though, I believe the way to interpret that statement is as follows:</p>
  <p>Heuristics help reduce the number of computations required to reach the goal node. An admissible heuristic guarantees that the path we find is the optimal path but we might have made a few unnecessary computations along the way. An admissible <em>and</em> consistent heuristic helps to remove these unnecessary computations while finding the optimal path.</p>
  <p>Further clarification:</p>
  <blockquote>
  <p>&quot;With an admissible heuristic, A* is cost-optimal...&quot;.</p>
  </blockquote>
  <p>Means that the <em>path</em> you find using A* with an admissible heuristic is always the the optimal path. It does not mean that you'll find that path as fast as possible.</p>
  <p>For some additional mathematical analysis on the proof of A* optimality you can read a proof I wrote <a href="https://rojasinate.com/documents/a-star-optimality.pdf" rel="nofollow noreferrer">here</a>. I developed this proof because I found the proof in AIMA to be unsatisfactory.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-02-01T05:41:01.543Z
Answers.Text: so why does the third edition say "the tree-search version of A∗ is
  optimal if h(n) is admissible, while the graph-search version is optimal if h(n) is consistent."
Answers.UserDisplayName: numq
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-02-01T16:14:10.147Z
Answers.Text: @numq I will investigate what they've written to see if there are some other mathematical points that they may not have expounded.
Answers.UserDisplayName: respectful
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-01-31T22:54:54.427Z
Answers.LastActivityDate: 2023-01-31T23:12:25.213Z
Answers.LastEditDate: 2023-01-31T23:12:25.213Z
Answers.UserDisplayName: respectful
Body: <p>The book &quot;Artificial Intelligence: A Modern Approach&quot; (4th edition, global version) says</p>
  <blockquote>
  <p>&quot;With an admissible heuristic, A* is cost-optimal...&quot;.</p>
  </blockquote>
  <p>An admissible heuristic is one that never overestimates the distance to the goal, while a consistent heuristic is one that satisfies the triangle inequality, meaning that the cost of reaching the goal through a particular path is no more than the cost of reaching the goal through any other path. A* is cost-optimal in a tree search when using an admissible heuristic function, but it needs the heuristic function to be both admissible and consistent for optimal results in graph search.</p>
  <p>I'm a bit confused by the AIMA statement. Are they saying that A* can be non-optimal if it uses an admissible but inconsistent heuristic with the graph search version?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-01-29T09:48:02.313Z
Comments.Text: Make sure my edits are _consistent_ with your actual question. Please, can you also precede the paragraph that you're quoting with `>`. In that way, we know what was copied from the book.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-01-31T11:18:02.737Z
Comments.Text: So, you didn't copy the part "An admissible heuristic is one that never overestimates the..." from the AIMA book?
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-01-31T22:33:09.627Z
Comments.Text: @nbro I. got it from my courses' slides, which are probably also based on the book.
Comments.UserDisplayName: numq
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-02-01T08:37:23.480Z
Comments.Text: Ok, so please edit your post to also precede that part with `>` because you copied then and so you should actually be quoting it and not pretend you wrote it. Thanks.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-02-01T17:14:12.770Z
Comments.Text: @nbro should I put everything in quotes apart from the last paragraph? everything I learnt is from the book (4th or 3rd) in some way or another.
Comments.UserDisplayName: numq
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-02-01T18:36:16.253Z
Comments.Text: Only if you really copied and pasted it. If you just wrote it yourself based on your knowledge, you don't have to do it
Comments.UserDisplayName: nbro
Tags: <search><norvig-russell><admissible-heuristic><optimality><consistent-heuristic>
Title: Can A* be non-optimal if it uses an admissible but inconsistent heuristic with graph search?
UserDisplayName: numq
ThreadText: # Can A* be non-optimal if it uses an admissible but inconsistent heuristic with graph search?
  
  (Asked by: username_0 on 2023-01-29)
  
  The book "Artificial Intelligence: A Modern Approach" (4th edition, global version) says
  
  > "With an admissible heuristic, A\* is cost-optimal...".
  
  An admissible heuristic is one that never overestimates the distance to the goal, while a consistent heuristic is one that satisfies the triangle inequality, meaning that the cost of reaching the goal through a particular path is no more than the cost of reaching the goal through any other path. A\* is cost-optimal in a tree search when using an admissible heuristic function, but it needs the heuristic function to be both admissible and consistent for optimal results in graph search.
  
  I'm a bit confused by the AIMA statement. Are they saying that A\* can be non-optimal if it uses an admissible but inconsistent heuristic with the graph search version?
  
  **Tags:** search, norvig-russell, admissible-heuristic, optimality, consistent-heuristic
  
  > **Comments:**
  > **username_1**: Make sure my edits are _consistent_ with your actual question. Please, can you also precede the paragraph that you're quoting with `>`. In that way, we know what was copied from the book.  
  > **username_1**: So, you didn't copy the part "An admissible heuristic is one that never overestimates the..." from the AIMA book?  
  > **username_0**: @username_1 I. got it from my courses' slides, which are probably also based on the book.  
  > **username_1**: Ok, so please edit your post to also precede that part with `>` because you copied then and so you should actually be quoting it and not pretend you wrote it. Thanks.  
  > **username_0**: @username_1 should I put everything in quotes apart from the last paragraph? everything I learnt is from the book (4th or 3rd) in some way or another.  
  > **username_1**: Only if you really copied and pasted it. If you just wrote it yourself based on your knowledge, you don't have to do it  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2023-01-31. Score: 1
  
  **TL;DR**: All A\* requires to find the *optimal path* is an admissible heuristic
  
  I'll read that section of the book for more clarity and extend this answer; though, I believe the way to interpret that statement is as follows:
  
  Heuristics help reduce the number of computations required to reach the goal node. An admissible heuristic guarantees that the path we find is the optimal path but we might have made a few unnecessary computations along the way. An admissible *and* consistent heuristic helps to remove these unnecessary computations while finding the optimal path.
  
  Further clarification:
  
  > "With an admissible heuristic, A\* is cost-optimal...".
  
  Means that the *path* you find using A\* with an admissible heuristic is always the the optimal path. It does not mean that you'll find that path as fast as possible.
  
  For some additional mathematical analysis on the proof of A\* optimality you can read a proof I wrote [here](https://rojasinate.com/documents/a-star-optimality.pdf). I developed this proof because I found the proof in AIMA to be unsatisfactory.
  
  > **Comments:**
  > **username_0**: so why does the third edition say "the tree-search version of A∗ is optimal if h(n) is admissible, while the graph-search version is optimal if h(n) is consistent."  
  > **username_2**: @username_0 I will investigate what they've written to see if there are some other mathematical points that they may not have expounded.  
  
  ---
  
  