lecture6-06

贪心法(Greedy Approach)基本思想算法设计设计要素与动态规划法的比较正确性证明得不到最优解的处理办法应用实例1基本思想实例：最小生成树的Kruskal算法,活动选择问题适用问题：组合优化问题，满足优化原则设计方法：多步判断，解为判断序列选择依据：是否满足约束条件局部优化测度使用贪心法要解决的问题:是否可以得到最优解?不能得到最优解,解与最优解的误差估计2例1活动选择问题S={1, 2, …, n}为n项活动的集合s i, f i分别为活动i 的开始和结束时间≥f j或s j≥f i活动i 与j相容当且仅当si求最大的两两相容的活动集思路：按结束时间递增顺序将活动排列为1,2,…,n, ≤f2≤…≤f n使得f1按照标号从小到大选择3定理1 算法Select 执行到第k步, 选择k项活动i1= 1, i2, …, ik, 那么存在最优解A包含i 1=1,i2, …, ik正确性证明根据定理：算法至多到第n步得到最优解67•证明存在最优解包含活动1•假设按照算法前k 步选择都导致最优解，证明第k +1步选择也导致最优解1. 第k 步：选择活动i 1=1, i 2, …, i k2. 归纳假设：存在最优解A ={i 1=1, i 2, …, i k }∪BB 是剩下的待选活动集S ’的一个最优解3. 由归纳基础，存在S ’的最优解B’包含i k +14. 由|B’|=|B | 知A’={i 1=1, i 2, …, i k }∪B’最优5. A’={i 1=1, i 2, …, i k , i k +1}∪(B’-{i k +1})最优. 对步数进行归纳的证明思路贪心算法的设计适用：满足优化原则的组合优化问题问题求解表示成多步判断整个判断序列对应问题的最优解子序列对应子问题的最优解贪心选择：确定一个优化测度不考虑以前的选择，只与当前状态有关以优化测度的极大（或极小）作为依据10贪心算法的设计（续）确定是否满足贪心选择性质具有贪心选择性质得到最优解，否则为近似解证明：贪心选择会导致最优解一般采用归纳法加以证明对算法步数归纳对问题规模归纳自顶向下计算通过贪心选择，将原问题规约为子问题线性表记录选择的结果1112数学归纳法叙述一个可以归纳证明的命题：•对步数k 归纳对于任意k ，k 步贪心选择得到i 1,i 2,…,i k , 那么存在最优解包含i 1,i 2,…,i k •规模k 归纳：对于任意k ,贪心法得到关于规模为k 的问题的最优解归纳基础：k =1, 命题为真归纳步骤：假设对<k 的正整数命题为真，证明对k 命题也为真贪心选择性质的证明13ni x cxw x i i n i i n i i ,...,2,11,0max11==≤∑∑==贪心法：将集装箱按照从轻到重排序，轻者先装例2最优装载Loadingn 个集装箱1,2,…,n 装上轮船，集装箱i 的重量w i , 轮船装载重量限制为c ，无体积限制. 问如何装使得上船的集装箱最多？不妨设w i ≤c .贪心选择性质证明思路•设集装箱标号按照从轻到重记为1, 2, …, n •对问题规模n 进行归纳•n=1, 贪心选择得到最优解（只有一个箱子）•假设对于规模为n-1的输入得到最优解，证明对规模为n的输入也得到最优解14说明Loading算法复杂性T(n) = O(n log n)Loading问题是0-1背包问题的特例：= 1, i=1, 2, …, n.即vi该问题是O(n log n) 时间可解的0-1背包问题是NP难的。

