Best-First Search

Best-first search is a general family of search algorithms that expand nodes based on an evaluation function that estimates the desirability of each node. Unlike uninformed search, which explores systematically, best-first search uses the evaluation function to direct attention toward the most promising regions of the search space. The family includes greedy best-first search — which uses only the heuristic estimate — and A* search — which combines the heuristic with the cost already incurred.

The evaluation function is the critical design choice. A good evaluation function compresses the search space by exploiting problem structure; a poor one may misdirect search into unproductive regions. The design of evaluation functions is as much art as science, requiring deep knowledge of the problem domain. In this respect, best-first search mirrors the problem of bounded rationality: the quality of the solution depends on the quality of the heuristic, and the heuristic depends on the match between the algorithm's assumptions and the world's structure.