第五章GreedyAlgorithm--精品PPT课件.ppt

第五章 Greedy Algorithm,邹权（博士） 计算机科学系,5.1 Elements of Greedy Algorithms 5.2 An activity-selection problem 5.3 Huffman codes 5.4 Minimal spanning tree problem,提要,5.1 Elements of Greedy Algorithms,Greedy算法的基本概念 Greedy选择性 优化子结构 与动态规划方法的比较 Greedy算法正确性证明方法,4,Optimal,Local Optimal,Greedy算法的基本思想 求解最优化问题的算法包含一系列步骤 每一步都有一组选择 作出在当前看来最好的选择 希望通过作出局部优化选择达到全局优化选择 Greedy算法不一定总产生优化解 Greedy算法是否产生优化解，需严格证明 Greedy算法产生优化解的条件 Greedy-choice-property Optimal substructure,Greedy算法的基本概念,Greedy选择性,Greedy选择性 若一个优化问题的全局优化解可以通过 局部优化选择得到，则该问题称为具有 Greedy选择性. 一个问题是否具有Greedy选择性需证明,若一个优化问题的优化解包含它的 子问题的优化解，则称其具有优化 子结构,优化子结构,与动态规划方法的比较,动态规划方法可用的条件 优化子结构 子问题重叠性 子问题空间小 Greedy方法可用的条件 优化子结构 Greedy选择性 可用Greedy方法时，动态规划方法可能不适用 可用动态规划方法时，Greedy方法可能不适用,证明算法所求解的问题具有优化子结构 证明算法所求解的问题具有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 输出：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的调 度问题的一个优化解且包括活动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，命题成立. 设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选择性 活动选择问题具有优化子结构 算法按照Greedy选择性计算解,算法正确性证明,定理. Greedy-Activity-Selector算法能够产 生最优解. 证. Greedy-Activity-Selector算法按照引 理3的Greedy选择性进行局部优化选 择.,5.3 Huffman codes,问题的定义 优化解的结构分析 算法设计 算法复杂性分析 算法正确性证明,二进制字符编码 每个字符用一个二进制0、1串来表示. 固定长编码 每个字符都用相同长的0、1串表示. 可变长编码 经常出现的字符用短码，不经常出现的用长码 前缀编码 无任何字符的编码是另一个字符编码的前缀,问题的定义,编码树,叶结点: 用字符及其出现频率标记,内结点: 用其子树的叶结点的频率和标记,边标记: 左边标记0，右侧边标记1,编码树T的代价 设C是字母表,cC f(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的优化前缀树，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(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的优化前缀树，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(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); /* 堆操作*/ 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 Minimal 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, T1是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 /* 不变命题真 */,算法的关键是第三步, 寻找安全边(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的边是轻边 红边集合是受尊重的边集合,定理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是最小生成树. 因为(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=红边集合,Kruskal算法,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(mlogm),算法正确性,定理2. MST-Kruskal(G,W)算法能够产生图 G的最小生成树. 证. 因为算法按照Greedy选择性进行局 部优化选择.,