Algorithms For Dummies

 

»

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 sketch an approximate algorithm that finds a partial, 

close-to-optimal solution. When you’re satisfied with a partial solution, you cut 

the algorithm’s running time short. Approximate algorithms can be

• 

Greedy algorithms (as discussed in Chapter 15)

• 

Local search using randomization or some other heuristic technique (the 

topic of the present chapter)

• 

Linear programming (the topic of Chapter 19)

Chapter 

18

---

340

 

   

  PART 5