算法设计与分析论文题 目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=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动态规划动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此读者在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论，逐渐学会并掌握这一设计方法。动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用