Video summary

RBFS (Recursive Best First Search) Algorithm | Solved Example Step-by-Step | Artificial Intelligence

Main summary

Key takeaways

Educational

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

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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.

Pro

Translate summary in another language

Pro

Ask questions to this video

Chat for follow-up questions, clarifications, and source-backed answers.

Coming soon

Share this summary

Original video