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.
Wikipedia entry for A* search.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 18 April 2005.
HTML page formatted Tue Dec 6 16:16:32 2011.
Cite this as:
Paul E. Black, "best-first search", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 18 April 2005. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/bestfirst.html