Answers.Body: <p>The recursive best-first search (RBFS) algorithm is optimal if the heuristic is admissible because it essentially mimics the behavior of <a href="https://en.wikipedia.org/wiki/A*_search_algorithm" rel="nofollow noreferrer">A* Search</a>, which is optimal when the heuristic is admissible.</p>
  <blockquote>
  <p>If the heuristic function is admissible – meaning that it never overestimates the actual cost to get to the goal – A* is guaranteed to return a least-cost path from start to goal.</p>
  </blockquote>
  <p>The difference is that RBFS does this in a more memory-efficient way by using recursive calls <em>along with</em> pruning suboptimal paths which doesn't affect the correctness or optimality of the search. Unlike A* which keeps all explored expanded nodes in a CLOSED list and all frontier nodes in a OPEN list in memory, RBFS only keeps track of the current path it is exploring and the best f values of sibling nodes as shown as <code>best.f</code> and <code>alternative</code> in your above pseudocode. If the estimated cost of the current path exceeds <code>f_limit</code> which is only a scalar value consuming negligible memory, RBFS backtracks to the an unexplored expanded node thus discards parts of the search tree that are no longer necessary. While recursion obviously still uses the stack for each level of depth in the tree, it doesn’t require additional memory for every node in the explored state space.</p>
  <p>Finally without updating the f-value after backtracking, RBFS might revisit the same suboptimal branch multiple times especially in scenarios where the heuristic underestimates costs. The updated f-value acts as a memory of what was learned in the previous recursive call. This prevents the algorithm from repeatedly exploring the same bad path. The <code>LIST()</code> function above ensures that at each step the best successor is expanded first, then after exploring a successor and backtracking, the critical f-value update ensures that this successor node retains the global <em>monotonic</em> estimated cost learned along any path during backtracking. While A* solely relies on admissibility for optimality, RBFS requires this f-value update because it doesn’t store the entire search tree in memory as discussed above.</p>
  <p>In summary RBFS's recursive structure <em>and</em> the <code>f-limit</code> mechanism ensure that RBFS explores all viable paths in a systematic way while keeping memory usage minimal. In contrast for A*, if the search space is very large, the CLOSED list could contain a lot of nodes to simply avoid re-expansion, even though A* only cares about the optimal path.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-12-22T11:47:25.557Z
Answers.Text: In the figure above, what do you think about the line that updates f with a value from the previous search? More specifically, why do we need to update the f-value of each successor in this way, and what would happen if we did not update it?
  I think that updating ensures the f-value will monotonically increase along each path. In other words, the updated heuristic is guaranteed to be consistent, thus maintaining consistency. However, for A* search, we only need the heuristic to be admissible for optimality. If RBFS mimics the behaviour of A*, why is that updating line necessary?
