Best-first search is aA* 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
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 or pure heuristic 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. (Neither A* nor B* is a greedy best-first search as they incorporate the distance from start in addition to estimated distances to the goal.)
Greedy BFS
Using a greedy algorithm, expand the first successor of the parent. After a successor is generated:
- If the successor's heuristic is better than its parent, the successor is set at the front of the queue (with the parent reinserted directly behind it), and the loop restarts.
- Else, the successor is inserted into the queue (in a location determined by its heuristic value). The procedure will evaluate the remaining successors (if any) of the parent.