计算机算法设计与分析：第三章 贪心法

1、第三章 贪心法 3.1 一般方法（原则） 约束条件：问题必须满足的条件。 可行解：若问题有n个输入，而它的解是由这n个输入的某个子集组成，这个子集满足事先给出的约束条件，则该子集称为问题的可行解。 目标函数：为了衡量可行解某方面的优劣，事先给出了一定的标准，这个标准一般以函数的形式给出，称为目标函数。 最优解：使目标函数取极值的可行解称为最优解。 局部可行解和局部最优解。 A(1)A(2)A(n-1)A(n)B1(1)B1(2)B1(m)Bk(1)Bk(2)Bk(m)最优解最优解B1是该问题的是该问题的一个可行解一个可行解B1满足一定满足一定的约束条件的约束条件B2(1)B2(2)B2(m)一

2、类问题有一类问题有n个输入个输入:B1是是A的一个子集的一个子集该问题有该问题有k个可行解个可行解该可行解可使该可行解可使 目目标函数取极值标函数取极值 输入局部解可行解最优解 局部最优解 贪心法方法：首先选取一个度量标准（测度函数）；按度量标准将n个输入排序，并按序一次处理一个输入；这个输入和当前的局部最优解加在一起能成为可行解则加入，否则去掉此输入；重复的过程直到枚举完成或不能再加入输入为止。 面向的问题：应用于最优解的求解，是某种量度意义下是某种量度意义下的最优解的直接分级处理设计技术。的最优解的直接分级处理设计技术。贪贪心方法的抽象化控制Procedure GREEDY(A,n) so

3、lution 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 n种物体和一个可容纳种物体和一个可容纳M M重量的背包，每种重量的

4、背包，每种物体物体i i的重量为的重量为w wi i，假定将物品任意可分，若将物体，假定将物品任意可分，若将物体i i的某一部分的某一部分x xi i放入背包就会得到相应的效益放入背包就会得到相应的效益p pi ix xi i(0 x(0 xi1,pi0) i1,pi0) ，采用怎样的装包方案会使装入背包物，采用怎样的装包方案会使装入背包物品的总效益为最大？品的总效益为最大？ 二、问题的解决 解的表达 （x1，x2，xn） 与概念对应的形式表示： 约束条件 wixi M wi0, 1in 目标函数 pixi 0 xi1, pi0 背包问题例背包问题例(x1, x2, x3)wi xipixi(

5、1, 2/15, 0) 2028.2(1, 0, 1/5)2028(0, 2/3, 1)2031(0, 1, 1/2)2031.5找出其中找出其中4个可行解如：个可行解如：有有3个物品个物品, 即即n=3, 背包能容纳的最大重量为背包能容纳的最大重量为20, 即即M=20物品的价值和重量物品的价值和重量: (p1,p2,p3)=(25,24,15), (w1,w2,w3)=(18,15,10)量度标准选择例量度标准选择例 选效益值为量度标准（注意和目标函数的差别）选效益值为量度标准（注意和目标函数的差别）该标准使得背包每装入一件物品就获得最大可能的效益值增量该标准使得背包每装入一件物品就获得最

6、大可能的效益值增量 可将物品按效益值非增次序排序可将物品按效益值非增次序排序: (p1,p2,p3)=(25,24,15) 按该次序将物品一件件放到背包中按该次序将物品一件件放到背包中, 先装物品先装物品1(效益最大效益最大), 即即x1=1, w1=18; 2,3都不能全放入，衡量后都不能全放入，衡量后2的一部分效益增量最大。的一部分效益增量最大。x2=2/15; 最后得到总效益值为最后得到总效益值为pixi = 25+24*2/15=28.2这是一个非最优解，原因是背包容量消耗过快这是一个非最优解，原因是背包容量消耗过快选容量为量度标准选容量为量度标准 将物品按重量的非降次序排序将物品按重

7、量的非降次序排序: (w3,w2,w1)=(10,15,18)按该次序将物品放到背包中按该次序将物品放到背包中,让容量尽可能慢地被消耗让容量尽可能慢地被消耗先装物品先装物品3, 即即x3=1, w3=10, p3x3 =15; 再装入物品再装入物品2, 因约束条件为因约束条件为wi xi M=20, 所以物品所以物品2只能装只能装入重量为入重量为10的一部分的一部分, 即即x2=10/15=2/3; 最后得到总效益值为最后得到总效益值为pixi =15+24*2/3=31这仍是一个非最优解这仍是一个非最优解, 原因是容量在慢慢消耗的过程中原因是容量在慢慢消耗的过程中, 效益值效益值却没有迅速的

