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

算法设计与分析论文

题 目0-1背包问题的算法设计策略对比与分析
专 业
班 级
学 号
姓 名

引言
对于计算机科学来说，算法（Algorithm）的概念是至关重要的。算法是一系列解决问题的清晰指令，也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
算法可以理解为有基本运算及规定的运算顺序所构成的完整的解题步骤。或者看成按照要求设计好的有限的确切的计算序列，并且这样的步骤和序列可以解决一类问题。算法可以使用自然语言、伪代码、流程图等多种不同的方法来描述。
一个算法应该具有以下五个重要的特征：
有穷性：一个算法必须保证执行有限步之后结束；
确切性：算法的每一步骤必须有确切的定义；
输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件；
输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；
可行性：算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。
计算机科学家尼克劳斯-沃思曾著过一本著名的书《数据结构十算法= 程序》，可见算法在计算机科学界与计算机应用界的地位。

1 算法复杂性分析的方法介绍
算法的复杂性是算法效率的度量，是评价算法优劣的重要依据。一个算法的复杂性的高低体现在运行该算法所需要的计算机资源的多少上面，所需的资源越多，我们就说该算法的复杂性越高；反之，所需的资源越低，则该算法的复杂性越低。
计算机的资源，最重要的是时间和空间（即存储器）资源。因而，算法的复杂性有时间复杂性和空间复杂性之分。
不言而喻，对于任意给定的问题，设计出复杂性尽可能地的算法是我们在设计算法是追求的一个重要目标；另一方面，当给定的问题已有多种算法时，选择其中复杂性最低者，是我们在选用算法适应遵循的一个重要准则。因此，算法的复杂性分析对算法的设计或选用有着重要的指导意义和实用价值。
关于算法的复杂性，有两个问题要弄清楚：用怎样的一个量来表达一个算法的复杂性；对于给定的一个算法，怎样具体计算它的复杂性。
让我们从比较两对具体算法的效率开始。
1.1比较两对算法的效率
考虑问题1：已知不重复且已经按从小到大排好的m个整数的数组A[1..m]（为简单起见。还设m=2 k，k是一个确定的非负整数）。对于给定的整数c，要求寻找一个下标i，使得A[i]=c；若找不到，则返回一个0。
问题1的一个简单的算法是：从头到尾扫描数组A。照此，或者扫到A的第i个分量，经检测满足A[i]=c；或者扫到A的最后一个分量，经检测仍不满足A[i]=c。我们用一个函数Search来表达这个算法：
Function Search (c:integer):integer;
Var J:integer;
Begin
J:=1; {初始化}
{在还没有到达A的最后一个分量且等于c的分量还没有找到时，
查找下一个分量并且进行检测}
While (A[i]<c)and(j<m) do
         j:=j+1;
