【教学课件】第五章GreedyAlgorithm.ppt

《【教学课件】第五章GreedyAlgorithm.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第五章GreedyAlgorithm.ppt（77页珍藏版）》请在三一办公上搜索。

1、第五章 Greedy Algorithm,骆吉洲计算机科学与工程系,5.1 Elements of Greedy Algorithms 5.2 An activity-selection problem5.3 Huffman codes 5.4 Theoretical foundations of Greedy Algorithms5.5 A task-scheduling problem5.6 Minimal spanning tree problem 5.7 Single-sourse shortest path problem,提要,参考资料,Introduction to Algori

2、thms 第16章:16.1,16.2,16.3,16.4,16.5 23.1,23.2 计算机算法设计与分析 第4章:4.1,4.2,4.4,4.5,4.6,4.8网站资料 第五章,5.1 Elements of Greedy Algorithms,Greedy算法的基本概念Greedy选择性 优化子结构与动态规划方法的比较 Greedy算法正确性证明方法,Greedy算法的基本思想求解最优化问题的算法包含一系列步骤每一步都有一组选择作出在当前看来最好的选择希望通过作出局部优化选择达到全局优化选择Greedy算法不一定总产生优化解Greedy算法是否产生优化解，需严格证明Greedy算法产生

3、优化解的条件Greedy-choice-propertyOptimal substructure,Greedy算法的基本概念,Greedy选择性,Greedy选择性 若一个优化问题的全局优化解可以通过 局部优化选择得到，则该问题称为具有 Greedy选择性.一个问题是否具有Greedy选择性需证明,若一个优化问题的优化解包含它的 子问题的优化解，则称其具有优化 子结构,优化子结构,与动态规划方法的比较,动态规划方法可用的条件优化子结构子问题重叠性子问题空间小Greedy方法可用的条件优化子结构Greedy选择性可用Greedy方法时，动态规划方法可能不适用可用动态规划方法时，Greedy方法可

4、能不适用,证明算法所求解的问题具有优化子结构证明算法所求解的问题具有Greedy选择性证明算法确实按照Greedy选择性进行局部优化选择,Greedy算法正确性证明方法,5.2 An activity-selection problem,问题的定义优化解的结构分析算法设计算法复杂性 算法正确性证明,问题的定义,活动 设S=1,2,n是n个活动的集合，各个活动使 用同一个资源，资源在同一时间只能为一个活动使用 每个活动i有起始时间si，终止时间fi，si fi 相容活动 活动i和j是相容的，若sjfi或sifj，即,Sj,fj,Si,fi,问题定义输入：S=1,2,n，F=si，fi，ni1输出

5、：S的最大相容集合,贪心思想:为了选择最多的相容活动，每次选fi最小的活动，使我们能够选更多的活动,引理1 设S=1,2,n是n个活动集合，si，fi 是活动 的起始终止时间，且f1f2.fn，S的活动选 择问题的某个优化解包括活动1.证 设A是一个优化解，按结束时间排序A中活动，设其第一个活动为k，第二个活动为j.如果k=1，引理成立.如果k1，令B=A-k1,由于A中活动相容，f1fk sj,B中活动相容.因为B=A,所以B是一个优化解，且包括活动1.,优化解结构分析,引理2.设S=1,2,n是n个活动集合，si，fi是活动i 的起始终止时间，且f1f2.fn，设A是S的调 度问题的一个优

6、化解且包括活动1，则A=A-1 是S=iS|sif1的调度问题的优化解.证.显然，A中的活动是相容的.我们仅需要证明A是最大的.设不然，存在一个S 的活动选择问题的优化解 B，BA.令B=1B.对于iS,si f1,B中活动相容.B是S的一个解.由于|A|=|A|+1,B=B+1A+1=A，与A最 大矛盾.,引理2说明活动选择问题具有优化子结构,Greedy选择性引理3.设 S=1,2,.,n 是 n 个活动集合，f0=0,li 是 Si=jS|sj fi-1 中具有最小结束时间 fli 的活 动.设A是S的包含活动1的优化解,其中 f1 fn，则A=证.对A作归纳法.当A=1时,由引理1，命

