3

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?

Adam Dingle
  • 131
  • 2

1 Answers1

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.

BlueRaja - Danny Pflughoeft
  • 171
  • 6