Algorithms For Dummies

Keeping greedy algorithms under control

When faced with a new difficult problem, it’s not hard to come up with a greedy 

solution using the four steps described in the previous section. All you have to do 

---

CHAPTER 15

  Working with Greedy Algorithms 

     287

is divide your problems into phases and determine which greedy rule to apply at 

each step. That is, you do the following:

 

»

Choose how to make your decision (determine which approach is the 

simplest, most intuitive, smallest, and fastest)

 

»

Start solving the problem by applying your decision rule

 

»

Record the result of your decision (if needed) and determine the status of 

your problem

 

»

Repeatedly apply the same approach at every step until reaching the problem 

conclusion

No matter how you apply the previous steps, you must determine whether you’re 

accomplishing your goal by relying on a series of myopic decisions. The greedy 

approach  works  for  some  problems  and  sometimes  for  specific  cases  of  some 

problems, but it doesn’t work for every problem. For instance, the make-change 

problem  works  perfectly  with  U.S.  currency  but  produces  less-than-optimal 

results with other currencies. For example, using a fictional currency (call it cred-

its, using a term in many sci-fi games and fiction) with denominations of 1, 15, 

and 25 credits, the previous algorithm fails to deliver the optimal change for a due 

sum of 30 credits:

print ('Change: %s (using %i bills)'

       % (change(30, [25, 15, 1])))

Change: [25, 1, 1, 1, 1, 1] (using 6 bills)

Clearly, the optimal solution is to return two 15 credit bills, but the algorithm, 

being shortsighted, started with the highest denomination available (25 credits) 

and then used five 1 credit bills to make up the residual 5 credits.

Some  complex  mathematical  frameworks  called  matroids  (read  the  article  at 

https://jeremykun.com/2014/08/26/when-greedy-algorithms-are-perfect- 

the-matroid/

 for details) can help verify whether you can use a greedy solution 

to optimally solve a particular  problem. If phrasing  a problem using  a matroid 

framework is possible, a greedy solution will provide an optimal result. Yet there 

are problems that have optimal greedy solutions that don’t abide by the matroid 

framework. (You can read about matroid structures being sufficient, but not nec-

essary for an optimal greedy solution in the article found at 

http://cstheory.

stackexchange.com/questions/21367/does-every-greedy-algorithm- 

have-matroid-structure

.)

The greedy algorithms user should know that greedy algorithms do perform well 

but don’t always provide the best possible results. When they do, it’s because the 

---

288

 

   

  PART 5