算法分析与设计论文-背包问题的算法设计策略对比与分析.doc

算法设计与分析论文题 目0-1背包问题的算法设计策略对比与分析专 业 班 级 学 号 姓 名 引言对于计算机科学来说，算法（Algorithm）的概念是至关重要的。算法是一系列解决问题的清晰指令，也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。算法可以理解为有基本运算及规定的运算顺序所构成的完整的解题步骤。或者看成按照要求设计好的有限的确切的计算序列，并且这样的步骤和序列可以解决一类问题。算法可以使用自然语言、伪代码、流程图等多种不同的方法来描述。一个算法应该具有以下五个重要的特征：有穷性：一个算法必须保证执行有限步之后结束；确切性：算法的每一步骤必须有确切的定义； 输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件； 输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的； 可行性：算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。计算机科学家尼克劳斯-沃思曾著过一本著名的书数据结构十算法= 程序，可见算法在计算机科学界与计算机应用界的地位。1 算法复杂性分析的方法介绍算法的复杂性是算法效率的度量，是评价算法优劣的重要依据。一个算法的复杂性的高低体现在运行该算法所需要的计算机资源的多少上面，所需的资源越多，我们就说该算法的复杂性越高；反之，所需的资源越低，则该算法的复杂性越低。 计算机的资源，最重要的是时间和空间（即存储器）资源。因而，算法的复杂性有时间复杂性和空间复杂性之分。 不言而喻，对于任意给定的问题，设计出复杂性尽可能地的算法是我们在设计算法是追求的一个重要目标；另一方面，当给定的问题已有多种算法时，选择其中复杂性最低者，是我们在选用算法适应遵循的一个重要准则。因此，算法的复杂性分析对算法的设计或选用有着重要的指导意义和实用价值。 关于算法的复杂性，有两个问题要弄清楚：用怎样的一个量来表达一个算法的复杂性；对于给定的一个算法，怎样具体计算它的复杂性。让我们从比较两对具体算法的效率开始。1.1比较两对算法的效率考虑问题1：已知不重复且已经按从小到大排好的m个整数的数组A1.m（为简单起见。还设m=2 k，k是一个确定的非负整数）。对于给定的整数c，要求寻找一个下标i，使得Ai=c；若找不到，则返回一个0。问题1的一个简单的算法是：从头到尾扫描数组A。照此，或者扫到A的第i个分量，经检测满足Ai=c；或者扫到A的最后一个分量，经检测仍不满足Ai=c。我们用一个函数Search来表达这个算法：Function Search (c:integer):integer;Var J:integer; BeginJ:=1; 初始化在还没有到达A的最后一个分量且等于c的分量还没有找到时，查找下一个分量并且进行检测 While (Aic)and(jc，则c只可能在A1,A2,.,Am/2-1之中，因而下一步只要在A1, A2, . ，Am/2-1中继续查找；如果Am/2=L时，继续查找While (not Found) and (U=L) doBeginI:=(U+L) div 2;找数组的中间分量If c=AI then Found:=Tureelse if cAI then L:=I+1 else U:=I-1;End;If Found then B_Search:=1else B_Search:=0;End;容易理解，在最坏的情况下最多只要测A中的k+1(k=logm,这里的log以2为底，下同)个分量，就判断c是否在A中。算法Search和B_Search解决的是同一个问题，但在最坏的情况下（所给定的c不在A中），两个算法所需要检测的分量个数却大不相同，前者要m=2 k个，后者只要k+1个。可见算法B_Search比算法Search高效得多。以上例子说明：解同一个问题，算法不同，则计算的工作量也不同，所需的计算时间随之不同，即复杂性不同。上图是运行这两种算法的时间曲线。该图表明，当m适当大（mm0）时，算法B_Search比算法Search省时，而且当m更大时，节省的时间急剧增加。不过，应该指出：用实例的运行时间来度量算法的时间复杂性并不合适，因为这个实例时间与运行该算法的实际计算机性能有关。换句话说，这个实例时间不单纯反映算法的效率而是反映包括运行该算法的计算机在内的综合效率。我们引入算法复杂性的概念是为了比较解决同一个问题的不同算法的效率，而不想去比较运行该算法的计算机的性能。因而，不应该取算法运行的实例时间作为算法复杂性的尺度。我们希望，尽量单纯地反映作为算法精髓的计算方法本身的效率，而且在不实际运行该算法的情况下就能分析出它所需要的时间和空间。1.2复杂性的计量算法的复杂性是算法运行所需要的计算机资源的量，需要的时间资源的量称作时间复杂性，需要的空间（即存储器）资源的量称作空间复杂性。这个量应该集中反映算法中所采用的方法的效率，而从运行该算法的实际计算机中抽象出来。换句话说，这个量应该是只依赖于算法要解的问题的规模、算法的输入和算法本身的函数。如果分别用N、I和A来表示算法要解问题的规模、算法的输入和算法本身，用C表示算法的复杂性，那么应该有：C =F(N,I,A)其中F(N,I,A)是N,I,A的一个确定的三元函数。如果把时间复杂性和空间复杂性分开，并分别用T和S来表示，那么应该有：T =T(N,I,A) (2.1)和 S =S(N,I,A) (2.2)通常，我们让A隐含在复杂性函数名当中，因而将（2.1）和（2.2）分别简写为T =T(N,I)和 S =S(N,I)由于时间复杂性和空间复杂性概念类同，计算方法相似，且空间复杂性分析相对地简单些，所以下文将主要地讨论时间复杂性。下面以T(N,I)为例，将复杂性函数具体化。根据T(N,I)的概念，它应该是算法在一台抽象的计算机上运行所需的时间。设此抽象的计算机所提供的元运算有k种，他们分别记为O1,O2 ,.,Ok；再设这些元运算每执行一次所需要的时间分别为t1,t2,.,tk 。对于给定的算法A，设经过统计，用到元运算Oi的次数为ei，i=1,2,.,k ，很明显，对于每一个i，1=i0和pi0(i=1,2,，n)的物品，选择哪些物品装入背包，可使在背包的容量限制之内所装物品的价值最大，这就是背包问题。0-1背包特点是：每种物品都仅有一件，可以选择放入或不放。0-1背包问题:给定n种物品和一个背包。物品i的重量是Wi,其价值为Vi,背包的容量为C。应如何选择装入背包的物品,使得装入背包中物品的总价值最大? 在选择装入背包的物品时,对每种物品i只有两种选择,即装入背包为1或不装入背包为0。不能将物品i装入背包多次,也不能只装入部分的物品i。021背包问题的主要特点是在选择物品i装入背包时,每种物品仅有一件,可以选择放或不放。3.2动态规划动态规划算法的基本思想是把原问题分解成一系列子问题,然后从这些子问题中求出原问题的解。对一个负重能力为m的背包,如果选择装入一个第i种物品,那么原背包问题就转化为负重能力为m2w的子背包问题。由于动态规划算法求解过程中反复出现子问题,且对每次重复出现的子问题都要重新解一次,这需要多花费不少时间,因此动态规划算法的时间复杂度为O ( n* m) ,其中n为物体的个数,m为背包负重。动态规划是用空间换时间的一种方法的抽象。其关键是发现子问题和记录其结果。然后利用这些结果减轻运算量。因为背包的最终最大容量未知，所以，我们得从1到M一个一个的试，比如，刚开始任选N件物品中的一个，看对应的M的背包，能不能放进去，如果能放进去，并且还有多少空间，则，多出来的空间能放N-1物品中的最大价值，怎么能保证总选则是最大价值呢，看下表：测试数据：10,33,44,55,6最大容量M物品个数Nj=0-m103C0123456789物品大小W物品价值p编号00000000034i=110004444444451-n 2200045559995633000456691011cij数组保存了1,2,3号物品依次选择后的最大价值。这个最大价值是怎么得来的呢?从背包容量为0开始,1号物品先试,0,1,2,的容量都不能放.所以置0,背包容量为3则里面放4.这样,这一排背包容量为4,5,6,.10的时候，最佳方案都是放4.假如1号物品放入背包.则再看2号物品.当背包容量为3的时候，最佳方案还是上一排的最价方案c为4.而背包容量为5的时候，则最佳方案为自己的重量5.背包容量为7的时候，很显然是5加上一个值了。加谁?很显然是7-4=3的时候.上一排c3的最佳方案是4.所以。总的最佳方案是5+4为9.这样.一排一排推下去。最右下放的数据就是最大的价值了。(注意第3排的背包容量为7的时候,最佳方案不是本身的6.而是上一排的9.说明这时候3号物品没有被选.选的是1,2号物品.所以得9。从以上最大价值的构造过程中可以看出。f(n,m)=maxf(n-1,m), f(n-1,m-wn)+P(n,m)这就是书本上写的动态规划方程.3.3回溯法用回溯法求解0-1背包问题的算法思路是按照物品的单位价值从大到小排序,计算当前节点的上界,搜索左子树。只有当右子树包含可行解时才搜索右子树。剪去右子树的条件是当前价值加上剩余物品的总价值小于当前的最优总价值时,不需搜索右子树,可将右子树剪去。回溯法用一定的剪枝进行优化,算法的时间复杂度为O ( n3 2n ) , n为物品个数。3.4 贪心算法在求解0-1背包问题时,对贪心算法可以使用一些策略, 使其得到的解更接近最优解。具体方案如下:(1) 价值优先策略:从剩余的物品中,选取价值最大的可以装入背包的物品。此时,价值最大的优先被装入背包,然后装入下一个价值最大的物品,直到不能再装入剩下的物品为止。(2) 重量优先策略:从剩余的物品中选取重量最小的物品装入背包中,这种策略一般不能得到最优解。(3) 单位价值优先策略:根据价值/重量的比值,按照每一次选取剩下的物品中比值最大的物品装入背包,直到不能再装入为止。以上三种策略都不能保证得到最优解,但三种策略相比较而言,第三种策略与最优解相差较小。如果可以选择物品的一部分,用单位价值策略可以保证得到最优解。在贪心算法时间复杂度的估算中,由于需要对重量或价值或两者的比值进行排序，所以贪心算法的时间复杂度为O(n*logn)。3.5分支限界法在解0-1背包问题的优先队列式分支限界法中，活结点优先队列中结点元素N的优先级由该结点的上界函数Bound计算出的值uprofit给出。子集树中以结点N为根的子树中任一结点的价值不超过N.profit。可用一个最大堆来实现活结点优先队列。堆中元素类型为HeapNode，其私有成员有uprofit,profit,weight和level。对于任意活结点N，N.weight是结点N所相应的重量；N.profit是N所相应的价值；N.uprofit是结点N的价值上界，最大堆以这个值作为优先级。子集空间树中结点类型为bbnode。3 算法比较以上方法对背包问题的求解各有其优缺点，如表3-1所示。表3-1求解背包问题的算法比较算法名称时间复杂度优点缺点改进回溯法O(n*2n )优解速度慢剪枝动态规划O(n*m)最优解速度慢递归方程求解贪心算法O(n*logn)速度快不一定是最优解启发式方法分支限界法O(n*2n)最优解速度慢0-1背包问题是一个经典的NP问题。对于规模过大的0-1背包问题，人们还是无法找到完美的求解方法。所有智能算法都有其局限性，只能在一定范围内求解。由于各种算法都有其自身的优缺点，许多学者通过利用一种算法的优点同时结合其他算法避免该算法的不足，出现了混合算法，这样就取得了很大的成功。0-1背包问题未来的发展趋势是继续研究结合多种算法的混合优化算法；通过其他学科的算法得到启发，提出一种新的算法，继而推动0-1背包问题的研究。4 总结在写论文的过程中，我上网查询了很多资料，并且也参考了书本里的内容，通过这些我对算法分析设计又有了进一步的了解，对算法的复杂度也有了新的认识。对于我们常用的动态规划算法、回溯法、分支限界法、贪心算法等的思想有了进一步的了解，我相信这对我以后的学习是非常有用的。虽然这门课程已经结束了，但是我所掌握的却很少，因此在接下来的时间里我还会继续学习算法分析与设计，从而能够运用这些算法解决更多的问题。参考文献: 1 王晓东.计算机算法设计与分析（第3版） 电子工业出版社, 2009. 2 应莉 0-1背包问题及其算法 计算机与现代化 （2009）06-0024-03 3 徐颖 回溯法在0-1背包问题中的应用 软件导刊（2008）12-0054-02