Algorithms For Dummies

Chapter 18

Performing Local Search

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 ...