教学课件第五章GreedyAlgorithm

HITCS&E第五章第五章 Greedy AlgorithmGreedy Algorithm骆吉洲骆吉洲计算机科学与工程系计算机科学与工程系HITCS&E5.1 Elements of Greedy Elements of Greedy AlgorithmsAlgorithms 5.2 An activity-selection problemAn activity-selection problem5.3 Huffman codes Huffman codes 5.4 Theoretical foundations of Greedy Theoretical foundations of Greedy AlgorithmsAlgorithms5.5 A task-scheduling problemA task-scheduling problem5.6Minimal spanning tree problemMinimal spanning tree problem 5.7 Single-sourse shortest path problem Single-sourse shortest path problem提要提要HITCS&E参考资料参考资料IntroductiontoAlgorithmsl第第16章章:16.1,16.2,16.3,16.4,16.523.1,23.2计算机算法设计与分析计算机算法设计与分析l 第第4章章:4.1,4.2,4.4,4.5,4.6,4.8网站资料网站资料l 第五章第五章HITCS&E5.1 Elements of Greedy Elements of Greedy AlgorithmsAlgorithmsGreedyGreedy算法的基本概念算法的基本概念GreedyGreedy选择性选择性 优化子结构优化子结构与动态规划方法的比较与动态规划方法的比较 GreedyGreedy算法正确性证明方法算法正确性证明方法 HITCS&EGreedy算法的基本思想算法的基本思想求解最优化问题的算法包含一系列步骤求解最优化问题的算法包含一系列步骤每一步都有一组选择每一步都有一组选择作出在当前看来最好的选择作出在当前看来最好的选择希望通过作出局部优化选择达到全局优化选择希望通过作出局部优化选择达到全局优化选择Greedy算法不一定总产生优化解算法不一定总产生优化解Greedy算法是否产生优化解，需严格证明算法是否产生优化解，需严格证明Greedy算法产生优化解的条件算法产生优化解的条件Greedy-choice-propertyOptimalsubstructureGreedyGreedy算法的基本概念算法的基本概念HITCS&EGreedy选择性选择性 Greedy选择性选择性 若一个优化问题的全局优化解可以通过若一个优化问题的全局优化解可以通过 局部优化选择得到，则该问题称为具有局部优化选择得到，则该问题称为具有 Greedy选择性选择性.一一个个问问题题是是否否具具有有Greedy选选择择性性需需证明证明HITCS&E若一个优化问题的优化解包含它的若一个优化问题的优化解包含它的 子问题的优化解，则称其具有优化子问题的优化解，则称其具有优化 子结构子结构优化子结构优化子结构 HITCS&E与动态规划方法的比较与动态规划方法的比较动态规划方法可用的条件动态规划方法可用的条件优化子结构优化子结构子问题重叠性子问题重叠性子问题空间小子问题空间小Greedy方法可用的条件方法可用的条件优化子结构优化子结构Greedy选择性选择性可用可用Greedy方法时，动态规划方法可能不适用方法时，动态规划方法可能不适用可用动态规划方法时，可用动态规划方法时，Greedy方法可能不适用方法可能不适用HITCS&E证明算法所求解的问题具有优化子结构证明算法所求解的问题具有优化子结构证证明明算算法法所所求求解解的的问问题题具具有有Greedy选选择性择性证明算法确实按照证明算法确实按照Greedy选择性进行选择性进行局部优化选择局部优化选择GreedyGreedy算法正确性证明方法算法正确性证明方法HITCS&E5.2 An activity-selection problemAn activity-selection probleml问题的定义问题的定义l优化解的结构分析优化解的结构分析l算法设计算法设计l算法复杂性算法复杂性 l算法正确性证明算法正确性证明HITCS&E问题的定义问题的定义 活动活动 设设S=1,2,n是是n个活动的集合，各个活动使个活动的集合，各个活动使 用同一个资源，资源在同一时间只能为一个活用同一个资源，资源在同一时间只能为一个活动使用动使用 每个活动每个活动i有起始时间有起始时间si，终止时间终止时间fi，si fil l 相容活动相容活动l l 活动活动i和和j是相容的，若是相容的，若sj fi或或si fj，即即SifiSjfjSjfjSifiSiSjfifjHITCS&E问题定义问题定义输输入入：S=1,2,n，F=si，fi，n i 1输出输出：S的最大相容集合的最大相容集合 贪心思想贪心思想:为为了了选选择择最最多多的的相相容容活活动动，每每次次选选fi最最小小的的活活动动，使使我我们们能能够够选选更多的活动更多的活动 HITCS&E 引理引理1 1 设设S=1,2,n是是n个活动集合，个活动集合，si，fi 是活动是活动 的起始终止时间，且的起始终止时间，且f1 f2.fn，S的活动选的活动选 择问题的某个优化解包括活动择问题的某个优化解包括活动1.证证 设设A是一个优化解，按结束时间排序是一个优化解，按结束时间排序A中活动，中活动，设其第一个活动为设其第一个活动为k，第二个活动为第二个活动为j.如果如果k=1，引理成立引理成立.如果如果k 1，令令B=A-k1,由于由于A中活动相容，中活动相容，f1 fk sj,B中活动相容中活动相容.因为因为B=A,所以所以B是一个优化解，且包括活动是一个优化解，且包括活动1.优化解结构分析优化解结构分析HITCS&E引理引理2.2.设设S=1,2,n是是n个活动集合，个活动集合，si，fi是活动是活动i 的起始终止时间，且的起始终止时间，且f1 f2.fn，设设A是是S的调的调 度问题的一个优化解且包括活动度问题的一个优化解且包括活动1，则，则A=A-1 是是S=i S|si f1的调度问题的优化解的调度问题的优化解.证证.显然，显然，A中的活动是相容的中的活动是相容的.我们仅需要证明我们仅需要证明A 是最大的是最大的.设不然，存在一个设不然，存在一个S 的活动选择问题的优化解的活动选择问题的优化解 B，BA.令令B=1B.对于对于 i S,si f1,B中活动相容中活动相容.B是是S的一个解的一个解.由于由于|A|=|=|A|+1,B=B+1 A+1=A，与与A最最 大矛盾大矛盾.引理引理2 2说明活动选择问题具有优化子结构说明活动选择问题具有优化子结构HITCS&EGreedy选择性选择性引理引理3.3.设设 S=1,2,.,n 是是 n 个活动集合，个活动集合，f0=0=0,li 是是 Si=j S|sj fi-1 中具有最小结束时间中具有最小结束时间 fli 的活的活 动动.设设A是是S的包含活动的包含活动1的优化解的优化解,其中其中 f1 fn，则则A=证证.对对A作归纳法作归纳法.当当A=1时时,由引理由引理1，命题成立，命题成立.设设A k时，命题成立时，命题成立.当当A=k时时,由引理由引理2，A=1A1,A1是是 S2=j S|sj f1 的优化解的优化解.由归纳假设，由归纳假设，A1=.=.于是于是,A=.=.HITCS&E贪心思想贪心思想 为为了了选选择择最最多多的的相相容容活活动动，每每次次选选fi最最小小的的活活动动，使使我我们们能能够够选选更多的活动更多的活动 算法的设计算法的设计HITCS&E算法算法 （设设f f1 1 f f2 2.f fn n已排序）已排序）Greedy-Activity-Selector(S,F)nlenyth(S);A1j1Fori2TonDoIfsi fjThenAAi；ji；ReturnAHITCS&E 如果结束时间已排序如果结束时间已排序 T(n)=(n)如果如果 结束时间未排序结束时间未排序 T(n)=(n)+(nlogn)=(nlogn)复杂性设计复杂性设计HITCS&E需要证明需要证明活动选择问题具有活动选择问题具有Greedy选择性选择性活动选择问题具有优化子结构活动选择问题具有优化子结构算法按照算法按照Greedy选择性计算解选择性计算解算法正确性证明算法正确性证明HITCS&E定理定理.Greedy-Activity-Selector算法能够产算法能够产 生最优解生最优解.证证.Greedy-Activity-Selector算法按照引算法按照引 理理3的的Greedy选择性进行局部优化选选择性进行局部优化选 择择.HITCS&E5.3Huffmancodes l问题的定义问题的定义l优化解的结构分析优化解的结构分析l算法设计算法设计l算法复杂性分析算法复杂性分析 l算法正确性证明算法正确性证明HITCS&E二进制字符编码二进制字符编码每个字符用一个二进制每个字符用一个二进制0、1串来表示串来表示.固定长编码固定长编码每个字符都用相同长的每个字符都用相同长的0、1串表示串表示.可变长编码可变长编码经常出现的字符用短码，不经常出现的用长码经常出现的字符用短码，不经常出现的用长码前缀编码前缀编码无任何字符的编码是另一个字符编码的前缀无任何字符的编码是另一个字符编码的前缀问题的定义问题的定义HITCS&E编码树编码树叶结点叶结点叶结点叶结点:用字符及用字符及用字符及用字符及其出现频率标记其出现频率标记其出现频率标记其出现频率标记内结点内结点内结点内结点:用其用其用其用其子树的叶结点子树的叶结点子树的叶结点子树的叶结点的频率和标记的频率和标记的频率和标记的频率和标记边标记边标记边标记边标记:左边标记左边标记左边标记左边标记0 0 0 0，右侧边标记，右侧边标记，右侧边标记，右侧边标记1 1 1 1100100a:45a:45555530302525c:12c:12b:13b:131414d:16d:16e:9e:9f:5f:50 00 00 00 00 01 11 11 11 11 1HITCS&E编码树编码树T的代价的代价设设C是字母表是字母表,c Cf(c)是是c在文件中出现的频率在文件中出现的频率dT(c)是叶子是叶子c在树在树T中的深度，即中的深度，即c的编码长度的编码长度T的代价是编码一个文件的所有字符的代码位数的代价是编码一个文件的所有字符的代码位数:B(T)=B(T)=HITCS&E优化编码树问题优化编码树问题输入输入:字母表字母表 C=c1,c2,.,cn，频率表频率表 F=f(c1),f(c2),.,f(cn)输出输出:具有最小具有最小B(T)的的C前缀编码树前缀编码树 贪心思想贪心思想：循环地选择具有最低频率的两个结点，循环地选择具有最低频率的两个结点，生成一棵子树，直至形成树生成一棵子树，直至形成树HITCS&E我们需要证明我们需要证明优化前缀树问题具有优化子结构优化前缀树问题具有优化子结构优化前缀树问题具有优化前缀树问题具有Greedy选择性选择性优化解的结构分析优化解的结构分析HITCS&E优化子结构优化子结构引理引理1.1.设设T是字母表是字母表C的优化前缀树，的优化前缀树，c C，f(c)是是c在文件中出现的频率在文件中出现的频率.设设x、y是是T中任意中任意 两个相邻叶结点，两个相邻叶结点，z是它们的父结点，则是它们的父结点，则z作作 为频率是为频率是f(z)=f(x)+f(y)的字符，的字符，T=T-x,y是是 字母表字母表C=C-x,yz的优化前缀编码树的优化前缀编码树.b bc cz zT0 00 01 11 1f(c)f(c)f(b)f(b)f(x)+f(y)f(x)+f(y)b bc cx xy yT0 00 00 01 11 11 1f(x)f(x)f(c)f(c)f(y)f(y)f(b)f(b)z zHITCS&E证证证证.往证往证往证往证B(T)=B(T)+f(x)+f(y).B(T)=B(T)+f(x)+f(y).v v C-x,y,dC-x,y,dT T(v)=d(v)=dTT(v),f(v)d(v),f(v)dT T(v)=f(v)d(v)=f(v)dTT(v).(v).由于由于由于由于 d dT T(x)=d(x)=dT T(y)=d(y)=dTT(z)+1,(z)+1,f(x)d f(x)dT T(x)+f(y)d(x)+f(y)dT T(y)(y)=(f(x)+f(y)(d =(f(x)+f(y)(dTT(z)+1)(z)+1)=(f(x)+f(y)d=(f(x)+f(y)dTT(z)+(f(x)+f(y)(z)+(f(x)+f(y)由由由由于于于于 f(x)+f(y)=f(z)f(x)+f(y)=f(z),f(x)df(x)dT T(x)+f(y)d(x)+f(y)dT T(y)=f(z)d(y)=f(z)dTT(z)+(f(x)+f(y).(z)+(f(x)+f(y).于是于是于是于是B(T)=B(T)+f(x)+f(y).B(T)=B(T)+f(x)+f(y).若若若若TT不不不不是是是是CC的优化前缀编码树，的优化前缀编码树，的优化前缀编码树，的优化前缀编码树，则必存在则必存在则必存在则必存在TT，使使使使B(T)B(T).B(T)B(T).因为因为因为因为z z是是是是CC中字符，它必为中字符，它必为中字符，它必为中字符，它必为TT中的叶子中的叶子中的叶子中的叶子.把结点把结点把结点把结点x x与与与与y y加入加入加入加入TT，作为作为作为作为z z的子结点，的子结点，的子结点，的子结点，则得到则得到则得到则得到C C的一个如下前缀编码树的一个如下前缀编码树的一个如下前缀编码树的一个如下前缀编码树TT：b bc cz zT0 00 01 11 1f(c)f(c)f(b)f(b)f(x)+f(y)f(x)+f(y)u uv vT0 00 01 11 1f(v)f(v)f(u)f(u)z zf(z)f(z)HITCS&ET代价为：代价为：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的优化编码树的优化编码树.u uv vx xy yT0 00 00 01 11 11 1f(x)f(x)f(v)f(v)f(y)f(y)f(u)f(u)z zu uv vT0 00 01 11 1f(v)f(v)f(u)f(u)z zf(z)f(z)HITCS&EGreedy选择性选择性引理引理2.2.设设C是字母表，是字母表，c C，c具有频率具有频率f(c),x、y 是是C中具有最小频率的两个字符，则存在一中具有最小频率的两个字符，则存在一 个个C的优化前缀树，的优化前缀树，x与与y的编码具有相同长的编码具有相同长 度，且仅在最末一位不同度，且仅在最末一位不同.HITCS&E不失一般性，设不失一般性，设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是具有最大深度的是具有最大深度的 两个兄弟字符两个兄弟字符:x xy yb bc cTHITCS&Eb by yx xc cT交换交换y和和c构造构造T b bc cx xy yTHITCS&E往证往证T 是最优化前缀树是最优化前缀树.B(T)-B(T B(T)-B(T )=f(x)d=f(x)dT T(x)+f(b)d(x)+f(b)dT T(b)-f(x)d(b)-f(x)dTT(x)-f(b)d(x)-f(b)dTT(b)(b)=f(x)d=f(x)dT T(x)+f(b)d(x)+f(b)dT T(b)-f(x)d(b)-f(x)dT T(b)-f(b)d(b)-f(b)dT T(x)(x)=(f(b)-f(x)(d=(f(b)-f(x)(dT T(b)-d(b)-dT T(x).(x).f(b)f(b)f(x),df(x),dT T(b)(b)d dT T(x)(x)(因为因为b的深度最大的深度最大)B(T)-B(T)B(T)-B(T)0,B(T)0,B(T)B(T)B(T)同理可证同理可证B(T)B(T)B(T)B(T).于是于是B(T)B(T)B(T).B(T).由于由于T T是最优化的，所以是最优化的，所以B(T)B(T)B(T).B(T).于是于是,B(T)=B(T)B(T)=B(T)，TT是是C C的最优化前缀编码树的最优化前缀编码树.在在TT中中,x和和y具有相同长度编码具有相同长度编码,且仅最后一位不同且仅最后一位不同.HITCS&E基本思想基本思想循循环环地地选选择择具具有有最最低低频频率率的的两两个个结结点点，生生成成一一棵子树，直至形成树棵子树，直至形成树初始初始:f:5,e:9,c:12,b:13,d:16,a:45 算法的设计算法的设计HITCS&EHITCS&EGreedy算法算法(使用堆操作实现使用堆操作实现)Huffman(C，F)1.nC;2.QC;/*用用BUILD-HEAP建立堆建立堆*/3.FORi1Ton-1Do4.zAllocate-Node();5.xleftzExtract-MIN(Q);/*堆操作堆操作*/6.yrightzExtract-MIN(Q);/*堆操作堆操作*/7.f(z)f(x)+f(y);8.Insert(Q,z);/*堆操作堆操作*/9.ReturnHITCS&E设设Q由一个堆实现由一个堆实现第第2步用堆排序的步用堆排序的BUILD-HEAP实现实现:O(n)每个堆操作要求每个堆操作要求O(logn)，循环循环n-1次次:O(nlogn)T(n)=0(n)+0(nlogn)=0(nlogn)复杂性分析复杂性分析HITCS&E 定理定理.Huffman算法产生一个优化前缀编码树算法产生一个优化前缀编码树 证证.由于引理由于引理1、引理、引理2成立成立,而且而且Huffman算算 法按照引理法按照引理2的的Greedy选择性确定的规选择性确定的规 则进行局部优化选择，所以则进行局部优化选择，所以Huffman算算 法产生一个优化前缀编码树。法产生一个优化前缀编码树。正确性证明正确性证明HITCS&E5.4Minimal spanning tree problemMinimal spanning tree problem 问题的定义问题的定义 优化解结构分析优化解结构分析 Greedy选择性选择性 Kruskal算法算法 算法复杂性算法复杂性 算法正确性证明算法正确性证明HITCS&E问题的定义问题的定义生成树生成树 设设G=(V,E)是一个边加权无向连通图是一个边加权无向连通图.G的生成的生成树是无向树树是无向树S=(V,T),T E,以下用以下用T表示表示S.如果如果W:E实数实数 是是G的的权函数权函数,T的权值定的权值定义为义为W(T)=(u,v)TW(u,v).最小生成树最小生成树l l G的最小生成树是的最小生成树是W(T)最小的最小的G之生成树之生成树.l l问题的定义问题的定义输入输入:无向连通图无向连通图G=(V,E),权函数权函数W输出输出:G的最小生成树的最小生成树HITCS&E实例实例B BC CA AE ED D707060608080505090907575300300200200B BC CA AE ED D707050509090300300B BC CA AE ED D707080805050300300B BC CA AE ED D7070606080805050HITCS&E算法思想算法思想B BC CA AE ED D707060608080505090907575300300200200B BC CA AE ED D7070606080805050HITCS&E定理定理1.设设T是是G的最小生成树的最小生成树.如果如果T包含子树包含子树T1和和T2,T1是是G的子连通图的子连通图G1的生成树，的生成树，T2是是G 的子连通图的子连通图G2的生成树，则的生成树，则T1是是G1的最小的最小生成树，生成树，T2是是G2的最小生成树的最小生成树.证证.优化解的结构分析优化解的结构分析uvT1T2THITCS&EGreedy选择性选择性 一般算法一般算法初始初始:A为空集合为空集合反复扩展边集合反复扩展边集合A,直至直至A成为最小生成树成为最小生成树 循环不变命题循环不变命题每次循环算法要保持下边循环不变命题为真每次循环算法要保持下边循环不变命题为真“在每次循环前，在每次循环前，A必是某个最小生成树的子集必是某个最小生成树的子集”在每次循环中在每次循环中,如果如果A(u,v)是是某个最小生成树某个最小生成树 的子集，则称边的子集，则称边(u,v)是是安全边安全边HITCS&E一般算法的定义一般算法的定义Generic-MST(G,W)1.A=;/*不变命题真不变命题真*/2.WhileA不是生成树不是生成树Do/*不变命题真不变命题真 */3.寻找一个安全边寻找一个安全边(u,v);4.A=A(u,v);5.ReturnA /*不变命题真不变命题真 */算法的关键是第三步算法的关键是第三步,寻找安全边寻找安全边(u,v)HITCS&E寻找安全边的规则寻找安全边的规则定义定义1.无向图无向图G=(V,E)的一个的一个划分划分是是V的一个划分的一个划分(S,V-S).定义定义2.如果如果u S,v V-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)的权值最小的权值最小.HITCS&E示例示例defgcihabSV-S7 78 811118 81414红结点集合是红结点集合是S浅蓝结点集合是浅蓝结点集合是V-S 蓝边是交叉边蓝边是交叉边,权为权为7的边是轻边的边是轻边红边集合是受尊重的边集合红边集合是受尊重的边集合HITCS&E定理定理1.设设G=(V,E)是具有边加权函数是具有边加权函数W的无向连通图的无向连通图,A E是包含在是包含在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)安全安全.HITCS&E由于由于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是最小生成树是最小生成树.因为因为(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=红边集合红边集合yxuvTpyxuvTpHITCS&E推论推论1.设设G=(V,E)是具有边加权函数是具有边加权函数W的无向连通图的无向连通图,A E是包含在是包含在G的某个最小生成树中的边集的某个最小生成树中的边集合合,C=(VC,EC)是森林是森林GA=(V,A)中的树中的树.如果如果(u,v)是连接是连接C和和GA中另一个树的交叉中另一个树的交叉轻轻边边,则则(u,v)对对A是安全的是安全的.证证.划分划分(VC,V-VC)尊重尊重A.(u,v)关于这个划分的交叉轻边关于这个划分的交叉轻边.于是于是,(u,v)对对A是安全的是安全的.HITCS&EKruskal算法算法MST-Kruskal(G,W)1.A=;2.For v VGDo3.Make-Set(v);/*4.按照按照W值的递增顺序排序值的递增顺序排序EG;5.For(u,v)EG(按按W值的递增顺序值的递增顺序)Do6.IfFind-Set(u)Find-Set(v)7.ThenA=A(u,v);Union(u,v);8.ReturnAHITCS&E算法复杂性算法复杂性令令n=|V|,m=|E|第第4步需要时间步需要时间:O(mlogm)第第2-3步执行步执行O(n)个个Make-Set操作操作 第第5-8步执行步执行 (n)个个Find-Set和和Union操作操作 每个每个Find-Set和和Union操作操作O(n)m n-1(因为因为G连通连通),(n)=O(logn)=O(logm)总时间复杂性总时间复杂性：O(mlogm)HITCS&E算法正确性算法正确性定理定理2.MST-Kruskal(G,W)算法能够产生图算法能够产生图G的最小生成树的最小生成树.证证.因为算法按照因为算法按照Greedy选择性进行局选择性进行局部优化选择部优化选择.HITCS&E5.5 Theoretical foundations of Theoretical foundations of GreedyGreedy AlgorithmsAlgorithmsl lMatroid(拟阵拟阵)l lMatroid实例实例l lMatroid的性质的性质 l l加权加权Matroid上的上的Greedy算法算法l l任务调度问题任务调度问题 HITCS&EMatroid定义定义 Matroid是一个序对是一个序对M=(S,I)，满足：满足：(1)S是一个有限非空集合是一个有限非空集合.(2)I是非空的是非空的S子集的集族，子集的集族，I中的子集称为中的子集称为 S的独立子集族的独立子集族.(3)遗传性遗传性:如果如果A I，B A，则则B I (4)交换性交换性:如果如果A I，B I，A B，则则 x B-A使得使得A x I.Matroid (拟阵拟阵)HITCS&E实例实例(GraphicMatroid)定义定义1 1.设设 G=(V，E)是一个无向图，由是一个无向图，由 G 确定的确定的 MG=(SG，IG)定义如下定义如下:SG是是G的边集合的边集合E，IG=A|A E,(V,A)是森林是森林.定理定理1.1.如果如果G是一个无向图，则是一个无向图，则MG=(SG，IG)是一是一 个个Matroid.证证.SG=E是一个有限集合是一个有限集合.e E,(V,e)是一个森林，是一个森林，e IG.于是，于是，IG是是SG的非空集族的非空集族.HITCS&E MG满足遗传性满足遗传性:如果如果B IG，A B，则则(V,A)是一个是一个 森林森林.于是，于是，A IG，MG满足遗传性满足遗传性.MG满足交换性满足交换性:设设A IG,B IG,|A|B|.如果如果B的任意一条边都包含在的任意一条边都包含在A的同一棵树中，则的同一棵树中，则B的边数不大于的边数不大于A的边数，与的边数，与|A|B|矛盾矛盾.于是，于是，B必包含一条边必包含一条边(u,v)，(u,v)在在A的不相同树中的不相同树中.(u,v)B-A连接连接A的两棵不同树的两棵不同树.(V,A(u,v)是森林，是森林，A(u,v)IG.于是于是,MG满足交换性满足交换性.HITCS&EMatroid的性质的性质定定义义2.设设M=(S,I)是是一一个个Matroid,A I.如如果果A x I,x A,x称为称为A的一个的一个extension.定义定义3.设设M=(S,I)是是Matroid,A I.若若A没有没有extension,则称则称A为最大独立子集合为最大独立子集合.定理定理2.一个一个Matroid的所有最大独立子集合都具有相的所有最大独立子集合都具有相同大小同大小.证证.设设A是是MatroidM的最大独立子集合，而且存的最大独立子集合，而且存在在M的另一个独立子集合的另一个独立子集合B,|A|maxmaxW(e)W(e)e e E E，W(e)0W(e)0.WW扩展为扩展为扩展为扩展为W(A)=W(A)=V V WW0 0-W(A)-W(A)，A A E EMMG G的最优子集的最优子集的最优子集的最优子集A A满足：满足：满足：满足：(V,AV,A)是森林是森林是森林是森林 W(A)W(A)最大最大最大最大，即即即即W(A)W(A)最小最小最小最小.最小生成森林问题可以由求最小生成森林问题可以由求最小生成森林问题可以由求最小生成森林问题可以由求MMG G的最优子集的算法来求解的最优子集的算法来求解的最优子集的算法来求解的最优子集的算法来求解 HITCS&E加权加权Matroid优化子集问题的定义优化子集问题的定义输入：输入：MatroidM=(S,I),M的加权函数的加权函数W输出：输出：M的最优子集的最优子集HITCS&E算法算法 Greedy(M,W)1A=;2按权按权W值大小排序值大小排序S;3For x S（按按W(x)递减顺序）递减顺序）DO4IfA x I/*选择目前选择目前W(x)最大的最大的x */5ThenA x;6ReturnA.时间复杂性时间复杂性step2:O(slogs)step4:O(f(s)T(s)=O(slogs+sf(s)HITCS&E算法正确性算法正确性引理引理1 1.Greedy算法总是返回一个独立子集合算法总是返回一个独立子集合.证证.设设Greedy返回集合返回集合A，对对A 做数学归纳法做数学归纳法.当当A=0时时,A是空集是空集,由遗传性由遗传性,A是独立子集合是独立子集合.设设A k时时,A是独立子集是独立子集.当当A=k+1时时,A由第由第4-5步得到步得到,即即A=A x.第第4步步已已判判定定A x I，A=A x是是独独立立子子集集.我们需要证明我们需要证明A是最优子集，即证明是最优子集，即证明加权加权Matroid最优子集问题具有最优子集问题具有Greedy选择性选择性加权加权Matroid最优子集问题具有优化子结构最优子集问题具有优化子结构算法按照优化子结构和选择规则选择最优子集算法按照优化子结构和选择规则选择最优子集HITCS&EGreedy选择性选择性 引理引理2 2.设设M=(S,I)是一个加权是一个加权Matroid,W是是M的权函数的权函数,S 按按W值递减排序值递减排序.若若S中满足中满足x I的的第一个元素第一个元素x,则存在一个则存在一个M的优化子集的优化子集A,x A.证证.设设S第一个元素第一个元素x满足满足x I.若存在优化子集若存在优化子集A包含包含x，则引理得证则引理得证.否则否则,设设B是任意非空优化子集是任意非空优化子集,x B.显然显然,y B，W(x)W(y).如下构造含如下构造含x的优化子集的优化子集A:初始初始:A=x I;用交换性用交换性:y y B-AB-A,若若若若A A y y I I,A A=A A y y,直至直至直至直至 A A=B B.显然，显然，z B,A=(B-z)x.于是于是,W(A)=W(B)-W(y)+W(x)W(B).因为因为B是优化子集是优化子集,所以所以W(A)W(B),W(A)=W(B).A是优化子集是优化子集,且且x A.HITCS&E引理引理3.3.设设M=(S,I)是一个是一个Matroid.如果如果x S不是空集不是空集 的的extension,则则x不是任何独立子集的不是任何独立子集的extension.证证.反证反证.设设x S是独立子集是独立子集A的的extension但不是但不是 的的extension.由于由于x是是A的的extension,A x I.由由M的遗传性，的遗传性，x I,即即x是是 的的extension,矛盾矛盾.推论推论1.1.任何元素一旦不能被选中任何元素一旦不能被选中,则永远不会被选中则永远不会被选中.推论推论2.2.Greedy算法不会由于不再考虑未被初始选中的元算法不会由于不再考虑未被初始选中的元素而产生错误素而产生错误.HITCS&E优化子结构优化子结构引理引理4.4.设设x是第一个被是第一个被Greedy算法选中的元素算法选中的元素.包含包含x的优化子集的优化子集A包含子问题包含子问题M=(S,I)的优化的优化子集子集A=A-x,M=(S,I)定义如下定义如下:S=y Sx,y I,I=B S-x B x I而且而且M的权函数与的权函数与M的权函数相同的权函数相同.证证.若若A是是M的优化子集且的优化子集且x A,则则A=A-x A.因为因为A=A x I,所以所以A=A-x I.若若A不是不是M的优化子集的优化子集,则存在则存在M的一个优的一个优化子集化子集B使得使得W(B)W(A).由于由于B x I,W(A)=W(A)+W(x),W(B x)=W(B)+W(x)W(A)+W(x)=W(A),与与W(A)优化矛盾优化矛盾.HITCS&El算法正确性算法正确性定理定理1.1.设设M=(S,I)是一个是一个Matroid,W是是M的权函数的权函数,Greedy(M,W)返回一个返回一个M的优化子集的优化子集.证证.引理引理3说明说明,任何没有被任何没有被Greedy选中的选中的S元素元素,以以后不会被选中，可以不再考虑后不会被选中，可以不再考虑.一旦一旦S的第一个的第一个x被选中被选中,x可以加到可以加到A,因为引理因为引理2说明存在一个包含说明存在一个包含x的优化子集的优化子集.引理引理4意味着余下的问题是在意味着余下的问题是在M中求解最优子中求解最优子集的问题集的问题.Greedy算法是按照上述三个规则工作的，算法是按照上述三个规则工作的，所以所以Greedy(M,W)返回一个返回一个M的优化子集的优化子集.HITCS&E5.6Atask-schedulingproblemHITCS&E单位时间任务单位时间任务 需要一个单位时间就能够完成的任务需要一个单位时间就能够完成的任务单位时间任务的调度问题单位时间任务的调度问题 输入：输入：输入：输入：单位时间任务集单位时间任务集单位时间任务集单位时间任务集S S=1,2,n1,2,n 正整数任务期限正整数任务期限正整数任务期限正整数任务期限D D=d d1 1,d,d2 2,d,dn n,任务任务任务任务i i须在须在须在须在d di i前完成前完成前完成前完成非负权集非负权集非负权集非负权集WW=w w1 1,w,w2 2,w,wn n,任务任务任务任务i i不在不在不在不在d di i前完成罚款前完成罚款前完成罚款前完成罚款w wi i 输出：输出：输出：输出：S S的一个调度的一个调度的一个调度的一个调度(S S的一个执行顺序的一个执行顺序的一个执行顺序的一个执行顺序),),具有最小总罚款具有最小总罚款具有最小总罚款具有最小总罚款问题定义问题定义HITCS&E转换为加权转换为加权Matroid的优化子集问题的优化子集问题定义定义1.1.设设S是一个任务调度是一个任务调度.一个任务在一个任务在S中中是迟的是迟的如如 果它在规定的期限之后完成果它在规定的期限之后完成;否则否则是早的是早的.定义定义2.2.如果在一个调度中如果在一个调度中,早任务总是先于迟任务早任务总是先于迟任务,则称该调度具有则称该调度具有早任务优先形式早任务优先形式.定义定义3.3.如果一个调度具有早任务优先形式而且按期如果一个调度具有早任务优先形式而且按期 限单调递增顺序执行各任务限单调递增顺序执行各任务,则称该调度具有则称该调度具有 规范化形式规范化形式.HITCS&E 任务调度的规范化任务调度的规范化第一步第一步:将调度安排成早任务优先形式将调度安排成早任务优先形式,即如果早即如果早 任务任务x跟在迟任务跟在迟任务y之后之后,交换交换x和和y的位置的位置;第二步第二步:如果任务如果任务i和和j是早任务是早任务,而且分别完成于时而且分别完成于时间间k和和k+1,djt,则有多于则有多于t个任务需要在个任务需要在t时间时间内完成内完成,不存在使得不存在使得A中无迟任务的调度中无迟任务的调度.23.若若A中任务依其期限递增排列中任务依其期限递增排列,则则2意味着意味着排序后排序后,在在时间时间t之前必须完成的之前必须完成的A中任务中任务数至多为数至多为t.于是于是,按按期限递增顺序调度期限递增顺序调度A中中任务任务,A无迟任务无迟任务.31.显然显然.HITCS&E定理定理1.若若S是一个带期限的单位时间任务的集合是一个带期限的单位时间任务的集合,且且I为为所有独立任务集构成的集族所有独立任务集构成的集族,则则M=(S,I)是一个是一个Matroid.证明证明证明证明.1.1.S S是非空有限集合是非空有限集合是非空有限集合是非空有限集合.2.2.I I是是是是S S的子集的非空集族的子集的非空集族的子集的非空集族的子集的非空集族,因为单个任务集属于因为单个任务集属于因为单个任务集属于因为单个任务集属于I I.3.3.遗传性遗传性遗传性遗传性:若若若若A A I I,B B A A,则则则则B B I I.4.4.交换性交换性交换性交换性:设设设设A,BA,B I I,|,|B B|A A|,|,k=k=maxmax1 1 t t n n t|t|N Nt t(B B)N Nt t(A A).).于是于是于是于是,B B中包含了比中包含了比中包含了比中包含了比A A中更多的具有期限中更多的具有期限中更多的具有期限中更多的具有期限k+1k+1的任务的任务的任务的任务.设设设设x x B-AB-A,x x具有期限具有期限具有期限具有期限k+1k+1.令令令令AA=A A x x.往证往证往证往证AA独立独立独立独立.对于对于对于对于1 1 t t k k,N Nt t(AA)=)=N Nt t(A A)t t,因为因为因为因为A A是独立的是独立的是独立的是独立的.对于对于对于对于k k t t n n,N Nt t(AA)N Nt t(B B)t t,因为因为因为因为B B是独立的是独立的是独立的是独立的.于是于是于是于是,AA是独立的是独立的是独立的是独立的.k kN Nj j(B B)N Nj j(A A)N Nt t(B)(B)N Nt t(A)(A)HITCS&E 最后最后,任务调度问题转换为任务调度问题转换为M=(S,I)上寻找上寻找最优子集问题，最优子集问题，M的加权函数为的加权函数为W(罚款罚款)HITCS&EHITCS&E