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 ), 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