算法分析与设计基础.docx

算法分析与设计基础 （清华版） Taken from Introduction to The Design and Analysis of Algorithms by Anany Levitin节选自算法设计与分析基础潘彦 译蛮力法 就像宝剑不是撬棍一样，科学也很少使用蛮力。Edward Lytton (1830 - 1873)，leila，第二卷，第一章认真做事常常是浪费时间。Robert Byrne，撞球大师，台球选手和作家人们是这样描述它的：蛮力法是一种简单直接地解决问题的方法，常常直接基于问题的描述和所涉及的概念定义。这里的“力”是指计算机的能“力”，而不是人的智“力”。我们也可以用“直接做吧！”来描述蛮力法的策略。而且一般来说，蛮力策略也常常是最容易应用的方法。虽然巧妙和高效的算法很少来自于蛮力法，但我们不应该忽略它作为一种重要的算法设计策略的地位。第一，和其他某些策略不同，我们可以应用蛮力法来解决广阔领域的各种问题（实际上，它可能是惟一一种几乎什么问题都能解决的一般性方法）。具体来说，蛮力法常常用于一些非常基本、但又十分重要的算法，比如计算n个数字的和，求一个列表的最大元素，等等。第二，对于一些重要的问题来说（比如：排序、查找、矩阵乘法和字符串匹配），蛮力法可以产生一些合理的算法，它们多少具备一些实用价值，而且并不限制实例的规模。第三，如果要解决的问题实例不多，而且蛮力法可以用一直能够接受的速度对实例求解，那么，设计一个更高效算法所花费的代价很可能是不值得的。第四，即使效率通常很低，仍然可以用蛮力算法解决一些小规模的问题实例。最后，一个蛮力算法可以为研究或教学目的服务，例如，它可以作为准绳，来衡量同样问题的更高效算法。下列这些著名的算法可以看作是蛮力法的例子：基于定义的矩阵乘法算法；选择排序；顺序查找；简单的字符串匹配算法。穷举查找是解组合问题的一种蛮力方法。它要求生成问题中的每一个组合对象，选出其中满足该问题约束的对象，然后找出一个期望的对象。旅行商问题、背包问题和分配问题是典型的能够用穷举查找算法求解的问题，至少在理论上是这样的。除了相关问题的一些规模非常小的实例，穷举查找法几乎是不实用的。 分治法 无论人们在祈祷什么，他们总是在祈祷一个奇迹。每一个祈祷都可以简化为：伟大的上帝呀，请让两个二相加不等于四吧。伊万屠格涅夫（1818 1883），俄国作家和短篇小说家分治法可能是最著名的通用算法设计技术了。虽然它的名气可能和它那好记的名字有关，但它的确是当之无愧的：很多非常有效的算法实际上是这个通用算法的特殊实现。其实，分治法是按照以下方案工作的： 将问题的实例划分为同一个问题的几个较小的实例，最好拥有同样的规模。 对这些较小的实例求解（一般使用递归方法，但在问题规模足够小的时候，有时也会使用一些其他方法）。 如果必要的话，合并这些较小问题的解，以得到原始问题的解。 不是所有的分治算法都一定比简单蛮干更有效。但是，通常我们向算法女神所做的祈祷都被应允了，因而，使用分治法往往比使用其他方法效率更高。实际上，分治法孕育了计算机科学中许多最重要和最有效的算法。虽然我们通常只考虑顺序算法，但要知道，分治法对于并行算法是非常理想的，因为各个子问题都可以由不同的CPU同时计算。许多分治算法的时间效率T(n)满足方程T(n)=aT(n/b)+f(n)。一些应用分治法的案例：合并排序是一种分治排序算法。它把一个输入数组一分为二，并对它们递归排序，然后把这两个排好序的子数组合并为原数组的一个有序排列。在任何情况下，这个算法的时间效率都是(nlogn)，而且它的键值比较次数非常接近理论上的最小值。它的主要缺点是需要相当大的额外存储空间。快速排序是一种分治排序算法，它根据元素值和某些事先确定的元素的比较结果，来对输入元素进行分区。快速排序十分有名，这不仅因为对于随机排列的数组，它是一种较为出众的nlogn效率算法，而且因为它的最差效率是平方级的。折半查找是一种对有序数组进行查找O(logn)效率算法。它是应用分治技术的一个非典型案例，因为在每次迭代中，它只需要解决两个问题的一个。二叉树的经典遍历算法前序、中序、后序和其他类似的算法都需要递归处理左右两棵子树，它们都可以当作是分治技术的例子。用一些特定的外部顶点来替代给定树的空子树，有助于对这些算法进行分析。有一种处理两个n位整数相乘的分治算法，大约需要做n(index:1.585)次一位数乘法。Strassen算法只需要做7次乘法就能计算出两个2桔方阵的积，但比基于定义的算法要做更多次的加法。利用分治技术，该算法计算两个n阶方阵的积，但比基于定义的算法要做更多次的加法。利用分治技术，该算法计算两个n阶方阵的乘法时需要做n(index:2.807)次乘法。分治技术可以成功地应用于两个重要的计算几何问题：最近对问题和凸包问题。 减治法 普卢塔克说，萨特斯为了告诉他的士兵坚忍和智慧比蛮力更重要的道理，把两匹马带到他们面前，然后让两个人拔光马的尾毛。一个人是魁梧的大力士，他用力地拔了又拔，但一点效果也没有；另一个人是一个精美的、长相矫捷的裁缝，他微笑着，每次拔掉一根毛，很快就把尾巴拔得光秃秃的。E. Cobham Brewer，惯用语和寓言词典，1898减治技术利用了一种关系：一个问题给定实例的解和同样问题较小实例的解之间的关系。一旦建立了这样一种关系，我们既可以从顶至下（递归地），也可以从底至上（非递归地）地来运用。减治法有3种主要的变种： 减去一个常量； 减去一个常数因子； 减去的规模是可变的。 在减常量变种中，每次算法迭代总是从实例规模中减去一个规模相同的常量。一般来说，这个常量等于一，但减二的情况偶尔也会发生，例如，有的算法会根据实例规模为奇数和偶数的不同情况，分别做不同的处理。减常因子技术意味着在算法的每次迭代中，总是才实例的规模中减去一个相同的常数因子。在大多数应用中，这样的常数因子等于二。最后，在减治法的减可变规模变种中，算法在每次迭代时，规模减小的模式都是不同的。计算最大公约数的欧几里德算法是这种情况的一个很好的例子。回想一下，这个算法是基于这个公式的：gcd(m,n)=gcd(n,m mod n)虽然等号右边的那些参数总是小于等号左边的参数（至少从该算法的第二次迭代开始），但它们既不是以常数也不是以常数因子的方式减小的。一些应用减治法的案例：插入排序是减（减一）治技术在排序问题上的直接应用。无论在平均情况还是最差情况下，它都是一个(n2)的算法，但在平均情况下的效率大约要比最差情况快两倍。该算法一个较为出众的优势在于，对于几乎有序的数组，它的性能是很好的。深度优先查找(DFS)和广度优先查找(BFS)是两种主要的图遍历算法。通过把图表示成深度优先森林或者广度优先森林的形式，有助于对图的许多重要特性进行研究。两种算法都有着相同的时间效率：对于邻接矩阵表示法来说是(|V|2)；对于邻接链表表示法来说是(|V|+|E|)。一个有向图是一个对边指定了方向的图。拓扑排序要求按照这种次序列出它的顶点，使得对于图中每一条边来说，边的起始顶点总是排在边的结束顶点之前。当且仅当有向图是一个无环有向图（不包含回路的有向图）的时候，该问题有解，也就是说，它不包含有向的回路。解决拓扑排序问题有两种算法。第一种算法基于深度优先查找；第二种算法基于减一技术的直接应用。在设计生成基本组合对象的算法时，减一技术是一种非常自然的选择。这类算法中最高效的类型是最小变化算法。然而，组合对象的数量增长地如此之快，使得实际应用中，即使最高效的算法也只能用来解决这类问题的一些非常小的实例。有些问题是能够用减常因子算法来解的，这样的例子包括：用天平来辨别假币、俄式乘法以及约瑟夫斯问题。其他两个更重要的例子是折半查找和用平方求幂。对于某些基于减治技术的算法，在算法的一次迭代和另一次迭代时消减的规模是变化的。这种减可变规模算法的例子包括欧几里德算法、选择问题的基于分区的算法、插值查找和二叉查找树中的查找和插入操作。 变治法 生活的秘密在于。用一个烦恼代替另一个烦恼。Charles M. Schulz (1922 - 2000)，美国漫画家，史努比之父这种设计方法基于变换的思想，称为变治法。因为这些方法都是分成两个阶段工作的。首先，在“变”的阶段，出于这样或者那样的原因，把问题的实例变得更容易求解。然后，在第二阶段或者说“治”的阶段，对实例进行求解。根据我们对问题实例的变换方式，变治思想有3种主要的类型： 变换为同样问题的一个更简单或者更方便的实例我们称之为实例化简； 变换为同样问题的不同表现我们称之为改变表现。 变换为另一个问题的实例，这种问题的算法是已知的我们称之为问题化简。 一些应用变治法的案例：堆是一棵基本完备二叉树，它的键都满足父母优势要求。虽然定义为二叉树，但一般用数组来实现堆。堆对于优先队列的高效实现来说尤为重要；同时，堆还是堆排序的基础。堆排序在理论上是一种重要的排序算法，它的基本思路是，在排好堆中的数组元素后，再从剩余的堆中连续删除最大的元素。无论在最差情况下还是在平均情况下，该算法的运行时间都属于(nlogn)，而且，它还是在位的排序算法。AVL树是一种在二叉树可能达到的广度上尽量平衡的二叉查找树。平衡是由四种称为旋转的变换来维持的。AVL树上的所有基本操作都属于(logn)；它消除了经典二叉查找树在最差效率上的弊端。2-3树是一种达到了完美平衡的查找树，它允许一个节点最多包含两个键和三个子女。这个思想推而广之，会产生一种非常重要的B树。高斯消去法是一种解线性方程组的算法，它是线性代数中的一种基本算法。它通过把方程组变换为反向替换法求解。高斯消去法大约需要1/3n3次乘法运算。在无需对系数进行预处理的多项式求解算法中，霍纳法则是最优的。它只需要n次乘法和n次加法。它还有一些有用的副产品，比如综合除法算法。两种计算a(index:n)的二进制幂算法。它们使用了指数n的二进制表示，但它们按照相反的方向对其进行处理：从左到右和从右到左。线性规划关心的是最优化一个包含若干变量的线性函数，这个函数受到一些形式为线性等式和线性不等式的约束。有一些高效的算法可以对这个问题的庞大实例求解，它们包含了成千上万的变量和约束，但不能要求变量必须是整数。如果变量一定要是整数，我们称之为整数线性规划问题，这类问题的难度要高很多。 时空权衡 最重要的事情永远不能受次要事情的支配。Johnn Wolfgang von Goethe (1749 - 1832)无论对于计算机理论工作者还是计算机实践工作者来说，算法设计中的时空权衡都是一个总所周知的问题。作为一个例子，考虑一下在函数定义域的多个点上计算函数值的问题。如果运算时间更为重要的话，我们可以事先把函数值计算好并将它们存储在一张表中。这就是在电子计算机发明前，“人工计算机”所做的工作，那时的图书馆也被厚重的数学用表堆满了。虽然随着电子计算机的广泛应用，这些数学用表失去了大部分的吸引力，但事实正面，在开发一些用于其他问题的重要算法时，它们的基本思想还是非常有用的。按照一种更一般的表述，这个思想是对问题的部分或全部输入做预处理，然后对获得的额外信息进行存储，以加速后面问题的求解。我们把这个方法称为输入增强。其他采用空间换时间权衡思想的技术简单地使用额外空间来实现更快和（或）更方便的数据存取。我们把这种方法称为预构造。这个名字强调了这种空间换时间权衡技术的两个方面：所讨论问题在实际处理之前，已经做过某些处理了；但和输入增强技术不同，这个技术只涉及存取结构。还有一种和空间换时间权衡思想相关的算法设计技术：动态规划。这个策略的基础是把给定问题中重复子问题的解记录在表中，然后求得所讨论问题的解。最后还要对算法设计中时间和空间的相互作用作两点说明：首先，并不是在所有的情况下，时间和空间这两种资源都必须相互竞争。实际上，它们可以联合起来，使得一个算法无论在运行时间上还是消耗的空间上都达到最小化。具体来说说，这种情况出现在一个算法使用了一种空间效率很高的数据结构来表示问题的输入，这种结构又反过来提高算法的时间效率。作为一个例子，考虑一下图的遍历问题。回忆一下两种主要的遍历算法（深度优先查找和广度优先查找），它们搜时间效率依赖于表示图的数据结构：对于邻接矩阵表示法是(n2)，对于邻接链表表示法是(n+m)，其中n和m分别是顶点和边的数量。如果输入图是稀疏的，也就是说，相对于顶点的数量来说，边的数量并不多（比方说，mO(n)），无论从空间角度还是从运行时间的角度来看，邻接链表表示法的效率都会更高一些。在处理稀疏矩阵和稀疏多项式的时候也会有相同的情况：如果在这些对象中，0所占的百分比足够高，在表示和处理对象时把0忽略，我们既可以节约空间也可以节约时间。其次，在讨论空间换时间权衡的时候，我们无法不提到数据压缩这个重要领域。然而，我们必须强调，数据压缩的主要目的是节约空间而不是作为解决另一个问题的一项技术。一些应用时空权衡的案例：分布计数是一种特殊的方法，用来对元素取值来自于一个小集合的列表排序。用于串匹配的Horspool算法可以看作是Boyer-Moore算法的一个简化版本。两个算法都以输入增强思想为基础，并且从右向左比较模式中的字符。两个算法都是用同样的坏符合移动表；Boyer-Moore算法还使用了第二个表，称为好后缀移动表。散列是一种非常高效的实现字典的方法。它的基本思想是把键映射到一张一维表中。这种表在大小上的限制使得它必须采用一种碰撞解决机制。散列的两种主要类型是开散列又称为分离链（键存储在散列表以外的链表中）以及闭散列又称为开式寻址（键存储在散列表中）。平均情况下，这两种算法的查找、插入和删除操作的效率都是属于(1)的。B树是一颗平衡查找树，它把2-3树的思想推广到允许多个键位于同多节点一个节点上。它的主要应用是维护存储在磁盘上的数据的类索引信息。通过选择恰当的树的次数，即使对于非常大的文件，我们所实现的查找、插入和删除操作也只需要执行很少几次的磁盘存取。 动态规划 思想，就像幽灵一样在它自己解释自己之前，必须先告诉它些什么。查尔斯狄更斯(1812-1870)动态规划(dynamic programming)是一种算法设计技术，它有着相当有趣的历史。作为一种使多阶段决策过程最优的通用方法，它是在20世纪50年代由一位卓越的美国数学家Richard Bellman所发明的。因此，这个技术名字中的programming是计划和规范的意思，不是代表计算机中的编程。它作为一种重要的工具在应用数学中的价值被大家认同以后，起码在计算机科学的圈子里，人们不仅用它来解决特定类型的最优问题，而且最终把它作为一种通用的算法设计技术来使用。在这里，我们正是从这个角度来考虑这种技术的。如果问题是由交叠的子问题所构成的，我们就可以用动态规划技术来解决它。一般来说，这样的子问题出现在对给定问题求解的递推关系中，这个递推关系中包含了相同类型的更小子问题的解。动态规划法建议，与其对交叠的子问题一次又一次地求解，还不如对每个较小的子问题只求解一次并把结果记录在表中，这样就可以从表中得出原始问题的解。一般来说，一个算法如果基于经典从底向上动态规划方法的话，需要解出给定问题的所有较小子问题。动态规划法的一个变种试图避免对不必要的子问题求解，它利用了一种所谓的记忆功能，可以把它看作是动态规划的一种从顶至下的变种。但无论我们使用动态规划的经典从底至上版本还是它基于记忆功能的从顶至下版本，设计这样一种算法的关键步骤还是相同的，即，导出一个问题实例的递推关系，该递推关系包含该问题的更小（并且是交叠的）子实例的解。对一个最优问题应用动态规划方法要求该问题满足最优性原则：一个最优问题的任何实例的最优解是由该实例的子实例的最优解组成的。一些应用动态规划的案例：通过构造帕斯卡三角形来计算二项式系数可以看作是动态规划技术在一个非最优问题上的应用。求传递闭包的Warshall算法和求完全最短路径问题的Floyd算法都基于同一种思想，可以把这种思想解释为动态规划技术的一种应用。如果已知键的一个集合以及它们的查找概率，可以使用动态规划方法来构造一颗最优二叉查找树。用动态规划算法求解背包问题可以作为应用该技术对组合难题求解的例证。 贪婪技术 贪婪，我找不到一个更好的词来描述它，它就是好！它就是对！它就是有效！美国演员迈克道格拉斯，在影片华尔街中扮演Gordon Gecko时的台词贪婪法建议通过一系列步骤来构造问题的解，每一步对目前构造的部分解做一个扩展，直到获得问题的完整解为止。这个技术的核心是，所做的每一步选择都必须满足： 可行的：即它必须满足问题的约束。 局部最优：它是当前步骤中所有可行选择中最佳的局部选择。 不可取消：即选择一旦做出，在算法的后面步骤中就无法改变了。 这些要求对这种技术的名称作出了解释：在每一步中，它要求“贪婪”地选择最佳操作，并希望通过一系列局部的最优选择，能够产生一个整个问题的（全局的）最优解。我们尽量避免从哲学的角度来讨论贪婪是好不好。（如果大家还没有看过本章的引语中提到的那部电影，我可以告诉大家，影片中男主人公的结局并不大好。）才我们算法的角度来看，这个问题应该是，贪婪算法是否是有效的。就像我们将会看到的，的确存在某些类型问题，一系列局部的最优选择对于它们的每一个实例都能够产生一个最优解。然而，还有一些问题并不是这种情况。对于这样的问题，如果我们关心的是，或者说我们能够满足于一个近似解，贪婪算法仍然是有价值的。作为一种规则，贪婪算法看上去既诱人又简单。尽管看上去它们并不复杂，但在这种技术背后有着相当复杂的理论，它是基于一种被称为“拟阵”的抽象组合结构。一些应用贪婪技术的案例：Prim算法是一种为加权连通图构造最小生成树的贪婪算法。它的工作原理是向前面构造的一颗子树中添加离树中顶点最近的顶点。Kruskal算法是另一种最小生成树问题的算法它按照权重的增序把边包含进来，以构造一颗最小生成树，并使得这种包含不会产生一条回路。为了保证这种检查的效率，需要应用一种所谓的union-find算法。Dijkstra算法解决了单起点最短路径问题，该问题要求出从给定的顶点（起点）出发通过加权图或者有向图的其他所有顶点的最短路径。它的工作过程和Prim算法是一样的，不同点在于它比较的是路径的长度而不是边的长度。对于不含负权重的图，Dijkstra算法总是能够产生一个正确的解。哈夫曼树是一颗二叉树，它使得从根出发到包含一组预定义权重的叶子之间的加权路径长度达到最小。哈夫曼树的最重要的应用是哈夫曼编码。哈夫曼编码是一种最优的自由前缀变长编码方案，它基于字符在给定文本中的出现频率，把比特串赋给字符。这是通过贪婪地构造一颗二叉树来完成的，二叉树的叶子代表字母表中的字符，而树中的边则标记为0或者1。 回溯法和分支限界法 关注那些不断已被他人成功应用的新思路。你的原创思想只应该应用在那些你正在研究的问题上。托马斯爱迪生(1847-1931)回溯和分支限界都是以构造一颗状态空间树为基础的，树的节点反映了对一个部分解所作的特定选择。如果可以保证，节点子孙所对应的选择不可能得出问题的一个解，两种技术都会立即停止处理这个节点。两种技术的区别在于它们能够处理的问题类型不同。分支限界法只能应用于最优问题，因为它基于针对一个问题的目标函数，计算其可能值的边界。回溯法并不受这种要求的制约，但在大多数情况下，它处理的是非优化问题。回溯法和分支限界法的另一个区别在于它们生成状态空间树的节点顺序不同。对于回溯法来说，它的树的生长顺序常常是深度优先的（也就是和DFS类似）。分支限界法可以根据多种规则生成节点，如最佳优先原则。回溯的主要思想是每次只构造解的一个分量，然后按照下面的方法来评估这个部分构造解。如果一个部分构造解可以进一步构造而不会违反问题的约束，我们就接受对解的下一个分量所做的第一个合法选择。如果无法对下一分量进行合法的选择，就不必在剩下的任何分量再做任何选择了。在这种情况下，该算法进行回溯，把部分构造解的最后一个分量替换为它的下一个选择。通过对所做的选择构造一颗所谓的状态空间树，我们很容易实现这种处理。树的根代表了在查找解之前的初始状态。树的第一层节点代表了对解的第一个分量所做的选择，第二层节点代表了对解的第二个分量所做的选择，以此类推。如果一个部分构造解仍然有可能导致一个完整解，我们说这个部分解在树中的相应节点是有希望的；否则，我们说它是没希望的。叶子则要么代表了没希望的死胡同，要么代表了算法找到的完整解。在大多数情况下，一个回溯算法的状态空间树是按照深度优先的方式来构造的。如果当前节点是有希望的，通过向部分解添加下一个分量的第一个合法选择，就生成了节点的一个子女，而处理也会转向这个子女节点。如果当前节点变得没希望了，该算法回溯到该节点的父母，考虑部分解的最后一个分量的下一个可能选择；如果这种选择不存在，它再回溯到树的上一层，以此类推。最后，如果