A method of
searching a
tree that uses a
heuristic to estimate how close to the goal it is at any one moment. It is known as an
informed search, as opposed to the
uninformed searches. (
depth-first,
breadth-first and
iterative deepening searches.)
Of course, this requires that the tree is sorted into some semblence of order, otherwise best-first search will be useless. Best-first is often used in problem solving; e.g. finding the best move in a chess game, or finding the way through a maze.
In agenda-based searching, best-first search is performed by the following steps:
- Add the first (or root) node to the agenda.
- Examine the first node on the agenda to see if it is the required item.
- Otherwise, expand the node (find all its children), and add those children to the agenda.
- Sort the agenda by heuristic value so that the most promising nodes come first.
- Repeat the second to fourth steps until the goal is reached.
A best-first search often finds solutions more quickly than a breadth-first or depth-first search, since the algorithm has some idea of the direction to head in (thanks to the sorting of the agenda). However, it will not always find the shortest solution. Of course, the effectiveness of best-first search depends entirely on the suitability of its heuristic; if you have a bad heuristic, you might as well not take the time sorting the agenda.
More complex versions of the best-first search are known as Algorithm A and A*.