16贪心法得不到最优解的处理办法讨论对于哪些输入贪心选择能够得到最优解输入应该满足的条件讨论贪心法的解最坏情况下与最优解的误差绝对误差与相对误差估计17确定得到最优解的输入所满足的条件例3找零钱问题设有n种零钱,重量分别为w1, w2, ... , wn,价值分别为v1=1, v2, ... , vn.付的总钱数是y如何付钱使得所付钱的总重最轻?1821n=2时得到最优解F 1(y ) =G 1(y ) F 2(y ) = G 2(y ))(])([])([])([)]())(([2212212222122222212222122221≤+−=+−=+−−++−−=+−−+++−w v w w v w x w x v y w w x w v x v y w x w x v y F x w x v y F δδδδδδδ22定理2 假定G k (y )=F k (y ),v k +1>v k 且v k +1=pv k －δ, 0≤δ<v k , p ∈Z +, 则以下命题等价.kk k k k k k k k k k pw G w pv F pv G y F y G y G y G ≤+==≤++++++)()4()()()3()()()2()()()1(111111δ用条件(4) 需O (k ) 时间验证G k +1(y )=F k +1(y )?对n 种零钱作出验证, 可在O (n 2) 时间内完成n >2时得到最优解的判定条件25例4装箱问题有n 个物体, 长度分别为a 1, a 2, ... , a n , a i ≤1, i =1,2,…,n . 要把它们装入长为1的箱子(只考虑长度的限制)问至少需要多少只箱子?mj B C B C a mj n i mj j i ,...,2,1,1)()(min 11=≤=∑∑==，C (B j )称为箱子B j 的装入量1—C (B j )称为箱子B j 的空隙近似解的误差估计例5最优二元前缀码问题前缀码：用0-1字符串作为代码表示字符，要求任何字符的代码都不能作为其它字符代码的前缀非前缀码a---001, b---00, c---010, d---010100001: 01, 00, 001 d, b, a010, 00, 01 c, b, d前缀码的存储采用二叉树的结构，每个字符作为树叶，每个前缀码看作根到树叶的路径, x2, …, x n，输入：n个字符x1), i=1, 2, …, n.每个字符传输概率f(xi求：前缀码，使得平均传输一个字符的位数达到最小算法：Huffman树得到最优解3234例如a :45, b :13; c :12; d :16; e :9; f :5, Huffman树为平均位数：4*5%+4*9%+3*16%+3*12%+3*13%+1*45% = 2.24编码：f --0000, e --0001, d --001, c --010, b --011, a --1正确性证明•证明存在一个对应于最优前缀码的二叉树，以最小的频率为树叶，且这两片树叶是兄弟•证明x, y 是树叶兄弟，z 是x, y 的父亲，z 的频率f[z]=f[x]+f[y], 令T’= T−{ x, y },则T’是对应于最优前缀码C’=(C−{ x, y })∪{ z }的树3536则T 与T ’的权之差为其中d T (i )为i 在T 中的层数（i 到根的距离）∑∑≥−=−∈∈Ci Ci T T i d i f i d i f T B T B 0)(][)(][)'()('引理1设C 是字符集，∀c ∈C , f [c ]为频率，x , y ∈C , f [x ], f [y ]频率最小，那么存在最优二元前缀码使得x , y 的码字等长，且仅在最后一位不同.T →T’f [y ] ≤f [c ]f [x ] ≤f [b ]b 与x 交换c 与y 交换37引理2 设T 是最优解对应的树，∀x , y ∈T , x , y 是树叶兄弟，z 是x ,y 的父亲，z 的频率f [z ]=f [x ]+f [y ], 令T’=T −{x , y }, 则T’是对应于最优前缀码C’= (C −{ x , y })∪{ z } 的树证明：∀c ∈C −{ x , y }, 有d T (c )=d T ’(c ) ⇒f [c ]d T (c )=f [c ]d T ’(c ) 由d T (x ) =d T (y ) = d T ’(z ) +1得f [x ] d T (x ) + f [y ] d T (y ) = (f [x ] + f [y ]) (d T ’(z ) + 1)= f [z ]d T ’(z ) + (f [x ] + f [y ])从而B (T ) = B (T ’) + f [x ] + f [y ]若T ’不是关于C ’的最优树，那么存在T*使得B (T*)<B (T ’), z 是T*中的树叶，将x, y 加到z 上作为儿子，那么得到B (T*) + f [x ] + f [y ] < B (T )与T 的最优性矛盾。

定理3 Haffman 算法得到最优前缀码算法•Huffman树的算法•时间O(n log n)42实例44对步数归纳命题：对于任意k < n, 存在一棵最小生成树包含算法前k 步选择的边k=1, 存在一棵最小生成树T 包含边e={1,i}, 其中{1,i}是所有关联1的边中权最小的.设T 为一棵最小生成树，假设T 不包含{1,i}, 则T∪{{1,i}}含有一条回路，回路中关联1的另一条边为{1,j}，令T’=(T-{{1,j}})∪{{1,i}}，则T’也是生成树，且W(T’)≤W(T).Prim算法的正确性证明45Prim算法的正确性证明（续）归纳步骤,e2,…,e k-1, 这假设算法进行了k-1步，生成树的边为e1些边的k个端点构成集合S. 由归纳假设存在G的一棵最小生成树T包含这些边., 则i k+1到S中顶点的边权最小,算法第k步选择了顶点ik+1={i k+1,i l}。

假设T不含有{i k+1,i l}，则将e k加设这条边为ek到T中形成一条回路. 这条回路有另外一条连接S与V-S}，则T*是G的一棵生中顶点的边e, 令T*=(T-{e})∪{ek,e2,…,e k, 且W(T*)≤W(T).成树，包含了e1时间T(n)=O(n2)46实例4849对顶点数归纳命题：对于任意n , 使用Kruskal 算法对于n 阶图得到一棵最小生成树.证明n =2, 只有一条边，命题显然为真.假设对于n 个顶点的图算法正确，考虑n +1个顶点的图G , G 中最小权边e ={ i , j }.从G 中短接i 和j ，得到图G ’为n 个顶点的图. 根据归纳假设，由算法存在G ’的最小生成树T ’.令T =T ’∪{e }, 则T 是关于G 的最小生成树.Kruskal算法的正确性证明Kruskal算法正确性证明(续)若不然，存在一棵G的最小生成树T*，W(T*)<W(T). 如果e 属于T*, 则短接e 得到G’的生成树T*−{e}, 且W(T*−{e})<W(T ’), 与T ’的最优性矛盾；如果e不属于T*, 在T*中加上边e，形成回路.去掉回路中任意别的边所得生成树的权小于W(T*)，与W(T*)的最小性矛盾.时间：T(m)=O(m log m)50。