<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>

CC BY-SA 4.0
2024-11-05T12:39:45.187Z
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".
Adam Dingle
CC BY-SA 4.0
2024-11-05T13:13:33.633Z
@AdamDingle Using that definition of "reached", then yes their claim is incorrect.
BlueRaja - Danny Pflughoeft
CC BY-SA 4.0
2024-11-05T12:31:14.130Z
2024-11-05T12:31:14.130Z
BlueRaja - Danny Pflughoeft
<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>

<search><a-star><norvig-russell>
Is there an error in Russell & Norvig (4th edition)'s claim about A* with a consistent heuristic?
Adam Dingle
# 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.  

---

