This strategy can find solutions more efficiently than an uninformed strategy. The general approach we will consider is called best – first search.

Best – first search is an instance of the general TREE – SEARCH or GRAPH – SEARCH algorithm in which a node is selected for expansion based on an evaluation function f(n).

Traditionally, the node with the lowest evaluation is selected for expansion, because the evaluation measures the distance to the goal. BFS an be implemented within our general search framework via a priority queue, a data structure that will maintain the fringe in ascending order of f – values.

There is a whole family of BEST – FIRST – SEARCH algorithms with different evaluation functions. A key component of these algorithms is a heuristic function denoted h(n):

h(n) = estimated cost of the cheapest path from node n to a goal node.