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

  • $\begingroup$ You don't understand only the line s.f <- max(s.g + s.h, node.f) or all the algorithm? $\endgroup$ – nbro Mar 20 at 2:07
  • $\begingroup$ Only the specific line. $\endgroup$ – Clintus Mar 20 at 2:39
  • $\begingroup$ I've edited your post to make it clearer then. Make sure that's still consistent with your original intent. $\endgroup$ – nbro Mar 20 at 3:02
  • $\begingroup$ It is computing the cost for the successors, it will be max of the current incurred cost (node.f) or sum of s.g and s.h (as far as I remember, it is the edge cost+estimate cost to goal, I am not sure, the book might have used a similar notation before) $\endgroup$ – SajanGohil Mar 20 at 11:46

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.

| improve this answer | |
  • $\begingroup$ If the current paths is better than the previous one. E.g. heruistic cost is lower. Got it! Thanks. $\endgroup$ – Clintus Mar 26 at 3:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.