Defines function l(x) for each node x as g(x) + h(x).
Here, g(x) is the cost of getting to node x and h(x) is an admissible heuristic estimate of getting from node x to the solution.
The open list is sorted on l(x).
The space requirement of BFS is exponential in depth!
Best-First Search: Example
Applying best-first search to the 8-puzzle: (a) initial configuration; (b) final configuration; and (c) states resulting from the first four steps of best-first search. Each state is labeled with its -value (that is, the Manhattan distance from the state to the final state).
Search Overhead Factor
The amount of work done by serial and parallel formulations of search algorithms is often different.
