文档介绍：Greedy algorithm
叶德仕
yedeshi@
找浊肯介弄头使颇乌封拇钧水钾脉套镰揽厘空沥碴缆妻杖卡僧武叮头锋卉浙江大学算法与程序设计贪心算法浙江大学算法与程序设计贪心算法
1
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
勘幸叶郑篙禾吨评七师妮占距镀篆酷腿慷匹镶履摇壹期缕恃撤寸剐侗痴报浙江大学算法与程序设计贪心算法浙江大学算法与程序设计贪心算法
2
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
鹤体犊弦饮钱削括丛肇埋认驾抓盂弱介图起镰犬诗庶挚敞惨缮惹侄酪藉筛浙江大学算法与程序设计贪心算法浙江大学算法与程序设计贪心算法
3
Rule 1
Select the interval which starts earliest (but not overlapping the already chosen intervals)
Underestimated solution!
Algorithm #1
OPT #4
结息翻暮挫挚感牙肃猪譬忽犊剂丽萧那嘻儿蝶齐李禄竿咯堰雾斯吏荫邪掖浙江大学算法与程序设计贪心算法浙江大学算法与程序设计贪心算法
4
Rule 2
Select the interval which is shortest (but not overlapping the already chosen intervals)
Underestimated solution!
Algorithm #1
OPT #2
皑须汪舵毗硅仕硫答挚铂粹绦呕澈登盏心虑拖摘甸迄躯笼忘费刁脂扯襟使浙江大学算法与程序设计贪心算法浙江大学算法与程序设计贪心算法
5
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
绎兴骚楞刺奎卓甸宰血疟溉厨懒叫鼎硫枣诞脚牵益窗盂准艰闭袜扰锯丧抠浙江大学算法与程序设计贪心算法浙江大学算法与程序设计贪心算法
6
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!
剂怒僚***顾男纪槛彪荆放绑捣存诬陀使陵设焚视呢捕井乘蜀寺丽睫妆祸摆浙江大学算法与程序设计贪心算法浙江大学算法与程序设计贪心算法
7
f1 sma