7、题成立.设Ak时，命题成立.当A=k时,由引理2，A=1A1,A1是 S2=jS|sj f1 的优化解.由归纳假设，A1=.于是,A=.,贪心思想 为了选择最多的相容活动，每次选fi最小的活动，使我们能够选更多的活动,算法的设计,算法（设f1f2.fn已排序）Greedy-Activity-Selector(S,F)nlenyth(S);A1 j1 For i2 To n Do If si fj Then AAi；ji；Return A,如果结束时间已排序 T(n)=(n)如果 结束时间未排序 T(n)=(n)+(nlogn)=(nlogn),复杂性设计,需要证明活动选择问题具有Greedy选

8、择性活动选择问题具有优化子结构算法按照Greedy选择性计算解,算法正确性证明,定理.Greedy-Activity-Selector算法能够产 生最优解.证.Greedy-Activity-Selector算法按照引 理3的Greedy选择性进行局部优化选 择.,5.3 Huffman codes,问题的定义优化解的结构分析算法设计算法复杂性分析 算法正确性证明,二进制字符编码每个字符用一个二进制0、1串来表示.固定长编码每个字符都用相同长的0、1串表示.可变长编码经常出现的字符用短码，不经常出现的用长码前缀编码无任何字符的编码是另一个字符编码的前缀,问题的定义,编码树,叶结点:用字符及其出

9、现频率标记,内结点:用其子树的叶结点的频率和标记,边标记:左边标记0，右侧边标记1,编码树T的代价设C是字母表,cCf(c)是c在文件中出现的频率dT(c)是叶子c在树T中的深度，即c的编码长度T的代价是编码一个文件的所有字符的代码位数:B(T)=,优化编码树问题输入:字母表 C=c1,c2,.,cn，频率表 F=f(c1),f(c2),.,f(cn)输出:具有最小B(T)的C前缀编码树,贪心思想：循环地选择具有最低频率的两个结点，生成一棵子树，直至形成树,我们需要证明优化前缀树问题具有优化子结构优化前缀树问题具有Greedy选择性,优化解的结构分析,优化子结构引理1.设T是字母表C的优化前缀

