Algorithms For Dummies

  Considering Algorithm Design 

     31

Learning that Greed Can Be Good

In some cases, you can’t see the end of a solution process or even know whether 

you’re winning the war. The only thing you can really do is to ensure that you win 

the individual battles to create a problem solution in hopes of also winning the war. 

A greedy method to problem solving uses this approach. It looks for an  overall solu-

tion such that it chooses the best possible outcome at each problem solution stage.

It  seems  that  winning  each  battle  would  necessarily  mean  winning  the  war  as 

well, but sometimes the real world doesn’t work that way. A Pyrrhic victory is one 

in which someone wins every battle but ends up losing the war because the cost of 

the victory exceeds the gains of winning  by such a large margin. You can read 

about  five  Pyrrhic  victories  at 

http://www.history.com/news/history-lists/ 

5-famous-Pyrrhic-victories

. The important lesson from these histories is that 

a greedy algorithm often does work, but not always, so you need to consider the 

best overall solution to a problem rather than become blinded by interim wins. 

The following sections describe how to avoid the Pyrrhic victory when working 

with algorithms.