算法分析与设计[贪心法].ppt

第三章贪心方法,什么是贪心方法背包问题带有期限的作业排序最优归并模式最小生成树单源点最短路径,3.1什么是贪心方法,某一问题的n个输入,该问题的一种解（可行解）,是A的一个子集,满足一定的条件,约束条件,目标函数,取极值,最优解,3.1什么是贪心方法,根据题意，选取一种量度标准，然后按量度标准对n个输入排序，按顺序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最优解加在一起不能产生一个可行解，则不把此输入加到这部分解中，这种能够得到某种量度意义下的最优解的分级处理方法就是贪心方法。,量度标准,量度标准意义下的部分最优解,原问题的n个输入,排序后的n个输入,A(j),贪心方法的抽象化控制,ProcedureGREEDY(A,n)solutionfori1tondoxSELECT(A)ifFEASIBLE(solution,x)thensolutionUNION(solution,x)endifrepeatreturn(solution)EndGREEDY,按某种最优量度标准从A中选择一个输入赋给x，并从A中除去,判断x是否可以包含在解向量中,将x与解向量合并并修改目标函数,3.2背包问题,问题描述已知有n种物品和一个可容纳M重量的背包，每种物品i的重量为wi，假定将物品i的某一部分xi放入背包就会得到pixi的效益(0xi1,pi0)，采用怎样的装包方法才会使装入背包物品的总效益为最大呢？问题的形式描述极大化pixi约束条件wixiM0xi1,pi0,wi0,1in,1in,1in,目标函数,背包问题实例,考虑下列情况的背包问题n=3,M=20,(p1,p2,p3)=(25,24,15),(w1,w2,w3)=(18,15,10)其中的4个可行解是：,贪心方法的数据选择策略(1),用贪心策略求解背包问题时，首先要选出最优的度量标准。可以选取目标函数为量度标准，每装入一件物品就使背包获得最大可能的效益值增量。在这种量度标准下的贪心方法就是按效益值的非增次序将物品一件件放到背包中。如上面的实例所示，可将物品按效益量非增次序排序：(p1,p2,p3)=(25,24,15)。先装入物品1重量为18，即x1=1；然后再装物品2，由于约束条为wixiM=20，所以物品2只能装入重量为2的一小部分，即x2=2/15。,贪心方法的数据选择策略(2),按上述的数据选择策略，装入顺序是按照物品的效益值从大到小的输入，由刚才的方法可得这种情况下的总效益值为pixi=25+24*2/15=28.2，显然是一个次优解，原因是背包容量消耗过快。2.若以容量作为量度，可让背包容量尽可能慢地被消耗。这就要求按物品重量的非降次序来把物品放入背包，即(w3,w2,w1)=(10,15,18)。,贪心方法的数据选择策略(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/10,25/18)。先装入重量为15的物品2，在装入重量为5的物品3，pixi=24+15*5/10=31.5。此结果为最优解。,背包问题的贪心算法,ProcedureGREEDY-KNAPSACK(P,W,M,X,n)realP(1:n),W(1:n),X(1:n),M,cu;integeri,n;X0;cuMfori1tondoifW(i)cuthenexitendifX(i)1;cucu-W(i)repeatifinthenX(i)cu/W(i)endifEndGREEDY-KNAPSACK,将解向量X初始化为0Cu为背包的剩余容量,只放物品i的一部分,预先将物品按pi/wi比值的非增次序排序,最优解的证明,基本思想把这个贪心解与任一最优解相比较，如果这两个解不同，就去找开始不同的第一个xi，然后设法用贪心解的这个xi去代换最优解的那个xi，并证明最优解在分量代换前后的总效益值无任何变化。反复进行这种代换，直到新产生的最优解与贪心解完全一样，从而证明了贪心解就是最优解。,最优解的证明,定理3.1如果p1/w1p2/w2pn/wn，则算法GREEDY-KNAPSACK对于给定的背包问题实例生成一个最优解。证明：设X=(x1,xn)是GREEDY-KNAPSACK算法所生成的解。如果所有的xi等于1，显然这个解就是最优解。否则，设j是使xj!=1的最小下标。由算法可知，对于1ij,xj=1;对于jM，这与Y是可行解矛盾。若yk=xk，与假设yk!=xk矛盾，故只有ykj，若ykxk=0，则wiyiM,这与Y是可行解矛盾。因此，结论ykxk成立。现在，假定把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)wkpk/wk-(yi-zi)wipi/wipiyi+(zk-yk)wk-(yi-zi)wipk/wk=piyi,1in,1in,kin,1in,kin,1in,k0(是整数)，当且仅当作业i在它的期限截止之前被完成时，则获得pj0的效益。这个问题的一个可行解是这n个作业的一个子集合J，J中的每个作业都能在各自的截止期限之前完成，可行解的效益值是J中这些作业的效益之和pj。具有最大效益值的可行解就是最优解。,带有限期的作业排序实例,例3.2n=4，(p1,p2,p3,p4)=(100,10,15,20)和(d1,d2,d3,d4)=(2,1,2,1)，这个问题可能的可行解和他们的效益值为：,带限期的作业排序算法,为了得到最优解，应制定如何选择下一个作业的量度标准，利用贪心策略，使得所选择的下一个作业在这种量度下达到最优。可把目标函数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（问题的最优解）,带限期的作业排序算法,作业按p1p2pn的次序输入：ProcedureGREEDY_JOB(D,J,n)J1fori2tondoifJi的所有作业都能在他们的截止期限前完成thenJJiendifrepeatEndGREEDY_JOB,定理3.2,对于作业排序问题，用GREEDY_JOB算法所描述的贪心方法总是得到一个最优解证明如下:,定理3.2证明,证明：设J是由贪心方法所选择的作业的集合；设I是一个最优解的作业集合。则IJ，否则J也是最优解。易知：I不是J的真子集，否则I就不是最优解；J也不是I的真子集，这是由贪心法的工作方式所决定的。因此，存在作业a和b，使得a属于J但不属于I；b属于I但不属于J。设a是使得a属于J但不属于I的一个具有最高效益的作业，对于在I中又不在J中的所有作业b，都有PaPb。这是因为若Par，则说明r+1k共k-r个作业可以向后延迟一个单位时间来处理，可将这些作业向后移动一个位置，然后把作业i插入到r+1位置，就可得解。,带限期序作业排序的贪心算法,procedureJS(D,J,n,k)integerD(0:n),J(0:n),i,k,n,rD(0)J(0)0;k1;J(1)1;fori2tondork;whileD(J(r)D(i)andD(J(r)rdorr-1;repeatifD(J(r)D(i)andD(i)rthenforiktor+1by1doJ(i+1)J(i)repeatJ(r+1)i;kk+1；endifrepeatEndJS,找到插入位置,检查插入的可能性,插入值,对于带限期序作业排序的贪心算法JS有两个赖以测量其复杂度的参数，即作业数n和包含在解中的作业数s。内层的while循环至多循环k次，插入作业i要执行时间为O(k-r)，外层for循环共执行(n-1)次。如果s是k的终值，即s是最后所得解的作业数，则JS算法所需要的总时间为O(sn)。由于sn，所以JS算法的时间复杂度为O(n2)。,带限期序作业排序的贪心算法,一种更快的作业排序算法,通过使用不相交集合的UNION与FIND算法以及使用一个不同的方法来确定部分解的可行性，可以将该问题的计算时间由O(n2)降到接近于O(n)。规则是：若还没有给作业i分配处理时间，则分配给它时间片a-1,a,其中a应尽量取大且时间片a-1,a是空的。若正被考虑的新作业不存在这样的a，这个作业就不能计入解中。,一种更快的作业排序算法(续),例：设n=5,(p1,p5)=(20,15,10,5,1)和（d1,d5)=(2,2,1,3,3),作业排序的一个更快算法,procedureFJS(D,n,b,J,k)/假定p1p2pn,b=minn,maxD(i)Integerb,D(n),J(n),F(0:b),P(0:b)fori=0tondoF(i)=i;P(i)=-1repeatk=0fori=1tondoj=FIND(min(n,D(i)ifF(j)0thenk=k+1;J(k)=iL=FIND(F(j)-1);callUNION(L,j)F(j)=F(L)endifrepeatendFJS,查看实例,课后思考题,0/1背包问题：在杂货店比赛中你获得了第一名，奖品是一车免费杂货。店中有n种不同的货物。规定从每种货物中最多只能拿一件，车子的容量为c，物品i需占用wi的空间，价值为pi。你的目标是使车中装载的物品价值最大。当然，所装货物不能超过车的容量，且同一种物品不得拿走多件。如何选择量度标准才能找到最优解？若n=2,w=100,10,10,p=20,15,15,c=105。证明利用价值贪心准则时，所得结果是否是最优解？,3.4最优归并模式,第二章中学习了如何用分治法将两个分别包含n个和m个记录的已分类文件在O(n+m)时间内归并成一个包含(n+m)个记录的分类文件。下面是两种将4个文件进行归并的方法。不同的配对法要求不同的计算时间。,什么是归并模式,给出n个文件，则由许多种把这些文件成对地归并成一个单一分类文件的方法。不同的配对方法要求不同的计算时间问题的关键是：确定一个把n个已分类文件归并在一起的最优方法（即需要最少的比较的方法）,X1，X2和X3是各自有30个记录、20个记录和10个记录的三个已分类文件。归并X1和X2需要50次记录移动，再与X3归并则还要60次移动，其所需要的记录移动次数总量为110。如果首先归并X2和X3，需要30次移动，然后再归并X1，需要60次移动，则所要移动记录的总量为90。因此，第二个归并模式比第一个要好。,例3.5,最优归并模式的实现,由于归并一个具有n个记录的文件和一个具有m个记录的文件可能需要m+n次记录移动，因此对于量度标准的一种很明显的选择是：每一步都归并尺寸比较小的两个文件。例如有五个文件长度分别是(F1,F2,F5)=(20,30,10,5,30),二元归并树,二路归并模式,上面所描述的归并模式称为二路归并模式。二路归并模式可以用二元归并树来表示。二元归并树中叶结点被画成方块，表示五个已知的文件。这些结点称为外部结点。剩下的结点被画成圆圈，称为内部结点。每个内部结点恰好有两个儿子，表示它是将两个儿子所表示的文件归并在一起而得到的文件。每个结点中的数字都是那个结点所表示文件的长度（即记录数）。,最优归并模式的实现,带权外部路径长度如果di表示从根到代表文件Fi的外部节点的距离，qi表示Fi的长度，则这棵二元归并树的记录移动总量是：diqi这个和数叫做这棵树的带权外部路径长度一个最优二路归并模式与一棵具有最小外部路径的二元树相对应。,i=1,n,二元归并树算法,二元归并树算法把n个树的表L作为输入。树中的每一个结点有三个信息段(LCHILD,RCHILD,WEIGHT)。起初，L中的每一棵树正好有一个结点。这个结点是一个外部结点，而且其LCHILD和RCHILD信息段为0，而WEIGHT是要归并的n个文件之一的长度。算法运行期间，对于L中的任何一棵具有根结点T的树，WEIGHT(T)表示要归并的文件的长度。WEIGHT(T)=树T中外部结点的长度和。,二元归并树算法,procedureTREE(L,n)fori1ton-1docallGETNODE(T)LCHILD(T)LEAST(L)RCHILD(T)LEAST(L)WEIGHT(T)WEIGHT(LCHILD(T)+WEIGHT(RCHILD(T)callINSERT(L,T)repeatreturn(LEAST(L)EndTREE,每个节点有三个信息：LCHILD,RCHILD,WEIGHT,构造一个新结点,找出L中一棵具有最小WEIGHT的树，并删除,把根为T的树插入到表L中,二元归并树算法的实例,例：L最初有6个文件，长度分别为：2,3,5,7,9,13。,2,3,5,5,10,13,23,7,9,16,39,二元归并树算法的计算时间,时间分析：1)循环体：n-1次2)L以有序序列表示LEAST(L):(1)INSERT(L,T):(n)总时间：(n2)3)L以min-堆表示LEAST(L):(logn)INSERT(L,T):(logn)总时间：(nlogn),最优解证明,定理3.4若L是最初包含n（1）个单个结点的树，这些树有WEIGHT值为(q1,q2,qn)，则算法TREE对于具有这些长度的n个文件生成一棵最优的二元归并树。,最优解的证明,证明：用归纳法证明当n=1时，返回一棵没有内部结点的树。定理得证。假定算法对所有的(q1,q2,qm)，1mn,生成一棵最优二元归并树。对于n,假定q1q2qn,则q1和q2将是在for循环的第一次迭代中首先选出的具有最小WEIGHT值的两棵树。如图所示，T是由这样的两棵树构成的子树：,最优解的证明,设T是一棵对于(q1,q2,qn)的最优二元归并树。设P是T中距离根最远的一个内部结点。若P的两棵子树不是q1和q2，则用q1和q2代换P当前的子树而不会增加T的带权外部路径长度。故，T应是最优归并树中的子树。在T中用一个权值为q1q2的外部结点代换T，得到的是一棵关于(q1q2,qn)最优归并树T”。而由归纳假设，在用权值为q1q2的外部结点代换了T之后，过程TREE将针对(q1q2,qn)得到一棵最优归并树。将T带入该树，根据以上讨论，将得到关于(q1,q2,qn)的最优归并树。故，TREE生成一棵关于(q1,q2,qn)的最优归并树。,3.5最小生成树,1.问题的描述生成树：设G=(V,E)是一个无向连通图。如果G的生成子图T=(V,E)是一棵树，则称T是G的一棵生成树(spanningtree)2.最小生成树:贪心策略度量标准：选择能使迄今为止所计入的边的成本和有最小增加的那条边。Prim算法Kruskal算法,Prim算法,策略：使得迄今所选择的边的集合A构成一棵树；对将要计入到A中的下一条边(u,v)，应是E中一条当前不在A中且使得A(u,v)也是一棵树的最小成本边。,Prim算法,Kruskal算法,策略：（连通）图的边按成本的非降次序排列，下一条计入生成树T中的边是还没有计入的边中具有最小成本、且和T中现有的边不会构成环路的边。,Kruskal算法,3.6单源点最短路径,什么是单源点最短路径已知一个n结点的有向图G=(V,E)和边的权函数c(e)，求由G中某指定结点v0到其他各个结点的最短路径。,v0,v2,v1,v3,v4,v5,20,45,50,10,15,15,20,10,35,30,3,贪心策略求解,1)度量标准量度的选择：迄今已生成的所有路径长度之和为使之达到最小，其中任意一条路径都应具有最小长度：假定已经构造了i条最短路径，则下一条要构造的路径应是下一条最短的路径。处理规则：按照路径长度的非降次序依次生成从结点v0到其它各结点的最短路径。例：v0v2v0v2v3v0v2v3v1v0v4,贪心策略求解,2)贪心算法设S是已经对其生成了最短路径的结点集合（包括v0)。对于当前不在S中的结点w，记DIST(w)是从v0开始，只经过S中的结点而在w结束的那条最短路径的长度。则有，,贪心策略求解,如果下一条最短路径是到结点u，则这条路径是从结点v0出发在u处终止，且只经过那些在S中的结点,即由v0至u的这条最短路径上的所有中间结点都是S中的结点:设w是这条路径上的任意中间结点，则从v0到u的路径也包含了一条从v0到w的路径，且其长度小于从v0到u的路径长度。v0,s1,s2,w,sm-1,u均在S中根据生成规则：最短路径是按照路径长度的非降次序生成的，因此从v0到w的最短路径应该已经生成。从而w也应该在S中。故,不存在不在S中的中间结点。所生成的下一条路径的终点u必定是所有不在S内的结点中且具有最小距离DIST(u)的结点。,产生最短路径的贪心方法,选出了结点u并生成了从v0到u的最短路径之后，结点u就成为S中的一个成员。此时，那些从v0开始，只通过S中的结点并且在S外的结点w处结束的最短路径