NIST

best-first search

(algorithm)

Definition: A state-space search algorithm that considers the estimated best partial solution next. This is typically implemented with a priority queue.

See also breadth-first search.

Note: This can be seen as an improved breadth-first search. Since there are different ways to compute the "estimated best", there are variants of best-first search: uniform-cost search (estimated best is the least cost so far), greedy search (least estimated cost to goal), A* (cost so far plus estimated cost to goal), and many refinements of those.

Author: PEB

More information

Wikipedia entry for A* search.


Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 18 April 2005.
HTML page formatted Fri Feb 23 10:06:07 2018.

Cite this as:
Paul E. Black, "best-first search", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 18 April 2005. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/bestfirst.html