《计算机算法设计与分析》第四章 贪心算法.ppt

1
第4章贪心算法
2
学习要点
理解贪心算法的概念
掌握贪心算法的基本要素
(1)最优子结构性质
(2)贪心选择性质
理解贪心算法与动态规划算法的差异
通过应用范例学习贪心设计策略
(1)活动安排问题
(2)最优装载问题
(3)找钱问题
(4)哈夫曼编码
(5)单源最短路径
(6)最小生成树
3
当一个问题具有最优子结构性质时,可用动态规划法求解,但有时用贪心算法求解会更加的简单有效。
顾名思义,贪心算法总是作出在当前看来最好的选择。贪心算法并不从整体最优考虑,它所作出的选择只是在某种意义上的局部最优选择。当然,希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解,但对许多问题它能产生整体最优解,如单源最短路径问题,最小生成树问题等。在一些情况下,即使贪心算法不能得到整体最优解,其最终结果却是最优解的很好近似。
4
例:用贪心法求解找零钱问题。
假设有面值为5元、2元、1元、5角、2角、1角的货币,需要找给顾客4元6角现金,为使付出的货币的数量最少。
首先选出1张面值不超过4元6角的最大面值的货币,即2元,再选出1张面值不超过2元6角的最大面值的货币,即2元,再选出1张面值不超过6角的最大面值的货币,即5角,再选出1张面值不超过1角的最大面值的货币,即1角,总共付出4张货币。
5
在找零钱问题每一步的贪心选择中,在不超过应找零钱金额的条件下,只选择面值最大的货币,而不去考虑在后面看来这种选择是否合理,而且它还不会改变决定:一旦选出了一张货币,就永远选定。
找零钱问题的贪心选择策略是尽可能使付出的货币最快地满足支付要求,其目的是使付出的货币张数最慢地增加,这正体现了贪心法的设计思想。
6
贪心法的求解过程
用贪心法求解问题应该考虑如下几个方面:
(1)候选集合C:为了构造问题的解决方案,有一个候选集合C作为问题的可能解,即问题的最终解均取自于候选集合C。例如在找零钱问题中,各种面值的货币构成候选集合。
(2)解集合S:随着贪心选择的进行,解集合S不断扩展,直到构成一个满足问题的完整解。例如在找零钱问题中,已付出的货币构成解集合。
7
(3)可行解函数solution:检查解集合S是否构成问题的一个可行解。例如,在找零钱问题中,可行解函数是已付出的货币金额恰好等于应找零钱。
(4)选择函数select:即贪心策略,这是贪心法的关键,它指出哪个候选对象最有希望构成问题的解,选择函数通常和目标函数有关。例如,在找零钱问题中,贪心策略就是在候选集合中选择面值最大的货币。
(5)约束函数constraint:检查解集合中加入一个候选对象是否满足约束条件。例如,在找零钱问题中,约束函数是每一步选择的货币和已付出的货币相加不超过应找零钱。
8
贪心算法的一般框架
Greedy(C) //C是问题的输入集合即候选集合
{
S={ }; //初始解集合为空集
while (not solution(S)) //集合S没有构成问题的一个可行解
{
x=select(C); //在候选集合C中做贪心选择
if constraint(S, x) //判断集合S中加入x后是否满足约束条件
S=S+{x};
C=C-{x};
}
return S;
}
9
活动安排问题
该问题是可以用贪心算法有效求解的很好例子。
该问题要求高效地安排一系列争用某一公共资源的活动。
贪心算法提供了一个简单、漂亮的方法,使得尽可能多的活动能兼容地使用公共资源。
10
设有n个活动的集合E={1,2,…,n},其中每个活动都要求使用同一资源,如演讲会场等,而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si<fi。如果选择了活动i,则它在半开时间区间[si,fi)内占用资源。若区间[si,fi)与区间[sj,fj)不相交,则称活动i与活动j是相容的。即当si≥fj或sj≥fi时,活动i与活动j相容。
活动安排问题:要在所给的活动集合中选出最大的相容活动子集合。