Next: Backtracking Up: Techniques Previous: Implementation Challenges

# Combinatorial Search and Heuristic Methods

We have seen how clever algorithms can reduce the complexity of sorting from to , which is good. However, the algorithmic stakes can be even higher for combinatorially explosive problems, whose time grows exponentially in the size of the problem. Looking back at Figure will make clear the limitations of exponential-time algorithms on even modest-sized problems.

By using exhaustive search techniques, we can solve small problems to optimality, although the time complexity may be enormous. For certain applications, it may well pay to spend extra time to be certain of the optimal solution. A good example occurs in testing a circuit or a program on all possible inputs. You can prove the correctness of the device by trying all possible inputs and verifying that they give the correct answer. Proving such correctness is a property to be proud of. However, claiming that it works correctly on all the inputs you tried is worth much, much less.

In this section, we present backtracking as a technique for listing all configurations representing possible solutions for a combinatorial algorithm problem. We then discuss techniques for pruning search that significantly improve efficiency by eliminating irrelevant configurations from consideration. We illustrate the power of clever pruning techniques to speed up real search applications. For problems that are too large to contemplate using brute-force combinatorial search, we introduce heuristic methods such as simulated annealing. Such heuristic methods are an important weapon in the practical algorist's arsenal.

The take-home lessons from this chapter are:

• Combinatorial search, augmented with tree pruning techniques, can be used to find the optimal solution of small optimization problems. How small depends upon the specific problem, but the size limit is likely to be somewhere between items.
• Clever pruning techniques can speed up combinatorial search to an amazing extent. Proper pruning will have a greater impact on search time than any other factor.
• Simulated annealing is a simple but effective technique to efficiently obtain good but not optimal solutions to combinatorial search problems.

Next: Backtracking Up: Techniques Previous: Implementation Challenges

Algorithms
Mon Jun 2 23:33:50 EDT 1997