8、增加却没有迅速的增加该标准使得背包每装入一件物品就获得最小可能的容量增量该标准使得背包每装入一件物品就获得最小可能的容量增量将物品按将物品按pi/wi比值的非增次序排序比值的非增次序排序: (p2/w2 , p3/w3 , p1/w1 )=(24/15, 15/10, 25/18)即每一次装入的物品使它占用的每一单位容量获得当前最大的即每一次装入的物品使它占用的每一单位容量获得当前最大的单位效益单位效益先装入物品先装入物品2, 即即x2=1, w2=15, p3x3 =24;再装入物品再装入物品3, 因约束条件为因约束条件为wi xi M=20, 所以物品所以物品3只能装入只能装入重量为重量为

9、5的一部分的一部分, 即即x3=5/10=1/2; 最后得到总效益值为最后得到总效益值为pixi =24+15*1/2=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;X 0 cu Mfor i 1 to n do if (W(i)cu) then exit

10、 endif X(i) 1 cu cu-W(i)repeatif (in) then X(i) cu/W(i)end GREEDY-KNAPSACK将解向量将解向量X初始化为初始化为0cu为背包的剩余容量为背包的剩余容量放入物品放入物品i 的一部分的一部分先将物品按先将物品按pi/wi比值的非增次序排序比值的非增次序排序(降序降序)若物品若物品i的重量大于背包的重量大于背包的剩余容量的剩余容量,则退出循环则退出循环若物品若物品i的重量小于等于背包的剩的重量小于等于背包的剩余容量余容量,则物品则物品i可放入背包内可放入背包内四、最优证明v定理定理3.1: 如果如果p1/w1 p2/w2 pn/w

11、n，则算法，则算法GREEDY-KNAPSACK对于给定的背包问题实例生成对于给定的背包问题实例生成一个最优解。一个最优解。3.3 有限期的作业调度一、问题描述一、问题描述 假定只有一台机器上处理假定只有一台机器上处理n个作业个作业, 每个作业均可在单位时每个作业均可在单位时间内完成间内完成; 又假定每个作业又假定每个作业i都有一个截止期限都有一个截止期限di0(di是整是整数数), 当且仅当作业当且仅当作业i在它的期限截止之前被完成时获得在它的期限截止之前被完成时获得pi0的效益。的效益。 该问题的一个可行解是这该问题的一个可行解是这n个作业的一个子集合个作业的一个子集合J,J中的每个中的每

12、个作业都能在各自的截止期限之前完成作业都能在各自的截止期限之前完成,可行解的效益值是可行解的效益值是J中中这些作业的效益之和这些作业的效益之和pj ，具有最大效益值的可行解就是最具有最大效益值的可行解就是最优解。优解。有有n个作业个作业, n=4, 其效益为其效益为(p1,p2,p3,p4)=(100,10,15,20)其截止期限为其截止期限为(d1,d2,d3,d4)=(2,1,2,1),求该问题的最优解求该问题的最优解有限期的作业排序实例有限期的作业排序实例可行解J处处理顺顺序效益值值pj （1）1100（2）210（3）315（4）420 （1，3） 1, 3或或3, 1 115 （1，

13、2） 2，1 110 （1，4） 4，1 120 （2，3） 2，3 25 （3，4） 4，3 35二、解决方法和必要的条件（可行否）二、解决方法和必要的条件（可行否） 解决方法：解决方法： 使用贪心策略，制定一个量度标准使用贪心策略，制定一个量度标准,如：可使得所选择如：可使得所选择的下一个作业在可行情况下达到最优。（注意与目标函数的下一个作业在可行情况下达到最优。（注意与目标函数的不同），则下一个要考虑的作业将是未考察过的有最大的不同），则下一个要考虑的作业将是未考察过的有最大收益的作业，这样只要将各作业按效益收益的作业，这样只要将各作业按效益pi降序来排列即可降序来排列即可,即即: p1

