Best-First Search

Best-first search is a class of search algorithms that explores a graph by expanding the most promising node next, chosen according to a specified rule. Judea Pearl described it as estimating a node's promise with a heuristic evaluation function that may depend on the node itself, the goal, information gathered during the search, and any extra domain knowledge. Some authors use the term specifically for a search whose heuristic predicts how close a path is to a solution, expanding the closest-judged paths first, a narrower sense called greedy best-first search or pure heuristic search and typically implemented with a priority queue. The A* and B* algorithms are both examples of best-first search, though neither is a greedy best-first search since both also incorporate the distance already travelled from the start, and best-first algorithms are commonly used for pathfinding in combinatorial search.