Best-first search
From Wikipedia, the free encyclopedia
| Graph search algorithms |
|---|
| Search |
Best-first search is a search algorithm which explores a graph by expanding the most promising node chosen according to some rule.
Judea Pearl described best-first search as estimating the promise of node n by a "heuristic evaluation function f(n) 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."[1] This general sense of the term is used by many authors, including Russell & Norvig.[2]
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. This specific type of search is called greedy best-first search by Russell & Norvig.[2]
Efficient selection of the current best candidate for extension is typically implemented using a priority queue.
Examples of best-first search algorithms include the A* search algorithm, and in turn, Dijkstra's algorithm (which can be considered a specialisation of A*). Best-first algorithms are often used for pathfinding in combinatorial search.
A path-finding problem might use the algorithm in this form:
1. Start with OPEN containing just the initial state
2. Until a goal state is found or there is no node left on OPEN do:
i)Pick the best node on OPEN
ii)Generate its successors
iii)For each successor do:
a]Pick the best node on OPEN
b]Generate its successors
c]For each successor do:
i)If it has not been generated before: evaluate it, add it to OPEN and record its parent.
ii)If it has been generated before: change the parent if this new path is better than previous one.
[edit] See also
[edit] References
- ^ Pearl, J. Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley, 1984. p. 48.
- ^ a b Russell, Stuart J. & Norvig, Peter (2003), Artificial Intelligence: A Modern Approach (2nd ed.), Upper Saddle River, NJ: Prentice Hall, ISBN 0-13-790395-2, <http://aima.cs.berkeley.edu/>. pp. 94 and 95 (note 3).