If A[j]=c then search:=j {在数组A中找到等于c的分量，且此分量的下标为j}
else Search:=0; {在数组中找不到等于c的分量}
End;
容易看出，在最坏的情况下，这个算法要检测A的所有m个分量才能判断在A中找不到等于c的分量。
解决问题1的另一个算法利用到已知条件中A已排好序的性质。它首先拿A的中间分量A[m/2]与c比较，如果A[m/2]=c则解已找到。如果A[m/2]>c，则c只可能在A[1],A[2],..,A[m/2-1]之中，因而下一步只要在A[1], A[2], .. ，A[m/2-1]中继续查找；如果A[m/2]<c，则c只可能在A[m/2+1],A[m/2+2],..,A[m]之中，因而下一步只要在A[m/2+1],A[m/2+2],..,A[m]中继续查找。不管哪一种情形，都把下一步需要继续查找的范围缩小了一半。再拿这一半的子数组的中间分量与c比较，重复上述步骤。照此重复下去，总有一个时候，或者找到一个i使得A[i]=c，或者子数组为空（即子数组下界大于上界）。前一种情况找到了等于c的分量，后一种情况则找不到。
这个新算法因为有反复把供查找的数组分成两半，然后在其中一半继续查找的特征，我们称为二分查找算法。它可以用函数B_Search来表达：
Function B_Search ( c: integer):integer;
Var
L,U,I：integer;{U和L分别是要查找的数组的下标的上界和下界}
Found：boolean;
Begin
L:=1; U:=m; {初始化数组下标的上下界}
Found:=false; {当前要查找的范围是A[L]..A[U]。}
{当等于c的分量还没有找到且U>=L时，继续查找}
While (not Found) and (U>=L) do
Begin
I:=(U+L) div 2;{找数组的中间分量}
If c=A[I] then Found:=Ture
else if c>A[I] then L:=I+1
else U:=I-1;
End;
If Found then B_Search:=1
else 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适当大（m>m0）时，算法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<=i<=k，ei是N和I的函数，即ei=ei(N,I)。那么有：
(2.3)
其中ti，i=1,2,..,k,是与N,I无关的常数。
显然，我们不可能对规模N的每一种合法的输入I都去统计ei(N,I),i=1,2,…,k。因此T(N,I)的表达式还得进一步简化，或者说，我们只能在规模为N的某些或某类有代表性的合法输入中统计相应的ei , i=1,2,…,k，评价时间复杂性。
下面只考虑三种情况的复杂性，即最坏情况、最好情况和平均情况下的时间复杂性，并分别记为Tmax(N )、Tmin(N)和Tavg(N )。在数学上有：
(2.4)
(2.5)
(2.6)
其中，DN是规模为N的合法输入的集合；I *是DN中一个使T(N,I *)达到Tmax(N)的合法输入，是DN中一个使T(N,)到Tmin(N)的合法输入；而P(I)是在算法的应用中出现输入I 的概率。
以上三种情况下的时间复杂性各从某一个角度来反映算法的效率，各有各的用处，也各有各的局限性。但实践表明可操作性最好的且最有实际价值的是最坏情况下的时间复杂性。下面我们将把对时间复杂性分析的主要兴趣放在这种情形上。
一般来说，最好情况和最坏情况的时间复杂性是很难计量的，原因是对于问题的任意确定的规模N达到了Tmax(N)的合法输入难以确定，而规模N的每一个输入的概率也难以预测或确定。我们有时也按平均情况计量时间复杂性，但那时在对P(I)做了一些人为的假设（比如等概率）之后才进行的。所做的假设是否符合实际总是缺乏根据。因此，在最好情况和平均情况下的时间复杂性分析还仅仅是停留在理论上。
2 常见的算法分析设计策略介绍
我们一般常见的几种算法分析设计策略主要有：动态规划、贪心算法、回溯法、分支限界法。接下来我主要介绍一下这几种算法。
1.1动态规划
动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此读者在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论，逐渐学会并掌握这一设计方法。
动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。
在编程中常用解决最长公共子序列问题、矩阵连乘问题、凸多边形最优三角剖分问题、电路布线等问题。
1.2 贪心算法
所谓贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。
贪心算法的基本思路：
a.建立数学模型来描述问题。
b.把求解的问题分成若干个子问题。
c..对每一子问题求解，得到子问题的局部最优解。
d..把子问题的解局部最优解合成原来解问题的一个解。
实现该算法的过程：
a.从问题的某一初始解出发；
b.while 能朝给定总目标前进一步 do
c.求出可行解的一个解元素；
d.由所有解元素组合成问题的一个可行解。
e.下面是一个可以试用贪心算法解的题目，贪心解的确不错，可惜不是最优解。
1.3 回溯法
回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。
回溯法的基本思想：确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。换句话说，这个结点不再是一个活结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。
用回溯法解题的一般步骤：
（1）针对所给问题，定义问题的解空间；
（2）确定易于搜索的解空间结构；
（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
1.4 分支限界法
分支定界 (branch and bound) 搜索法是一种在问题的解空间树上搜索问题的解的方法。但与回溯算法不同，分支定界算法采用广度优先或最小耗费优先的方法搜索解空间树，并且，在分支定界算法中，每一个活结点只有一次机会成为扩展结点。
分支定界法的思想是：首先确定目标值的上下界，边搜索边减掉搜索树的某些支，提高搜索效率。
解题步骤：
（1）在问题的边带权的解空间树中进行广度优先搜索
（2）找一个叶结点使其对应路径的权最小(最大)
（3）当搜索到达一个扩展结点时,一次性扩展它的所有儿子
（4）将满足约束条件且最小耗费函数£目标函数限界的儿子,插入活结点表中
（5）从活结点表中取下一结点同样扩展
（6）直到找到所需的解或活动结点表为空为止
3 0-1背包问题的几种算法
背包问题是一类具有广泛的实际应用背景的经典NP-hard组合优化问题，在解决大量的复杂组合优化问题时，它常常作为一个子问题出现，从实际观点看，许多问题可以用背包问题来描述，如装箱问题，货仓装载，预算控制，存储分配，项目选择决策等等，都是典型的应用例子。随着网络技术的不断发展，背包公钥密码在电子商务中的公钥设计中也起着重要的作用。然而当问题的规模较大时，得到最优解是极其困难的。因此，借鉴前人的研究成果，开展对解决复杂组合优化问题的算法研究或改进是一项十分优异的工作。
Dantzing 在20世纪50年代首先进行了开创性的研究，利用贪心算法求得了0-1背包问题最优解的上届。1974年，horowitz和salmi利用分支限界法解答了背包问题，并提出了背包问题的可分性，指出了求解该问题的一条新途径。随后，Balas和Zemel提出了背包问题的“核”思想，是背包问题的呀牛获得了较大进展。上世纪九十年代以后，随着生物仿生技术和网络技术的飞速发展，各种模拟生物物理规律的并行近似算法不断涌现，例如遗传算法已经在 0-1背包问题上得到了较好的应用，蚂蚁算法、粒子群等仿生算法也在组合优化问题中得到了很好的应用。
综上所述，传统求解该问题的方法可以概括为精确算法和近似算法，其中精确算法有动态规划法、回溯法、分支限界法等，近似算法有遗传算法、贪婪法、粒子群算法、蚁群算法等，由于精确算法的时间复杂性和空间复杂性等缺点，近年来利用近似算法求解背包问题成为重点。因此此处对精确算法只做简单的描述，对几种近似算法则较为详细的说明了它们的思想和在背包问题中的运用。除了以上几种常见的算法，最近几年又出现了知识进化算法、二进制差异演化算法等新的算法解决背包问题，本文也对它们做一个简介。最后提出了将知识发现的方法引入遗传算法中来解决背包问题，拟提高单存遗传算法的搜索效率和解的质量。
3.1 0-1背包问题描述
一个旅行者有一个最多能装C公斤重量的背包，已知n个重量和价值分别为ci>0和pi>0(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
物品个数N

j=0-m

10
3

C
0
1
2
3
4
5
6
7
8
9
物品大小W
物品价值p
编号
0
0
0
0
0
0
0
0

0
3
4
i=1
1
0
0
0
4
4
4
4
4
4
4
4
5
1-n 2
2
0
0
0
4
5
5
5
9
9
9
5
6
3
3
0
0
0
4
5
6
6
9
10
11

c[i][j]数组保存了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)=max{f(n-1,m), f(n-1,m-w[n])+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