What is the difference between the breadth-first search and recursive best-first search? How can I describe the key difference between them?
$\begingroup$
$\endgroup$
0
asked Nov 17, 2018 at 13:22
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
According to this article
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
According to the book Algorithms and Theory of Computation Handbook by Mikhail J. Atallah.
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 function used.
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.