《算法分析与设计[贪心法]》由会员分享，可在线阅读，更多相关《算法分析与设计[贪心法]（63页珍藏版）》请在金锄头文库上搜索。
1、第三章 贪心方法,什么是贪心方法背包问题带有期限的作业排序最优归并模式最小生成树单源点最短路径,3.1 什么是贪心方法,某一问题的n个输入,该问题的一种解（可行解）,是A的一个子集,满足一定的条件,约束条件,目标函数,取极值,最优解,3.1 什么是贪心方法,根据题意，选取一种量度标准，然后按量度标准对n个输入排序，按顺序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最优解加在一起不能产生一个可行解，则不把此输入加到这部分解中，这种能够得到某种量度意义下的最优解的分级处理方法就是贪心方法。,量度标准,量度标准意义下的部分最优解,原问题的 n 个输入,排序后的 n 个输入,A(j)
2、,贪心方法的抽象化控制,Procedure GREEDY(A,n) solution for i1 to n do xSELECT(A) if FEASIBLE(solution,x) then solutionUNION(solution,x) endif repeat return (solution)End GREEDY,按某种最优量度标准从A中选择一个输入赋给x，并从A中除去,判断x是否可以包含在解向量中,将x与解向量合并并修改目标函数,3.2 背包问题,问题描述已知有n种物品和一个可容纳M重量的背包，每种物品i的重量为wi，假定将物品i的某一部分xi放入背包就会得到pixi的效益(0
3、xi1, pi0) ，采用怎样的装包方法才会使装入背包物品的总效益为最大呢？问题的形式描述极大化 pixi 约束条件 wi xi M 0xi1, pi0, wi0, 1in,1in,1in,目标函数,背包问题实例,考虑下列情况的背包问题n=3,M=20,(p1,p2,p3)=(25,24,15),(w1,w2,w3)=(18,15,10)其中的4个可行解是：,贪心方法的数据选择策略(1),用贪心策略求解背包问题时，首先要选出最优的度量标准。可以选取目标函数为量度标准，每装入一件物品就使背包获得最大可能的效益值增量。在这种量度标准下的贪心方法就是按效益值的非增次序将物品一件件放到背包中。如上面的
4、实例所示，可将物品按效益量非增次序排序： (p1,p2,p3)=(25,24,15)。先装入物品1重量为18，即x1=1；然后再装物品2，由于约束条为wi xi M=20，所以物品2只能装入重量为2的一小部分，即x2=2/15。,贪心方法的数据选择策略(2),按上述的数据选择策略，装入顺序是按照物品的效益值从大到小的输入，由刚才的方法可得这种情况下的总效益值为pixi = 25+24*2/15=28.2，显然是一个次优解，原因是背包容量消耗过快。2.若以容量作为量度，可让背包容量尽可能慢地被消耗。这就要求按物品重量的非降次序来把物品放入背包，即(w3,w2,w1)=(10,15,18)。,贪心
5、方法的数据选择策略(2),先装入物品3, x3=1, p3x3 =15，再装入重量为10的物品2， pixi =15+24*10/15=31。由刚才的方法可得这种情况下的总效益值为31，仍是一个次优解，原因是容量在慢慢消耗的过程中，效益值却没有迅速的增加。,贪心方法的数据选择策略(3),3.采用在效益值的增长速率和容量的消耗速率之间取得平衡的量度标准。即每一次装入的物品应使它占用的每一单位容量获得当前最大的单位效益。这就需使物品的装入次序按pi/wi比值的非增次序来考虑。这种策略下的量度是已装入物品的累计效益值与所用容量之比。(p2/w2 , p3/w3 , p1/w1 )=(24/15,15
6、/10,25/18)。先装入重量为15的物品2，在装入重量为5的物品3， pixi =24+15*5/10=31.5。此结果为最优解。,背包问题的贪心算法,Procedure GREEDY-KNAPSACK(P,W,M,X,n) real P(1:n),W(1:n),X(1:n),M,cu; integer i,n; X0;cuM for i1 to n do if W(i) cu then exit endif X(i)1;cucu-W(i) repeat if in then X(i)cu/W(i) endifEnd GREEDY-KNAPSACK,将解向量X初始化为0Cu为背包的剩余容量
7、,只放物品i 的一部分,预先将物品按pi/wi比值的非增次序排序,最优解的证明,基本思想把这个贪心解与任一最优解相比较，如果这两个解不同，就去找开始不同的第一个xi，然后设法用贪心解的这个xi去代换最优解的那个xi ，并证明最优解在分量代换前后的总效益值无任何变化。反复进行这种代换，直到新产生的最优解与贪心解完全一样，从而证明了贪心解就是最优解。,最优解的证明,定理3.1 如果p1/w1 p2/w2 pn/wn，则算法GREEDY-KNAPSACK对于给定的背包问题实例生成一个最优解。证明：设X=(x1,xn )是GREEDY-KNAPSACK算法所生成的解。如果所有的xi 等于1，显然这个解
8、就是最优解。否则，设j是使xj !=1的最小下标。由算法可知，对于1ij , xj =1;对于jin , xj =0 ; 对于i=j ，0xjpixi 。假定wiyi =M，设k是使得 yk!=xk的最小下标，则可以推出结论ykxk成立。这个结论可从下面三种可能发生的情况分别证明：若kj，则xk=1。因yk!=xk ，则ykxk成立若k=j，由于wixi =M，且对于1ij，有 xj =yi = 1，而对于jxk，则有wiyi M，这与Y是可行解矛盾。若yk=xk，与假设yk!=xk 矛盾，故只有ykj，若ykxk =0 ，则wiyi M,这与Y是可行解矛盾。因此，结论ykxk成立。现在，假定
9、把 yk 增加到 xk，那么必须从(yk+1,yn) 中减去同样多的量，使得所用的总容量仍为M。这导致一个新的解Z = (z1,zn)，其中，zi= xi,1ik，并且wi ( yi-zi )= wk ( zk-yk) 。因此，对于Z有pizi=piyi +(zk-yk)pk-(yi-zi)pi = piyi +(zk-yk)wk pk /wk -(yi-zi)wipi/wipiyi +(zk-yk)wk -(yi-zi)wipk/wk = piyi,1in,1in,kin,1in,kin,1in,kin,1in,k piyi ，则Y不可能是最优解。若pizi =piyi ，同时Z=X，则X就
10、是最优解；若pizi =piyi ， 但Z!=X，则重复上面的讨论，或者证明Y不是最优解，或者把Y转换成X，从而证明了X也是最优解。证毕。,课后思考题,找零钱问题：一个小孩买了价值为33美分的糖，并将1美元的钱交给售货员。售货员希望用数目最少的硬币找给小孩。假设提供了数目不限的面值为25美分、10美分、5美分、及1美分的硬币。使用贪心算法求解最优结果。并证明找零钱问题的贪心算法是否总能产生具有最少硬币数的零钱。考虑假设售货员只有数目有限的25美分，10美分，5美分和1美分的硬币，给出一种找零钱的贪心算法。,3.3 带有限期的作业排序,问题描述假定只能在一台机器上处理n个作业，每个作业均可在单位
11、时间内完成；又假定每个作业i都有一个截止期限di0(是整数)，当且仅当作业i在它的期限截止之前被完成时，则获得pj0的效益。这个问题的一个可行解是这n个作业的一个子集合J，J中的每个作业都能在各自的截止期限之前完成，可行解的效益值是J中这些作业的效益之和pj 。具有最大效益值的可行解就是最优解。,带有限期的作业排序实例,例3.2 n=4，(p1,p2,p3,p4) = (100,10,15,20) 和(d1,d2,d3,d4)=(2,1,2,1)，这个问题可能的可行解和他们的效益值为：,带限期的作业排序算法,为了得到最优解，应制定如何选择下一个作业的量度标准，利用贪心策略，使得所选择的下一个作
12、业在这种量度下达到最优。可把目标函数pj作为量度，则下一个要计入的作业将是使得在满足所产生的J是一个可行解的限制条件下使pj得到最大增加的作业，这一方法只要将各作业按效益pi降序来排列就可以了。,例3.2,求解 (p1，p2，p3，p4)(100,10,15,20) (d1，d2，d3，d4)(2,1,2,1) 首先令J=； 作业1具有当前的最大效益值，且1是可行解，所以作业1计入J； 在剩下的作业中，作业4具有最大效益值，且1,4也是可行解，故作业4计入J，即J=1,4； 考虑1,3,4和1,2,4均不能构成新的可行解，作业3和2将被舍弃。 故最后的J=1,4，最终效益值120（问题的最优解
13、）,带限期的作业排序算法,作业按p1 p2 pn的次序输入：Procedure GREEDY_JOB(D,J,n) J1 for i2 to n do if Ji的所有作业都能在他们的截止期限前完成 then JJi endif repeatEnd GREEDY_JOB,定理3.2,对于作业排序问题，用GREEDY_JOB算法所描述的贪心方法总是得到一个最优解 证明如下:,定理3.2 证明,证明： 设J是由贪心方法所选择的作业的集合；设I是一个最优解的作业集合。则 IJ，否则J也是最优解。 易知：I不是J的真子集，否则I就不是最优解；J也不是I的真子集，这是由贪心法的工作方式所决定的。因此，存
14、在作业a和b，使得a属于J但不属于I；b属于I但不属于J。 设a是使得a属于J但不属于I的一个具有最高效益的作业，对于在I中又不在J中的所有作业b，都有PaPb。这是因为若PaPb，则贪心法会先于作业a考虑作业b并且把b计入到J中。,定理3.2 证明（续）,设SJ是J的可行调度表；SI是I的可行调度表。对于每一个I和J的共同作业i，做以下调整：（tt，则可在SI中作类似的调整。用这种方法，就使得J和I中共有的所有作业在相同的时间被调度。,定理3.2 证明（续）,设作业a是使得a属于J但不属于I的一个具有最高效益的作业。,由于PaPb,显然，转换后I的效益值没有减少。重复应用上述转换，使I在不减
15、少效益值的情况下转换成J，因此，J也必定是最优解。证毕。,如何判断J的可行性,方法一： 检验J中作业所有可能的排列，对于任一种次序排列的作业排列，判断这些作业是否能够在其期限前完成，也即若J中有k个作业，则将要检查k!个序列方法二： 检查J中作业的一个特定序列就可判断J的可行性：对于所给出的一个排列i1i2ik,由于作业ij完成的最早时间是j，因此只要判断出排列中的每个作业dijj，就可得知是一个允许的调度序列，从而J是一个可行解。反之，如果排列中有一个dijj,则将是一个行不通的调度序列，因为至少作业ij不能在其期限之前完成。这一检查过程可以只通过检验J中作业的一种特殊的排列：按照作业期限的非降次序排列的作业序列即可完成。,
