next up previous contents index CD CD Algorithms
Next: Simulated Annealing Up: Combinatorial Search and Heuristic Previous: War Story: Covering Chessboards

Heuristic Methods

The techniques we have discussed thus far seek to find the optimal answer to a combinatorial problem as quickly as possible. Traditional algorithmic methods fail whenever the problem is provably hard (as discussed in Chapter gif), or the problem is not clean enough to lead to a nice formulation.  

Heuristic methods provide a way to approach difficult combinatorial optimization problems. Combinatorial search gives us a method to construct possible solutions and find the best one, given a function that measures how good each candidate solution is. However, there may be no algorithm to find the best solution short of searching all configurations. Heuristic methods such as simulated annealing, genetic algorithms, and neural networks provide general ways to search for good but not optimal solutions.

In this section we discuss such heuristic methods. Each of these three techniques relies on a simple model of a real-world physical process. We devote the bulk of our attention to simulated annealing, which is the easiest method to apply in practice, as well as the most reliable.

Mon Jun 2 23:33:50 EDT 1997