Best-first search

Best-first search is a search algorithm which optimises breadth first search by ordering all current paths according to some heuristic. The heuristic attempts to predict how close the end of a path is to a solution. 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-star search algorithm. Best-first algorithms are often used for pathfinding in combinatorial search.

See also

• Breadth-first search
• Depth-first search
• Iterative deepening depth-first search

External links

• http://www.cee.hw.ac.uk/~alison/ai3notes/subsubsection2_6_2_3_2.html