2013秋期-算法设计与分析_第三章

2020/1/131第三章贪心方法2020/1/1323.1一般方法1.问题的一般特征问题有n个输入，问题的解是由这n个输入的某个子集组成，这个子集必须满足某些事先给定的条件。约束条件：子集必须满足的条件；可行解：满足约束条件的子集；可行解可能不唯一；目标函数：用来衡量可行解优劣的标准，一般以函数的形式给出；最优解：能够使目标函数取极值（极大或极小）的可行解。分类：根据描述问题约束条件和目标函数的数学模型的特性和问题的求解方法的不同，可分为：线性规划、整数规划、非线性规划、动态规划等。贪心方法：一种改进的分级的处理方法，可对满足上述特征的某些问题方便地求解。2020/1/1332.贪心方法的一般策略问题的一般特征：问题的解是由n个输入的、满足某些事先给定的条件的子集组成。1）一般方法根据题意，选取一种度量标准。然后按照这种度量标准对n个输入排序，并按序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最优解加在一起不能产生一个可行解，则不把此输入加到这部分解中。否则，将当前输入合并到部分解中从而得到包含当前输入的新的部分解。2）贪心方法这种能够得到某种量度意义下的最优解的分级处理方法称为贪心方法注：贪心解最优解直接将目标函数作为量度标准也不一定能够得到问题的最优解3）使用贪心策略求解的关键选取能够得到问题最优解的量度标准。？＝2020/1/1343.贪心方法的抽象化控制描述procedureGREEDY(A,n)//A(1:n)包含n个输入//solution←Φ//将解向量solution初始化为空//fori←1tondox←SELECT(A)//按照度量标准，从A中选择一个输入，其值赋予x并将之从A中删除//ifFEASIBLE(solution,x)then//判定x是否可以包含在解向量中，即是否能共同构成可行解//solution←UNION(solution,x)//将x和当前的解向量合并成新的解向量，并修改目标函数//endifrepeatreturnendGREEDY2020/1/1353.2背包问题1.问题的描述已知n种物品具有重量(w1,w2,…,wn)和效益值(p1,p2,…,pn)，及一个可容纳M重量的背包；设当物品i全部或一部分xi放入背包将得到pixi的效益，这里，0≤xi≤1,pi0。问题：采用怎样的装包方法才能使装入背包的物品的总效益最大？分析：①装入背包的总重量不能超过M②如果所有物品的总重量不超过M，即≤M，则把所有的物品都装入背包中将获得最大可能的效益值③如果物品的总重量超过了M，则将有物品不能（全部）装入背包中。由于0≤xi≤1，所以可以把物品地一部分装入背包，所以最终背包中可刚好装入重量为M的若干物品（整个或一部分）目标：使装入背包的物品的总效益达到最大。niiixw12020/1/136问题的形式描述目标函数：约束条件：可行解：满足上述约束条件的任一集合(x1,x2,…,xn)都是问题的一个可行解——可行解可能为多个。(x1,x2,…,xn)称为问题的一个解向量最优解：能够使目标函数取最大值的可行解是问题的最优解——最优解也可能为多个。niiixp1niwpxMxwiiiniii1,0,0,1012020/1/137例3.1背包问题的实例设，n=3，M=20，(p1,p2,p3)=(25,24,15)，(w1,w2,w3)=(18,15,10)。可能的可行解如下：(x1,x2,x3)①(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iixpiixw2020/1/1382.贪心策略求解度量标准的选择：三种不同的选择1）以目标函数作为度量标准即，每装入一件物品，就使背包背包获得最大可能的效益增量。该度量标准下的处理规则：●按效益值的非增次序将物品一件件地放入到背包；●如果正在考虑的物品放不进去，则只取其一部分装满背包：如果该物品的一部分不满足获得最大效益增量的度量标准，则在剩下的物品中选择可以获得最大效益增量的其它物品，将它或其一部分装入背包。如：若ΔM=2,背包外还剩两件物品i,j，且有(pi＝4，wi＝4)和(pj＝3，wj＝2)，则下一步应选择j而非i放入背包：pi/2=2＜pj＝32020/1/139实例分析（例3.1)∵p1＞p2＞p3∴首先将物品1放入背包，此时x1＝1，背包获得p1＝25的效益增量，同时背包容量减少w1＝18个单位，剩余空间ΔM=2。其次考虑物品2和3。就ΔM=2而言有，只能选择物品2或3的一部分装入背包。物品2：若x2＝2/15，则p2x2＝16/5＝3.2物品3：若x3＝2/10，则p3x3＝3为使背包的效益有最大的增量，应选择物品2的2/15装包，即x2＝2/15最后，背包装满，ΔM=0，故物品3将不能装入背包，x3＝0。背包最终可以获得效益值＝x1p1＋x2p2＋x3p3＝28.2(次优解,非问题的最优解)2020/1/13102）以容量作为度量标准以目标函数作为度量标准所存在的问题：尽管背包的效益值每次得到了最大的增加，但背包容量也过快地被消耗掉了，从而不能装入“更多”的物品。改进：让背包容量尽可能慢地消耗，从而可以尽量装入“更多”的物品。即，新的标准是：以容量作为度量标准该度量标准下的处理规则：●按物品重量的非降次序将物品装入到背包；●如果正在考虑的物品放不进去，则只取其一部分装满背包；2020/1/1311实例分析（例3.1)∵w3＜w2＜w1∴首先将物品3放入背包，此时x3＝1，背包容量减少w3＝10个单位，还剩余空间ΔM=10。同时，背包获得p3＝15的效益增量。其次考虑物品1和2。就ΔM=10而言有，也只能选择物品1或2的一部分装入背包。为使背包的按照“统一”的规则，下一步将放入物品2的10/15装包，即x2＝10/15＝2/3最后，背包装满ΔM=0，故物品1将不能装入背包，x1＝0。背包最终可以获得效益值＝x1p1＋x2p2＋x3p3＝31(次优解,非问题的最优解)存在的问题：效益值没有得到“最大”的增加2020/1/13123）最优的度量标准影响背包效益值得因素：背包的容量M放入背包中的物品的重量及其可能带来的效益值可能的策略是：在背包效益值的增长速率和背包容量消耗速率之间取得平衡，即每次装入的物品应使它所占用的每一单位容量能获得当前最大的单位效益。在这种策略下的量度是：已装入的物品的累计效益值与所用容量之比。新的量度标准是：每次装入要使累计效益值与所用容量的比值有最多的增加（首次装入）和最小的减小（其后的装入）。此时，将按照物品的单位效益值：pi/wi比值（密度）的非增次序考虑。2020/1/1313实例分析（例3.1)∵p1/w1＜p3/w3＜p2/w2∴首先将物品2放入背包，此时x2＝1，背包容量减少w2＝15个单位，还剩余空间ΔM=5。同时，背包获得p2＝24的效益增量。其次考虑物品1和3。此时，应选择物品3,且就ΔM=5而言有，也只能放入物品3的一部分到背包中。即x3＝5/10＝1/2最后，背包装满ΔM=0，故物品1将不能装入背包，x1＝0。背包最终可以获得效益值＝x1p1＋x2p2＋x3p3＝31.5(最优解)2020/1/13143.背包问题的贪心求解算法算法3.2背包问题的贪心算法procedureGREEDY－KNAPSACK(P,W,M,X,n)//p(1:n)和w(1:n)分别含有按P(i)/W(i)≥P(i＋1)/W(i＋1)排序的n件物品的效益值和重量。M是背包的容量大小，而x(1:n)是解向量//realP(1:n),W(1:n),X(1:n),M,cu;integerI,nX←0//将解向量初始化为空//cu←M//cu是背包的剩余容量//fori←1tondoifW(i)cuthenexitendifX(i)←1cu←cu-W(i)repeatifi≤nthenX(i)←cu/W(i)endifendGREEDY-KNAPSACK2020/1/13154.最优解的证明即证明：由第三种策略所得到的贪心解是问题的最优解。最优解的含义：在满足约束条件的情况下，可使目标函数取极（大或小）值的可行解。贪心解是可行解，故只需证明：贪心解可使目标函数取得极值。证明的基本思想：将此贪心解与（假设中的）任一最优解相比较。●如果这两个解相同，则显然贪心解就是最优解。否则，●这两个解不同，就去找开始不同的第一个分量位置i，然后设法用贪心解的这个xi去替换最优解的那个xi，并证明最优解在分量代换前后总的效益值没有任何变化。可反复进行代换，直到新产生的最优解与贪心解完全一样。这一代换过程中，最优解的效益值没有任何损失，从而证明贪心解的效益值与代换前后最优解的效益值相同。即，贪心解如同最优解一样可取得目标函数的最大/最小值。从而得证：该贪心解也即问题的最优解。2020/1/1316定理3.1如果p1/w1≥p2/w2≥…≥pn/wn,则算法GREEDY-KNAPSACK对于给定的背包问题实例生成一个最优解。证明：设X=(x1,x2,…,xn)是GRDDDY-KNAPSACK所生成的贪心解。①如果所有的xi都等于1,则显然X就是问题的最优解。否则，②设j是使xi≠1的最小下标。由算法可知，xi=11≤i＜j,0≤xj＜1xi=0j＜i≤n若X不是问题的最优解，则必定存在一个可行解Y=(y1,y2,…,yn),使得：且应有：iiiixpypMywii2020/1/1317设k是使得yk≠xk的最小下标，则有yk＜xk:a)若kj，则xk=1。因为yk≠xk,从而有yk＜xkb)若k=j，由于，且对1≤i＜j，有yi=xi=1,而对j＜i≤n,有xi＝0；故此时若yk＞xk，则将有，与Y是可行解相矛盾。而yk≠xk,所以yk＜xkc)若k＞j，则，不能成立在Y中作以下调整：将yk增加到xk，因为yk≤xk,为保持解的可行性，必须从(yk+1,…,yn)中减去同样多的量。设调整后的解为Z=(z1,z2,…,zn)，其中zi＝xi，1≤i≤k，且有：则对于Z有：MxwiiMywiiMywiinikkkkiiiyzwzyw)()(niiiinikiikkkkkiiniiiwpwzywpwyzypzp11/)(/)(nikkinikiikkkiiwpwzywyzyp1/])()[(1iiinpy2020/1/1318由以上分析得，若，则Y将不是最优解；若，同时Z=X，则X就是最优解；若Z≠X，则重复以上替代过程，或者证明Y不是最优解，或者把Y转换成X，从而证明X是最优解由于分量的个数n有限，必到某一步停止，我们能找到解向量y*,它和x有相同的分量，又与y有相同的总价值（大于x的总价值），矛盾。这个矛盾源于x不是最优解的假设。故，x是最优解。iiiiypzpiiiiypzp2020/1/13193.3带有限期的作业排序1.问题描述假定在一台机器上处理n个作业，每个作业均可在单位时间内完成；同时每个作业i都有一个截至期限di0,当且仅当作业i在其截至期限以前被完成时，则获得pi0的效益。问题：求这n个作业的一个子集J，其中的所有作业都可在其截至期限内完成。——J是问题的一个可行解。可行解J中的所有作业的效益之和是，具有最大效益值的可行解是该问题的最优解。如果所有的作业都能在其期限之内完成则显然可以获得当前最大效益值；否则，将有作业无法完成——决策应该执行哪些作业，以获得最大可能的效益值。目标函数：约束条件：所有的作业都应在其期限之前完成JiipJiip2020/1/1320例3.2n=4，(p1，p2，p3，p4)＝(100,10,15,20)和(d1，d2，d3，d4)＝(2,1,2,1)。可行解如下表所示：问题的最优解是⑦