单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,算法,算法(algorithm)可以被定义为一个良定的计算过程，它具有一个或者若干输入值，并产生一个或者若干输出值。,人们采用一般术语陈述问题，确定输入输出关系，而算法则是描述这种输入输出关系的特定计算过程。,算法正确性：对每一个输入实例算法都能终止，并给出正确输出。,算法正确性有两个要素；1是能够终止。2是结果正确。,算法设计和分析的步骤可概括:,（1）问题的陈述。,（2）模型的选择。,（3）算法的设计。,（4）算法的程序实现。,（5）算法分析。,算法具有以下五大特性,（1）确定性。一个算法中给出的每一个计算步骤，必须是精确的定义、无二义性的。,（2）有穷性。一个算法在执行有穷个计算步骤后必须停止。,（3）可行性。算法中要执行的每一个计算步骤都是可以在有限时间内做完的。可行性、有穷性和确定性是相容的。,（4）输入。一个算法一般都要求一个或多个输入信息。,（5）输出。一个算法一般有一个或多个输入信息。它们通常可以被解释成为“对输入的计算结果”。,循环不变式具有以下三个性质：,初始：在循环的第一次迭代之前，循环不变式为真。,维持：如果在循环的某次迭代之前循环不变式为真，那么在下一次迭代之前，循环不变式仍然为真。,终止：当循环终止时，循环不变式给出有用性质，这个性质可以用于证明算法的正确性,循环不变式：Aj是Aj.LengthA中的最小元素。,循环不变式：在14行外层for循环的每次迭代开始，子数组A1.i-1中的元素有序。,算法分析(p4),算法分析是指对一个算法所需的计算资源进行预测。,考虑算法的好坏主要有以下几点：,（1）执行算法所耗费的时间。,（2）执行算法所耗费的存储空间，其中主要考虑辅助存储空间。,（3）算法应易于理解，易于编码，易于调试等。,最重要的计算资源是时间和空间资源(存储器),输入规模是输入元素的个数、用二进制表示的输入的总位数、和用图中顶点数和边数表示输入。,一个算法的运行时间是指在某个输入时，算法执行基本操作的次数或者步数。,2、影响程序运行时间的主要因素：,（1）程序的输入。,（2）由编译系统所产生的代码程序的质量。,（3）执行程序的计算机机器指令的性能与速度。,（4）程序所依据的算法的时间复杂度。,3、算法的复杂性测度主要有两个方面：,(1)空间复杂度,(2)时间复杂度,最坏情况和平均情况分析(P6),算法最坏情况下的运行时间，即对于规模n的任何输入，算法运行最长的时间。,之所以这样，是由于以下三个原因：,1、算法的最坏情况运行时间是任一输入运行时间的上界。,2、对于某些算法，最坏情况经常出现。,3、算法的“平均情况”性能常常与最坏情况大致相同。,渐近表示(P8),渐进表示：是方便地表示算法的最坏情况下，计算的复杂度。,三个定义，三例题。,定义11如果存在三个正常数,第2章 分 治 法,递归(P13),递归程序可被简单地定义为对自己的调用。,递归程序要求必须有终止条件。,斐波那契(Fibonacci)序列。,替换方法(P16),用替换方法解某个递归方程时，分为两步。首先猜测问题解的某个界限，然后用数学归纳法证明所猜测解的正确性。,主方法(P18)主定理（三种情况，三个例题）,分治法的基本思想,(p20),分治法在每一层递归上由三个步骤组成：,(1)划分(divide)：将原问题分解为若干规模较小、相互独立、与原问题形式相同的子问题。,(2)解决(conquer)：若子问题规模较小，则直接求 解；否则递归求解各子问题。,(3)合并(combine)：将各子问题的解合并为原问题的解。,算法思想,如果我们将分治策略用于此问题，每次将问题分成大致相等的两部分，分别在这两部分中找出最大值与最小值，再将这两个子问题的解组合成原问题的解，就可得到该问题的分治算法。,归并排序算法(P28),归并排序的关键操作是归并两个已排序的子序列的过程。,找最大值与最小值分治算法,归并排序最坏情况下的时间复杂度,(n lb n)要优于冒泡排序最坏情况下的时间复杂度,(n,2,)。,动态规划（P49）,动态规划(dynamic programming)已经成为计算机科学中重要的算法设计范型。,1、提出：,1957年，Richard Bellman在描述一类优化控制问题时创造了这个名字。,2、作用：,那时，这个名字更多地用于描述问题，而不是解问题的技巧。,3、特点：,此方法的主要特点是通过采用表格技术。计算所有子问题的解。计算的过程从小问题到大问题，并将计算结果存储在一张表中。,4、优点：,一旦一个子问题被解决，就存储其结果，此后遇到同样的子问题，就不再重复计算。用多项式算法代替指数算法。,5、应用：动态规划典型的应用领域是组合优化问题。,在这类问题中，可能会有许多可行解(feasible solution)，每个解对应一个值，我们想要找出一个具有最优值的解，称这个解为问题的一个最优解。可能有多个解都达到这个最优值。,6、概念：,规划(programming)的含义意味着一系列的决策；,动态(dynamic)的含义则传递着这样一种思想，就是所做决策可能依赖于当前状态，而与此前所做决策无关。,约束条件为,1表示第i个物品选中,0为第i个物品没选中。,0-1背包问题(52),目标,0-1背包问题最优解的结构：,设,X=(x,1,x,2,x,n,)是一个最优解，其结构为：,1、这个包含第n个物品时，即x,n,=1,则,x,1,x,2,x,n-1,，W-w,i,为子问题的最优解。,2、这个不包含第n个物品时，即x,n,=0,则,x,1,x,2,x,n-1,，W为子问题的最优解,矩阵链乘问题的最优结构。,非平凡矩阵链乘：在矩阵链乘中可以进行分割矩阵链乘。,平凡矩阵链乘：在矩阵链乘中不能进行分割矩阵链乘。,非平凡矩阵链乘问题都会对矩阵进行分割，而分割的位置是未定的，需要我们确定,。,动态规划算法的研制可由4步组成：,(1)刻画最优解的结构。,(2)递归定义最优解的值：,(3)以自底向上(或自顶向下)的方式计算最优解的值。,(4)根据计算的结果，构造问题最优解。,动态规划的基本元素,(p60),动态规划应用于组合优化问题时，问题自身应有的两个特点。这就是问题具有最优子结构和重叠子问题。,1最优子结构,动态规划应用于组合优化问题的第一个特征是问题自身具有最优子结构。,如果问题的最优解包含子问题的最优解，则问题展示了最优子结构。,只要问题展示最优子结构，就为应用动态规划提供了可能性,。,在寻找问题的最优子结构时，问题具有以下公共结构：,(1)问题的解由一系列决策组成。,(2)对于给定的问题，假定已知一个选择导致最优解。不需关心如荷做出这个选择，只需假定它是已知的。,(3)给定这个决策，你来决定哪些子问题最好地刻画子问题的其余空间。,(4)证明在问题最优解中所用到的子问题的解，通过使用“切割一粘贴”技术，一定是最优的。,刻画子问题的空间的原则是,尽可能保持这个空间简单,然后在需要的时候扩展它。,最优子结构随问题域的变化有两种方式：,(1)原问题的最优解中,利用了多少个子问题?,(2)决定最优解中使用哪些子问题需做多少次决策?,在0-1背包问题中,最优解利用两个子问题，即ci-1,w和ci-1,w-wi。,在矩阵链乘子问题最优解利用两个子问题。这是因为,对于在矩阵某处分裂的Ak,产生两个子问题：AiAi+1Ak的加括号方式和Ak+1Ak+2Aj的加括号方式,我们必须最优解决这两个子问题。,自顶向下的动态规划方法具有如下特点：,它是一种对自然问题求解的机械转换。,方法自身可以确定计算子问题的顺序。,可能不需要计算出所有子问题的解。,备忘录方法(64),2重叠子问题,动态规划应用于组合优化问题的第二个特征是问题自身具有重叠子问题。,动态规划算法的运行时间取决于两个因素的乘积:,第4章贪心法,(p98),贪心法的当前选择可能要依赖已经做出的所有选择，但不依赖于有待于做出的选择和子问题。,贪心法自顶向下，一步一步地做出贪心选择。,贪心法总是做出在当前时刻看起来最优的决策，即希望通过局部最优决策导致问题的全局最优解。,贪心法并不总是产生问题的全局最优解，但许多问题利用贪心法求解得到全局最优解。,约束条件为：,背包问题(p98),可行解即满足约束条件的解,用贪心策略求解背包问题时，首先要选出度量的标准。,取目标函数作为度量标准,，,即每放入一件物品使背包获得最大可能的效益值增量。,按物品权重的非降次序把物品放入背包。,用每单位容量所带来价值之比作为贪心的策略，可以得到问题的最优解。,分几步求解这个问题。,首先找出该问题的动态规划解，组合两个子问题的解成原问题的解。,在决定最优解中选择哪个子问题，考虑几种选择。,通过贪心选择策略,我们只需要选择一个子问题。当进行贪心选择时,要保证其中一个子问题为空,只剩下一个非空子问题。,基于这些观察思考，我们可以研制一个解决活动选择问题的递归贪心算法。,最后，将递归算法变成迭代算法，完成问题求解。,活动选择问题,(p101),前缀码,如果我们只用0/1对字符进行编码，并限定任一字符的编码都不是另一个字符编码的前缀，则称这样的编码为前缀码。,哈夫曼提出的贪心算法可以构造最优前缀编码，这样产生的编码称为哈夫曼编码。,