What is the difference between breadth first search and recursive best first search ? How can I describe the key difference between them?
Breadth First Search (BFS) searches breadth-wise in the problem space. Breadth-First search is like traversing a tree where each node is a state which may a be a potential candidate for solution. It expands nodes from the root of the tree and then generates one level of the tree at a time until a solution is found. It is very easily implemented by maintaining a queue of nodes. Initially the queue contains just the root. In each iteration, node at the head of the queue is removed and then expanded. The generated child nodes are then added to the tail of the queue
The memory limitation of the heuristic path algorithm can be overcome simply by replacing the best-first search with IDA* search using the sure weighted evaluation function, with w>=1/2.
IDA* search is no longer a best-first search since the total cost of a child can beless than that of its parent, and thus nodes are not necessarily expanded in best-first order. Recursive Best-First Search (RBFS) is an alternative algorithm. Recursive best-first search is a best-first search that runs in space that is linear with respect to the maximum search depth, regardless of the cost funtion used. Even with an admissible cost function, Recursive Best-First Search generates fewer nodes than IDA*, and is generally superior to IDA*, except for a small increase in the cost per node generation.
It works by maintaining on the recursion stack the complete path to the current node being expanded as well as all immediate siblings of nodes on that path, along with the cost of the best node in the sub-tree explored below each sibling. Whenever the cost of the current node exceeds that of some other node in the previously expanded portion of the tree, the algorithm backs up to their deepest common ancestor, and continues the search down the new path. In effect, the algorithm maintains a separate threshold for each sub-tree diverging from the current search path.