并行算法及其应用教学课件CH6 几个“难”问题的算法设计

计算的复杂性计算的复杂性计算机科学与工程学院计算机科学与工程学院顾小丰顾小丰EmailEmail：9/8/20229/8/2022计算的复杂性计算的复杂性第六章几个第六章几个“难难”问题问题的算法的算法设计设计第六章几个第六章几个“难难”问题问题的的算法算法设计设计贪心法和背包问题 动态规划和货郎担问题 回溯法和图的可着色性问题 分枝限界法和带时限的作业调度问题9/8/20222电子科技大学计算机学院电子科技大学计算机学院计算的复杂性计算的复杂性第六章几个第六章几个“难难”问题问题的算法的算法设计设计在“数据结构”中，不难找到一般较容易的算法设计，例如分类和查找等算法，它们的复杂性是多项式阶的。这里将介绍一些较“难”的问题的算法设计，对这些问题，迄今为止，人们只找到复杂性是n的指数阶的算法。本章目的有两个：一是介绍较“难”问题程序设计的常用技术；二是为以后章节的问题讨论做准备。9/8/20223电子科技大学计算机学院电子科技大学计算机学院计算的复杂性计算的复杂性第六章几个第六章几个“难难”问题问题的算法的算法设计设计6.16.1贪心法和背包问题贪心法和背包问题 贪贪心心法法是是一一种种直直接接的的设设计计技技术术，它它能能应应用用于于多多种种问问题题。这这类类问问题题的的一一般般特特征征是是有有n个个输输入入以以及及一一组组约约束束条条件件、一一个个目目标标函函数数，满满足足约约束束条条件件的的任任一一输输入入的的子子集集，称称为为可可行行解解（也也称称可可能能解解）。在在实实践践中中，常常常常要要在在其其中中找找出出一一个个解解，使使给给定定的的目目标标函函数数达达到到极大或者极小，满足这样条件的解称为极大或者极小，满足这样条件的解称为最佳解最佳解。下下边边我我们们使使用用贪贪心心法法完完成成所所谓谓背背包包问问题题的的程程序序设设计。计。9/8/20224电子科技大学计算机学院电子科技大学计算机学院计算的复杂性计算的复杂性第六章几个第六章几个“难难”问题问题的算法的算法设计设计背包问题背包问题的一般描述的一般描述背背包包问问题题的的一一般般描描述述是是：给给定定n n种种不不同同的的物物品品和和一一个个背背包包。物物品品i i的的重重量量是是w wi i，背背包包容容量量为为M M。假假定定物物品品的的一一部部分分x xi i（0 x0 xi i11），被被放放进进背背包包里里，就就会会得得到到利利润润为为P Pi ix xi i。因因为为背背包包的的容容量量为为M M，要要求求被被放放进进的的物物品品的的总总重重量量不不超超过过M M（若若只只考考虑虑物物重重而而不不考考虑虑其其形形状状和和体体积积）。问问怎怎样样选选择择物物品品的的种种类类和和数数量量，使使背背包装满，而获得最大利润。包装满，而获得最大利润。9/8/20225电子科技大学计算机学院电子科技大学计算机学院计算的复杂性计算的复杂性第六章几个第六章几个“难难”问题问题的算法的算法设计设计背包问题背包问题的的形式化形式化描述描述背背包包问问题题的形式化描述是：给定M0，wi0，Pi0，1in，要求找出一个n元向量(x1，x2，.，xn)，0 xi1，1in，使之满足：使 达到最大。(1)式称为约束条件约束条件；(2)式称为目标函数目标函数。(1)(2)9/8/20226电子科技大学计算机学院电子科技大学计算机学院计算的复杂性计算的复杂性第六章几个第六章几个“难难”问题问题的算法的算法设计设计这类问题，通常有n个输入和一些约束条件。任何满足这些约束条件的子集称为一个可可能能解解，使目标函数达到最大或最小的可能解称为最佳解最佳解，目标函数则是问题中给定的。采用贪心法给出背包问题的算法。贪贪心心法法是一个多步决策法。每一步的选择要能构成问题的一个可能解，同时使目标函数的值增加最快(当求目标函数最大时)或增加最小(当求目标函数最小时)。这种选择过程是以某些最优化量度为根据，而最优化量度有时是目标函数本身，有时可能是别的量度。最优化量度的选择是贪心法的关键。在背包问题中，满足(1)式的任何向量：(x1，x2，.，xn)，0 xi1，1in都是一个可能解。而问题是找使(2)式达到最大值的一个可能解，即最佳解。9/8/20227电子科技大学计算机学院电子科技大学计算机学院计算的复杂性计算的复杂性第六章几个第六章几个“难难”问题问题的算法的算法设计设计例例6.1-1给给定定n=3n=3，M=40M=40，(w(w1 1，w w2 2，w w3 3)=(28)=(28，1515，24)24)，(p(pl l，p p2 2，p p3 3)=(35)=(35，2525，24)24)。以下是此例的五个可能解：。以下是此例的五个可能解：(x(x1 1，x x2 2，x x3 3)(1)(1)(1,4/5,0)(1,4/5,0)40405555(2)(2)(1/2,1,1/3)(1/2,1,1/3)373750.550.5(3)(3)(1/28,1,1)(1/28,1,1)404050.2550.25(4)(4)(5/7,1,5/24)(5/7,1,5/24)40405555(5)(5)(25/28,1,0)(25/28,1,0)404056.2556.259/8/20228电子科技大学计算机学院电子科技大学计算机学院计算的复杂性计算的复杂性第六章几个第六章几个“难难”问题问题的算法的算法设计设计从此例可见，它的可能解有无穷多个(因为xi可取0，1间的任何实数)，不可能用枚举方法求它的最佳解，我们采用贪心方法：首先，如果，很显然最佳解将xi=1，1in。因此，不妨设，在此情况下，任何最佳解必定将背包装满。很明显，在任何背包未装满的可能解上，可以增加那些xi1的值，直到背包装满。同时，由干Pi0，这样做可以使利润增加，所以得到的解比原来解要好。例如上述例的可能解(2)，因为 为37，所以在xi1的值中都可增加，比如x3由原来的增加至，则=40，而=53.5，比原来的50.5增加了。9/8/20229电子科技大学计算机学院电子科技大学计算机学院计算的复杂性计算的复杂性第六章几个第六章几个“难难”问题问题的算法的算法设计设计贪心法的思想贪心法的思想人们可能想到，当背包未装满时，下一个选择应是利润Pi最大的物品装进背包。这伴就使得目标函数增加起快，当这种物品装不满背包时，才选择另一个适当的xi1，使物品装满背包。这里的最优化量度是Pi最大，期望目标函数达到最大，解(1)就是按这种策略求得的。但这个解显然不是最佳解，因为这种选择方法虽然每一步都使目标函数得到最大的增量，但由于背包可能很快被装满，加入目标函数Pi的个数少了，不一定能使目标函数达到最大。因此，人们又可能转而想到使背包容量消9/8/202210电子科技大学计算机学院电子科技大学计算机学院计算的复杂性计算的复杂性第六章几个第六章几个“难难”问题问题的算法的算法设计设计耗最慢的一种方法，即按wi按递升的顺序来考虑选取wi。解(3)正是按这一方法求得的解，但它也不是最佳解。这样做，虽然背包的重量上升得慢，却没有兼顾利润的增长速度，不能保证得到最佳解。这就启示我们，应当考虑利润增长和容量消耗二者的综合效果最好的方法。这就是每次选择利润与重量比pi/wi最大的物品先装进背包。解(5)就是按元按这一方法求得的。这就是背包问题的贪心法的思想。下面给出该算法，然后证明该算法可以得到背包问题的最佳解。9/8/202211电子科技大学计算机学院电子科技大学计算机学院计算的复杂性计算的复杂性第六章几个第六章几个“难难”问题问题的算法的算法设计设计算法算法6.1-1背包问题的贪心算法背包问题的贪心算法ProcedureGREEDY-KNAPSACKreal:p(1:n)，w(1:n)，x(1:n)，m，CUinteger:i，nbegin1.read(p(1:n)，w(1:n)，M)；/设按p(i)/w(i)的非递增顺序读入/2.fori1tondo3.x(i)=0；/x(i)赋初值/4.CUM；/CU是背包当前的剩余容量/5.i1；6.whi1ewiCUdobegin7.xi1；8.CUCU-wi；9.ii+1end；10.xiCU/wi；11.fori1tond012.write(xi)end9/8/202212电子科技大学计算机学院电子科技大学计算机学院计算的复杂性计算的复杂性第六章几个第六章几个“难难”问题问题的算法的算法设计设计贪心法的时间复杂性贪心法的时间复杂性关关于于上上述述算算法法的的时时间间复复杂杂性性，如如果果不不计计按按物物品品的的利利润润-重重量量比比(即即pi/wi)排成非递增序所需时间，它只消耗排成非递增序所需时间，它只消耗O(n)的时间。的时间。9/8/202213电子科技大学计算机学院电子科技大学计算机学院计算的复杂性计算的复杂性第六章几个第六章几个“难难”问题问题的算法的算法设计设计贪心法正确性定理贪心法正确性定理定定 理理 6.1-1如 果 p1/w1p2/w2pn/wn，过 程GREEDY-KNAPSACK将产生背包的一个最佳解。9/8/202214电子科技大学计算机学院电子科技大学计算机学院计算的复杂性计算的复杂性第六章几个第六章几个“难难”问题问题的算法的算法设计设计定理定理6.1-1的证明的证明 证证明明：设x=(x1，x2，.，xn)是GREEDY-KNAPSACK产生的解。如果一切xi=1，显然它是一个最佳解。不妨说存在某个j，1jn，有x1=x2=.=xj-1=1，0 xj1，且xj+1=xj+2=.=xn=0，由算法可知，解(x1，x2，.，xn)必满足：又设x=(x1，x2，.，xn)是问题的某个最佳解。显然也有：我们将证明x=x。如若不然，存在k，1kn。对1ik，有xi=xi，但xkxk。这里只可能有两种情况发生：9/8/202215电子科技大学计算机学院电子科技大学计算机学院计算的复杂性计算的复杂性第六章几个第六章几个“难难”问题问题的算法的算法设计设计(1)xkxk 由，所以有：且xk+1，xk+2，.，xn不全为0。又因xkxk1，故可增大xk，使xk取xk之值，并从xk+1，xk+2，.，xn中适当减小某些值，以使背包的总重量不变。这样就产生一个新的解x=(x1，x2，.，xn)，对1ik，有：9/8/202216电子科技大学计算机学院电子科技大学计算机学院计算的复杂性计算的复杂性第六章几个第六章几个“难难”问题问题的算法的算法设计设计x xi i=x=xi i，x xk kx xk k=x xk k 对kin，有考查：p1x1+.+pk-1xk-1+pkxk+pk+lxk+l+.+pnxn(1)p1x1+.+pk-1xk-1+pkxk+pk+lxk+l+.+pnxn(2)令(2)一(1)为，有：=pk(xk一xk)+pk+l(xk+l-xk+l)+.+pn(xn-xn)(3)变换(3)：x xi ixxi i，且 9/8/202217电子科技大学计算机学院电子科技大学计算机学院计算的复杂性计算的复杂性第六章几个第六章几个“难难”问题问题的算法的算法设计设计由0，可推得：如果0，说明x不是最佳解，矛盾；如果=0，说明x可变换为x，使得：xi=xi，1ik若xk+1xk+1，令xk+1=xk+1，重复上述讨论。这样可使x=x。9/8/202218电子科技大学计算机学院电子科技大学计算机学院计算的复杂性计算的复杂性第六章几个第六章几个“难难”问题问题的算法的算法设计设计(2)xkxk，这时必有xk1。由如果xk=0，说明：，因此也成立。x=(x1，x2，.，xn)不是问题的解，矛盾；如果0 xk1，可得：及xkxk 有所以x=(x1，x2，.，xn)不是问题的解，矛盾。9/8/202219电子科技大学计算机学院电子科技大学计算机学院计算的复杂性计算的复杂性第六章几个第六章几个“难难”问题问题的算法的算法设计设计整数背包问题整数背包问题以上讨论的背包问题是限定解x=(x1，x2，.，