3 Searching for Solutions

3.8 More Sophisticated Search

A number of refinements can be made to the preceding strategies. First, we present depth-first branch-and-bound search, which is guaranteed to find an optimal solution, and can take advantage of a heuristic function, like A* search, but with the space advantages of depth-first search. We also present problem-reduction methods to break down a search problem into a number of smaller search problems, each of which may be much easier to solve. Finally, we show how dynamic programming can be used for finding paths from anywhere to a goal and for constructing heuristic functions.