第五章GreedyAlgorithm精品PPT课件.ppt

第五章第五章 Greedy AlgorithmGreedy Algorithm邹权（博士）邹权（博士）计算机科学系计算机科学系5.1 Elements of Greedy Elements of Greedy AlgorithmsAlgorithms 5.2 An activity-selection problemAn activity-selection problem5.3  Huffman codes Huffman codes 5.4  Minimal spanning tree problemMinimal spanning tree problem 提要提要 5.1 Elements of Greedy Elements of Greedy AlgorithmsAlgorithms•GreedyGreedy算法的基本概念算法的基本概念•GreedyGreedy选择性选择性 •优化子结构优化子结构•与动态规划方法的比较与动态规划方法的比较 •GreedyGreedy算法正确性证明方法算法正确性证明方法 4OptimalLocal Optimal•Greedy算法的基本思想算法的基本思想–求解最优化问题的算法包含一系列步骤求解最优化问题的算法包含一系列步骤–每一步都有一组选择每一步都有一组选择–作出在当前看来最好的选择作出在当前看来最好的选择–希望通过作出局部优化选择达到全局优化选择希望通过作出局部优化选择达到全局优化选择–Greedy算法不一定总产生优化解算法不一定总产生优化解–Greedy算法是否产生优化解，需严格证明算法是否产生优化解，需严格证明•Greedy算法产生优化解的条件算法产生优化解的条件–Greedy-choice-property–Optimal substructure  GreedyGreedy算法的基本概念算法的基本概念Greedy选择性选择性 •Greedy选择性选择性 若一个优化问题的全局优化解可以通过若一个优化问题的全局优化解可以通过 局部优化选择得到，则该问题称为具有局部优化选择得到，则该问题称为具有 Greedy选择性选择性. .•一一个个问问题题是是否否具具有有Greedy选选择择性性需需证明证明  若一个优化问题的优化解包含它的若一个优化问题的优化解包含它的 子问题的优化解，则称其具有优化子问题的优化解，则称其具有优化 子结构子结构优化子结构优化子结构 与动态规划方法的比较与动态规划方法的比较•动态规划方法可用的条件动态规划方法可用的条件–优化子结构优化子结构–子问题重叠性子问题重叠性–子问题空间小子问题空间小•Greedy方法可用的条件方法可用的条件–优化子结构优化子结构–Greedy选择性选择性•可用可用Greedy方法时，动态规划方法可能不适用方法时，动态规划方法可能不适用•可用动态规划方法时，可用动态规划方法时，Greedy方法可能不适用方法可能不适用•证明算法所求解的问题具有优化子结构证明算法所求解的问题具有优化子结构•证证明明算算法法所所求求解解的的问问题题具具有有Greedy选选择性择性•证明算法确实按照证明算法确实按照Greedy选择性进行选择性进行局部优化选择局部优化选择GreedyGreedy算法正确性证明方法算法正确性证明方法5.2  An activity-selection problemAn activity-selection probleml问题的定义问题的定义l优化解的结构分析优化解的结构分析l算法设计算法设计l算法复杂性算法复杂性 l算法正确性证明算法正确性证明问题的定义问题的定义• 活动活动• 设设S={1,2,…,n}是是n个活动的集合，各个活动使个活动的集合，各个活动使 用同一个资源，资源在同一时间只能为一个活用同一个资源，资源在同一时间只能为一个活动使用动使用• 每个活动每个活动i有起始时间有起始时间si，，终止时间终止时间fi，，si  fil l 相容活动相容活动l l 活动活动i和和j是相容的，若是相容的，若sj fi或或si fj，，即即SifiSjfjSjfjSifiSiSjfifj•问题定义问题定义–输输入入：：S={1, 2, …, n}，，F={  [si，，fi]  }，，n i 1–输出输出：：S的最大相容集合的最大相容集合 贪心思想贪心思想: 为为了了选选择择最最多多的的相相容容活活动动，，每每次次选选fi最最小小的的活活动动，，使使我我们们能能够够选选更多的活动更多的活动  引理引理1 1 设设S={1,2,…,n}是是n个活动集合，个活动集合，[si，，fi ]是活动是活动 的起始终止时间，且的起始终止时间，且f1 f2 …. fn，，S的活动选的活动选 择问题的某个优化解包括活动择问题的某个优化解包括活动1. 证证 设设A是一个优化解，按结束时间排序是一个优化解，按结束时间排序A中活动，中活动， 设其第一个活动为设其第一个活动为k，，第二个活动为第二个活动为j. . 如果如果k=1，，引理成立引理成立. . 如果如果k 1，，令令B=A-{k}∪∪{1}, 由于由于A中活动相容，中活动相容，f1 fk   sj , B中活动相容中活动相容. . 因为因为B=A, 所以所以B是一个优化解，且包括活动是一个优化解，且包括活动1. .优化解结构分析优化解结构分析引理引理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’，，B’>A’. . 令令B={1}∪∪B’. . 对于对于 i S’, si  f1, B中活动相容中活动相容. . B是是S的一个解的一个解.  由于由于| |A|=||=|A’| |+1, , B= =B’+1> > A’ +1= = A ，，与与A最最 大矛盾大矛盾. . 引理引理2 2说明活动选择问题具有优化子结构说明活动选择问题具有优化子结构•Greedy选择性选择性引理引理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<

