Best-first search

From Wikipedia, the free encyclopedia

Best-first search is a search algorithm which explores a graph by expanding the most promising node chosen according to a specified 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] [2]}

Some 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.^[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 specialization of A*). Best-first algorithms are often used for path finding in combinatorial search.

[edit] Code Example ^[3]

open = initial state
while open != null
do
 1. Pick the best node on open.
 2. Create open's successors
 3. For each successor do:
       a. If it has not been generated before: evaluate it, add it to OPEN, and record its parent
       b. Otherwise: change the parent if this new path is better than previous one.
done

[edit] Greedy BFS

Using a greedy algorithm, expand the first successor that has the parent and with a better heuristic. After a successor is made and analyzed, two cases arise ^[4]:

1. If the successor's heuristic is better than its parent, the successor is set at the front of the queue, and the loop restarts.
2. Else, the successor is appended into the queue in place (determined by heuristic value). The procedure evaluates the successors of the parent.

[edit] See also

• Beam search
• A* search algorithm
• Dijkstra's algorithm

[edit] References

1. ^ Pearl, J. Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley, 1984. p. 48.
2. ^ ^{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).
3. ^ http://www.macs.hw.ac.uk/~alison/ai3notes/subsubsection2_6_2_3_2.html Best First Search
4. ^ http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume28/coles07a-html/node11.html#modifiedbestfs Greedy Best-First Search when EHC Fails, Carnegie Mellon

[edit] External links

• http://www.macs.hw.ac.uk/~alison/ai3notes/subsubsection2_6_2_3_2.html
• Wikibooks: Artificial Intelligence: Best-First Search