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 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."
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.
Efficient selection of the current best candidate for extension is typically implemented using a priority queue.
The A* search algorithm is an example of best-first search, as is B*. Best-first algorithms are often used for path finding in combinatorial search.
Read more about Best-first Search: Algorithm, Greedy BFS
Famous quotes containing the word search:
“Let the maiden, with erect soul, walk serenely on her way, accept the hint of each new experience, search in turn all the objects that solicit her eye, that she may learn the power and charm of her new-born being, which is the kindling of a new dawn in the recesses of space.”
—Ralph Waldo Emerson (18031882)