Answers.Body: <p>This is probably more easily understood as the <a href="http://www.bgu.ac.il/~felner/2015/SoCS/Collpase.pdf" rel="nofollow noreferrer">collapse/restore macro</a>. 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.</p>
  
  <p>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.)</p>
  
  <p>The linked paper gives several examples where similar ideas are used during search.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-03-26T03:06:33.140Z
Answers.Text: If the current paths is better than the previous one. E.g.  heruistic cost is lower. Got it! Thanks.
Answers.UserDisplayName: Just_Alex
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-03-22T04:29:13.597Z
Answers.LastActivityDate: 2020-03-22T04:29:13.597Z
Answers.UserDisplayName: Nathan S.
Body: <p>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.</p>
  
  <p>Here's the pseudocode.</p>
  
  <p><a href="https://i.sstatic.net/fd70Z.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/fd70Z.png" alt="enter image description here"></a></p>
  
  <p>What does the line <code>s.f &lt;- max(s.g + s.h, node.f)</code> do? </p>
  
  <p>Here's a diagram of the execution of RBFS.</p>
  
  <p><a href="https://i.sstatic.net/yYh4p.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/yYh4p.png" alt="enter image description here"></a></p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-03-20T02:07:51.013Z
Comments.Text: You don't understand only the line `s.f <- max(s.g + s.h, node.f)` or all the algorithm?
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-03-20T02:39:35.003Z
Comments.Text: Only the specific line.
Comments.UserDisplayName: Just_Alex
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-03-20T03:02:03.557Z
Comments.Text: I've edited your post to make it clearer then. Make sure that's still consistent with your original intent.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-03-20T11:46:49.140Z
Comments.Text: 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)
Comments.UserDisplayName: SajanGohil
Tags: <search><norvig-russell><best-first-search>
Title: What does the statement with the max do in the recursive best-first search algorithm?
UserDisplayName: Just_Alex
ThreadText: # What does the statement with the max do in the recursive best-first search algorithm?
  
  (Asked by: username_0 on 2020-03-20)
  
  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](https://i.sstatic.net/fd70Z.png)](https://i.sstatic.net/fd70Z.png)
  
  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](https://i.sstatic.net/yYh4p.png)](https://i.sstatic.net/yYh4p.png)
  
  **Tags:** search, norvig-russell, best-first-search
  > **Comments:**
  > **username_1**: You don't understand only the line `s.f <- max(s.g + s.h, node.f)` or all the algorithm?  
  > **username_0**: Only the specific line.  
  > **username_1**: I've edited your post to make it clearer then. Make sure that's still consistent with your original intent.  
  > **username_2**: 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)  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_3 on 2020-03-22. Score: 1
  
  This is probably more easily understood as the [collapse/restore macro](http://www.bgu.ac.il/~felner/2015/SoCS/Collpase.pdf). 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.
  
  > **Comments:**
  > **username_0**: If the current paths is better than the previous one. E.g.  heruistic cost is lower. Got it! Thanks.  
  
  ---
  
  