第四章 贪心算法.ppt

《第四章 贪心算法.ppt》由会员分享，可在线阅读，更多相关《第四章 贪心算法.ppt（29页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 1OUTLINE1、背包问题2、贪心算法的基本要素3、贪心和DP的区别4、单源点最短路径问题 2第4章 贪心算法 顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。34.1 背包问题-问题描述已知有n种物品和一个可容纳c重量的背包，每种物品i的重量为wi。假定物品i的一

2、部分放入背包会得到vixi的效益。其中0 xi1,vi0.采用怎样的装包方法才会使装入背包物品的总效益最大呢？即求解(4.2.1)(4.2.2)(4.2.3)其中（4.2.1）是目标函数，（4.2.2）及（4.2.3）是约束条件。满足约束条件的任一集合(x1,xn)一个可行解，使目标函数取最大值的可行解是最优解。4 例例4.4 考虑下列情况下的背包问题:n3,c20,(v1,v2,v3)=(25,24,15),(w1,w2,w3)=(18,15,10)其中的四个可行解是 （1/2,1/3,1/4）16.5 24.25（1,2/15,0）20 28.2（0,2/3,1）20 31（0,1,1/2

3、）20 31.5 先检验这四个为可行解*,即满足约束条件(4.2.2),(4.2.3).再比较目标函数值,vixi.知组解效益值最大.该组解是背包问题的最优解。4.1 背包问题的实例背包问题的实例问题求解策略问题求解策略：度量标准的选择：三种不同的选择 5 （1）取目标函数作为量度标准，取目标函数作为量度标准，即每次选择利润最大的即每次选择利润最大的物品装包，使背包获得最大可能的效益值增量。物品装包，使背包获得最大可能的效益值增量。在此量度标准下贪心方法就是按效益值的非增次序按效益值的非增次序，将物品一一装包，直到直到某一某一i物品放不下时物品放不下时，取一种能获得最大增量的物品，将它（或取一

4、种能获得最大增量的物品，将它（或其一部分）放入背包，其一部分）放入背包，而使最后一次装包也符合量度标准的要求，如：还剩下两个单位的空间，而背包外还有两种物品。，则用i比j好，装入A，Vi=4;而装入B,Vj=3。对例 4.4的数据使用按效益值的非增次序的选择策略按效益值的非增次序的选择策略.例例4.4 n3,c20,背包剩：C182；物品2有次大效益值(V2=24)但w2=15,背包装不下物品2。使用 x2=2/15,刚好装满背包 6按此选择策略,得即(1,2/15,0),vixi=28.2.此解是一个次优解。显然，按物品效益值的非增次序装包不能得最优解。原因原因：背包可用容量消耗过快。（2）

5、以容量作为量度。即按物品重量的非降次序将物按物品重量的非降次序将物品装包品装包。如例4.4中的解（让背包尽可能慢被消耗）排序:(w3,w2,w1)=(10,15,18)V3=15,x3=1,w3=10,背包剩余C1010;物品2有次大重量(w215),但包装不下。使用x22/3，刚好装满背包且物品2装入2/3与物品1装入5/9的容量均为10个单位。但前者的效益值242/3=16 后者效益值255/914，但 vixi=31,解（0，2/3，1)仍是一个次优解。原因原因：容量慢慢消耗，但效益值未能迅速增大。7 （3）效益值的增长速率和容量的消耗速率间取平衡的量度标准。即以单位效益为量度，使物品装

6、入次序按比值的非以单位效益为量度，使物品装入次序按比值的非增次序排列增次序排列，应用于例4.4的数据，得解:（0,1,1/2）,vixi=31.5,wixi=20.为例4.4背包问题的最优解.选取最优的量度标准实为用贪心方法求解问题的核心选取最优的量度标准实为用贪心方法求解问题的核心.直接将目标函数作为量度标准也不一定能够得到问题的最优解贪心解 最优解 8 首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重单位重量价值最高量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一

