前　　言

一个人在接受科技教育时能得到的最珍贵的收获是能够终身受用的通用智能工具。 

——乔治?福赛思

无论是计算科学还是计算实践，算法都在其中扮演着重要角色。因此，这门学科中出现了大量的教材。它们在介绍算法的时候，基本上都选择了以下两种方案中的一种。第一种方案是按照问题的类型对算法进行分类。这类教材安排了不同的章节分别讨论排序、查找、图等算法。这种做法的优点是，对于解决同一问题的不同算法，它能够立即比较这些算法的效率。其缺点在于，由于过于强调问题的类型，它忽略了对算法设计技术的讨论。

第二种方案围绕着算法设计技术来组织章节。在这种结构中，即使算法来自于不同的计算领域，如果它们采用了相同的设计技术，就会被编成一组。从各方(例如[BaY95])获得的信心使我相信，这种结构更适合于算法设计与分析的基础课程。强调算法设计技术有三个主要原因。第一，学生们在解决新问题时，可以运用这些技术设计出新的算法。从实用的角度看，这使得学习算法设计技术颇有价值。第二，学生们会试图按照算法的内在设计方法对已知的众多算法进行分类。计算机科学教育的一个主要目的，就是让学生们知道如何发掘不同应用领域的算法间的共性。毕竟，每门学科都会倾向于把它的重要主题归纳为几个甚至一个规则。第三，依我看来，算法设计技术作为问题求解的一般性策略，在解决计算机领域以外的问题时，也能发挥相当大的作用。

遗憾的是，无论是从理论还是从教学的角度，传统的算法设计技术分类法都存在一些严重的缺陷。其中最显著的缺陷就是无法对许多重要的算法进行分类。由于这种局限性，这些书的作者不得不在按照设计技术进行分类的同时，另外增加一些章节来讨论特殊的问题类型。但这种改变导致课程缺乏一致性，而且很可能会使学生感到迷惑。

算法设计技术的新分类法

传统算法设计技术分类法的缺陷令我感到失望，它激发我开发一套新的分类法([Lev99])，这套分类法就是本书的基础。以下是这套新分类法的几个主要优势。

新分类法比传统分类法更容易理解。它包含的某些设计策略，例如蛮力法、减治法、变治法、时空权衡和迭代改进，几乎从不曾被看作重要的设计范例。

新分类法很自然地覆盖了许多传统方法无法分类的经典算法(欧几里得算法、堆排序、查找树、散列法、拓扑排序、高斯消去法、霍纳法则等，不胜枚举)。所以，新分类法能够以一种连贯的、一致的方式表达这些经典算法的标准内容。

新分类法很自然地容纳了某些设计技术的重要变种(例如，它能涵盖减治法的3个变种和变治法的3个变种)。

在分析算法效率时，新分类法与分析方法结合得更好(参见附录B)。

设计技术作为问题求解的一般性策略

在本书中，主要将设计技术应用于计算机科学中的经典问题(这里唯一的创新是引入了一些数值算法的内容，我们也是用同样的通用框架来表述这些算法的)。但把这些设计技术看作问题求解的一般性工具时，它们的应用就不仅限于传统的计算问题和数学问题了。有两个因素令这一点变得尤其重要。第一，越来越多的计算类应用超越了它们的传统领域，并且有足够的理由使人相信，这种趋势会愈演愈烈。第二，人们渐渐认识到，提高学生们的问题求解能力是高等教育的一个主要目标。为了满足这个目标，在计算机科学课程体系中安排一门算法设计和分析课程是非常合适的，因为它会告诉学生如何应用一些特定的策略来解决问题。

虽然我并不建议将算法设计和分析课程变成一门教授一般性问题求解方法的课程，但我深信，我们不应错过算法设计和分析课程提供的这样一个独一无二的机会。为了这个目标，本书包含了一些和谜题相关的应用。虽然利用谜题来教授算法课程绝不是我的创新，但本书打算通过引进一些全新的谜题来系统地实现这个思路。

如何使用本书

我的目标是写一本既不泛泛而谈，又可供学生们独立阅读的教材。为了实现这个目标，本书做了如下努力。

根据乔治?福赛思的观点(参见前面的引文)，我试图着重强调隐藏在算法设计和分析背后的主要思想。在选择特定的算法来阐述这些思想的时候，我并不倾向于涉及大量的算法，而是选择那些最能揭示其内在设计技术或分析方法的算法。幸运的是，大多数经典算法满足这个要求。

第2章主要分析算法的效率，该章将分析非递归算法的方法和分析递归算法的典型方法区别开来。这一章还花了一些篇幅介绍算法经验分析和算法可视化。

书中系统地穿插着一些面向读者的提问。其中有些问题是经过精心设计的，而且答案紧随其后，目的是引起读者的注意或引发疑问。其余问题的用意是防止读者走马观花，不能充分理解本书的内容。

每一章结束时都会对本章最重要的概念和结论做一个总结。

本书包含600多道习题。有些习题是为了给大家练习，另外一些则是为了指出书中正文部分所涉及内容的重要意义，或是为了介绍一些书中没有涉及的算法。有一些习题利用了因特网上的资源。较难的习题数量不多，会在教师用书中用一种特殊的记号标注出来(因为有些学生可能没有勇气做那些有难度标注的习题，所以本书没有对习题标注难度)。谜题类的习题用一种特殊的图标做标注。

本书所有的习题都附有提示。除了编程练习，习题的详细解法都能够在教师资源中找到。请发送邮件到coo@netease.com，申请教师相关资源(也可联系培生公司的当地销售代表，或者访问www.pearsonhighered.com/irc)。本书的任何读者都可以在CS支持网站http://cssupport.pearsoncmg.com上找到PowerPoint格式的幻灯片文件。如果对算法有兴趣，欢迎加入QQ群“算法学习交流”，群号：425283001。