14、 p2 pn 必要条条件： 考察的作业业能否加入（可行解的判断断）三、带有限期的作业排序的一般方法的粗略描述三、带有限期的作业排序的一般方法的粗略描述 p105 procedure GREEDY_JOB(D, J, n) J1 for i 2 to n do if (Ji的所有作业业都能在它们它们的截止期限前完成 ) then J=Ji endif repeat end GREEDY_JOB 算法中最关键的一步算法中最关键的一步 四、最优解的证明 定理 p105 五、可行解的充分必要条件 定理 p106 六、有限期的作业排序的贪心算法六、有限期的作业排序的贪心算法从从D(Jk)到到 D(J1)

15、依次与依次与D(i)比较来寻比较来寻找插入位置找插入位置r的过程的过程 满足条件表满足条件表示找到插入示找到插入位置位置r实现作业实现作业r+1到到作业作业k依次往后依次往后移动一个位置移动一个位置 将作业将作业i插入到插入到r+1位置位置procedure JS(D, J, n, k) integer D(0:n), J(0:n), i, k, n, r D0J0 0; k 1; J1 1 for i 2 to n do r k while DJrDi and DJr r do r r 1 repeat if DJrDi and Dir then for i k to r+1 by 1 do

16、 J i+1 J i repeat Jr+1 i ; k k+1； endif repeatend JS对于对于JS有两个赖以测量其时间复杂度的参数有两个赖以测量其时间复杂度的参数:作业数作业数 n 和包含在解和包含在解J中的作业数中的作业数 s 内层的内层的while循环至多循环循环至多循环k次次插入作业插入作业 i 要执行时间为要执行时间为O(k-r)外层外层for循环共执行循环共执行(n-1)次次如果如果s是是k的终值，即的终值，即s是最后所得解的作业数，是最后所得解的作业数，则则JS算法所需要的总时间为算法所需要的总时间为O(sn)由于由于s n，所以，所以JS算法的时间复杂度为算法的

17、时间复杂度为O(n2)带限期序作业排序的贪心算法的时间复杂度带限期序作业排序的贪心算法的时间复杂度 七、一个更快的作业排序算法思想（正确性） 八、实现方法讨论 九、union和find的实现 p44-46 十、一个更快的作业排序算法 p108 十一、运行实例 设 n=7，（p1，p7）=（35，30，25，20，15，10，5）和，（d1，d7）=（4，2，4，3，4，8，3）。利用算法FJS求解上述作业排序问题的最优解。3.4 最优归并优归并模式将两个分别包含将两个分别包含n个和个和m个记录的已排序的文件合并个记录的已排序的文件合并成一个包含成一个包含(n+m)个记录的排序文件个记录的排序文

18、件, 时间为时间为O(n+m)1460357901345679文件文件1: n=3文件文件2: m=5 归并模式归并模式: 给给出n个个已排序的文件, 则则存在多种种把这这些文件归并归并成一个个排序文件的方法, 这这些方法就称为归并称为归并模式 每一步都归并两个文件称二路归并每一步都归并两个文件称二路归并例例: 将将4个文件进行归并的两种方法个文件进行归并的两种方法, 方法不同则计算时方法不同则计算时间不同。设文件间不同。设文件X1-X4的记录数分别为的记录数分别为:20, 35, 10, 25X1X2X3X4Y1Y2Y3X1X2X3X4Y1Y2Y3556590553590归并方法归并方法1:

19、归并方法归并方法2:记录移动的总次数记录移动的总次数: 55+65+90=210记录移动的总次数记录移动的总次数: 55+35+90=180较优较优 由例子可以看出不同的归并方法具有不同的计算时间由例子可以看出不同的归并方法具有不同的计算时间,所以问题的关键是所以问题的关键是: 如何确定一个把如何确定一个把k个已排序文件归个已排序文件归并在一起的最优方法并在一起的最优方法Y1Y2Y3553590记录移动的总次数记录移动的总次数: 55+35+90=180X1X2X3X420 35 10 25Y1Y2Y3X1X320 10X425X235305590记录移动的总次数记录移动的总次数: 30+55

20、+90=175最优最优 用贪心法求解问题的关键是选择能产生最优解的最优量用贪心法求解问题的关键是选择能产生最优解的最优量度标准。对于归并文件来说度标准。对于归并文件来说, 因为归并一个具有因为归并一个具有n个记录的文个记录的文件和一个具有件和一个具有m个记录的文件可能需要个记录的文件可能需要m+n次记录次记录 移动移动, 所以所以对量度标准的一种很明显的选择是对量度标准的一种很明显的选择是: 每一步都归并尺寸比较小每一步都归并尺寸比较小的两个文件的两个文件例例: 有五个文件长度分别是有五个文件长度分别是(F1,F5)=(20, 30,10, 5, 30)5F410F315Z120F130F23

