Recursive Best First Search (RBFS) of A* Algorithm

Recursive Best First Search (RBFS)

It is simple recursive algorithm that resembles the operation of standard best first search but uses only linear space. It is similar to recursive DFS and differs from Recursive DFS as follows,

It keeps track of the f value of the best alternative path available from any ancestor of the current node. Instead of continuing indefinitely down the current path.

Algorithm

{

function RECURSIVE_BEST_FIRST_SEARCH (Problem)

    returns a solution, or failure

    RBFS (problem, MAKE_NODE (INITIAL_STATE problem), Ұ)

function RBFS (Problem, Node, f-limit) returns a solution or failure and a new f-cost limit

    if GOAL_TEST [Problem] [State] then return node

Successors ← EXPAND (node, problem)

    if successors is empty then return failure, ¥

for each S in successors do

    f(s) ← max (g(s) + h(s), f[node])

repeat

    best ← the lowest f value node in successors

        if [best] > f-limit then return failure, f[best]

    alternative ← the second lowest f-value among successors

    result, f[best] ← BFS (Problem, best, min (f-limit, alternative)

        if result # failure then return result

}

Advantages

• More efficient than IDA*
• It is an optimal algorithm if h(n) is admissible 
• Space complexity is O(bd). 

Disadvantages

• It suffers from excessive node regeneration.
• Its time complexity is difficult to characterize because it depends on the accuracy of h(n) and how often the best path changes as the nodes are expanded.