算法分析基础pd

目录 XY 64.堆的概念 ,170 83最优二叉查找树....... 223 64.2堆排序 174 习题8.3.-27 与题64 175 84背包问题和记忆功能 6.5霍纳法则和二进制幂....176 841背包问题 651霍纳法则.1 176 842记忆功能 6.52二:进制幂...... ...177 习题8.4 231 与题6.5 .179 小结 66问题化简. ...18l 第9章贪婪技术... 233 66.1求最小公倍数.181 662计算图中的路径数量 9.1Prim算法 663优化问题的化简............82 习题9.1...238 664线性规划 9,2 Kruskal算法, 239 665简化为图问题...185 习题9.2 245 习题66.1111-186 93 Dijkstra算法 246 小结 a188 与题9.3.....249 94哈夫曼树.,250 第7章时空权衡 与题9.4 1和道通 253 7.1计数排序 191 小结 254 与题7,1 第10章迭代改进 255 7.2字子符串匹配中的输入增强技术.........194 721 Horspool算法... 195 10.1单纯形法,256 7.22 Boyer- Moore算法,,197 10.1.1线性规划的几何解释,256 题7.2. 20l 10.1,2单纯形法概述, 73散列法 202 10.L.3单纯形法其他要点...264 7.3.1开散列(分离链)... 习题10.l 265 7.32闭散列(开式寻址) 20 10.2最大流量问题 与题73 207 习题10.2 74B树 208 10.3分图的最大匹配 276 与题7.4 习题10.3, ∴281 小结 211 10.4稳定婚姻问题, 282 习题104 第8章动态规划 .213 +?++++” ...1286 8.1计算项式系数....214 第11章算法能力的极限 习题8.1. .2l5 8.2 Warshall算法和Foyd算法.116 11.l如何求下界 288 8.2.1 Warshall算法 .217 11.1平凡下界 8.22计算完全最短路径的 l.1.2信息论下界 1289 Floyd算 220 111.3敔手下界 289 习题8.2..222 11.1.4问题化简 匀题11. 29 xv 算法设计与分析基础(第2版) 11.2决策树. 292 122.2背包问题...... 324 11,2.1排序算法的决策树......293 122,3旅行商问题125 11.2.2查找有序数组的决策树...295 习题12.2... 327 与题11.2 296 12.3NP困难问题的近似算法.........328 113P、NP和NP完全问题 298 12.3.1旅行商问题的近似算法...329 11.3.IP和NP问题, 298 123.2背包问题的近似算法 38 13.2NP完全问题 习题12.3....341 习题11.3. 304 124解非线性方程的算法. 342 114数值算法的挑战 306 12.4.1平分法 343 」题114 311 1242试位法 小结... 4.++a, 312 1243牛顿法 347 第12章超越算法能力的极限 ,314 习题12.4... 1349 小结 350 12.I回溯法... 314 12.1.1n旱后问题 跋 ...,351 12l2哈密顿回路问题...1316附录A算法分析的实用公式... 354 12.13集和问题.... 317 附录B递推关系简明指南 12.14般性说明.......318 小题12.1 319习题提示... 12.2分支界限法... 321参考文献... 400 122.1分配问题. 第1章绪论 科技殿堂里陈列着两颗熠熠生辉的宝石,一颗是微积分,另一颗就是算法。微积分以 及在微积分基础上建立起来的数学分析体系成就了现代科学,而算法则咸就了现代世界。 -David Berlinski, The Advent of the Algorithm, 2000 为什么要学习算法?如果你想成为一名计算机专业人土,无论从理论还是从实践的角 度,学习算法都是必需的。从实践的角度来看,我们必须了解计算领域中不同问题的一系 列标准算法。此外,我们还要具备设计新算法和分析其效率的能力。从理论的角度来看, 对算法(有时称为“算法学”)的硏究已经被公认为是计算机科学的基石。 David harel写了 本非常好的书,他直截了当地将其命名为 algorithmics: the spirit of Computing《算法学: 计算精髓》。书中是这样阐述这个问题的: 算法不仅是计算机科学的一个分支,它更是计算机科学的核心。而且,可以亳不夸张 地说,它同绝大多数科学、商业和技术都是相关的。(Har92l,p6) 即使是非计算机相关专业的学生,学习算法的理由也是非常充分的。坦率地说,没有 算法,计算机程序将不复存在。而且,随着计算机日益渗透到我们的工作和生活的方方面 面,需要学习算法的人也越来越多 学习算法的另一个理由是可以用它来开发人们的分析能力。毕竟,算法可以看作是解 决问题的一类特殊方法——它虽非问题的答案,但它是经过准确定义以获得答案的过程。 因此,无论是否涉及计算机,特定的算法设计技术都能看作是问题求解的有效策略。当然, 算法思想天生固有的精确性限制了它所能够解决的问题种类。比如说,我们找不到一种使 人幸福快乐的算法,也找不到一种使人功成名就的算法。但另一方面,从教育角度来看, 这种必要的精确性却是很重要的。 Donald knuth,算法学历史上最卓越的计算机科学家之 是这样论述这个问题的: 受过良好训练的计算机科学家知道怎样处理算法:如何构造算法、操作算法、理解算 法以及分析算法。这些知识远不止为了编写良好的计算机程序而准备的。算法是一种一般 性的智能工具,它必定有助于我们对其他学科的理解,不管是化学、语言学、音乐,还是 另外的学科。为什么算法会有这种作用呢?我们可以这样理解:人们常说,一个人只有把 知识教给别人,才能真正掌握它。实际上,一个人只有把知识教给“计算机”,才能“真 正”掌握它,也就是说,将知识表述为一种算法......比起简单地按照常规去理解事物,用 算法将其形式化会使我们的理解更加深刻。([Kn96],p.9) 我们从1.1节开始涉及算法的概念。作为例子,我们将针对同一问题(求最大公约数) 使用3种不同的算法。这样做有几个理由。首先,这是大家在中学时代就非常熟悉的问题。 其次,它揭示了一个重要的观点:同样的问题往往能用多种算法解决。这3种算法之所以 算法设计与分析基础(第2版) 具有典型意义,是因为它们的解题思路不同,复杂程度不同,解题效率也各不相冋。第三, 我希望将其中一个算法作为本书最先介绍的算法,这不仅因为它历史悠久——两千多年前 它就出现在了欧几里得的著作中,还因为它不朽的力量和重要性。最后,以中学里求最大 公约数的步骤为例,我们可以重点指出作为一个算法所必须满足的严格要求。 1.2节讲述算法解题的分析和计算问题。我们将会讨论有关算法设计和分析的一些重要 内容。内容涉及算法解题的不同方面,包括问题的分析、如何正确表述一个算法以及算法 的效率分析。这一节不能传授秘方为任意问题设计算法。这是一个公认的事实—这种秘 方是不存在的。但当大家日后进行自己的算法设计和分析工作时,肯定会用到1.2节的 内容。 1.3节将讨论几种重要的问题类型。经验证明,无论对于算法教学还是对于算法应用, 这些问题类型都是极其重要的。实际上,有些教材比如[Sed88]就是围绕这些问题类型来 组织内容的。尽管包括我在内的许多人都认为围绕算法设计技术来组织内容更有优势,但 无论如何,了解这些重要的问题类型是十分必要的。一是因为这些类型是实际应用中最常 遇到的,二是由于本书从头到尾都会用它们来演示一些特殊的算法设计技术。 1.4节复习了基本的数据结构。安排这一节的目的与其说是为了讨论这方面的内容,还 不如说是为了把它作为读者的参考材料。如果需要了解更详细的内容,有许多关于该主题 的优秀书籍可供参阅,但大多数都是和某一种编程语言相关的。 11什么是算法 虽然对于这个概念没有一个大家公认的定义,但我们对它的含义还是有基本共识的。 箅法是一系列解决问题的清晰指令,也就是说,对于符合一定规范的输入,能够在有 限时间内获得所要求的输出。 这个定义可以用一幅简单的图来说明(图L.1)。 问题 算法 输入 comp uter” 输出 图1.1算法的概念 定义中使用了“指令”这个词,这意味着有人或物能够理解和执行所给出的命令,我 们将这种人或物称为“ computer”。请记住,在电子计算机发明以前,“ computer”的含义 是指那些从事数学计算的人。现在,“ computer”当然是特指那些做每件事情都越发不可 或缺的、无所不在的电子设备。但要注意的是,虽然绝大多数算法最终会靠计算机来执行, 第1章绪论 但算法概念本身并不依赖于这样一个假设。 为了阐明算法的概念,本节将以3种方法为例子来解决同一个问题:计算两个整数的 最大公约数。这些例子会帮助我们阐明凡项要点 算法的每一个步骤都必须没有歧义,不能有半点含糊。 必须认真确定算法所处理的输入的值域 同一算法可以用几种不同的形式来描述 同一问题,可能存在几种不同的算法。 针对同一问题的算法可能会基于完全不同的解题思路,而且解题速度也会有显著 不同。 还记得最大公约数的定义吗?两个不全为0的非负整数m和n的最大公约数记为 gcdm,n),代表能够整除(即余数为0m和n的最大正整数。亚历山大的欧几里得(公元前3 世纪所著的《几何原本》,以系统论述几何学而著称,在其中的一卷里,他简要描述了一 个最大公约数算法。用现代数学的术语来表述,欧几里得算法基于的方法是重复应用下列 等式,直到 m mod n等于0。 gcd(mn,n)=gcd(n, m mod n)( m mod n表示m除以n之后的余数) 因为gcd(m,O)=m(为什么?),m最后的取值也就是m和n的初值的最大公约数。 举例米说,gcd(60,24)可以这样计算: gcd(60,24)=gcd(24,12)=gcd02,0)=12 如果你对这个算法还没有足够的认识,可以做习题1.1的第5题,试着求一些较大数 的最大公约数。 下面是该算法的一个更加结构化的描述 用于计算gcd(m,m的欧几里得算法 第一步:如果n=0,返回m的值作为结果,同时过程结東;否则,进入第二步。 第二步:m除以n,将余数赋给r。 第三步:将n的值赋给m,将r的值赋给n,返回第一步。 我们也可以使用伪代码来描述这个算法: 算法 Euclid(m,n ∥使用欧几里得算法计算gcdm,m) ∥输入:两个不全为0的非负整数m,n H输出:m,n的最大公约数 while n≠0do ← m mod n HI←n F +I return m 我们怎么知道欧几里得算法最终一定会结束呢?通过观察,我们发现,每经过一次循 环,参加运算的两个算子中的后一个都会变得更小,而且绝对不会变成负数。确实,下一 次循环时,n的新值是 m mod n,这个值总是比n小。所以,第二个算子的值最终会变成0, 此时,这个算法也就停止了。 算法设计与分析基础(第2版) 就像其他许多问题一样,最大公约数问题也有多种算法。让我们看看解这个问题的另 外两种方法。第一个方法只基于最大公约数的定义:m和n的最大公约数就是能够同时整 除它们的最大正整数。显然,这样一个公约数不会大于两数中的较小者,因此,我们先有 r=minm,n}。我们现在可以开始检査t是否能够整除m和n:如果能,t就是最大公约数; 如果不能,我们就将t减1,然后继续尝试(我们如何确定该算法最终一定会结束呢?)。例 如,对于60和24这两个数来说,该算法会先尝试24,然后是23,这样一直尝试到12, 算法就结束了。 用于计算gcd(m,m)的连续整数检测算法 第一步:将mn{m,n)的值赋给t 第二步:m除以b,如果余数为0,进入第三步;否则,进入第四步。 第三步:n除以t,如果余数为0,返回t的值作为结果;否则,进入第四步。 第四步:把t的值减1。返回第二步。 注意,和欧几里得算法不同,按照这个算法的当前形式,当它的一个输入为0时,计 算岀来的结果是错误的。这个例子说明了为什么必须认真、清晰地规定算法输入的值域。 求最大公约数的第三种过程,我们应该从中学起就很熟悉了。 中学里计算gcd(m,m)的过程 第一步:找到m的所有质因数。 第二步:找到n的所有质因数。 第三步:从第-一步和第二步求得的质因数分解式中找出所有的公因数(如果p是一个公 因数,而且在m和n的质因数分解式分别出现过pn和p次,那么应该将p 重复min{pnpn}次)。 第四步:将第三步中找到的质因数相乘,其结果作为给定数字的最大公约数 这样,对于60和24这两个数,我们得到: 60=2×2×3×5 24=2×2×2×3 gcd(60,24)=2×2x3=12 虽然学习这个方法的那段中学时光是令人怀念的,但我们仍然注意到,第三个过程比 欧几里得算法要复杂得多,也慢得多(下一章中,我们将会讨论对算法运行时间进行求解和 比较的方法)。撇开低劣的性能不谈,以这种形式表述的中学求解过程还不能称为一个真正 意义上的算法。为什么?因为其中求质因数的步骤并没有明确定义:该步骤要求得到一个 质因数的列表,但我们十分怀疑中学里是否曾教过如何求这样一个列表。必须承认,这并 不是鸡蛋里挑骨头。除非解决了这个问题,否则我们不能下结论说,能够写一个实现这个 过程的程序(顺便说一句,第三步也没有定义清楚。当然,它的不明确性要比求质因数的步 燥史容易纠正一些。想想我们是如何求两个有序列表的公共元素的 所以,我们要介绍一个简单的算法,用来产生一个不大于给定整数n的连续质数序列。 第1章绪论 它很可能是古希腊人发明的,称为“埃拉托色尼筛”。该算法一开始初始化一个2~n的 连续整数序列,作为候选质数。然后,在算法的第一个循环中,它将类似4和6这样的2 的倍数从序列中消去。然后,它指向列表中的下一个数字—3,又将其倍数消去(我们这 里的做法过于直接,增加了不必要的开销。因为有一些数字,拿6来说吧,被消去了不止 次)。不必处理数字4,因为4本身和它的倍数都是2的倍数,它们已经在前面的步骤中 被消去了(同样道理,任何被消去的数字的倍数都不必考虑)。第三步处理序列中剩下的下 个元素—5。该算法以这个方式不断做下去,直到序列中已经没有可消的元素为止。序 列中剩下的整数就是我们要求的质数。 作为一个例子,我们尝试用这个算法找出n不大于25的质数序列: 2345678910I112131415161718192021 22 2324 11 13 15 17 19 21 13 25 13 3 对于这个例子来说,更多步骤已经多余了,因为它们只会消去在算法的前面循环中已 经消去的数字。序列中剩下的数字就是小于等于25的连续质数。 总而言之,其倍数仍未消去的最大数p应该满足什么条件呢?在回答这个问题之前, 我们先要注意到:如果当前步骤中,我们正在消去p的倍数,那么第一个值得考虑的倍数 是pxp,因为其他更小的倍数2p,...,(p-1)p己经在先前的步骤中从序列里消去了。了解 这个事实可以帮助我们避免多次消去相同的数字。显然,PXp不会大于n,p也不会大于万 向下取整的值记作√/,称向下取整函数)。在下面这段伪代码中,我们假设有一个函 数可以计算|m,当然,我们也能以不等式Pxp≤n作为判断循环是否继续的条件。 算法 Sieve(n) ∥实现“埃拉托色尼的筛子” ∥输入:一个正整数n≥2 /输出:包含所有小于等于n的质数的数组L forp←2 to n do alp]←p forp←2toyn」do∥参见伪代码前的说明 if AIp]≠0作没有被前面的步骤消去 j←p*p while j≤ndo A[←0∥将该元素标记为已经消去 ∥将A中剩余的元素复制到质数数组L中 i←0 for p 2 to n do ifAp]≠0 L[←AIp] 1译注:埃拉托色尼生于昔勒尼(在今利比亚)约公元前200年。 2译注:p以后,消去过程就可以停止了。 8译注:舍去小数部分后的整数值 算法设计与分析基础(第2版) i←i+l return L 这样就能够将“埃拉托色尼筛”应用在中学求解过程中了,我们得到了一个计算两个 正整数的最大公约数的正规算法。注意,还必须关注其中一个输入参数为1或者两个都为 的情况:因为严格来讲,数学家并不认为1是一个质数,所以这个方法并不能处理这种 输入。 在结束本节之前,还需要做一些说明。虽然我们这里举的例子有一些数学味道,但当 今所使用的大多数算法(即使是那些已经应用于计算机程序的算法)都不涉及数学问题。大 家可以看到,无论是工作中还是生活中,算法每天都在帮助我们处理各种事务。算法在当 今社会是无所不在的,它是信息时代的魔力引擎,希望这个事实能够使大家下定决心,深 入学习算法课程 习题1.1 1·研究一下 al-Khorezmil或者称为al- Khwarizmi),“算法”( algorithm)-词起源于 这个人的名字。研究过程中我们还会发现,“算法”一词的起源和“代数 (algebra) 词的起源是相同的。 2.如果告诉你,设立美国专利体系的基本目的是为了促进“有用的技术”,你认为 算法在这个国家能够申请到专利吗?算法是否应该允许申请专利呢? .a.按照算法要求的精确性写出你从学校到家里的驾驶指南。 b.按照算法要求的精确性写出你最喜欢的菜的烹饪方法。 4.设计一个计算L√m」的算法,n是任意正整数。除了赋值和比较运算,该算法只能 用到基本的四则运算操作 a.用欧几里得算法求gcd(31415,14142)。 b.用欧几里得算法求gcd31415,14142),比检查mn(m,n和gd(m,m)间连续整 数的算法快多少倍?请估算一下 6.证明等式gcd(mt,n)=gcd(n, m mod n对每一对正整数(mn)都成立 7.对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理?该算法在 处理这种输入的过程中,上述情况最多会发生几次? 8.a.对于所有m≥1,n≤10的输入,欧几里得算法最少要做几次除法? b.对于所有m≥1,n≤10的输入,欧几里得算法最多要做几次除法? 9.a.在欧几里得的书里,欧几里得算法用的不是整数除法,而是减法。请用伪代码 描述这个版本的欧几里得算法。 b.欧几里得游戏(参见[Bog)一开始,板上写有两个不相等的正整数。两个玩家 交替写数字,每一次,当前玩家都必须在板上写出任意两个板上数字的差,而且 这个数字必须是新的,也就是说,不能与板上任何一个已有的数字相同。当玩家 再也写不出新数字时,他就输了。请问,你是选择先行动还是后行动呢? 10.扩展欧几里得算法不仅能够求出两个正整数m和n的最大公约数d,还能求出 两个整数x和y(不一定为正),使得mx+ny=d