Catalogue of Artificial Intelligence Techniques
Recursive Best-First Search
Keywords: best, best-first, recursive, search
Author(s): Chris Berry
Recursive Best-First Search is a search algorithm that acts in a way similar to the Standard Best-First Search, only in a linear space. It is also very similar in design to the recursive depth-first search algorithm, although there is one significant difference.
The RBFS algorithm works by keeping track of an upper bound. This upper bound allows the algorithm to ‘choose’ better paths rather than continuing indefinitely down the same one.
The upper bound is set to the f-value of the best alternative path from the ancestor of the current node. The current node is then expanded and the child nodes investigated. If all the child nodes exceed the upper bound then the current nodes f-value is set to the best child nodes f-value, and the best alternative path (i.e. the upper bound) is visited. Should one or more of the child nodes be less than the upper bound the node with the smallest f-value is visited and the upper bound is set to the lowest alternative (which could mean it does not change). The process is then repeated, please see diagram for more details.
One major flaw of this algorithm is that it can visit the same node several times. This occurs due to the algorithm changing paths only to come back to the same path again. It is understandable how this can happen as once a node is expanded there is a good chance its current f-value will become worse.
- Stuart Russel, Peter Norvig, Artificial Inteligence: A modern approach.