Answers.UserDisplayName: Minh Hoang
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-12-22T16:50:23.957Z
Answers.Text: Recursion usually does not mean more memory-efficient. Actually, recursion can use the stack too much and lead to memory errors. So, you need to clarify how recursion makes this algorithm more memory-efficient or remove that statement.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-12-22T23:14:26.083Z
Answers.Text: @nbro I've updated my answer to address your concern.
Answers.UserDisplayName: cinch
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-12-22T23:15:04.753Z
Answers.Text: @MinhHoang I've updated my answer to address your lingering confusion. Hope it clarifies now for this specific post.
Answers.UserDisplayName: cinch
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-12-22T07:45:16.580Z
Answers.LastActivityDate: 2024-12-22T23:13:57.003Z
Answers.LastEditDate: 2024-12-22T23:13:57.003Z
Answers.UserDisplayName: cinch
Answers.Body: <p>Let me explain RBFS optimality through a story of a treasure hunter named Alex who's searching for a golden artifact in a maze of caves.</p>
  <p>Alex has a special magic map (this is our admissible heuristic h(n)) that shows the minimum possible distance to the treasure from any point. The map never lies by showing distances shorter than reality - it might sometimes show longer paths, but never shorter ones.
  Alex uses a clever strategy (this is our RBFS algorithm):</p>
  <ol>
  <li>At each cave intersection, they write down two numbers on their notebook:</li>
  </ol>
  <ul>
  <li>The actual distance they've walked so far</li>
  <li>The minimum remaining distance shown by the magic map
  Adding these gives them their 'f-value' - their best guess of total journey length.</li>
  </ul>
  <ol start="2">
  <li><p>Here's the clever part: Before going down any path, Alex leaves a note saying &quot;I think the total journey this way will be X steps&quot; (where X is their f-value). If they have to backtrack, they update this note with any new information they've learned.</p>
  </li>
  <li><p>When Alex reaches a fork in the caves, they:</p>
  </li>
  </ol>
  <ul>
  <li>Always choose the path with the most promising (lowest) total journey estimate</li>
  <li>Remember the second-best path's estimate</li>
  <li>If they find the current path is longer than expected, they go back and try the second-best path</li>
  </ul>
  <p>For example:</p>
  <ul>
  <li>Alex is at a fork. Left path estimates 100 steps, right path 120 steps</li>
  <li>They try left path first, but mark &quot;Don't go further if you find a path taking more than 120 steps&quot;</li>
  <li>If the left path starts looking longer than 120 steps, Alex returns and tries the right path</li>
  <li>This ensures they never waste time on paths that can't be optimal</li>
  </ul>
  <p>Why does this guarantee finding the shortest path?</p>
  <ul>
  <li>The magic map never underestimates (admissible heuristic)</li>
  <li>Alex always explores the most promising path first</li>
  <li>They never permanently abandon any path without proving it can't be optimal</li>
  <li>When they finally find the treasure, they can be sure it's the shortest route because:
  <ul>
  <li>They've explored all more promising paths</li>
  <li>Any unexplored paths must be longer (thanks to the magic map's honesty)</li>
  </ul>
  </li>
  </ul>
  <p>Just like Alex using their magic map and systematic exploration strategy to find the shortest path to the treasure, RBFS uses its admissible heuristic and recursive strategy to guarantee finding the optimal solution. The magic map's honesty (admissibility) combined with Alex's systematic exploration (RBFS's recursive strategy) ensures they never miss a better path.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-12-26T08:35:44.150Z
Answers.LastActivityDate: 2024-12-26T08:35:44.150Z
Answers.UserDisplayName: codex
Body: <p>The figure below shows the recursive best-first search (RBFS) algorithm from the AIMA book. Could someone explain why RBFS is optimal if the heuristic function h(n) is admissible? I understand best-first search, but I feel like this recursive version is somewhat different.</p>
  <p><a href="https://i.sstatic.net/TMU9oP3J.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/TMU9oP3J.png" alt="enter image description here" /></a></p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-12-22T16:44:04.177Z
Comments.Text: Can you explain why you "feel like this recursive version is somewhat different"? Yes, recursion makes it different. But what part of the algorithm do you think doesn't make the algorithm optimal even when using an admissible heuristic?
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-12-23T03:25:30.430Z
Comments.Text: @nbro Previously, I was quite unsure about the line in Figure 3.22 that updates f with a value from the previous search. I find that update a bit unnatural compared to the original best-first-search algorithm. I haven’t tried to identify specific parts that might make the algorithm suboptimal; rather, I just want to confirm its correctness more rigorously instead of relying solely on intuition.
Comments.UserDisplayName: Minh Hoang
Tags: <a-star><norvig-russell>
Title: Why recursive best first search is optimal if the heuristic function h(n) is admissible?
UserDisplayName: Minh Hoang
ThreadText: # Why recursive best first search is optimal if the heuristic function h(n) is admissible?
  
  (Asked by: username_0 on 2024-12-22)
  
  The figure below shows the recursive best-first search (RBFS) algorithm from the AIMA book. Could someone explain why RBFS is optimal if the heuristic function h(n) is admissible? I understand best-first search, but I feel like this recursive version is somewhat different.
  
  [![enter image description here](https://i.sstatic.net/TMU9oP3J.png)](https://i.sstatic.net/TMU9oP3J.png)
  
  **Tags:** a-star, norvig-russell
  > **Comments:**
  > **username_1**: Can you explain why you "feel like this recursive version is somewhat different"? Yes, recursion makes it different. But what part of the algorithm do you think doesn't make the algorithm optimal even when using an admissible heuristic?  
  > **username_0**: @nbro Previously, I was quite unsure about the line in Figure 3.22 that updates f with a value from the previous search. I find that update a bit unnatural compared to the original best-first-search algorithm. I haven’t tried to identify specific parts that might make the algorithm suboptimal; rather, I just want to confirm its correctness more rigorously instead of relying solely on intuition.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2024-12-22. Score: 4
  
  The recursive best-first search (RBFS) algorithm is optimal if the heuristic is admissible because it essentially mimics the behavior of [A\* Search](https://en.wikipedia.org/wiki/A*_search_algorithm), which is optimal when the heuristic is admissible.
  
  > If the heuristic function is admissible – meaning that it never overestimates the actual cost to get to the goal – A\* is guaranteed to return a least-cost path from start to goal.
  
  The difference is that RBFS does this in a more memory-efficient way by using recursive calls *along with* pruning suboptimal paths which doesn't affect the correctness or optimality of the search. Unlike A\* which keeps all explored expanded nodes in a CLOSED list and all frontier nodes in a OPEN list in memory, RBFS only keeps track of the current path it is exploring and the best f values of sibling nodes as shown as `best.f` and `alternative` in your above pseudocode. If the estimated cost of the current path exceeds `f_limit` which is only a scalar value consuming negligible memory, RBFS backtracks to the an unexplored expanded node thus discards parts of the search tree that are no longer necessary. While recursion obviously still uses the stack for each level of depth in the tree, it doesn’t require additional memory for every node in the explored state space.
  
  Finally without updating the f-value after backtracking, RBFS might revisit the same suboptimal branch multiple times especially in scenarios where the heuristic underestimates costs. The updated f-value acts as a memory of what was learned in the previous recursive call. This prevents the algorithm from repeatedly exploring the same bad path. The `LIST()` function above ensures that at each step the best successor is expanded first, then after exploring a successor and backtracking, the critical f-value update ensures that this successor node retains the global *monotonic* estimated cost learned along any path during backtracking. While A\* solely relies on admissibility for optimality, RBFS requires this f-value update because it doesn’t store the entire search tree in memory as discussed above.
  
  In summary RBFS's recursive structure *and* the `f-limit` mechanism ensure that RBFS explores all viable paths in a systematic way while keeping memory usage minimal. In contrast for A\*, if the search space is very large, the CLOSED list could contain a lot of nodes to simply avoid re-expansion, even though A\* only cares about the optimal path.
  
  > **Comments:**
  > **username_0**: In the figure above, what do you think about the line that updates f with a value from the previous search? More specifically, why do we need to update the f-value of each successor in this way, and what would happen if we did not update it? I think that updating ensures the f-value will monotonically increase along each path. In other words, the updated heuristic is guaranteed to be consistent, thus maintaining consistency. However, for A* search, we only need the heuristic to be admissible for optimality. If RBFS mimics the behaviour of A*, why is that updating line necessary?  
  > **username_1**: Recursion usually does not mean more memory-efficient. Actually, recursion can use the stack too much and lead to memory errors. So, you need to clarify how recursion makes this algorithm more memory-efficient or remove that statement.  
  > **username_2**: @nbro I've updated my answer to address your concern.  
  > **username_2**: @MinhHoang I've updated my answer to address your lingering confusion. Hope it clarifies now for this specific post.  
  
  ---
  
  ### Answer by username_3 on 2024-12-26. Score: 0
  
  Let me explain RBFS optimality through a story of a treasure hunter named Alex who's searching for a golden artifact in a maze of caves.
  
  Alex has a special magic map (this is our admissible heuristic h(n)) that shows the minimum possible distance to the treasure from any point. The map never lies by showing distances shorter than reality - it might sometimes show longer paths, but never shorter ones.
  Alex uses a clever strategy (this is our RBFS algorithm):
  
  1. At each cave intersection, they write down two numbers on their notebook:
  
  * The actual distance they've walked so far
  * The minimum remaining distance shown by the magic map
    Adding these gives them their 'f-value' - their best guess of total journey length.
  
  2. Here's the clever part: Before going down any path, Alex leaves a note saying "I think the total journey this way will be X steps" (where X is their f-value). If they have to backtrack, they update this note with any new information they've learned.
  3. When Alex reaches a fork in the caves, they:
  
  * Always choose the path with the most promising (lowest) total journey estimate
  * Remember the second-best path's estimate
  * If they find the current path is longer than expected, they go back and try the second-best path
  
  For example:
  
  * Alex is at a fork. Left path estimates 100 steps, right path 120 steps
  * They try left path first, but mark "Don't go further if you find a path taking more than 120 steps"
  * If the left path starts looking longer than 120 steps, Alex returns and tries the right path
  * This ensures they never waste time on paths that can't be optimal
  
  Why does this guarantee finding the shortest path?
  
  * The magic map never underestimates (admissible heuristic)
  * Alex always explores the most promising path first
  * They never permanently abandon any path without proving it can't be optimal
  * When they finally find the treasure, they can be sure it's the shortest route because:
    + They've explored all more promising paths
    + Any unexplored paths must be longer (thanks to the magic map's honesty)
  
  Just like Alex using their magic map and systematic exploration strategy to find the shortest path to the treasure, RBFS uses its admissible heuristic and recursive strategy to guarantee finding the optimal solution. The magic map's honesty (admissibility) combined with Alex's systematic exploration (RBFS's recursive strategy) ensures they never miss a better path.
  
  
  ---
  
  