7、直地进行下去，直到背包装满为止。用算法KNAPSACK可实现求背包问题的最优解.具体算法可描述如下页：4.1 用贪心算法解背包问题的基本步骤：9void KNAPSACK(int n,float c,float v,float w,float x)/v,W分别含有按Vi/WiVi+1/wi+1排序的n件物品的/效益值和重量；c是背包的容量，x是解向量/int i;for(i=1;i=n;i+)xi=0;/将解向量初始化为0/float cu=c;/cu是背包剩余容量/for(i=1;icu)break;xi=1;cu=cu-wi;if(i=n)xi=cu/wi;背包问题的贪心算法背包问题的贪心

8、算法 算法算法knapsackknapsack的主要计算时间在的主要计算时间在于将各种物品依其于将各种物品依其单位重量的价值从单位重量的价值从大到小排序。因此，大到小排序。因此，算法的计算时间上算法的计算时间上界为界为O O（nlognnlogn）。当然，）。当然，为了证明算法的正为了证明算法的正确性，还必须证明确性，还必须证明背包问题具有贪心背包问题具有贪心选择性质选择性质。104.1 最优解的证明 即证明由第三种策略所得到的贪心解是问题的最优解。最优解的含义：在满足约束条件的情况下，使目标函数取极（大或小）值的可行解。贪心解是可行解，故只需证明贪心解可使目标函数取得极值。11证明的基本思想

9、：将此贪心解与（假设中的）任一最优解相比较。如果这两个解相同，则显然贪心解就是最优解。如果这两个解不同，就设法去找两者开始出现不同的第一个分量位置i，然后设法用贪心解的这个xi去替换最优解对应的分量，并证明最优解在分量代换前后总的效益值没有任何变化(且不违反约束条件)。然后再比较二者。若还不同，则反复进行代换，直到代换后产生的“最优解”与贪心解完全一样。在上述代换中，最优解的效益值没有任何损失，从而证明贪心解的效益值与代换前后最优解的效益值相同,即贪心解如同最优解一样可取得目标函数的最大/最小值。从而得证：该贪心解即是问题的最优解。12定理定理3.1 如果如果p1/w1 p2/w2 pn/wn

10、,则算法则算法GREEDY-KNAPSACK对于给定的背包问题实例生成一个最优解。对于给定的背包问题实例生成一个最优解。证明：设X=(x1,x2,xn)是GREEDY-KNAPSACK所生成的贪心解。如果所有的xi都等于1,则显然X就是问题的最优解。否则，设j是使xi1的最小下标。由算法的执行过程可知，l xi=1 1ij,l 0 xj 1l xi=0 jin 13 假设Y是问题的最优解：Y=(y1,y2,yn)且有：若X Y，则X就是最优解。否则，X和Y至少在1个分量上存在不同。设k是使得yk xk的最小下标，则有y yk k x xk k。可分以下情况说明：a)若kj，则xk=1。因为yk

11、 xk,从而有yk xk b)若k=j，由于 ，且对1ij，有yi=xi=1,而对jin,有xi0，故此时若ykxk，则 ，与Y是可行解相矛盾。而yk xk,所以yk xk c)若kj，则 （因为此时xk=0,yk0），不能成立 14在Y中作以下调整：将yk增加到xk，因为ykxk,为保持解的可行性，必须从(yk+1,yn)中减去同样多的重量。设调整后的解为Z=(z1,z2,zn)，其中zixi，1ik，且有：Z的效益值有：差值0 15由以上分析得，若 ，则Y不是最优解；若 ，如果Z=X，则X就是最优解；如果ZX，则重复以上替代过程，或者证明Y不是最优解，或者把Y转换成X，进而证明X是最优解

