1、计算机算法分析与设计论文信息技术学院算法设计与分析课程考查论文题 目0-1背包问题的算法设计策略对比与分析专 业 软件工程 班 级 2007级软件工程 学 号 * 姓 名 马进杰 任课教师 刘维群 完成日期 2010年6月20日 0-1背包问题的算法设计策略对比与分析0 引言对于计算机科学来说，算法（Algorithm）的概念是至关重要的。算法是一系列解决问题的清晰指令，也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间
2、复杂度来衡量。算法可以理解为有基本运算及规定的运算顺序所构成的完整的解题步骤。或者看成按照要求设计好的有限的确切的计算序列，并且这样的步骤和序列可以解决一类问题。算法可以使用自然语言、伪代码、流程图等多种不同的方法来描述。一个算法应该具有以下五个重要的特征：有穷性：一个算法必须保证执行有限步之后结束；确切性：算法的每一步骤必须有确切的定义； 输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件； 输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的； 可行性：算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后
3、即可完成。计算机科学家尼克劳斯-沃思曾著过一本著名的书数据结构十算法= 程序，可见算法在计算机科学界与计算机应用界的地位。1 算法复杂性分析的方法介绍算法的复杂性是算法效率的度量，是评价算法优劣的重要依据。一个算法的复杂性的高低体现在运行该算法所需要的计算机资源的多少上面，所需的资源越多，我们就说该算法的复杂性越高；反之，所需的资源越低，则该算法的复杂性越低。 计算机的资源，最重要的是时间和空间（即存储器）资源。因而，算法的复杂性有时间复杂性和空间复杂性之分。 不言而喻，对于任意给定的问题，设计出复杂性尽可能地的算法是我们在设计算法是追求的一个重要目标；另一方面，当给定的问题已有多种算法时，选
4、择其中复杂性最低者，是我们在选用算法适应遵循的一个重要准则。因此，算法的复杂性分析对算法的设计或选用有着重要的指导意义和实用价值。 关于算法的复杂性，有两个问题要弄清楚：用怎样的一个量来表达一个算法的复杂性；对于给定的一个算法，怎样具体计算它的复杂性。让我们从比较两对具体算法的效率开始。1.1比较两对算法的效率考虑问题1：已知不重复且已经按从小到大排好的m个整数的数组A1.m（为简单起见。还设m=2 k，k是一个确定的非负整数）。对于给定的整数c，要求寻找一个下标i，使得Ai=c；若找不到，则返回一个0。问题1的一个简单的算法是：从头到尾扫描数组A。照此，或者扫到A的第i个分量，经检测满足Ai
5、=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;找数组的中间分量
6、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高效得多。以上例子说明：解同一个问题，算法不同，
7、则计算的工作量也不同，所需的计算时间随之不同，即复杂性不同。上图是运行这两种算法的时间曲线。该图表明，当m适当大（mm0）时，算法B_Search比算法Search省时，而且当m更大时，节省的时间急剧增加。不过，应该指出：用实例的运行时间来度量算法的时间复杂性并不合适，因为这个实例时间与运行该算法的实际计算机性能有关。换句话说，这个实例时间不单纯反映算法的效率而是反映包括运行该算法的计算机在内的综合效率。我们引入算法复杂性的概念是为了比较解决同一个问题的不同算法的效率，而不想去比较运行该算法的计算机的性能。因而，不应该取算法运行的实例时间作为算法复杂性的尺度。我们希望，尽量单纯地反映作为算法精
8、髓的计算方法本身的效率，而且在不实际运行该算法的情况下就能分析出它所需要的时间和空间。1.2复杂性的计量算法的复杂性是算法运行所需要的计算机资源的量，需要的时间资源的量称作时间复杂性，需要的空间（即存储器）资源的量称作空间复杂性。这个量应该集中反映算法中所采用的方法的效率，而从运行该算法的实际计算机中抽象出来。换句话说，这个量应该是只依赖于算法要解的问题的规模、算法的输入和算法本身的函数。如果分别用N、I和A来表示算法要解问题的规模、算法的输入和算法本身，用C表示算法的复杂性，那么应该有：C =F(N,I,A)其中F(N,I,A)是N,I,A的一个确定的三元函数。如果把时间复杂性和空间复杂性分
9、开，并分别用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 。对于给
10、定的算法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 )。在数学上
11、有：(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的每一个输入的概率也
12、难以预测或确定。我们有时也按平均情况计量时间复杂性，但那时在对P(I)做了一些人为的假设（比如等概率）之后才进行的。所做的假设是否符合实际总是缺乏根据。因此，在最好情况和平均情况下的时间复杂性分析还仅仅是停留在理论上。1.3复杂性的渐近性态及其阶随着经济的发展、社会的进步、科学研究的深入，要求用计算机解决的问题越来越复杂，规模越来越大。但是，如果对这类问题的算法进行分析用的是第二段所提供的方法，把所有的元运算都考虑进去，精打细算，那么，由于问题的规模很大且结构复杂，算法分析的工作量之大、步骤之繁将令人难以承受。因此，人们提出了对于规模充分大、结构又十分复杂的问题的求解算法，其复杂性分析应如何简
13、化的问题。我们先要引入复杂性渐近性态的概念。设T(N)是在第二段中所定义的关于算法A的复杂性函数。一般说来，当N单调增加且趋于时,T(N)也将单调增加趋于。对于T(N)，如果存在T(N)，使得当N时有：(T(N )-T(N )/T(N ) 0那么，我们就说T(N)是T(N)当N时的渐近性态，或叫T(N)为算法A当N的渐近复杂性而与T(N)相区别，因为在数学上，T(N)是T(N)当N时的渐近表达式。直观上，T(N)是T(N)中略去低阶项所留下的主项。所以它无疑比T(N)来得简单。比如当T(N)=3N 2+4Nlog2N +7时，T(N)的一个答案是3N 2，因为这时有：显然3N 2比3N 2 +
14、4Nlog2N +7简单得多。由于当N时T(N)渐近于T(N)，我们有理由用T(N)来替代T(N)作为算法A在N时的复杂性的度量。而且由于于T(N)明显地比T(N)简单，这种替代明显地是对复杂性分析的一种简化。进一步，考虑到分析算法的复杂性的目的在于比较求解同一间题的两个不同算法的效率，而当要比较的两个算法的渐近复杂性的阶不相同时，只要能确定出各自的阶，就可以判定哪一个算法的效率高。换句话说，这时的渐近复杂性分析只要关心T(N)的阶就够了，不必关心包含在T(N)中的常数因子。所以，我们常常又对T(N)的分析进-步简化，即假设算法中用到的所有不同的元运算各执行一次，所需要的时间都是一个单位时间。
15、综上所述，我们已经给出了简化算法复杂性分析的方法和步骤，即只要考察当问题的规模充分大时，算法复杂性在渐近意义下的阶。与此简化的复杂性分析方法相配套，需要引入五个渐近意义下的记号：、和。以下设f(N)和g(N)是定义在正数集上的正函数。如果存在正的常数C和自然数N0，使得当NN0时有f(N)Cg(N)。则称函数f(N)当N充分大时上有界，且g(N)是它的一个上界，记为f(N)=(g(N)。这时我们还说f(N)的阶不高于g(N)的阶。举几个例子：(1)因为对所有的N1有3N4N，我们有3N =(N)；(2)因为当N1时有N+10241025N，我们有N +1024=(N)；(3)因为当N10时有2
16、N 2+11N -103N 2，我们有2N 2+11N -10=(N 2)；(4)因为对所有N1有N 2N 3，我们有N2=(N 3)；(5)作为一个反例N 3(N 2)。因为若不然，则存在正的常数C和自然数N0，使得当NN0时有N3C N 2，即NC 。显然当取N =max(N0,C+l)时这个不等式不成立，所以N3(N 2)。按照大的定义，容易证明它有如下运算规则：(f)+(g)=(max(f,g)； (f)+ (g)=(f +g)； (f)(g)= (fg)； 如果g(N)= (f(N)，则(f)+ (g)= (f)； (Cf(N)= (f(N)，其中C是一个正的常数； f =(f)；
17、1.4复杂性渐近阶的重要性计算机的设计和制造技术在突飞猛进，一代又一代的计算机的计算速度和存储容量在直线增长。有的人因此认为不必要再去苦苦地追求高效率的算法，从而不必要再去无谓地进行复杂性的分析。他们以为低效的算法可以由高速的计算机来弥补，以为在可接受的一定时间内用低效的算法完不成的任务，只要移植到高速的计算机上就能完成。这是一种错觉。造成这种错觉的原因是他们没看到：随着经济的发展、社会的进步、科学研究的深入，要求计算机解决的问题越来越复杂、规模越来越大，也呈线性增长之势；而问题复杂程度和规模的线性增长导致的时耗的增长和空间需求的增长，对低效算法来说，都是超线性的，决非计算机速度和容量的线性增
18、长带来的时耗减少和存储空间的扩大所能抵销。事实上，我们只要对效率上有代表性的几个档次的算法作些简单的分析对比就能明白这一点。我们还是以时间效率为例。设A1,A2,和A6。是求解同一间题的6个不同的算法，它们的渐近时间复杂性分别为N，NlogN，N 2，N 3，2N，N!。让这六种算法各在C1和C2两台计算机上运行，并设计算机C2的计算速度是计算机C1的10倍。在可接受的一段时间内，设在C1上算法Ai可能求解的问题的规模为N1i，而在C2上可能求解的问题的规模为N2i，那么，我们就应该有Ti(N2i)=10Ti(N1i)，其中Ti(N)是算法Ai渐近的时间复杂性，i=1,2,6。分别解出N2i和
19、N1i的关系，可列成下表：表1-1算法与渐近时间复杂性的关系算法渐进时间复杂性T(N)在C1上可解的规模N1在C2上可解的规模N2N1和N2的关系A1NN11N21N21=10N11A2NlogNN12N22N2210N12A3N2N13N23A4N3N14N24A52NN15N25N25 =N15+log10A6N!N16N26N26 =N16+小的常数从表1-1的最后一列可以清楚地看到，对于高效的算法A1，计算机的计算速度增长10倍，可求解的规模同步增长10倍；对于A2，可求解的问题的规模的增长与计算机的计算速度的增长接近同步；但对于低效的算法A3，情况就大不相同，计算机的计算速度增长10
20、倍只换取可求解的问题的规模增加log10。当问题的规模充分大时，这个增加的数字是微不足道的。换句话说，对于低效的算法，计算机的计算速度成倍乃至数10倍地增长基本上不带来求解规模的增益。因此，对于低效算法要扩大解题规模，不能寄希望于移植算法到高速的计算机上，而应该把着眼点放在算法的改进上。从表1-l的最后一列我们还看到，限制求解问题规模的关键因素是算法渐近复杂性的阶，对于表中的前四种算法，其渐近的时间复杂性与规模N的一个确定的幂同阶，相应地，计算机的计算速度的乘法增长带来的是求解问题的规模的乘法增长，只是随着幂次的提高，规模增长的倍数在降低。我们把渐近复杂性与规模N的幂同阶的这类算法称为多项式算
21、法。对于表中的后两种算法，其渐近的时间复杂性与规模N的一个指数函数同阶，相应地计算机的计算速度的乘法增长只带来求解问题规模的加法增长。我们把渐近复杂性与规模N的指数同阶的这类算法称为指数型算法。多项式算法和指数型算法是在效率上有质的区别的两类算法。这两类算法的区别的内在原因是算法渐近复杂性的阶的区别。可见，算法的渐近复杂性的阶对于算法的效率有着决定性的意义。所以在讨论算法的复杂性时基本上都只关心它的渐近阶。多项式算法是有效的算法。绝大多数的问题都有多项式算法。但也有一些问题还未找到多项式算法，只找到指数型算法。我们在讨论算法复杂性的渐近阶的重要性的同时，有两条要记住：“复杂性的渐近阶比较低的算
22、法比复杂性的渐近阶比较高的算法有效”这个结论，只是在问题的求解规模充分大时才成立。比如算法A4比A5有效只是在N 32N，即Nc 时才成立。其中c是方程N 3=2N的解。当N c时，A5反而比A4有效。所以对于规模小的问题，不要盲目地选用复杂性阶比较低的算法。其原因一方面是如上所说，复杂性阶比较低的算法在规模小时不一定比复杂性阶比较高的算法更有效；另方面，在规模小时，决定工作效率的可能不是算法的效率而是算法的简单性，哪一种算法简单，实现起来快，就选用那一种算法。 当要比较的两个算法的渐近复杂性的阶相同时，必须进一步考察渐近复杂性表达式中常数因子才能判别它们谁好谁差。显然常数因子小的优于常数因子
23、大的算法。比如渐近复杂性为N1ogN/l00的算法显然比渐近复杂性为l00NlogN的算法来得有效。2 常见的算法分析设计策略介绍我们一般常见的几种算法分析设计策略主要有：动态规划、贪心算法、回溯法、分支限界法。接下来我主要介绍一下这几种算法。1.1动态规划动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，
24、可以解决各类最优化问题。因此读者在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论，逐渐学会并掌握这一设计方法。动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问
25、题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。在编程中常用解决最长公共子序列问题、矩阵连乘问题、凸多边形最优三角剖分问题、电路布线等问题。1.2 贪心算法所谓贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是
26、在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。贪心算法的基本思路：a.建立数学模型来描述问题。b.把求解的问题分成若干个子问题。c.对每一子问题求解，得到子问题的局部最优解。d.把子问题的解局部最优解合成原来解问题的一个解。实现该算法的过程： a.从问题的某一初始解出发；b.while 能朝给定总目标前进一步 doc.求出可行解的一个解元素；d.由所有解元素组合成问题的一个可行解。e.下面是一个可以试用贪心算法解的题目，贪心解的确不错，可惜不是最优解。1.3 回溯法回溯法是一个既带有系统性又带有跳跃性的
27、的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。回溯法的基本思想：确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，
28、以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。换句话说，这个结点不再是一个活结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。用回溯法解题的一般步骤：（1）针对所给问题，定义问题的解空间； （2）确定易于搜索的解空间结构； （3）以深度优先方式搜索解空间，
29、并在搜索过程中用剪枝函数避免无效搜索。1.4 分支限界法分支定界 (branch and bound) 搜索法是一种在问题的解空间树上搜索问题的解的方法。但与回溯算法不同，分支定界算法采用广度优先或最小耗费优先的方法搜索解空间树，并且，在分支定界算法中，每一个活结点只有一次机会成为扩展结点。分支定界法的思想是：首先确定目标值的上下界，边搜索边减掉搜索树的某些支，提高搜索效率。解题步骤：（1）在问题的边带权的解空间树中进行广度优先搜索 （2）找一个叶结点使其对应路径的权最小(最大)（3）当搜索到达一个扩展结点时,一次性扩展它的所有儿子（4）将满足约束条件且最小耗费函数目标函数限界的儿子,插入活结点表中（5）从活结点表中取下一结点同样扩展（6）直到找到所需
