CSE 101 Class Notes Greedy Algorithms November 6 2006 Overview Greedy algorithms always choose the intuitively best option at each decision point and unlike backtracking do not consider other alternatives The problem is that while this powerful intuition is powerful it is often wrong just as in life acting in one s immediate best interest is not always the best longer term strategy Therefore it is especially important to prove that a greedy algorithm finds the best solution Luckily these proofs typically follow a standard form which we will discuss today Example Event scheduling Instance a set of events E Ei si fi where si fi Solution form A subset S E Constraints No two events in S intersect Objective Maximize the number of events S Algorithm The right heuristic is to always choose the event with the earliest end time Here is the backtracking version of Schedule using this choice heuristic 1 2 3 4 5 6 7 8 Schedule E e event minimizing finish e s1 Schedule E overlap e e s2 Schedule E e if s1 s2 return s1 else return s2 The greedy version differs by never considering s2 on line 4 always returning s1 1 Correctness We need to prove that s1 is always at least as good as s2 i e S1 S2 Consider an event ei chosen by the greedy algorithm Let S 0 be the best schedule not containing ei i e the best solution violating our greedy heuristic and let S be the best schedule including ei i e the best following the heuristic in considering ei Our goal is to show that S is at least as good as S 0 Theorem The greedy schedule is always a largest legal schedule Lemma Let Ei be the event with minimal fi Let S 0 be any legal schedule s t Ei S Then there is a legal schedule S s t Ei S and S S 0 Proof Let C Ei be the set of elements that conflict with Ei Any even Ej C Ei must have si fj fi Let S S 0 C Ei Ei Then S containing Ei is a legal schedule since S 0 has no conflicts and S does not contain any events in C Ei We still need to show that S S 0 i e that C Ei 1 Assume that this is not the case i e Ej Ek with si fj fk fi Then Ej Ek must conflict contradicting our assumption that S 0 is a legal schedule Therefore C Ei 1 and S S 0 Proof by strong induction on S the number of events Inductive hypothesis for all n if there exists a schedule S 0 with n events then the transformation above can be used to generate a greedy schedule S with S S 0 Base case If S 0 1 the algorithm finds either 0 or 1 event Inductive case Assume the greedy algorithm is optimal for S n and let Ei be the first remaining event to finish i e the greedy choice Let Sn0 be the non greedy optimal schedule making a non greedy choice instead of Ei 0 and let Sn 1 be its first n 1 events By our lemma the schedule S 00 0 Sn 1 C Ei Ei has S 00 Sn0 and Ei S 00 By our inductive hypothesis 0 0 Sn 1 Sn 1 Also since Sn 1 is greedy the last event in Sn 1 finishes no sooner than the last event in Sn 1 so Sn 1 Ei is a legal solution Therefore Sn Sn 1 Ei Sn 1 C Ei Ei 0 Sn 1 C Ei Ei S 00 Sn0 proving our inductive hypothesis 2 Example S2 A B S1 1 3 2 4 3 6 0 6 5 7 5 8 9 10 Here S2 s first move is non greedy The transformation in our proof replaces 2 4 with 1 3 line A then performs another greedy transformation line B yielding an equal sized schedule S1 Implementation A naive implementation of the above approach searching the entire list at each step for the next choice then for overlapping events would take O n2 An efficient implementation instead sorts the list by finish time and skips over overlapping events as it traverses this sorted list 1 2 3 4 5 6 7 8 Schedule2 E E sort by finish E S E 1 f finish E 1 for i 2 n if start E i f S S E i f finish E i General approach The modify the solution approach used above can be applied to prove the correctness of many greedy algorithms In general we proceed by the following steps 1 Let d be the first decision point and let g be the greedy choice at d 2 Let S 0 be a solution not choosing g 3 Show how to transform S 0 into some S that chooses g and that is at least as good as S 0 4 Conclude by induction that any S 0 with a series of non greedy decisions at d1 dn can be transformed into an equal or better greedy solution and that therefore the greedy algorithm is optimal 3