Search Algorithms for Discrete Optimization Problems Ananth Grama, Anshul Gupta, George Karypis, and Vipin Kumar

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.

•