# Algorithms - greedy problems

Solo disponible en BuenasTareas
• Páginas : 7 (1511 palabras )
• Descarga(s) : 0
• Publicado : 29 de noviembre de 2010

Vista previa del texto
The Greedy Algorithm
Tom Morgan, Jacob Steinhardt October 06, 2006

The Basics
The greedy algorithm is perhaps the most straightforward and powerful algorithm you will learn. The idea is simple: given a problem in which you are trying to minimize or maximize something and have some system you can operate on, you ask what the best thing you can do if you were to only do one. Next, you updatethe system and repeat.

When it works
The greedy algorithm can be used when a local change (as in taking the current best action) will not detrimentally aﬀect the system as a whole. A classic example is as follows. Say you are low on funds and decide to rob a convenience store. To your misfortune you ﬁnd that the convenience store has been robbed by another criminal moments before hand. As thestore now lacks any cash, you decide to steal and resell some of the store’s donuts. The store has a variety of donuts which each can be sold for diﬀerent amounts. For example, they may have ten donuts that are worth \$2 each, ﬁve that are worth \$3 each and three that are worth \$1 each. You have room for exactly seven donuts in your pack. What is the maximum amount of money you can make? The greedyapproach is to say: I have seven spots, what is the best donut I can pick for the ﬁrst spot? I take it and repeat. This amounts to taking as many of the most valuable ones as possible and then moving on to the next most. We quickly ﬁnd that the answer in this case is to take ﬁve \$3 donuts and two \$2 donuts.

When it doesn’t work
Taking the problem from before, it is no longer possible to solveif the donuts come in diﬀerent sizes and we can not take fractions of donuts. For example if we have six spaces, and there is a donut of size four that is worth \$8 and there are two donuts of size three that are worth \$5 each. The greedy solution says to ﬁrst take the \$8 one but then we don’t have room for any more, while optimally we could ﬁt the two \$5 donuts for a total value of \$10.Heuristics
The way in which the current best is evaluated is called a heuristic. Given the previous example (in which greedy doesn’t work) possible heuristics include: the donut worth the most, the donut that takes the least space and (most logically) the donut with the highest ratio of value to size. What can make greedy problems diﬃcult is having complicated heuristics. When approaching a greedyproblem (or a problem you are trying to get partial credit on) do not be afraid to use multiple heuristics. By running multiple greedy algorithms and taking the best result, you can maximize your partial credit and on occasion simulate more complicated (and accurate) heuristics.