CMSC 441: Algorithms Greedy Algorithms
Hillol Kargupta, Professor
http://www.cs.umbc.edu/~hillol/
hillol@gl.umbc.edu
1
Greedy Algorithms
Greedyalgorithmshavethefollowingproperty:Continuously finding the local optimum leads to the global optimum solution.
In simple words, be greedy at every step!
Agreedyalgorithmalwaysmakesthechoicethatlooksbestat
the moment.
Examples:
Gas station problem to minimize the number of gas stops
Activity selection problem
Huffman code for data compression
Fractionalknapsackproblem
Minimumspanningtree:Prim’salgorithm
2
Example: Minimize gas stops
Problem statement:
Goal is to minimize the number of gas stops.
Input: start & end positions, exact locations of all gas stations along the way. Exactly m miles can be covered with one full tank of gas, irrespective of speed. Assume that initially gas tank is full.
Output: a list of gas stops.
Greedyidea:Goasfarasyoucangobeforestoppingforgas!
s Gas station locations
t
…
3
Algorithm
Algorithm find_gas_stops():
current position = start position;
while (current_position < end_position)
compute the position at which car will run out of gas. if (that position < end position) then
find closest gas station before reaching that position. output fill up gas at that gas station.
current position = that gas station location
else
current position = end position; /* reached */
4
Proof
• Prove that the algorithm finds an optimal solution, i.e. another solution with less number of gas stations does NOT exist.
• Induction or contradiction can be used. Contradiction will work well. • Proof:
• Assume that our algorithm does not find an optimal solution, i.e. there exists another better solution.
• Our solution is s1 =
• Continues in the next slide…
5
• Compare the gas stops, starting with the first gas stop: – Therearethreepossibilities:
Proof …
– gsi = gsi’ : Continue to compare next gas stops.
– gsi > gsi’ : This is strange, s1 is taking lead.Without affecting the outcome, we can make gsi’ = gsi and collapse this one to previous case.
– gsi