Best-first search
From Free net encyclopedia
Template:Tree search algorithm Best-first search is a search algorithm which optimizes breadth-first search by expanding the most promising node chosen according to some rule.
Judea Pearl (1984) described best-first search as estimating the promise of node n by a "heuristic evaluation function <math>f(n)</math> which, in general, may depend on the description of n, the description of the goal, the information gathered by the search up to that point, and most important, on any extra knowledge about the problem domain."Template:Ref This general sense of the term is used by many authors, including Russell & Norvig.Template:Ref
Other authors have used best-first search to refer specifically to a search with a heuristic that attempts to predict how close the end of a path is to a solution, so that paths which are judged to be closer to a solution are extended first.
Efficient selection of the current best candidate for extension is typically implemented using a priority queue.
Examples of best-first search algorithms include Dijkstra's algorithm and the A* search algorithm. Best-first algorithms are often used for pathfinding in combinatorial search.
See also
References
- Template:Note Pearl, J. (1984) Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley. p. 48.
- Template:Note Russell, S.J., & Norvig, P. Artificial Intelligence: A Modern Approach (2nd ed., 2003). Pearson Education, Inc. pp. 94 and 95 (note 3).