Best-First Search is a state space search to traverse nodes of tree-like data structures (i. e. search trees) in breadth-first manner. It is usually implemented with a priority queue instead of the FIFO of breadth-first [1] , to expand the most promising node of one level first. Best-first turns a uninformed breadth-first into an informed search. Since all nodes of one level must be saved until their child nodes at the next level have been generated, the space complexity and memory requirement is proportional to the number of nodes at the deepest level.
Following best-first algorithms were invented and implemented for computer chess programs as well for other two-player zero-sum board game players with perfect information:
Ayumu Nagai, Hiroshi Imai (1999). Proof for the Equivalence Between Some Best-First Algorithms and Depth-First Algorithms for AND/OR Trees. Proceedings of the Korea-Japan Joint Workshop on Algorithms and Computation
Best-first algorithms like A* are used for path finding in combinatorial search and puzzles. Iterative deepening is a technique to turn depth-first searches into best-first with the advantage space grows linear rather than exponential with increasing search depth, as applied for instance in IDA*.
Table of Contents
Two-Player
Following best-first algorithms were invented and implemented for computer chess programs as well for other two-player zero-sum board game players with perfect information:See also
Publications
1980 ...
1990 ...
2000 ...
2010 ...
Forum Posts
External Links
Arjen Gorter, Willem Breuker, Pierre Courbois, Gunter Hampel, Jeanne Lee
References
What links here?
Up one Level