Chapter 18

IN THIS CHAPTER

**Determining how to perform a local search on an NP-hard problem**

**Working with heuristics and neighboring solutions**

**Solving the 2-SAT problem with local search and randomization**

**Discovering that you have many tricks to apply to a local search**

When dealing with an NP-hard problem, a problem for which no known solution has a running complexity less than exponential (see the NP-completeness theory discussion in Chapter 15), you have a few alternatives worth trying. Based on the idea that NP-class problems require some compromise (such as accepting partial or nonoptimal results), the following options offer a solution to this otherwise intractable problem:

- Identify special cases under which you can solve the problem efficiently in polynomial time using an exact method or a greedy algorithm. This approach simplifies the problem and limits the number of solution combinations to try.
- Employ dynamic programming techniques (described in Chapter 16) that improve on brute-force search and reduce the complexity of the problem.
- Compromise and ...

Start Free Trial

No credit card required