12、164.2 贪心算法的基本要素 本节着重讨论可以用贪心算法求解的问题的一般特征。对于一个具体的问题，怎么知道是否可用贪心算法解此问题，以及能否得到问题的最优解呢?这个问题很难给予肯定的回答。但是，从许多可以用贪心算法求解的问题中看到这类问题一般具有2个重要的性质：贪心选择性质贪心选择性质和最优子结构性质最优子结构性质。选取最优的量度标准实为用贪心方法求解问题的核心选取最优的量度标准实为用贪心方法求解问题的核心.174.2 贪心算法的基本要素1.1.贪心选择性质贪心选择性质 所谓贪心选择性质是指所求问题的整体最优解整体最优解可以通过一系列局部最优局部最优的选择，即贪心选择来达到。这是贪心算法可行

13、的第一个基本要素，也是贪心算法与动态规划算法的主要区别。动态规划算法通常以自底向上自底向上的方式解各子问题，而贪心算法则通常以自顶向下自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解整体最优解。184.3 贪心算法的基本要素 2.2.最优子结构性质最优子结构性质 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。19 对于0-10-1背包

14、问题背包问题，贪心选择之所以不能得到最优解是因为在这种情况下，它无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。事实上，在考虑0-1背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后再作出最好选择。由此就导出许多互相重叠的子问题。这正是该问题可用动态规划动态规划算法算法求解的另一重要特征。实际上，动态规划算法的确可以有效地解0-1背包问题。4.3 贪心和动归的区别：背包问题 204.3 贪心和动归的区别：背包问题背包问题：背包问题：与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品可以选择物品i i的一部分的一部分，而不一定要全部装入背

15、包，1in。这2类问题都具有最优子结构最优子结构性质，极为相似，但背包问题可以用贪心算法求解，而0-1背包问题却不能用贪心算法求解。214.3 贪心和动归的区别：0-10-10-1背包问题：背包问题：给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?在选择装入背包的物品时，对每种物品在选择装入背包的物品时，对每种物品i i只有只有2 2种选择，即种选择，即装入背包或不装入背包。不能将物品装入背包或不装入背包。不能将物品i i装入背包多次，也不能只装入背包多次，也不能只装入部分的物品装入部分的物品i i。22 例例

16、4.3 贪心算法不能求得0-1背包问题得最优解。考虑背包问题:n3,c50kg,(v1,v2,v3)=(60,100,120),(w1,w2,w3)=(10,20,30).vi/wi=(6,5,4).贪心算法解是(1,1,0),vixi=60+100,wixi=30;最优解是(0,1,1),vixi=100+120,wixi=50,对于0-1背包问题背包问题，贪心选择之所以不能得到最优解是因为在这种情况下，它无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。事实上，在考虑0-1背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后再作出最好选择。由此就导出许多

17、互相重叠的子问题。这正是该问题可用动态规划算法动态规划算法求解的另一重要特征。实际上，动态规划算法的确可以有效地解0-1背包问题。4.3 贪心和动归的区别：实例实例 234.4 单源最短路径：问题概述单源最短路径：问题概述给定一个带权有向图G=（V，E），其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到所有其它各顶点的最短路径长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。244.4 算法基本思想算法基本思想如何求得这些路径？Dijkstra按照贪心算法提出了一个按路径长度递增的次序产生最短路径算法。254.4 算法步骤首先引进一个辅助向量

18、D，它的每个分量Di表示当前所找到的从始点v到每个终点vi的最短路径长度。它的初态为：若从v到vi有弧，则Di为弧上的权值；否则Di为。显然长度为 Dj=MinDi|viV 的路径就是从v出发的长度最短的一条路径（v,vi）。264.4 算法步骤其次要找的是下一条长度次短路径 假设该次短路径的终点是vk,则可想而知，这条路径或者是（v,vk）,或者是（v,vj,vk）。它的长度或者是从v到vk的弧上权值，或者是Dj和从vj 到vk的弧上的权值之和。27The Algorithm in action,e.g.28The Algorithm in action,e.g.d(A,F)=9 d(A,F)=8 29总结1、背包问题2、贪心算法的基本要素3、贪心和DP的区别4、单源点最短路径问题