4

I am reading the book "Artificial Intelligence: A Modern Approach" by Stuart and Norvig. I'm having trouble understanding a step of the recursive best-first search (RBFS) algorithm.

Here's the pseudocode.

enter image description here

What does the line s.f <- max(s.g + s.h, node.f) do?

Here's a diagram of the execution of RBFS.

enter image description here

nbro
  • 42,615
  • 12
  • 119
  • 217
Just_Alex
  • 151
  • 5

2 Answers2

1

This is probably more easily understood as the collapse/restore macro. The idea is that the previously explored state was collapsed and only the minimum f-cost from the sub-tree was stored. This represents the best unexpanded state in the subtree that was collapsed.

When restoring the portion of the collapsed tree, the f-cost of the restored node could either be the original f-cost (g+h), or it could be the stored f-cost if it is larger. By taking the max, the code ensures that states that are restored maintain at least the cost of the previously best unexpanded state. (If the g+h cost is larger, then we know the state wasn't previously expanded and it wasn't previously the state on the fringe with the minimum edge cost.)

The linked paper gives several examples where similar ideas are used during search.

Nathan S.
  • 371
  • 2
  • 9
0

That's because the estimated cost(g + h) of a successor node deep down may be a lot larger than its ancestor, and the algorithm records the best cost of all child nodes on the parent's f-value recursively. When we reexpand the parent later, by setting child's f-value to be the max, we may be able to avoid reexpanding the 'seemingly cost efficient' children again, whose (g + h) < f-value of the parent.

sify
  • 101