算法设计与分析(王佳)04贪心算法

第六章贪心算法,主要内容:,6.1一般方法,6.2背包问题,6.3带时限的作业排序,6.4最佳归并模式,6.5最小生成树,6.7多机调度问题,6.6单源点最短路径,引言,找零钱问题贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。,最优化问题（optimizationproblems）是指这样一类问题，问题给定某些约束条件（constraint），满足这些约束条件的问题解称为可行解（feasiblesolution）。通常满足约束条件的解不是惟一的。为了衡量可行解的好坏，问题还给出了某个数值函数，称为目标函数（objectivefunction），使目标函数取最大（或最小）值的可行解称为最优解（optimalsolution）。,贪心法是通过分步决策（stepwisedecision）的方法来求解问题的。贪心法每一步上用作决策依据的选择准则被称为最优量度标准（optimizationcriterion）。在根据最优量度标准选择分量的过程中，还需要使用一个可行解判定函数。贪心策略并不是从整体上加以考虑的，它所做出的选择只是当前看似最佳选择，必须进一步证明该算法最终导致问题的一个整体最优解。,Greedy算法的基本思想求解最优化问题的算法包含一系列步骤每一步都有一组选择作出在当前看来最好的选择希望通过作出局部优化选择达到全局优化选择Greedy算法不一定总产生优化解Greedy算法是否产生优化解，需严格证明Greedy算法产生优化解的条件Greedy-choice-propertyOptimalsubstructure,Greedy算法的基本概念,Greedy选择性,Greedy选择性若一个优化问题的全局优化解可以通过局部优化选择得到，则该问题称为具有Greedy选择性.一个问题是否具有Greedy选择性需证明,若一个优化问题的优化解包含它的子问题的优化解，则称其具有优化子结构,优化子结构,与动态规划方法的比较,动态规划方法可用的条件优化子结构子问题重叠性子问题空间小Greedy方法可用的条件优化子结构Greedy选择性可用Greedy方法时，动态规划方法可能不适用可用动态规划方法时，Greedy方法可能不适用,证明算法所求解的问题具有优化子结构证明算法所求解的问题具有Greedy选择性证明算法确实按照Greedy选择性进行局部优化选择,Greedy算法正确性证明方法,【程序61】贪心法SolutionTypeGreedy(STypea,intn)SolutionTypesolution=;for(inti=0;i0，pi0，0in。所谓背包问题是指求一种最佳装载方案，使得收益最大。所以，背包问题是现实世界一个常见的最优化问题。两类背包问题:如果每一件物品不能分割，只能作为整体或者装入背包，或者不装入，称为0/1背包问题；如果物品是可以分割的，也就是允许将其中的一部分装入背包为一般背包问题或简称背包问题。,6.2.2贪心法求解,背包问题背包问题的解可以表示成一个n-元组：X=(x0,x1,xn1)，0xi1，0icuthenexitendifX(i)1cucu-W(i)repeatifinthenX(i)cu/W(i)endifendGREEDY-KNAPSACK,4.最优解的证明,即证明：由第三种策略所得到的贪心解是问题的最优解。最优解的含义：在满足约束条件的情况下，使目标函数取极（大或小）值的可行解。贪心解是可行解，故只需证明：贪心解可使目标函数取得极值。,证明的基本思想：将此贪心解与（假设中的）任一最优解相比较。如果这两个解相同，则显然贪心解就是最优解。如果这两个解不同，就设法去找两者开始不同的第一个分量位置i，然后设法用贪心解的这个xi去替换最优解对应的分量，并证明最优解在分量代换前后总的效益值没有任何变化(且不违反约束条件)。然后比较二者。若还不同，则反复进行代换，直到代换后产生的“最优解”与贪心解完全一样。在上述代换中，最优解的效益值没有任何损失，从而证明贪心解的效益值与代换前后最优解的效益值相同。即，贪心解如同最优解一样可取得目标函数的最大/最小值。从而得证：该贪心解即是问题的最优解。,定理6.1如果p1/w1p2/w2pn/wn,则算法GREEDY-KNAPSACK对于给定的背包问题实例生成一个最优解。证明：设X=(x1,x2,xn)是GREEDY-KNAPSACK所生成的贪心解。如果所有的xi都等于1,则显然X就是问题的最优解。否则，设j是使xi1的最小下标。由算法的执行过程可知，xi=11ij,0xj1xi=0jin,假设Y是问题的最优解：Y=(y1,y2,yn)且有：若XY，则X就是最优解。否则，X和Y至少在1个分量上存在不同。设k是使得ykxk的最小下标，则有ykxk。可分以下情况说明：a)若k0的收益。问题要求得到一种作业调度方案，该方案给出作业的一个子集和该作业子集的一种排列，使得若按照这种排列次序调度作业运行，该子集中的每个作业都能如期完成，并且能够获得最大收益。也就是说这种作业调度是最优的。,6.3.2贪心法求解,例62设有4个作业，每个作业的时限为(d0,d1,d2,d3)=(2,1,2,1),收益为(p0,p1,p2,p3)=(100,10,15,27)。,6.3带有限期的作业排序,1.问题描述假定在一台资源无约束的机器上处理n个作业，每个作业均可在单位时间内完成；同时每个作业i都有一个截至期限di0,当且仅当作业i在其截至期限以前被完成时，则获得pi0的效益。问题：求这n个作业的一个子集J，其中的所有作业都可在其截至期限内完成。J是问题的一个可行解。可行解J中的所有作业的效益之和是，具有最大效益值之和的可行解是该问题的最优解。,分析：目标函数：约束条件：所有的作业都应在其期限之前完成如果所有的作业都能在其期限之内完成则显然可以获得当前最大效益值；否则，将有作业无法完成决策应该执行哪些作业，以获得最大可能的效益值。,例6.2n=4，(p1，p2，p3，p4)(100,10,15,20)(d1，d2，d3，d4)(2,1,2,1)。可行解如下表所示：问题的最优解是。所允许的处理次序是：先处理作业4再处理作业1。,1.带有限期的作业排序算法,1)度量标准的选择以目标函数作为量度。量度标准：下一个要计入的作业将是使得在满足所产生的J是一个可行解的限制条件下让得到最大增加的作业。处理规则：按pi的非增次序来考虑这些作业；同时因受作业期限的限制，必须为作业安排合理的处理顺序。,例：例6.2求解首先令J=,p1p4p3p2作业1具有当前的最大效益值，且1是可行解，所以作业1计入J（一般情况下，假定至少有一个时间单元）。在剩下的作业中，作业4具有最大效益值，且1,4也是可行解，故作业4计入J，即J=1,4；考虑1,3,4和1,2,4均不能构成新的可行解，作业3和2将被舍弃。故，最后的J=1,4，加工顺序是：4，1。最终效益值120（问题的最优解）,2)作业排序算法的概略描述算法6.3procedureGREEDY-JOB(D,J,n)/作业按p1p2pn的次序输入，它们的期限值D(i)1,1in,n1。J是在它们的截止期限前完成的作业的集合/J1/用作业序号代表作业/fori2tondoifJi的所有作业能在它们的截止期限前完成thenJJiendifrepeatendGREEDY-JOB,2.最优解证明,定理6.2算法6.3对于作业排序问题的解是问题的一个最优解证明：设J是由算法6.3所得的作业集合贪心解，I是一个最优解的作业集合。若I=J，则J就是最优解；否则，则至少存在两个作业a和b，使得aJ且,bI且。（为什么）并设a是这样的一个具有最高效益值的作业(由算法的处理规则可得：对于在I中而不在J中的作业所有b，有：papb),设SJ和SI分别是J和I的可行的调度表。因为J和I都是可行解，故这样的调度表一定存在；设i是既属于J又属于I地一个作业，并设i在调度表SJ中的调度时刻是t，t+1，而在SI中的调度时刻是t，t+1。在SJ和SI中作如下调整：若tt，则将SJ中在t，t+1时刻调度的那个作业（如果有的话）与i相交换。如果J中在t，t+1时刻没有作业调度，则直接将i移到t，t+1调度。新的调度表也是可行的。,若tt，则在SI中作类似的调换，即将SI中在t，t+1时刻调度的那个作业（如果有的话）与i相交换。如果I中在t，t+1时刻没有作业调度，则直接将i移到t，t+1调度。同样，新的调度表也是可行的。对J和I中共有的所有作业作上述的调整。设调整后得到的调度表为SJ和SI，则在SJ和SI中J和I中所有的共有作业将在相同时间被调度。,设a在SJ中的调度时刻是ta,ta+1，b是SI中该时刻调度的作业，则有papb（为什么？）。在SI中，去掉作业b，而去调度作业a，得到的是作业集合I=（I-b）a的一个可行的调度表，且I的效益值不小于I的效益值。而I中比I少了一个与J不同的作业。重复上述的转换，可使I在不减效益值的情况下转换成J。从而J至少有和I一样的效益值。所以J也是最优解。证毕。,3.如何判断J的可行性,方法一：枚举法，检验J中作业所有可能的排列，对于任一种次序排列的作业序列，判断这些作业是否能够在其期限前完成若J中有k个作业，则将要检查k!个序列判断策略：对于一个给定作业处理序列i1i2ik,由于作业ij完成的最早时间是j，因此只要判断出排列中的每个作业的期限有dijj，就可得知是一个允许的调度序列，从而J是一可行解。反之，如果排列中有一个作业有dijj,则将是一个行不通的调度序列，因为至少作业ij不能在其期限之前完成。,方法二：检查J中作业的一个特定序列就可判断J的可行性：这一特定序列是按照作业期限的非降次序排列的作业序列,定理6.3设J是k个作业的集合，i1i2ik是J中作业的一种排列，它使得di1di2dik。则J是一个可行解，当且仅当J中的作业可以按照的次序而又不违反任何一个期限的情况来处理。,证明：如果J中的作业可以按照的次序而又不违反任何一个作业期限的情况来处理，则J是一个可行解现证若J是一个可行解，是否代表一个可行的调度序列？J是可行解必存在一可行的调度序列r1r2rk，使得drjj,1jk。若，则即是可行的调度序列。否则，令a是使得raia的最小下标（如下图）,i1i2iaicikr1r2rarbrk,设rb=ia。则有：ba且dradrb故，在中调换ra与rb，所得的新序列s1s2sk的处理次序不违反任何一个期限，而中位置a及a之前的作业均与相同。重复上述过程，则可将转换成且不违反任何一个期限，故是一个可行的调度序列故定理得证。,4.带有限期的作业排序算法的实现,对当前正在考虑的作业j，按限期大小采用一种“插入排序”的方式，尝试将其“插入”到一个按限期从小到大顺序构造的作业调度序列中，以此判断是否能够将作业j合并到当前部分解J中：如果有合适的插入位置，则插入到序列中，形成新的可行解序列。否则，舍弃该作业。具体如下：假设n个作业已经按照效益值从大到小的次序，即p1p2pn的顺序排列好，每个作业可以在单位时间内完成，并具有相应的时间期限di；且至少有一个单位时间可以执行作业首先，将作业1计入部分解J中，此时J是可行的；然后，依次考虑作业2到n。假设已经处理了i-1个作业，其中有k个作业计入了部分解J中：J(1),J(2),J(k)，且有D(J(1)D(J(2)D(J(k),对当前正在考虑的作业i,将D(i)依次和D(J(k),D(J(k-1),，D(J(1)相比较。若1）找到位置q：使得D(i)D(J(l)，qlk，且D(J(q)D(i)qD(i)此时，若D(J(l)l,qlk,即q位置之后的所有作业均可推迟一个单位时间执行，而又不违反各自的执行期限。执行“移位”处理：将q位置之后的所有作业后移一位，将作业i插入到位置q1处，从而得到一个包含k+1个作业的新的可行解。2）若找不到这样的位置q，作业i将被舍弃。对i之后的其它作业重复上述过程，直到n个作业处理完毕。最后J中所包含的作业集合是此时算法的贪心解，根据定理3.2,也是问题的最优解。,算法6.4带有限期和效益的单位时间的作业排序贪心算法procedureJS(D,J,n,k)/n1。作业已按p1p2pn的顺序排序。D(1),D(n)是期限值,J(i)是最优解中的第i个作业，1ik。终止时，D(J(i)D(J(i1)，1ik/integerD(0:n),J(0:n),i,k,n,rD(0)J(0)0/初始化/k1;J(1)1/计入作业1/fori2tondo/按p的非增次序考虑作业i。找i的插入位置并检查可行性/rkwhileD(J(r)D(i)andD(J(r)rdo/D(J(r)r/rr-1/这样的r有D(J(r)r/repeatIfD(J(r)D(i)andD(i)rthen/把i插入到J中/foriktor+1by-1doJ(i+1)J(i)/将插入点的作业后移一位/repeatJ(r+1)i;kk+1/将i计入J中/endifrepeatendJS,另一退出条件是D(J(r)D(i)而D(J(r)=r,计算时间分析fori2tondo将循环n-1次rkwhileD(J(r)D(i)andD(J(r)rdo至多循环k次，k是当前计入J中的作业数1kn-1rr-1repeatIfD(J(r)D(i)andD(i)rthenforiktor+1by-1do循环k-r次，r是插入点之前的位置最坏情况下循环k次，插入到最头部J(i+1)J(i)repeatJ(r+1)I;kk+1endifrepeat设s是最终计入J中的作业数，则算法JS所需要的总时间是O(sn)。sn，故最坏情况：TJS=(n2)，特例情况：pi=di=n-i+1,1in最好情况：TJS=(n)，特例情况：pi=n-i+1,di=i,1in,6.一种“更快”的作业排序问题判定作业i可行的另一种方法：对于作业i，若还没有给i分配处理时间，则分配给它时间片-1,，其中是尽量取大且-1,为空的时间片。即：尽量推迟作业i的处理时间。这样在安排作业处理次序时不必每有一个作业加入就需移动J中已有的作业。如果不存在这样的时间片，作业i被舍弃。（如何按照该方法改进算法？）使用不相交集合的UNION和FIND算法（见数据结构相关章节），可以将JS的计算时间降低到数量级接近(n)。（略）,【程序63】带时限作业排序的贪心算法voidGreedyJob(intd,SetX,intn)/前置条件：p0p1,pn-1X=0;for(inti=1;in;i+)if(集合Xi中作业都能在给定时限内完成)X=Xi;,6.3.3算法正确性,定理62程序62的贪心算法对于带时限作业排序问题将得到最优解。,6.3.4可行性判定,定理63X=（x0,x1,xk）是k个作业的集合，=（0,1,k）是X的一种特定排列，它使得，其中，是作业j的时限。X是一个可行解当且仅当X中的作业能够按次序调度而不会有作业超期。,6.3.5作业排序贪心算法,定理63提供了一种高效的可行解判定方法。使得在按最优量度标准，即按作业收益的非增次序选择下一个作业后，可以有效地判定是否可将该作业加入已生成的部分解向量X。,【程序64】带时限的作业排序程序intJS(int*d,int*x,intn)/设p0p1pn-1intk=0;x0=0;for(intj=1;j=0,6.3.6一种改进算法,本小节将介绍一种带时限作业排序的快速算法，它采用不同于前者的可行解判定方法，可使算法的时间从(n2)减少到接近O(n)。,例63设n=5个作业，作业的时限为:(d0,d1,d2,d3,d4)=(2,2,1,3,3),收益为:(p0,p1,p2,p3,p4)=(20,15,10,5,1)。,【程序65】使用并查集的带时限作业排序intFJS(int*d,int*x,intn)UFSets(n);intb,k=-1,*f=newintn+1;for(inti=0;i=n;i+)fi=i;,for(i=0;in;i+)if(npq(2*n-1);BTNode*p;HNodea,b;for(inti=0;i(wi);a.ptr=p;a.weight=wi;pq.Append(a);,for(i=1;i(a.weight,a.ptr,b.ptr);a.ptr=p;pq.Append(a);pq.Serve(a);returna.ptr;,6.4.3算法正确性,定理64设有n个权值W=w0,w1,wn1作为外结点的权值，构造两路合并树的贪心算法将生成一棵具有最小带权外路径长度的二叉树。,6.5最小代价生成树,6.5.1问题描述,问题一个无向连通图的生成树是一个极小连通子图，它包括图中全部结点，并且有尽可能少的边。一棵生成树的代价是树中各条边上的代价之和。一个网络的各生成树中，具有最小代价的生成树称为该网络的最小代价生成树（minimum-costspanningtree）。,6.5.2贪心法求解,最优量度标准选择使得迄今为止已入选S中边的代价之和增量最小的边克鲁斯卡尔算法的贪心准则是：按边代价的非减次序考察E中的边，从中选择一条代价最小的边e=(u,v)。普里姆算法的贪心准则是：在保证S所代表的子图是一棵树的前提下选择一条最小代价的边e=(u,v)。,【程序67】最小代价生成树的贪心算法ESetTypeSpanningTree(ESetTypeE,intn)/G=(V,E)为无向图ESetTypeS=;intu,v,k=0;ETypee;while(kn-1,6.5.3普里姆算法,【程序68】普里姆算法templatestructENode/带权图的边结点intadjVex;Tw;ENode*nextArc;,templateclassGraphpublic:Graph(intmSize);voidPrim();protected:voidPrim(intk,int*nearest,T*lowcost);ENode*a;intn;,templatevoidGraph:Prim(ints)/公有成员函数int*nearest=newintn,*lowcost=newintn;Prim(s,nearest,lowcost);for(intj=0;jn;j+)cout(nearestj,“j,lowcostj);cout,while(kn-1克鲁斯卡尔算法的时间复杂度为O（eloge）。,6.5.5算法正确性,定理65设图G=（V，E）是一个带权连通图，U是V的一个真子集。若边(u,v)E是所有uU,vV-U的边中权值最小者，那么一定存在G的一棵最小代价生成树T=(V,S)，(u,v)S。这一性质称为MST（minimumspanningtree）性质。,定理66普里姆算法和克鲁斯卡尔算法都将产生一个带权无向连通图的最小代价生成树。,6.6单源最短路径,6.6.1问题描述,单源最短路径问题是：给定带权的有向图G=(V,E)和图中结点sV，求从s到其余各结点的最短路径，其中，s称为源点。,6.6.2贪心法求解,迪杰斯特拉（Dijkstra）算法首先求得长度最短的一条最短路径，再求得长度次短的一条最短路径，依此类推，直到从源点到其它所有结点之间的最短路径都已求得为止。,6.6.3迪杰斯特拉算法,【程序610】迪杰斯特拉算法templateclassMGraphpublic:MGraph(intmSize);voidDijkstra(ints,T*,private:intChoose(int*d,bool*s);T*a;intn;,templateintMGraph:Choose(int*d,bool*s)inti,minpos;Tmin;min=INFTY;minpos=-1;for(i=1;in;i+)if(dimin,templatevoidMGraph:Dijkstra(ints,T*,inSs=true;ds=0;for(i=1;in-1;i+)k=Choose(d,inS);inSk=true;for(j=0;jn;j+)if(!inSj,6.6.4算法正确性,定理67已知带权有向图G=(V,E)，其源点为s，迪杰斯特拉算法使得对所有i，iV-s，di(s,i)，且一旦di=(s,i)，它将不再改变。定理68已知带权有向图G=(V,E)，其源点为s，迪杰斯特拉算法使得对所有结点i和j,iS，jV-S，必有didj。,定理69已知带非负权值的有向图G=(V,E)，路径（s=v0,vi,vk=t）是从s到vk的一条最短路径，viV，0