算法201104-贪心1.

第四章贪心算法贪心算法的基本思想背包问题的贪心求解最小生成树最短路径最优归并模式哈夫曼编码贪心算法的基本思想背包问题的贪心求解贪心算法求解问题的类型-解与解向量现实中有这样的问题：有n个输入和一组约束条件。解的结构对应为一个n维向量（x1,x2,,xn）,其中xi（i=1,2,,n）对应为输入元素的相应取值（具体根据实际问题不同取值方法不同）。（x1,x2,,xn）需满足相应约束条件满足约束条件的任意一组输入称为问题的一组可行解；使目标函数达到最大或最小（根据实际问题的要求）的可行解称为最优解。贪心法用于求解的问题，其目标往往是求最优解。例子-11找零钱问题：以人民币1元，2元，5元，10元，20元，50元，以99元为例，要求所找的张数最少？99=50+20*2+5+2*22古代有一位医师到某个到处都是草药的山洞里采药，山洞里有一些不同的草药，同时每种草药只有一株，采每一株都需要一些时间，每一株都有它自身的价值。只能在一段时间内采药，在这段时间里，医师可以采到一些草药，医师了解每种草药需要的时间及其价值。如果是你，你应该如何采药才可以让采到的草药的总价值最大。例子-23[渴婴问题]有一个非常渴的、聪明的小婴儿，她可能得到的东西包括一杯水、一桶牛奶、多罐不同种类的果汁、许多不同的装在瓶子或罐子中的苏打水，即婴儿可得到n种不同的饮料。根据以前关于这n种饮料的不同体验，此婴儿知道这其中某些饮料更合自己的胃口，因此，婴儿采取如下方法为每一种饮料赋予一个满意度值：饮用1盎司第i种饮料，对它作出相对评价，将一个数值si作为满意度赋予第i种饮料。但当前情况是：具有最大满意度值的饮料有时并没有足够的量来满足此婴儿解渴的需要。设ai是第i种饮料的总量（以盎司为单位），而此婴儿需要t盎司的饮料来解渴，那么，需要饮用n种不同的饮料各多少量才能满足婴儿解渴的需求呢（最大满意度）？例子-34[最小代价通讯网络]城市及城市之间所有可能的通信连接可被视作一个无向图，图的每条边都被赋予一个权值，权值表示建成由这条边所表示的通信连接所要付出的代价。包含图中所有顶点（城市）的连通子图都是一个可行解。设所有的权值都非负，则所有可能的可行解都可表示成无向图的一组生成树，而最优解是其中具有最小代价的生成树。例子-4城市高速路问题其他问题GoHomeTravelInvestmentBudget贪心法向着某一目标（最大、最小、最优化、最短、其他？），考虑问题的求解方法，每一步尽量与目标要求一致，逐步求解，步步为“赢”活动安排问题•设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，且在同一时间里只能有一个活动可以使用该资源。现要求给出一个活动安排，使得利用该资源活动为最多。•每个活动i都有使用该资源的一个启始时间si和一个结束时间fi，si＜fi，其占用资源的时间为半开区间[si,fi)。若区间[si,fi)与区间[sj,fj)不相交，则称活动i与活动j是相容的。•活动安排问题就是求E的最大相容活动子集。会场或教室活动安排问题的描述•用数组A分别存放所有活动的启始时间和结束时间以及是否予以安排的标记。•某项活动结束时间愈早，安排其它活动的剩余区间愈大。所以贪心策略为尽量选择结束时间早的活动来安排。•为此，将数组中的活动按结束时间的非减顺序排序，即f1≤f2≤…≤fn。•显然排序需要的时间为O(nlogn)。活动安排问题的算法•ActionArragement(intn,TypeA[][])•//A[i][0],A[i][1],A[i][3]分别为s,f和安排标记•{•将A依照A[i][1]的非减顺序排序；•intj=1;A[j][3]=1;//先安排活动1•for(inti=2;i=n;i++){•ifA[i][0]=A[j][1]//若活动i与j相容•{A[i][3]=1;j=i;}//则安排活动i•elseA[i][3]=0}//否则不安排活动i•}活动安排问题实例•设待安排的11个活动的始末时间排序如下：i1234567891011s[i]130535688212f[i]4567891011121314首先选定活动1，其结束时间f[1]=4。然后因s[4]=5≥4，选定活动4，这时f[4]=7。又因s[8]=8≥7，选定活动8，这时f[8]=11。最后因s[11]=12≥11，选定活动11。最终的活动安排为：1、4、8和11。贪心算法的特点•贪心算法总是作出在当前来看是最好的选择。•贪心算法并不从整体最优上来考虑，所作出的选择只是某种意义上的局部最优选择。•当然希望贪心算法得到的最终结果是最优的。•贪心算法并不能保证最终结果是最优的。•不过，在许多的情况下，应用贪心算法能够得到整体最优解；并且在一些情况下，即使得到的不是最优解，也是一个很好的近似解。贪心算法也能获得最优解•设活动集合E={1,2,…,n}已经按结束时间的非减顺序排列，活动1具有最早结束时间。•首先，必定有一个最优解包含活动1。不然设AE是最优解且A中最早结束的活动是k。若k=1，则最优解包含活动1。若k＞1，则活动1必与A中除k以外的活动相容。令B=A–{k}∪{1}，则B也是一个最优解。其次，若A是原问题的包含活动1的最优解，则A=A–{1}是活动集合E={i∈E：si≥f1}的一个最优解。不然设B是E的解且|B|＞|A|，则B∪{1}是E的解且|B|+1＞|A|。此与A是最优解矛盾。对贪心选择次数用数学归纳法即知，贪心算法最终产生原问题的最优解。对贪心选择次数用数学归纳法即知，贪心算法最终产生原问题的最优解2）设m=k时，活动安排选择的前k动作已包含在一个最优解A中，则m=k+1时，活动安排选择的前k+1动作肯定包含在一个最优解中，否则，考虑选择的第k+1个活动，对贪心选择次数m进行归纳。1）m=1时，活动安排选择的第一个动作肯定包含在一个最优解中（已证）；若A是原问题的包含活动{1,,k}的最优解，则A=A–{1,,k}是活动集合E={i∈E：si≥fk}的一个最优解。若活动k+1不在A中，则A中第一个活动t满足：ft≥fk+1,构造B=A-{t}{k+1},则{1,,k}B为原问题的一个最优解。由数学归纳法性质得到，活动安排问题的贪心选择可以得到原问题的最优解贪心算法的基本要素•贪心算法的基本要素是：最优子结构性质与贪心选择性质。•所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优解的选择，即贪心选择来达到。•贪心选择每次选取当前最优解，因此它依赖以往的选择，而不依赖于将来的选择。•贪心算法通常以自顶向下的方式进行，每次贪心选择就将原问题转化为规模更小的子问题。1）每个大问题的最优解里面包含下一级小问题的最优解；2）每个小问题的最优解可由贪心选择得到。贪心算法的一般框架•GreedyAlgorithm(parameters)•{•初始化；•重复执行以下的操作：•选择当前可以选择的(相容)最优解；•将所选择的当前解加入到问题的解中去；•直至满足问题求解的结束条件。•}逐1扩充解向量贪心方法的抽象化控制ProcedureGREEDY(A,n)solutionФfori1tondoxSELECT(A)ifFEASIBLE(solution,x)thensolutionUNION(solution,x)endifrepeatreturn(solution)EndGREEDY按某种最优量度标准从A种选择一个输入赋给x，并从A中除去判断x是否可以包含在解向量中将x与解向量合并并修改目标函数如何确定贪心选择性质•必须证明每一步的贪心选择将导致整体上的最优解。其方法类似于活动安排中的证明。•首先考察问题的一个整体最优解，并证明可修改此最优解，使其以贪心选择开始。•证明在做了贪心选择后，原问题简化为规模较小的类似子问题，即可继续使用贪心选择。•于是用数学归纳法可证明，经过一系列贪心选择可以得到整体最优解。•满足贪心选择性质必满足最优子结构性质。最优子结构第一个选择是正确的贪心选择与最优子结构•满足贪心选择性质必满足最优子结构性质。若原问题E的最优解A是经过有限次贪心选择后获得的，则并必定包含了贪心选择1。实际上在选择了贪心选择1后，就将原问题分解为子问题E’和E”，贪心选择1显然是E’的最优解，而A–{1}必定是E”的最优解。否则将导出A不是最优解的矛盾。因此原问题的最优解是由子问题的最优解组成的。用归纳法可证明其后的贪心选择同样保持最优子结构性质。但是满足最优子结构性质却未必满足贪心选择性质。问题1背包问题的贪心求解•问题描述–已知有n种物品和一个可容纳M重量的背包，每种物品i的重量为wi，假定将物品i的某一部分xi放入背包就会得到pixi的效益(0≤xi≤1,pi0)，采用怎样的装包方法才会使装入背包物品的总效益为最大呢？目标函数1≤i≤n1≤i≤n问题的形式化描述极大化max∑pixi约束条件∑wixi≤M0≤xi≤1,pi0,wi0,1≤i≤n例如：在杂货店举行的某个比赛中你获得了第一名，奖品是一车免费的商品。已知店中有n种不同的货物，规则规定从每种货物中你最多只能拿一件，车子的容量为M，每件物品i需占用的空间为Wi，价值为Pi（i=1,2,…,n）。你的目标是使车中装载的物品具有价值最大。（注意：所装货物不能超过车的容量，且同一种物品不得拿走多件，一种物品可以拿一部分，并获得部分价值。）要求：1)给出该问题的形式化（数学）描述；2)给出求解该问题最优解的贪心算法描述。背包问题实例•考虑下列情况的背包问题–n=3,M=20,(p1,p2,p3)=(25,24,15),(w1,w2,w3)=(18,15,10)–其4个可行解是：(x1,x2,x3)∑wixi∑pixi①(1/2,1/3,1/4)16.524.25②(1,2/15,0)2028.2③(0,2/3,1)2031④(0,1,1/2)2031.5用贪心策略求解背包问题时，首先要选出最优的度量标准。1可以选取目标函数为量度标准，每装入一件物品就使背包获得最大可能的效益值增量。在这种量度标准下的贪心方法就是按效益值的非增次序将物品一件件放到背包中。如上面的实例所示，可将物品按效益量非增次序排序：(p1,p2,p3)=(25,24,15)。先装入物品1重量为18，即x1=1；然后再装物品2，由于约束条为∑wixi≤M=20，所以物品2只能装入重量为2的一小部分，即x2=2/15。贪心方法的数据选择策略(1)•背包问题n=3,M=20,(p1,p2,p3)=(25,24,15),(w1,w2,w3)=(18,15,10)•按上述的数据选择策略，装入顺序是按照物品的效益值从大到小的输入，由刚才的方法可得这种情况下的总效益值为∑pixi=25+24*2/15=28.2，显然是一个次优解，原因是背包容量消耗过快。贪心方法的数据选择策略(1)2.若以容量作为量度，可让背包容量尽可能慢地被消耗。这就要求按物品重量的非降次序来把物品放入背包，即(w3,w2,w1)=(10,15,18)。贪心方法的数据选择策略(2)贪心方法的数据选择策略(2)•先装入物品3,x3=1,p3x3=15，再装入重量为10的物品2，∑pixi=15+24*10/15=31。由刚才的方法可得这种情况下的总效益值为31，仍是一个次优解，原因是容量在漫漫消耗的过程中，效益值却没有迅速的增加。•背包问题n=3,M=20,(p1,p2,p3)=(25,24,15),(w1,w2,w3)=(18,15,10)贪心方法的数据选择策略(3)3.采用在效益值的增长速率和容量的消耗速率之间取得平衡的量度标准。即每一次装入的物品应使它占用的每一单位容量获得当前最大的单位效益。这就需使物品的装入次序按pi/wi比值的非增次序来考虑。这种策略下的量度是已装入物品的累计效益值与所用容量之比。(p2/w2,p3/w3,p1/w1)=(24/15,15/10,25/