Video summary
RBFS (Recursive Best First Search) Algorithm | Solved Example Step-by-Step | Artificial Intelligence
Main summary
Key takeaways
Summary
The video demonstrates Recursive Best-First Search (RBFS) on a weighted graph. RBFS is an informed search method that uses heuristic estimates to guide the search toward a goal.
The example starts at A and aims to reach G, with the goal of finding a path with the lowest total cost.
RBFS procedure
- Assign the root node an initial F-limit of infinity.
-
Evaluate nodes using:
- (g(n)): the path cost from the start node to node (n).
- (h(n)): the heuristic estimate from (n) to the goal.
- (f(n) = g(n) + h(n)). The video uses the parent’s F-value as a lower bound: (f(\text{child}) = \max(\text{parent F},\ g(\text{child}) + h(\text{child}))).
-
Among the current node’s successors, choose the one with the lowest F-value as the best node.
- Keep track of the second-lowest successor as the alternative.
- Pass a recursive limit based on the smaller of the current F-limit and the alternative’s F-value.
- If the best successor’s F-value exceeds the limit, backtrack and update the parent’s F-value with the value returned from that branch. Then consider another branch.
- Stop when the goal node is reached.
Walkthrough
-
Start at A
- A has F = 12.
- Its successors have F-values B = 17, C = 14, and D = 12.
- D is selected first, with C as the alternative, so D’s limit is 14.
-
Explore D
- D’s successors are A and F, with F-values A = 22 and F = 15.
- F is the best successor, but 15 exceeds D’s limit of 14.
- The search backtracks and updates D’s F-value to 15.
-
Return to A and explore C
- A’s successor values are now B = 17, C = 14, and D = 15.
- C is selected, with D as the alternative, so C’s limit becomes 15.
- C’s successors have F-values 20, 15, and 17. E, with F = 15, is the best choice.
-
Explore E
- E’s successors include G, whose F-value is 17.
- Since 17 exceeds E’s limit of 15, RBFS backtracks and updates E’s F-value to 17.
- C’s best available value is then 17, which also exceeds C’s limit of 15. The search backs up again and updates C to 17.
-
Return to A and revisit D
- A’s values are now B = 17, C = 17, and D = 15.
- D is again the best choice. Its limit is 17, based on the next-best alternative.
-
Explore D → F
- At D, F has a value of 15, which is within the limit of 17, so the search continues.
- F’s successors have values C = 26, D = 20, and G = 15.
- G is the best successor and the target, so the search stops.
Result
The path found is A → D → F → G, with a total cost of 5 + 4 + 6 = 15.
Speakers and sources
- Speaker: One narrator or instructor explains the algorithm and worked example.
- Other speakers or cited sources: None identified.
Rate this summary
Your feedback will help improve summaries.
Improve this summary
Reprocess with a stronger model when the summary feels incomplete or inaccurate.
Translate summary in another language
Ask questions to this video
Chat for follow-up questions, clarifications, and source-backed answers.