Greedy Algorithms
Greed is good.
Greed is right.
Greed works.
Greed cuts through,
clarifies, and
captures the
essence of the
evolutionary spirit.
-Gordon Gekko
(Michael Douglas)
http://en.wikipedia.org/wiki/Wall_Street_(film)
Greedy Algorithms
Simple idea, but it doesnt always work.
Used to solve optimization problems that involve choosing
objects, events, (some type of entities) from a set.
The Greedy Strategy:
At each step, make the best next choice.
Never backtrack or change past choices.
Never look ahead to see if this choice has negative
consequences.
Depending on the problem: this may or may not give
the correct answer.
The text treats greedy algorithms as a special case
of dynamic programming
The greedy paradigm is simpler
We will do greedy algorithms first
1 Properties of Greedy Algorithms
Usually simple and fast (often linear time).
Hard part is demonstrating optimality.
Examples: Huffman encoding, some sorting
algorithms.
Typically applied to optimization problems
(find solution which maximizes or minimizes
some objective function).
Example: Making Change
Input:
Suppose we are given the specification of a
monetary denominational system
(a list of the values of different coins that are in use,
for example: 1, 5, 10, 25, 100, 200 cents).
We are also given an amount (specified in cents)
to return to a customer
Problem:
Do this using the fewest number of coins
2 Alexandrian
Coin
Denominations
Used in AD 117-138
Timeof emperor
Hadrian
The Coin Changing Problem
Assume that we have an unlimited number of coins of
various denominations:
1c (pennies), 5c (nickels), 10c (dimes), 25c (quarters), 1$ (loonies)
Objective: Pay out a given sum S with the smallest
number of coins possible.
The greedy coin changing algorithm :
This is a (m) algorithm where m = number of denominations.
while S > 0 do
c := value of the largest coin no larger than S;
num := S div c;
pay out num coins of value c;
S := S - num*c;
3 Example: Making Change
E.g.:
$5.64 = $2 +$2 + $1 +
.25 + .25 + .10 +
.01 + .01 + .01 +.01
Nontrivial exercise: prove this always uses
smallest number of coins
Easier exercise:
set up a monetary system for which this
algorithm fails
Framework for Greedy Algorithms
At each stage, we have a partial solution
which can be extended to a larger solution.
We have a set of choices for this next step and
we select a good choice to extend the solution.
We have some sort of predefined measure
of what a good choice is.
Take the best choice under that measure.
Repeat until a complete solution is obtained.
4

More
Less