21、0F560Z335Z295Z4这种模式称这种模式称二路归并模式二路归并模式 用用二元归并树二元归并树来表示来表示叶结点称叶结点称外部结点外部结点表示已知的文件表示已知的文件内部结点内部结点, 每个内部结点每个内部结点有两个儿子有两个儿子, 表示它是由表示它是由两个文件归并而得到的两个文件归并而得到的5F410F315Z120F130F230F560Z335Z295Z4带权外部路径长度带权外部路径长度 如果如果di表示从根到代表文件表示从根到代表文件Fi的外部结点的距离的外部结点的距离, qi表示文件表示文件Fi的长度的长度(即记录数即记录数), 则这棵二元归并树则这棵二元归并树 的记录移动总量

22、是的记录移动总量是:diqi ( i=1,2,n) 问题的转化：一个最优问题的转化：一个最优二路归并模式与构造一棵二路归并模式与构造一棵具有最小外部路径的二元具有最小外部路径的二元树相对应树相对应计算实例中的记录移动总量计算实例中的记录移动总量diqi =5*3+10*3+20*2+30*2+30*2 =205二元归并树算法二元归并树算法 算法把算法把n个树的表个树的表L作为输入作为输入, 树中的每一个结点有树中的每一个结点有三个信息段三个信息段( LCHILD,RCHILD,WEIGHT ) 起初起初L中的每一棵树正好是一个结点中的每一棵树正好是一个结点, 即外部结点即外部结点, 结点的结点

23、的LCHILD和和RCHILD信息段都为信息段都为0, 而而WEIGHT信息段的值就是已知文件的长度。信息段的值就是已知文件的长度。 算法运行时算法运行时, 对于对于L中的任何一棵具有根结点中的任何一棵具有根结点T的树的树, WEIGHT(T)表示要归并的文件的长度表示要归并的文件的长度 WEIGHT(T) = 树树T中外部结点的长度和中外部结点的长度和 算法包括三个子算法算法包括三个子算法: GETNODE(T)用来产生一个用来产生一个新结点新结点; LEAST(L)找出表找出表L中中WEIGHT最小的树最小的树, 并将它从并将它从L中删除中删除; INSERT(L,T)把根为把根为T的树插

24、入的树插入到表到表L中中procedure TREE(L, n)for i=1 to n- -1 do call GETNODE(T); LCHILD(T)=call LEAST(L); RCHILD(T)=call LEAST(L); WEIGHT(T)=WEIGHT(LCHILD(T)+WEIGHT(RCHILD(T) call INSERT(L,T); return (LEAST(L);end TREE二元归并树算法描述二元归并树算法描述构造一个新结点构造一个新结点 作作为当前树的根结点为当前树的根结点找出找出L中一棵中一棵WEIGHT最小的树最小的树, 把它作为新把它作为新结点的左子树

25、结点的左子树, 然后在然后在L中将这棵树删除中将这棵树删除把根为把根为T的树插的树插入到表入到表L中中新结点的新结点的WEIGHT信信息段的值等于左、右息段的值等于左、右子树的子树的WEIGHT之和之和最后留在表最后留在表L中的树就是归中的树就是归并树并树,将它作为结果返回将它作为结果返回例例: 有有6个文件个文件, 长度分别为长度分别为: 2 , 3 , 5 , 7 , 9 , 13, 对它们对它们进行最优二元归并进行最优二元归并23初始初始, 表表L中有中有6棵树棵树,每棵树只有一个结点每棵树只有一个结点,分别代表分别代表6个文件个文件i=1, 先产生一个新结点先产生一个新结点(内结点内结点), 从从L的的6棵树中找出棵树中找出WEIGHT值值最小的树最小的树,作为新结点的左子树作为新结点的左子树, 再从剩余再从剩余5棵树中找出棵树中找出WEIGHT最小的树最小的树,作为新结点的右子树作为新结点的右子树, 新结点的新结点的WEIGHT的值等于左、的值等于左、右子树右子树WEIGHT值之和值之和, 表表L中还有中还有5棵树棵树2351379表表L:i=1,表表L:513795i=2, 先产生一个新结点先产生一个新结点, 从从L的棵树中找出的棵树中找出WEIGHT值为值为5的树的树,作为新结点的左子树作为新结点的左子树, 再在剩余再在剩