第3版的变化

第3版有若干变化。其中最重要的变化是介绍减治法和分治法的先后顺序。第3版会先介绍减治法，后介绍分治法，这样做有以下几个优点。

较之分治法，减治法更简单。

在求解问题方面，减治法应用更广。

这样的编排顺序便于先介绍插入排序，后介绍合并排序和快速排序。

数组划分的概念通过选择性问题引入，这次利用Lomuto算法的单向扫描来实现，而将Hoare划分方法的双向扫描留至后文与快速排序一并介绍。

折半查找归入介绍减常量算法的章节。

另一个重要变化是重新编排第8章关于动态规划的内容，具体如下所述。

导述部分的内容是全新的。在前两版中用计算二项式系数的例子来引入动态规划这一重要技术，但在第3版中会介绍3个基础性示例，这样介绍的效果更好。

8.1节的习题是全新的，包括一些在前两版中没有涉及的流行的应用。

第8章其他小节的顺序也做了调整，以便达到由浅入深、循序渐进的效果。

此外，还有其他一些变化。增加了不少与本书所述算法相关的应用。遍历图算法不再随减治法介绍，而是纳入蛮力算法和穷举查找的范畴，我认为这样更合理。在介绍生成组合对象的算法时，新增了格雷码算法。对求解最近对问题的分治法有更深入的探讨。改进的内容包括算法可视化和求解旅行商问题的近似算法，当然参考文献也有相应的更新。

第3版一共新增约70道习题，其中涉及算法谜题和面试问题。

先修课程

本书假定读者已经学习了离散数学的标准课程和一门基础性的编程课程。有了这样的知识背景，读者应该能够掌握本书的内容而不会遇到太大的困难。尽管如此，1.4节、附录A和附录B仍然对基本的数据结构以及必须用到的求和公式与递推关系分别进行复习和回顾。只有3个小节(2.2节、11.4节和12.4节)会用到一些简单的微积分知识，如果读者缺少必要的微积分知识，完全可以跳过这3个涉及微积分的小节，这并不妨碍对本书其余部分的理解。

课程进度安排

如果打算开设一门围绕算法设计技术来讲解算法设计和分析理论的基础课程，可以采用本书作为教材。但要想在一个学期内完成该课程，本书涵盖的内容可能过于丰富了。大体上来说，跳过第3～12章的部分内容不会影响读者对后面部分的理解。本书的任何一个部分都可以安排学生自学。尤其是2.6节和2.7节，它们分别介绍了经验分析和算法可视化，这两小节的内容可以结合课后练习 布置给学生。

下面给出了针对一个学期课程的教学计划，这是按照40课时的集中教学来设计的。

课次 主题                                                     小  节

1 课程简介                                              1.1～1.3

2，3 分析框架；常用符号 、 和                                     2.1，2.2                                  

4 非递归算法的数学分析                                       2.3

5，6 递归算法的数学分析                                       2.4，2.5(+附录B)

7　 蛮力算法                                               3.1，3.2(+3.3)

8 穷举查找                                                   3.4

9 深度优先查找和广度优先查找                                3.5

10～11 减一算法：插入排序、拓扑排序                              4.1，4.2

12 折半查找和其他减常量算法                             4.4

13 减变量算法                                              4.5

14～15 分治法：合并排序、快速排序                              5.1～5.2

16 其他分治法示例                                             5.3、5.4或5.5

16　 减变量算法                                            5.6

17～19 实例化简：预排序、高斯消去法、平衡查找树           6.1～6.3

20 改变表现：堆和堆排序或者霍纳法则和二进制幂            6.4或6.5

21 问题化简                                             6.6

22～24 时空权衡：串匹配、散列法、B树　                            7.2～7.4

25～27 动态规划算法                                               8.1～8.4(选3节)

28～30 贪婪算法：Prim算法、Kruskal算法、Dijkstra算法、哈夫曼算法 9.1～9.4

31～33 迭代改进算法                                               10.1～10.4(选3节)

34 下界的参数                                                  11.1

35 决策树                                                           11.2

36 P、NP和NP完全问题                                          11.3

37 数值算法                                                 11.4(+12.4)

38 回溯法                                                         12.1

39 分支界限法                                                 12.2

40 NP困难问题的近似算法　                                         12.3 

致谢

我要向本书的评审表达衷心的感谢，还要感谢本书前两版的许多读者，他们提供了许多宝贵的意见和建议，帮助本书得以改进和完善。本书第3版尤其得益于下列人士的评审，包括Andrew Harrington(芝加哥洛约拉大学)、David Levine(圣文德大学)、Stefano Lombardi(加州大学河滨分校)、Daniel McKee(宾州曼斯菲尔德大学)、Susan Brilliant(弗吉尼亚州立联邦大学)、David Akers(菩及海湾大学)以及两名匿名评审。

我要感谢培生出版社所有为本书付出不懈努力的工作人员和相关人士。尤其要感谢本书编辑Matt Goldstein、编务助理Chelsea Bell、市场经理Yez Alayan和产品总监Kayla Smith-Tarbox。我还要感谢Richard Camp为本书审稿，Windfall Software的Paul Anagnostopoulos和Jacqui Scarlott为本书排版并提供项目管理支持，以及MaryEllen Oliver为本书进行校对。

最后，我要感谢两位家人。另一半整天都在写书比自己本人写书更让人崩溃，我的妻子Maria已容忍我多年并任劳任怨地帮助我，本书400多幅插图以及教师手册都是凭她一己之力完成的。女儿Miriam是我多年的英语老师，她不但阅读了本书大量篇幅，还帮我为每章找到了合适的名人名言。

Anany Levitin

anany.levitin@villanova.edu