COMP251: Greedy algorithms
Jérôme Waldispühl School of Computer Science
McGill University
Based on (Cormen et al., 2002)
Based on slides from D. Plaisted (UNC) & (goodrich & Tamassia, 2009)
Overview
• Algorithm design technique to solve optimization problems.
• Problems exhibit optimal substructure. • Idea (the greedy choice):
– When we have a choice to make, make the one that looks best right now.
– Make a locally optimal choice in hope of getting a globally optimal solution.
Greedy Strategy
The choice that seems best at the moment is the one we go with.
– Prove that when there is a choice to make, one of the optimal choices is the greedy choice. Therefore, it is always safe to make the greedy choice.
– Show that all but one of the sub-problems resulting from the greedy choice are empty.
Activity-selection Problem
• Input: Set S of n activities, a1, a2, …, an. – si = start time of activity i.
– fi = finish time of activity i.
• Output: Subset A of maximum number of compatible activities.
– 2 activities are compatible, if their intervals do not overlap.
Example:
Activities in each line are compatible.
0 1 2 3 4 5 6 7 8 9 10
Activity-selection Problem
i1234567 si 0 1 2 4 5 6 8
fi
2 3 5 6 9 9 10 Activities sorted by finishing time.
s a3 s6 a6 f
3 f3 6
a2fsa5 f 255
s2
s a1 114477
f s a4 f s a7 f
0 1 2 3 4 5 6 7 8 9 10 Optimal compatible set: { a1 , a3 , a5 }
Optimal Substructure
• Assumeactivitiesaresortedbyfinishingtimes.
• Supposeanoptimalsolutionincludesactivityak.This solution is obtained from:
– An optimal selection of a1, …, ak-1 activities compatible with one another, and that finish before ak starts.
– An optimal solution of ak+1, …, an activities compatible with one another, and that start after ak finishes.
0 1 2 3 4 5 6 7 8 9 10
Optimal Substructure
• Let Sij = subset of activities in S that start after ai
finishes and finish before aj starts. S=a∈S:∀i,j f≤s
f1 ¬ Q.minKey()
T1 ¬ Q.removeMin() f2 ¬ Q.minKey()
T2 ¬ Q.removeMin() T ¬ join(T1, T2) Q.insert(f1 + f2, T)
return Q.removeMin()