10、树，cC，f(c)是c在文件中出现的频率.设x、y是T中任意 两个相邻叶结点，z是它们的父结点，则z作 为频率是f(z)=f(x)+f(y)的字符，T=T-x,y是 字母表C=C-x,yz的优化前缀编码树.,证.往证B(T)=B(T)+f(x)+f(y).vC-x,y,dT(v)=dT(v),f(v)dT(v)=f(v)dT(v).由于 dT(x)=dT(y)=dT(z)+1,f(x)dT(x)+f(y)dT(y)=(f(x)+f(y)(dT(z)+1)=(f(x)+f(y)dT(z)+(f(x)+f(y)由于 f(x)+f(y)=f(z),f(x)dT(x)+f(y)dT(y)=f(z)dT

11、(z)+(f(x)+f(y).于是B(T)=B(T)+f(x)+f(y).若T不是C的优化前缀编码树，则必存在T，使B(T)B(T).因为z是C中字符，它必为T中的叶子.把结点x与y加入T，作为z的子结点，则得到C的一个如下前缀编码树T：,T代价为：B(T)=+(f(x)+f(y)(dT(z)+1)=+f(z)dT(z)+(f(x)+f(y)(dT(z)=dT(z)=B(T)+f(x)+f(y)B(T)+f(x)+f(y)=B(T)与T是优化的矛盾，故T是C的优化编码树.,Greedy选择性引理2.设C是字母表，cC，c具有频率f(c),x、y 是C中具有最小频率的两个字符，则存在一 个C的优

12、化前缀树，x与y的编码具有相同长 度，且仅在最末一位不同.,不失一般性，设f(b)f(c),f(x)f(y).因x与y是具有最低频率的字符,f(b)f(x),f(c)f(y).交换T的b和x,从T构造T:,证:设T是C的优化前缀树，且b和c是具有最大深度的 两个兄弟字符:,交换y和c构造T,往证T是最优化前缀树.B(T)-B(T)=f(x)dT(x)+f(b)dT(b)-f(x)dT(x)-f(b)dT(b)=f(x)dT(x)+f(b)dT(b)-f(x)dT(b)-f(b)dT(x)=(f(b)-f(x)(dT(b)-dT(x).f(b)f(x),dT(b)dT(x)(因为b的深度最大)B

13、(T)-B(T)0,B(T)B(T)同理可证B(T)B(T).于是B(T)B(T).由于T是最优化的，所以B(T)B(T).于是,B(T)=B(T)，T是C的最优化前缀编码树.在T中,x和y具有相同长度编码,且仅最后一位不同.,基本思想循环地选择具有最低频率的两个结点，生成一棵子树，直至形成树初始:f:5,e:9,c:12,b:13,d:16,a:45,算法的设计,Greedy算法(使用堆操作实现)Huffman(C，F)1.nC;2.QC;/*用BUILD-HEAP建立堆*/3.FOR i1 To n-1 Do 4.zAllocate-Node();5.xleftzExtract-MIN(Q

14、);/*堆操作*/6.yrightzExtract-MIN(Q);/*堆操作*/7.f(z)f(x)+f(y);8.Insert(Q,z);/*堆操作*/9.Return,设Q由一个堆实现第2步用堆排序的BUILD-HEAP实现:O(n)每个堆操作要求O(logn)，循环n-1次:O(nlogn)T(n)=0(n)+0(nlogn)=0(nlogn),复杂性分析,定理.Huffman算法产生一个优化前缀编码树 证.由于引理1、引理2成立,而且Huffman算 法按照引理2的Greedy选择性确定的规 则进行局部优化选择，所以Huffman算 法产生一个优化前缀编码树。,正确性证明,5.4 Mi

15、nimal spanning tree problem,问题的定义 优化解结构分析 Greedy选择性 Kruskal算法 算法复杂性 算法正确性证明,问题的定义,生成树 设G=(V,E)是一个边加权无向连通图.G的生成 树是无向树S=(V,T),TE,以下用T表示S.如果 W:E实数 是G的权函数,T的权值定 义为W(T)=(u,v)TW(u,v).最小生成树 G的最小生成树是W(T)最小的G之生成树.问题的定义输入:无向连通图G=(V,E),权函数W输出:G的最小生成树,实例,算法思想,B,C,A,E,D,70,60,80,50,定理1.设T是G的最小生成树.如果T包含子树T1和 T2,T

16、1是G的子连通图G1的生成树，T2是G 的子连通图G2的生成树，则T1是G1的最小 生成树，T2是G2的最小生成树.证.,优化解的结构分析,Greedy选择性,一般算法 初始:A为空集合 反复扩展边集合A,直至A成为最小生成树 循环不变命题每次循环算法要保持下边循环不变命题为真“在每次循环前，A必是某个最小生成树的子集”在每次循环中,如果A(u,v)是某个最小生成树 的子集，则称边(u,v)是安全边,一般算法的定义Generic-MST(G,W)1.A=;/*不变命题真*/While A 不是生成树 Do/*不变命题真*/寻找一个安全边(u,v);A=A(u,v);Return A/*不变命题

17、真*/,算法的关键是第三步,寻找安全边(u,v),寻找安全边的规则定义1.无向图G=(V,E)的一个划分是V的一个划分(S,V-S).定义2.如果uS,vV-S,则边(u,v)称为划分(S,V-S)的交叉边.定义3.如果边集合A中没有边是划分(S,V-S)的交 叉边,则称划分(S,V-S)尊重A.定义4.划分(S,V-S)的交叉边(u,v)称为轻边,如果在 所有(S,V-S)的交叉边中,(u,v)的权值最小.定义5.边(u,v)是满足某性质的轻边,如果在满足该性 质的边中,(u,v)的权值最小.,示例,红结点集合是S 浅蓝结点集合是V-S 蓝边是交叉边,权为7的边是轻边 红边集合是受尊重的边集

18、合,定理1.设G=(V,E)是具有边加权函数W的无向连通图,AE是包含在G的某个最小生成树中的边集合,(S,V-S)是G的尊重A的任意划分,(u,v)是(S,V-S)的交叉轻边,则(u,v)对A是安全的.证.令T是包含A的最小生成树.如果(u,v)属于T,则(u,v)对A是安全的.设(u,v)不属于T.我们构造一个G的最小生成树 T,使其包含A(u,v),从而证明(u,v)安全.,由于u和v在划分(S,V-S)的两边,T至少存在一条交叉边在p中,设为(x,y).由于划分尊重A,(x,y)不在A中.删除 p中的(x,y),增加(u,v),得到T=T-(x,y)(u,v).往证T是最小生成树.因为

19、(u,v)是轻交叉边,(x,y)是交叉边,W(u,v)W(x,y).W(T)=W(T)-W(x,y)+W(u,v)W(T)由于T是最小生成树,W(T)=W(T).T是最小生成树,A(u,v)T,(u,v)对于A是安全的.,S=黄结点集合 V-S=浅蓝结点集合 A=红边集合,推论1.设G=(V,E)是具有边加权函数W的无向连通图,AE是包含在G的某个最小生成树中的边集合,C=(VC,EC)是森林GA=(V,A)中的树.如果(u,v)是连接C和GA中另一个树的交叉轻边,则(u,v)对A是安全的.证.划分(VC,V-VC)尊重A.(u,v)关于这个划分的交叉轻边.于是,(u,v)对A是安全的.,Kr

20、uskal算法,MST-Kruskal(G,W)1.A=;2.For vVG Do Make-Set(v);/*按照W值的递增顺序排序EG;For(u,v)EG(按W值的递增顺序)Do If Find-Set(u)Find-Set(v)Then A=A(u,v);Union(u,v);Return A,算法复杂性,令n=|V|,m=|E|第4步需要时间:O(mlogm)第2-3步执行O(n)个Make-Set操作 第5-8步执行(n)个Find-Set和Union操作 每个Find-Set和Union操作O(n)mn-1(因为G连通),(n)=O(logn)=O(logm)总时间复杂性：O(m

21、logm),算法正确性,定理2.MST-Kruskal(G,W)算法能够产生图 G的最小生成树.证.因为算法按照Greedy选择性进行局 部优化选择.,5.5 Theoretical foundations of Greedy Algorithms,Matroid(拟阵)Matroid 实例Matroid的性质 加权Matroid上的Greedy算法任务调度问题,Matroid定义 Matroid是一个序对M=(S,I)，满足：(1)S是一个有限非空集合.(2)I是非空的S子集的集族，I中的子集称为 S的独立子集族.(3)遗传性:如果AI，BA，则BI(4)交换性:如果AI，BI，AB，则 x

22、B-A使得AxI.,Matroid(拟阵),实例(Graphic Matroid)定义1.设 G=(V，E)是一个无向图，由 G 确定的 MG=(SG，IG)定义如下:SG是G的边集合E，IG=A|AE,(V,A)是森林.定理1.如果G是一个无向图，则MG=(SG，IG)是一 个Matroid.证.SG=E是一个有限集合.eE,(V,e)是一个森林，eIG.于是，IG是SG的非空集族.,MG满足遗传性:如果BIG，AB，则(V,A)是一个 森林.于是，AIG，MG满足遗传性.MG满足交换性:设AIG,BIG,|A|B|.如果B的任意一条边都包含在A的同一棵树中，则B 的边数不大于A的边数，与|

23、A|B|矛盾.于是，B必包含一条边(u,v)，(u,v)在A的不相同树中.(u,v)B-A连接A的两棵不同树.(V,A(u,v)是森林，A(u,v)IG.于是,MG满足交换性.,Matroid的性质定义2.设M=(S,I)是一个Matroid,AI.如果AxI,xA,x称为A的一个extension.定义3.设M=(S,I)是Matroid,AI.若A没有extension,则称A为最大独立子集合.定理2.一个Matroid的所有最大独立子集合都具有相 同大小.证.设A是Matroid M的最大独立子集合，而且存 在M的另一个独立子集合B,|A|B|.根据M的交换性,xB-A使AxI,与A最

24、大矛盾.,Matroid的优化子集定义4.设M=(S，I)是一个Matroid。如果存在一 个权函数W，使得xS,W(x)是一个正 数，则称M是加权Matroid。W可以扩展到 S的任意子集合A:W(A)=xAW(x).定义5.Matroid M=(S,I)中具有最大权值W(A)的独立子集AI称为M的优化子集.,加权Matroid上的Greedy算法,实际背景:很多可用Greedy算法获得最优解的问题可以归 结为在加权Matroid中寻找优化子集的问题,即 给定M=(S,I)和权函数W,搜索独立子集AI,使 得W(A)最大。,实例:最小生成森林问题问题定义 输入：无向图G=(V,E)，权函数W

25、:E正整数集 输出：边子集合AE,(V,A)是森林，W(A)最小 转换为加权Matroid上寻找优化子集问题构造：MG=(SG,IG)是图Matroid W(e)=W0-W(e)，W0 maxW(e)eE，W(e)0.W扩展为W(A)=VW0-W(A)，AEMG的最优子集A满足：(V,A)是森林W(A)最大，即W(A)最小.最小生成森林问题可以由求MG的最优子集的算法来求解,加权Matroid优化子集问题的定义 输入：Matroid M=(S,I),M的加权函数W 输出：M的最优子集,算法 Greedy(M,W)1 A=;2 按权W值大小排序S;3 For xS（按W(x)递减顺序）DO 4

26、If AxI/*选择目前W(x)最大的x*/5 Then Ax;6 Return A.时间复杂性 step 2:O(slogs)step 4:O(f(s)T(s)=O(slogs+s f(s),算法正确性引理1.Greedy算法总是返回一个独立子集合.证.设Greedy返回集合A，对A做数学归纳法.当A=0时,A是空集,由遗传性,A是独立子集合.设Ak时,A是独立子集.当A=k+1时,A由第4-5步得到,即A=Ax.第4步已判定AxI，A=Ax是独立子集.,我们需要证明A是最优子集，即证明加权Matroid最优子集问题具有Greedy选择性加权Matroid最优子集问题具有优化子结构算法按照优

27、化子结构和选择规则选择最优子集,Greedy选择性 引理2.设M=(S,I)是一个加权Matroid,W是M的权函数,S 按W值递减排序.若S中满足xI的第一个元素x,则存在一个M的优化子集A,xA.证.设S第一个元素x满足xI.若存在优化子集A包含x，则引理得证.否则,设B是任意非空优化子集,xB.显然,yB，W(x)W(y).如下构造含x的优化子集A:初始:A=xI;用交换性:yB-A,若AyI,A=Ay,直至A=B.显然，zB,A=(B-z)x.于是,W(A)=W(B)-W(y)+W(x)W(B).因为B是优化子集,所以W(A)W(B),W(A)=W(B).A是优化子集,且xA.,引理3

28、.设M=(S,I)是一个Matroid.如果xS不是空集的 extension,则x不是任何独立子集的extension.证.反证.设xS是独立子集A的extension但不是的 extension.由于x是A的extension,AxI.由M的遗传性，xI,即x是的 extension,矛盾.推论1.任何元素一旦不能被选中,则永远不会被选中.推论2.Greedy算法不会由于不再考虑未被初始选中的元 素而产生错误.,优化子结构引理4.设x是第一个被Greedy算法选中的元素.包含 x的优化子集A包含子问题M=(S,I)的优化 子集A=A-x,M=(S,I)定义如下:S=ySx,yI,I=BS-

29、xBxI 而且M的权函数与M的权函数相同.证.若A是M的优化子集且xA,则A=A-x A.因为A=AxI,所以A=A-xI.若A不是M的优化子集,则存在M的一个优 化子集B使得W(B)W(A).由于BxI,W(A)=W(A)+W(x),W(Bx)=W(B)+W(x)W(A)+W(x)=W(A),与W(A)优化矛盾.,算法正确性定理1.设M=(S,I)是一个Matroid,W是M的权函数,Greedy(M,W)返回一个M的优化子集.证.引理3说明,任何没有被Greedy选中的S元素,以 后不会被选中，可以不再考虑.一旦S的第一个x被选中,x可以加到A,因为引理 2说明存在一个包含x的优化子集.引

30、理4意味着余下的问题是在M中求解最优子 集的问题.Greedy算法是按照上述三个规则工作的，所以Greedy(M,W)返回一个M的优化子集.,5.6 A task-scheduling problem,单位时间任务 需要一个单位时间就能够完成的任务单位时间任务的调度问题 输入：单位时间任务集S=1,2,n正整数任务期限D=d1,d2,dn,任务i须在di前完成非负权集W=w1,w2,wn,任务i不在di前完成罚款wi 输出：S的一个调度(S的一个执行顺序),具有最小总罚款,问题定义,转换为加权Matroid的优化子集问题定义1.设S是一个任务调度.一个任务在S中是迟的如 果它在规定的期限之后完

31、成;否则是早的.定义2.如果在一个调度中,早任务总是先于迟任务,则称该调度具有早任务优先形式.定义3.如果一个调度具有早任务优先形式而且按期 限单调递增顺序执行各任务,则称该调度具有 规范化形式.,任务调度的规范化第一步:将调度安排成早任务优先形式,即如果早 任务x跟在迟任务y之后,交换x和y的位置;第二步:如果任务i和j是早任务,而且分别完成于时 间k和k+1,djdi,交换i和j的位置.调度优先形式不改变任何任务的早或迟状态 调度规范形式不改变任何任务的早或迟状态,寻找最优调度问题成为寻找在该最优调度中的早任务集合A的问题.一旦A被确定后，就可以按期限单调递增序列出A中的所有元素,然后按任

32、意顺序列出迟任务(即S-A),定义4.任务集合A称为独立的如果存在一个关于 于A的调度,使得A中的任务皆非迟任务.,例.一个优化调度的早任务集合是独立 任务集合.,以下:用I表示所有独立任务集合的集族 用Nt(A)表示A中期限小于等于t的任务数,引理1.对于任何任务集合A,下边的命题等价:1.A是独立集合,2.对于t=1,2,n,Nt(A)t,3.如果按照期限递增顺序调度A中任务,则 A中无迟任务.证.12.如果Nt(A)t,则有多于t个任务需要在t时间 内完成,不存在使得A中无迟任务的调度.23.若A中任务依其期限递增排列,则2意味着 排序后,在时间t之前必须完成的A中任务 数至多为t.于是

33、,按期限递增顺序调度A中 任务,A无迟任务.31.显然.,定理1.若S是一个带期限的单位时间任务的集合,且I为 所有独立任务集构成的集族,则M=(S,I)是一个 Matroid.证明.1.S是非空有限集合.2.I是S的子集的非空集族,因为单个任务集属于I.3.遗传性:若AI,BA,则BI.4.交换性:设A,BI,|B|A|,k=max1tnt|Nt(B)Nt(A).于是,B中包含了比A中更多的具有期限k+1的任务.设 xB-A,x具有期限k+1.令A=Ax.往证A独立.对于1tk,Nt(A)=Nt(A)t,因为A是独立的.对于ktn,Nt(A)Nt(B)t,因为B是独立的.于是,A是独立的.,最后,任务调度问题转换为M=(S,I)上寻找最优子集问题，M的加权函数为W(罚款),