Algorithms For Dummies

  Performing Local Search 

     339

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

Performing Local Search

W

hen 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: