Algorithms For Dummies

 Challenging Difficult Problems

analysis and design of algorithms. The remainder of this book discusses the fol-

lowing general approaches:

 

»

Greedy algorithms (explained in this chapter)

 

»

Dynamic programming

 

»

Randomization, local search, and farsighted heuristics

 

»

Linear programming and optimization problems

Deciding When It Is Better to Be Greedy

When  faced  with  difficult  problems,  you  quickly  discover  that  no  magic  potion 

exists for making wishes come true or silver bullets to dispel bad things. Similarly, 

no  algorithmic  technique  saves  the  day  every  time.  That’s  the  no-free-lunch 

principle often quoted in the book. The good news is, you can arm yourself with 

different general techniques and test them all on your problem, because you have 

a good chance that something will work well.

Greedy algorithms come in handy for solving a wide array of problems, especially 

when drafting a global solution is difficult. Sometimes, it’s worth giving up com-

plicated plans and simply start looking for low-hanging fruit that resembles the 

solution you need. In algorithms, you can describe a shortsighted approach like 

this as greedy. Looking for easy-to-grasp solutions constitutes the core distin-

guishing characteristic of greedy algorithms. A greedy algorithm reaches a prob-

lem solution using sequential steps where, at each step, it makes a decision based 

on  the  best  solution  at  that  time,  without  considering  future  consequences  or 

implications.

Two elements are essential for distinguishing a greedy algorithm: