Scribd
Upload
153 views8 pages

12 Heuristic Search Algorithm RBFS

Recursive Best First Search (RBFS) is a heuristic search algorithm that expands nodes in best-first order using stack-based backtracking. It is memory efficient, utilizing linear space compared to other algorithms like A-star, and helps avoid loops in previously tested paths. The algorithm tracks the best alternative path and uses an evaluation limit to manage node expansion.

Uploaded by

fatimatheresa.27it
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
153 views8 pages

12 Heuristic Search Algorithm RBFS

Recursive Best First Search (RBFS) is a heuristic search algorithm that expands nodes in best-first order using stack-based backtracking. It is memory efficient, utilizing linear space compared to other algorithms like A-star, and helps avoid loops in previously tested paths. The algorithm tracks the best alternative path and uses an evaluation limit to manage node expansion.

Uploaded by

fatimatheresa.27it
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Recursive Best First

Search
How it works
▪Recursive best first search (RBFS) is an algorithm that expands nodes in best-first
order.
▪It's a heuristic search algorithm that's similar to depth-first search (DFS).
▪RBFS expands nodes in best-first order
▪It uses stack-based backtracking to determine the next node to expand
▪It keeps track of the best alternative path
▪If the current f-value exceeds the best alternative path, it backtracks to the
alternative path
▪It uses an evaluation limit to keep track of the best alternative path
Why it's useful

▪RBFS is a linear-space algorithm, which means it uses less memory


than other algorithms

▪It's similar to A-star search, but it uses linear space instead of


exponential space

▪It helps prevent the system from getting stuck in loops of previously
tested paths or nodes
Algorithm
1. s.f = max(s.g + s.h , node.f)

2. Best = best successor node

3. Best.f > f_limit return failure

4. Alt = second best succ node

5. f_limit = min(f_limit,alt.f)
The f -limit value for each recursive call is shown on top of
each current node, and every node is labeled with its f -cost
The f -limit value for each recursive call is shown on top of
each current node, and every node is labeled with its f -cost
The f -limit value for each recursive call is shown on top of
each current node, and every node is labeled with its f -cost

You might also like