文档介绍：大学
ZheJiang University
Greedy algorithm
叶德仕
******@
洲 Greedy algorithm's
paradigm
o Algorithm is greedy if
o it builds up a solution in small steps
o it chooses a decision at each step myopically
to optimize some underlying criterion
Analyzing optimal greedy algorithms by
showing that
o in every step it is not worse than any other
algorithm, or
o every algorithm can be gradually transformed
to thegreedy one without hurting its quality
浙大学
ZheJlang University Interval scheduling
o Input: set of intervals on the line, represented by
pairs of points(ends of intervals). In another word
the ith interval, starts at time s; and finish at fi
o Output: finding the largest set of intervals such
that none two of them overlap. Or the maximum
number of intervals that without overlap
o Greedy algorithm
o Select intervals one after another using some rule
大学
ZheJiang University
Rule 1
o Select the interval which starts earliest
(but not overlapping the already chosen
intervals
o Underestimated solution!
OPT #4
Algorithm #1
浙大学
ZheJiang University
Rule 2
o Select the interval which is shortest(but
not overlapping the already chosen
intervals
o Underestimated solution!
OPT #2
Algorithm #1
浙大学
ZheJiang University
Rule 3
o Select the interval with the fewest conflicts
with other remaining intervals(but still not
overlapping the already chosen intervals
o Underestimated solution
OPT #4
Algorithm #3
大学
f smallest
ZheJiang University
Algorithm #3
大学
ang Hier Analysis- exact solution
o Algorithm gives non-overlapping intervals
o obvious, since we always choose an interval which
does not overlap the previously chosen intervals
o The solution is exact
o Let a be the set of intervals obtained by the
algorithm
o and oPt be the largest set of pairwise non-
overlapping intervals
o We show that a must be as large as opt
大学
ZheJiang University
Analysis
exact solution cont
oLet A=