Answers.Body: <blockquote>
  <p>But in Dijkstra's algorithm, the first time we reach a state (i.e. add it to the frontier [..])</p>
  </blockquote>
  <p>When they say &quot;reach the state&quot;, they mean when the node is dequeued from the frontier, not when it is added to the frontier.</p>
  <p>In Dijkstra's, when you dequeue a node, you know for certain you've reached the optimal path to that node.  The same is true of A* with a consistent heuristic.  However, it's <em>not</em> true when the heuristic is admissible-but-not-consistent.  In that case, it's possible that dequeuing the same node multiple times will be necessary.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-11-05T12:39:45.187Z
Answers.Text: Page 72 of the text says "We say that any state that has had a node generated for it has been _reached_ (whether or not that node has been expanded)".  In other words, they consider a node to be reached when it is added to the frontier, not when it is dequeued.
  
  I agree with everything you wrote in your second paragraph, but I don't think this proves their claim (1) to be true given their definition of "reached".
Answers.UserDisplayName: Adam Dingle
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-11-05T13:13:33.633Z
Answers.Text: @AdamDingle Using that definition of "reached", then yes their claim is incorrect.
Answers.UserDisplayName: BlueRaja - Danny Pflughoeft
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-11-05T12:31:14.130Z
Answers.LastActivityDate: 2024-11-05T12:31:14.130Z
Answers.UserDisplayName: BlueRaja - Danny Pflughoeft
Body: <p>In &quot;AI: A Modern Approach&quot; (Russell &amp; Norvig, 4th edition), section 3.5.2 &quot;A* search&quot; includes this sentence on page 88:</p>
  <blockquote>
  <p>In addition, with a consistent heuristic, the first time we reach a state it will be on an optimal path, so we never have to re-add a state to the frontier, and never have to change an entry in <em>reached</em>.</p>
  </blockquote>
  <p>There are three claims here:</p>
  <ol>
  <li>The first time we reach a state it will be on an optimal path.</li>
  <li>We never have to re-add a state to the frontier.</li>
  <li>We never have to change an entry in <em>reached</em>.</li>
  </ol>
  <p>I believe that claims (1) and (3) are false.  To see this easily, consider the heuristic <span class="math-container">$h(n) = 0$</span> for all <span class="math-container">$n$</span>.  Clearly it is consistent.  With this heuristic, A* is just Dijkstra's algorithm.  But in Dijkstra's algorithm, the first time we reach a state (i.e. add it to the frontier, as defined on p. 72) it certainly might not be on an optimal path, and we may have to update its entry in <em>reached</em> (i.e. the parent pointer, as seen in the pseudocode in Figure 3.7 on p. 73) as soon as we discover a shorter path to it.</p>
  <p>So is this simply an error in the book, or am I missing something here?</p>
  
Tags: <search><a-star><norvig-russell>
Title: Is there an error in Russell & Norvig (4th edition)'s claim about A* with a consistent heuristic?
UserDisplayName: Adam Dingle
ThreadText: # Is there an error in Russell & Norvig (4th edition)'s claim about A* with a consistent heuristic?
  
  (Asked by: username_0 on 2024-11-05)
  
  In "AI: A Modern Approach" (Russell & Norvig, 4th edition), section 3.5.2 "A\* search" includes this sentence on page 88:
  
  > In addition, with a consistent heuristic, the first time we reach a state it will be on an optimal path, so we never have to re-add a state to the frontier, and never have to change an entry in *reached*.
  
  There are three claims here:
  
  1. The first time we reach a state it will be on an optimal path.
  2. We never have to re-add a state to the frontier.
  3. We never have to change an entry in *reached*.
  
  I believe that claims (1) and (3) are false. To see this easily, consider the heuristic $h(n) = 0$ for all $n$. Clearly it is consistent. With this heuristic, A\* is just Dijkstra's algorithm. But in Dijkstra's algorithm, the first time we reach a state (i.e. add it to the frontier, as defined on p. 72) it certainly might not be on an optimal path, and we may have to update its entry in *reached* (i.e. the parent pointer, as seen in the pseudocode in Figure 3.7 on p. 73) as soon as we discover a shorter path to it.
  
  So is this simply an error in the book, or am I missing something here?
  
  **Tags:** search, a-star, norvig-russell
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2024-11-05. Score: 0
  
  > But in Dijkstra's algorithm, the first time we reach a state (i.e. add it to the frontier [..])
  
  When they say "reach the state", they mean when the node is dequeued from the frontier, not when it is added to the frontier.
  
  In Dijkstra's, when you dequeue a node, you know for certain you've reached the optimal path to that node. The same is true of A\* with a consistent heuristic. However, it's *not* true when the heuristic is admissible-but-not-consistent. In that case, it's possible that dequeuing the same node multiple times will be necessary.
  
  > **Comments:**
  > **username_0**: Page 72 of the text says "We say that any state that has had a node generated for it has been _reached_ (whether or not that node has been expanded)".  In other words, they consider a node to be reached when it is added to the frontier, not when it is dequeued.  I agree with everything you wrote in your second paragraph, but I don't think this proves their claim (1) to be true given their definition of "reached".  
  > **username_1**: @AdamDingle Using that definition of "reached", then yes their claim is incorrect.  
  
  ---
  
  