《算法分析与设计贪心法ppt课件.ppt》由会员分享，可在线阅读，更多相关《算法分析与设计贪心法ppt课件.ppt（63页珍藏版）》请在三一文库上搜索。
1、第三章 贪心方法,什么是贪心方法 背包问题 带有期限的作业排序 最优归并模式 最小生成树 单源点最短路径,3.1 什么是贪心方法,某一问题的n个输入,该问题的一种解（可行解）,是A的一 个子集,满足一定 的条件,约束条件,目标函数,取极值,最优解,3.1 什么是贪心方法,根据题意，选取一种量度标准，然后按量度标准对n个输入排序，按顺序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最优解加在一起不能产生一个可行解，则不把此输入加到这部分解中，这种能够得到某种量度意义下的最优解的分级处理方法就是贪心方法。,量度标准,量度标准意义下的部分最优解,原问题的 n 个输入,排序后的 n 个
2、输入,A(j),贪心方法的抽象化控制,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放入背包就会得到
3、pixi的效益(0xi1, 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
5、)=(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
6、, p1/w1 )=(24/15,15/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) endif End GREEDY-KNAPSACK,
7、将解向量X初始化为0 Cu为背包的剩余容量,只放物品i 的一部分,预先将物品按pi/wi比值的非增次序排序,最优解的证明,基本思想 把这个贪心解与任一最优解相比较，如果这两个解不同，就去找开始不同的第一个xi，然后设法用贪心解的这个xi去代换最优解的那个xi ，并证明最优解在分量代换前后的总效益值无任何变化。反复进行这种代换，直到新产生的最优解与贪心解完全一样，从而证明了贪心解就是最优解。,最优解的证明,定理3.1 如果p1/w1 p2/w2 pn/wn，则算法GREEDY-KNAPSACK对于给定的背包问题实例生成一个最优解。 证明：设X=(x1,xn )是GREEDY-KNAPSACK算法
8、所生成的解。如果所有的xi 等于1，显然这个解就是最优解。否则，设j是使xj !=1的最小下标。 由算法可知，对于1ij , xj =1; 对于jin , xj =0 ; 对于i=j ，0xj1。,最优解的证明,假设X不是最优解，则必定存在一个最优解Y= (y1,yn)，使得piyi pixi 。假定wiyi =M，设k是使得 yk!=xk的最小下标，则可以推出结论ykxk，则有wiyi M，这与Y是可行解矛盾。若yk=xk，与假设yk!=xk 矛盾，故只有ykxk成立。,若kj，若ykxk =0 ，则wiyi M,这与Y是可行解矛盾。因此，结论ykxk成立。 现在，假定把 yk 增加到 xk
9、，那么必须从(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/wi piyi +(zk-yk)wk -(yi-zi)wipk/wk = piyi,1in,1in,kin,1in,kin,1in,kin,1in,kin,所以pizi piyi 成立,最优解的证明,若pizi piyi ，则Y不可能是最优解。
10、 若pizi =piyi ，同时Z=X，则X就是最优解； 若pizi =piyi ， 但Z!=X，则重复上面的讨论，或者证明Y不是最优解，或者把Y转换成X，从而证明了X也是最优解。证毕。,课后思考题,找零钱问题：一个小孩买了价值为33美分的糖，并将1美元的钱交给售货员。售货员希望用数目最少的硬币找给小孩。假设提供了数目不限的面值为25美分、10美分、5美分、及1美分的硬币。使用贪心算法求解最优结果。并证明找零钱问题的贪心算法是否总能产生具有最少硬币数的零钱。 考虑假设售货员只有数目有限的25美分，10美分，5美分和1美分的硬币，给出一种找零钱的贪心算法。,3.3 带有限期的作业排序,问题描述
11、假定只能在一台机器上处理n个作业，每个作业均可在单位时间内完成；又假定每个作业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将被舍
13、弃。 故最后的J=1,4，最终效益值120（问题的最优解）,带限期的作业排序算法,作业按p1 p2 pn的次序输入： Procedure GREEDY_JOB(D,J,n) J1 for i2 to n do if Ji的所有作业都能在他们的截止期限前完成 then JJi endif repeat End GREEDY_JOB,定理3.2,对于作业排序问题，用GREEDY_JOB算法所描述的贪心方法总是得到一个最优解 证明如下:,定理3.2 证明,证明： 设J是由贪心方法所选择的作业的集合；设I是一个最优解的作业集合。则 IJ，否则J也是最优解。 易知：I不是J的真子集，否则I就不是最优解；
14、J也不是I的真子集，这是由贪心法的工作方式所决定的。因此，存在作业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的一个具有最高效益的作业。,由于PaP
15、b,显然，转换后I的效益值没有减少。 重复应用上述转换，使I在不减少效益值的情况下转换成J，因此，J也必定是最优解。 证毕。,如何判断J的可行性,方法一： 检验J中作业所有可能的排列，对于任一种次序排列的作业排列，判断这些作业是否能够在其期限前完成，也即若J中有k个作业，则将要检查k!个序列 方法二： 检查J中作业的一个特定序列就可判断J的可行性：对于所给出的一个排列i1i2ik,由于作业ij完成的最早时间是j，因此只要判断出排列中的每个作业dijj，就可得知是一个允许的调度序列，从而J是一个可行解。反之，如果排列中有一个dijj,则将是一个行不通的调度序列，因为至少作业ij不能在其期限之前完
16、成。 这一检查过程可以只通过检验J中作业的一种特殊的排列：按照作业期限的非降次序排列的作业序列即可完成。,可行解的确定,定理3.3: 设J是k个作业的集合，=i1,i2,ik是J中作业的一种排列，它使得di1di2dik。J是一个可行解，当且仅当J中的作业可以按照的次序而又不违反任何一个期限的情况来处理。,定理3.2 证明,证明： （充分性）若J中的作业可以按照的次序而又不违反任何一个期限的情况来处理，则J就是一个可行解。 （必要性）由于J可行，则必存在一种调度序列=r1r2rk，drjj，1j k。 假设 ，则a是使得ra ia的最小下标。,ra,rb= ia,ia,=i1,i2,ik ,
17、di1di2dik,=r1r2rk, drjj，1j k,rb = ia,ra,ia,连续使用这一方法，就可将转换成且不违反任何一个期限。 定理得证。,带限期序作业排序的处理,首先将作业1存入数组J中，然后处理作业2到作业n 假设已处理了i-1个作业，其中有k个作业存入了J(1),J(2)J(k)中，并且D(j(1)D(j(2)D(J(k)，现在开始处理作业i 判断Ji是否可行，只需找出按期限的非降次序插入作业i的位置，插入后有D(J(r) r。 找作业i可能的插入位置：将D(J(k),D(j(k-1),D(J(1)逐个与D(i)比较，直到找到位置r，它使得D(i)D(J(r),且D(i) r
18、，则说明r+1k共k-r个作业可以向后延迟一个单位时间来处理，可将这些作业向后移动一个位置，然后把作业i插入到r+1位置，就可得解。,带限期序作业排序的贪心算法,procedure JS(D,J,n,k) integer D(0:n),J(0:n),i,k,n,r D(0)J(0)0; k1;J(1)1; for i2 to n do rk; while D(J(r)D(i) and D(J(r) r do rr -1; repeat if D(J(r)D(i) and D(i)r then for ik to r+1 by 1 do J(i+1)J(i) repeat J(r+1)i ; k
19、k+1； endif repeat End JS,找到插入位置,检查插入的可能性,插入值,对于带限期序作业排序的贪心算法JS有两个赖以测量其复杂度的参数，即作业数 n 和包含在解中的作业数 s 。内层的while循环至多循环k次，插入作业 i 要执行时间为O(k-r)，外层for循环共执行(n-1)次。 如果s是k的终值，即s是最后所得解的作业数，则JS算法所需要的总时间为O(sn)。由于s n，所以JS算法的时间复杂度为O(n2)。,带限期序作业排序的贪心算法,一种更快的作业排序算法,通过使用不相交集合的UNION与FIND算法以及使用一个不同的方法来确定部分解的可行性，可以将该问题的计算时
20、间由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),作业排序的一个更快算法,procedure FJS(D,n,b,J,k) /假定p1p2pn , b=minn,maxD(i) Integer b,D(n),J(n),F(0:b),P(0:b) for i=0 to n do F(i)=i; P(i)=-1 rep
21、eat k=0 for i=1 to n do j=FIND(min(n,D(i) if F(j)0 then k=k+1;J(k)=i L=FIND(F(j)-1); call UNION(L, j) F(j)=F(L) endif repeat end FJS,查看实例,课后思考题,0/1背包问题：在杂货店比赛中你获得了第一名，奖品是一车免费杂货。店中有n 种不同的货物。规定从每种货物中最多只能拿一件，车子的容量为c，物品i 需占用wi 的空间，价值为pi。你的目标是使车中装载的物品价值最大。当然，所装货物不能超过车的容量，且同一种物品不得拿走多件。如何选择量度标准才能找到最优解？ 若n=
22、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个记录的
23、三个已分类文件。 归并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),二元归并树,二路归并模式,上面所描述的归并模式称为二路归并模式。二路归并模
24、式可以用二元归并树来表示。 二元归并树中叶结点被画成方块，表示五个已知的文件。这些结点称为外部结点。 剩下的结点被画成圆圈，称为内部结点。每个内部结点恰好有两个儿子，表示它是将两个儿子所表示的文件归并在一起而得到的文件。 每个结点中的数字都是那个结点所表示文件的长度（即记录数）。,最优归并模式的实现,带权外部路径长度 如果di表示从根到代表文件Fi的外部节点的距离，qi表示Fi的长度，则这棵二元归并树的记录移动总量是： diqi 这个和数叫做这棵树的带权外部路径长度 一个最优二路归并模式与一棵具有最小外部路径的二元树相对应。,i=1,n,二元归并树算法,二元归并树算法把n个树的表L作为输入。树
25、中的每一个结点有三个信息段(LCHILD,RCHILD,WEIGHT)。 起初，L中的每一棵树正好有一个结点。这个结点是一个外部结点，而且其LCHILD和RCHILD信息段为0，而WEIGHT是要归并的n个文件之一的长度。 算法运行期间，对于L中的任何一棵具有根结点T的树， WEIGHT(T)表示要归并的文件的长度。 WEIGHT(T)=树T中外部结点的长度和。,二元归并树算法,procedure TREE(L,n) for i1 to n-1 do call GETNODE(T) LCHILD(T)LEAST(L) RCHILD(T)LEAST(L) WEIGHT(T)WEIGHT(LCHI
26、LD(T) +WEIGHT(RCHILD(T) call INSERT(L,T) repeat return (LEAST(L) End TREE,每个节点有三个信息：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): (
27、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值的两棵树。如图所
28、示，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)的最
29、优归并树。,3.5 最小生成树,1. 问题的描述 生成树：设G=(V,E)是一个无向连通图。如果G的生 成子图T=(V,E)是一棵树，则称T是G的一棵 生成树(spanning tree) 2. 最小生成树: 贪心策略 度量标准：选择能使迄今为止所计入的边的成本和有最小 增加的那条边。 Prim算法 Kruskal算法,Prim算法,策略： 使得迄今所选择的边的集合A构成一棵树；对将要计入到A中的下一条边(u,v)，应是E中一条当前不在A中且使得A(u,v)也是一棵树的最小成本边。,Prim算法,Kruskal算法,策略： （连通）图的边按成本的非降次序排列，下一条计入生成树T中的边是还没有计
30、入的边中具有最小成本、且和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到其它各结点的最短路径
31、。 例： v0v2 v0v2v3 v0v2v3v1 v0v4,贪心策略求解,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中 根据生成
32、规则：最短路径是按照路径长度的非降次序生成的，因此从v0到w的最短路径应该已经生成。从而w也应该在S中。 故,不存在不在S中的中间结点。 所生成的下一条路径的终点u必定是所有不在S内的结点中且具有最小距离DIST(u)的结点。,产生最短路径的贪心方法,选出了结点u并生成了从v0到u的最短路径之后，结点u就成为S中的一个成员。 此时，那些从v0开始，只通过S中的结点并且在S外的结点w处结束的最短路径可能会减小。 如果长度改变了，则它必定是由一条从v0开始，经过u然后到w的更短路径所造成的。 其中从v0到u的路径是一条最短路径，从u到w的路径是边，于是这条路径的长度就是：DIST(u)+c(u,w
33、),生成最短路径的贪心算法,Procedure SHORTEST-PATHS(v,COST,DIST,n) boolean S(1:n);real COST(1:n,1:n),DIST(1:n) integer u,v,n,num,i,w for i1 to n do s(i)0;DIST(i)COST(v,i) repeat S(v)1;DIST(v)0 for num2 to n-1 do 选取结点u, 它使得DIST(u)= min S(w)=0 DIST(w), s(u)1 for 所有S(w)=0的结点w do DIST(w)min(DIST(w),DIST(u)+COST(u,w)
34、 repeat repeat End SHORTEST-PATHS,将集合S初始化为空， 初始化DIST数组,确定从结点v开始出发的n-1条路,当有更小最短距离时，修改距离,结点v计入S,结点u计入S,算法实例,求下图中v1到其余各结点的最短路径,0 20 50 30 0 25 70 0 40 25 50 0 55 0 10 70 0 50 0,算法实例,SHORTEST-PATHS执行踪迹,1、多机调度问题：设有n 项独立的作业1,2, n,由m 台相同的机器加工处理。作业i 所需要的处理时间为ti。约定：任何一项作业可在任何一台机器上处理，但未完工前不准中断处理；任何作业不能拆分成更小的子作业。多机调度问题要求给出一种调度方案，使所给的n 个作业在尽可能短的时间内由m 台机器处理完。利用贪心策略，设计算法解决多机调度问题，并计算其时间复杂度。 2、设有7 项独立的作业1,2,3,4,5,6,7,要由三台机器M1, M2 ,M3 处理。各个作业所需要的处理时间分别为 2,14,4,16,6,5,3。利用你设计的贪心算法，安排作业的处理顺序使得机器处理作业的时间最短。,课 后 思 考 题,