算法设计与分析 论文.doc

6 算法初步结课论文 0-1背包问题的算法设计策略对比与分析孙旭东（天津师范大学2011级软件工程5班，天津，300387）摘 要：算法的复杂性是算法效率的度量，是评价算法优劣的重要依据。一个算法的复杂性的高低主要体现在运行该算法需要占取多大的计算机资源。0-1背包问题是一例典型的组合优化的NP完全问题。但是对于规模过大的0-1背包问题，还是无法找到最完美的求解方法。本文主要通过对背包问题使用不同的算法进行求解，并对他们的时间复杂度，空间复杂度，优缺点进行比较并提出改进的措施。从而深化对于算法复杂性的认知。关键词: 算法的复杂性；计算机资源；0-1背包问题；精确最优解；近似最优解 0-1 Knapsack problem algorithm design strategyof contrast and analysisSun Xu-dong(2011 the software engineering class five，Tianjin normal university，Tianjin ,300387)Abstract: The algorithm is the complexity of the algorithm is efficiency measure, the important basis of evaluation algorithm. The complexity of an algorithm of high and low in running the algorithm need to take how much computer resources. 0-1 knapsack problem is a typical combinatorial optimization of np-complete problems. But for 0-1 knapsack problem too big, still cant find the perfect solution. This article mainly through to the knapsack problem using different algorithms for solving, and for their time complexity and space complexity, the advantages and disadvantages are compared and improved measures are put forward. To deepen the perception of algorithm complexity.Key words:The complexity of the algorithm; Computer resources;0-1 knapsack problem; Accurate optimal solutions; The approximate optimal solution0 引言对于计算机科学而言，算法（Algorithm）的概念是至关重要的。算法是一系列解决问题的清晰指令，即能够对一定规范的输出，在有限时间内获得所要求的输出。如果一个算法有缺陷，或者不适用于某个问题，那么，执行这个算法将不会解决这个问题。用不同的算法来完成相同的任务需要的时间、空间以及效率都有可能会有所不同。而一个算法的优劣主要通过时间复杂度和空间复杂度来衡量。算法可以看成有基本运算以及规定的运算顺序所构成的完成解题步骤。算法可以使用自然语言、伪代码、流程图等多种不同的算法来描述。一个算法应该具有五个重要的特征，它们分别是：有穷性：一个算法必须保证执行有限步骤之后结束；确切性：算法的每一个步骤必须有明确的定义；可行性：算法原则上能够精确地进行，并且人们用笔和纸在做有限次运算之后即可完成；输入：一个算法有0个或者多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身出了初始条件；输出；一个算法有一个或者多个输出，以反映输出数据加工后的结果没有输出的算法是没有任何意义的.计算机科学家尼克劳斯-沃思曾经写过一本著名的书数据结构+算法=程序，由此可见算法在计算机科学界与计算机应用界的地位。1 算法复杂性分析的方法介绍算法的复杂性是算法效率的度量，是评价算法优劣的重要依据。一个算法的复杂性的高低体现在运行该算法所需要的计算机资源的多少上面，所需的资源越多，那就称之为该算法的复杂性越高；反之，所需的资源越低，则该算法的复杂性越低。 计算机的资源，最重要的是时间资源和空间（即存储器）资源。因而，算法的复杂性有时间复杂性和空间复杂性之分。 不言而喻，对于任意给定的问题，设计出复杂性尽可能地的算法是我们在设计算法是追求的一个重要目标；另一方面，当给定的问题已有多种算法时，选择其中复杂性最低者，是我们在选用算法适应遵循的一个重要准则。因此，算法的复杂性分析对算法的设计或选用有着重要的指导意义和实用价值。 关于算法的复杂性，有两个问题要弄清楚：用怎样的一个量来表达一个算法的复杂性；对于给定的一个算法，怎样具体计算它的复杂性。2 常见的算法分析设计策略介绍我们一般常见的几种算法分析设计策略主要有：动态规划、贪心算法、回溯法。接下来我主要介绍一下这几种算法。2.1 动态规划动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此读者在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论，逐渐学会并掌握这一设计方法。动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。在编程中常用解决最长公共子序列问题、矩阵连乘问题、凸多边形最优三角剖分问题、电路布线等问题。2.2 贪心算法所谓贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。贪心算法的基本思路：a.建立数学模型来描述问题。b.把求解的问题分成若干个子问题。c.对每一子问题求解，得到子问题的局部最优解。d.把子问题的解局部最优解合成原来解问题的一个解。实现该算法的过程： a.从问题的某一初始解出发；b.while 能朝给定总目标前进一步 doc.求出可行解的一个解元素；d.由所有解元素组合成问题的一个可行解。e.下面是一个可以试用贪心算法解的题目，贪心解的确不错，可惜不是最优解。2.3 回溯法回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。回溯法的基本思想：确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。换句话说，这个结点不再是一个活结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。用回溯法解题的一般步骤：（1）针对所给问题，定义问题的解空间； （2）确定易于搜索的解空间结构； （3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。3 0-1背包问题的几种算法背包问题是一类具有广泛的实际应用背景的经典NP-hard组合优化问题，在解决大量的复杂组合优化问题时，它常常作为一个子问题出现，从实际观点看，许多问题可以用背包问题来描述，如装箱问题，货仓装载，预算控制，存储分配，项目选择决策等等，都是典型的应用例子。随着网络技术的不断发展，背包公钥密码在电子商务中的公钥设计中也起着重要的作用。然而当问题的规模较大时，得到最优解是极其困难的。因此，借鉴前人的研究成果，开展对解决复杂组合优化问题的算法研究或改进是一项十分优异的工作。Dantzing在20世纪50年代首先进行了开创性的研究，利用贪心算法求得了0-1背包问题最优解的上届。1974年，Horowitz和salmi利用分支限界法解答了背包问题，并提出了背包问题的可分性，指出了求解该问题的一条新途径。随后，Balas和Zemel提出了背包问题的“核”思想，是背包问题的呀牛获得了较大进展。上世纪九十年代以后，随着生物仿生技术和网络技术的飞速发展，各种模拟生物物理规律的并行近似算法不断涌现，例如遗传算法已经在 0-1背包问题上得到了较好的应用，蚂蚁算法、粒子群等仿生算法也在组合优化问题中得到了很好的应用。综上所述，传统求解该问题的方法可以概括为精确算法和近似算法，其中精确算法有动态规划法、回溯法、分支限界法等，近似算法有遗传算法、贪婪法、粒子群算法、蚁群算法等，由于精确算法的时间复杂性和空间复杂性等缺点，近年来利用近似算法求解背包问题成为重点。因此此处对精确算法只做简单的描述，对几种近似算法则较为详细的说明了它们的思想和在背包问题中的运用。除了以上几种常见的算法，最近几年又出现了知识进化算法、二进制差异演化算法等新的算法解决背包问题，本文也对它们做一个简介。最后提出了将知识发现的方法引入遗传算法中来解决背包问题，拟提高单存遗传算法的搜索效率和解的质量。3.1 0-1背包问题描述一个旅行者有一个最多能装C公斤重量的背包，已知n个重量和价值分别为ci0和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,3)，(3,4)，（4,5），（5,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)。4 算法比较0-1背包问题是一