文档介绍：Greedy algorithm’s paradigm
Algorithm is greedy if
it builds up a solution in small steps
it chooses a decision at each step myopically to optimize some underlying criterion
Analyzing optimal greedy algorithms by showing that:
in every step it is not worse than any other algorithm, or
every algorithm can be gradually transformed to thegreedy one without hurting its quality
1
Interval scheduling
Input: set of intervals on the line, represented by pairs of points (ends of intervals). In another word, the ith interval, starts at time si and finish at fi.
Output: finding the largest set of intervals such that none two of them overlap. Or the maximum number of intervals that without overlap.
Greedy algorithm:
Select intervals one after another using some rule
2
Rule 1
Select the interval which starts earliest (but not overlapping the already chosen intervals)
Underestimated solution!
Algorithm #1
OPT #4
3
Rule 2
Select the interval which is shortest (but not overlapping the already chosen intervals)
Underestimated solution!
Algorithm #1
OPT #2
4
Rule 3
Select the interval with the fewest conflicts with other remaining intervals (but still not overlapping the already chosen intervals)
Underestimated solution!
Algorithm #3
OPT #4
5
Rule 4
Select the interval which ends first (but still not overlapping the already chosen intervals)
Quite a nature idea: we ensure that our resource e free as soon as possible while still satisfying one request
Hurray! Exact solution!
6
f1 smallest
Algorithm #3
7
Analysis - exact solution
Algorithm gives non-overlapping intervals:
obvious, since we always choose an interval which does not overlap the previously chosen intervals
The solution is exact:
Let A be the set of intervals obtained by the algorithm,
and OPT be the largest set of pairwise non-overlapping intervals.
We show that A must be as large as OPT
8
Analysis – exact solution cont.
Let and be sorted. By definition of OPT we have k ≤ m
Fact: for e