法产生一个优化前缀编码树 正确性证明正确性证明5.4  Minimal spanning tree problemMinimal spanning tree problem •问题的定义问题的定义 •优化解结构分析优化解结构分析• Greedy选择性选择性• Kruskal算法算法• 算法复杂性算法复杂性• 算法正确性证明算法正确性证明问题的定义问题的定义•生成树生成树• 设设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的最小生成树的最小生成树•实例实例B BC CA AE ED D707060608080505090907575300300200200B BC CA AE ED D707050509090300300B BC CA AE ED D707080805050300300B BC CA AE ED D7070606080805050•算法思想算法思想B BC CA AE ED D707060608080505090907575300300200200B BC CA AE ED D7070606080805050定理定理1. 设设T是是G的最小生成树的最小生成树. 如果如果T包含子树包含子树T1和和             T2, T1是是G的子连通图的子连通图G1的生成树，的生成树，T2是是G 的子连通图的子连通图G2的生成树，则的生成树，则T1是是G1的最小的最小            生成树，生成树，T2是是G2的最小生成树的最小生成树.证证.优化解的结构分析优化解的结构分析uvT1T2TGreedy选择性选择性• 一般算法一般算法• 初始初始: A为空集合为空集合• 反复扩展边集合反复扩展边集合A, 直至直至A成为最小生成树成为最小生成树• 循环不变命题循环不变命题•每次循环算法要保持下边循环不变命题为真每次循环算法要保持下边循环不变命题为真“在每次循环前，在每次循环前，A必是某个最小生成树的子集必是某个最小生成树的子集”• 在每次循环中在每次循环中, 如果如果A {(u, v)} }是是某个最小生成树某个最小生成树 的子集，则称边的子集，则称边(u, v)是是安全边安全边•一般算法的定义一般算法的定义Generic-MST(G, W)1.  A= ;        /*  不变命题真不变命题真  */2.While  A 不是生成树不是生成树   Do        /* 不变命题真不变命题真 */3.       寻找一个安全边寻找一个安全边(u, v);4.        A=A { (u, v) };     5. Return A /* 不变命题真不变命题真 */算法的关键是第三步算法的关键是第三步, 寻找安全边寻找安全边(u, v)•寻找安全边的规则寻找安全边的规则定义定义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)的权值最小的权值最小.•示例示例defgcihabSV-S7 78 811118 81414• 红结点集合是红结点集合是S• 浅蓝结点集合是浅蓝结点集合是V-S• 蓝边是交叉边蓝边是交叉边, 权为权为7的边是轻边的边是轻边• 红边集合是受尊重的边集合红边集合是受尊重的边集合定理定理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)安全安全. 由于由于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=红边集合红边集合yxuvTpyxuvT’pKruskal算法算法MST-Kruskal(G,W)1.   A= ;2.   For   v V[G]   Do3.       Make-Set(v);   /* 4. 按照按照W值的递增顺序排序值的递增顺序排序E[G];5. For  (u, v) E[G] (按按W值的递增顺序值的递增顺序)   Do6.       If   Find-Set(u) Find-Set(v)7.       Then  A=A {(u, v)};  Union(u, v);8. 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)• m n-1(因为因为G连通连通),  (n)=O(logn)=O(logm)•总时间复杂性总时间复杂性：：O(mlogm)算法正确性算法正确性定理定理2. MST-Kruskal(G,W)算法能够产生图算法能够产生图            G的最小生成树的最小生成树.      证证. 因为算法按照因为算法按照Greedy选择性进行局选择性进行局            部优化选择部优化选择. 。