前言 PREFACE
算法的思想非常广泛，遍及计算机科学的内外.在因特网路由选择标准中的某些较大变化可以看做对一种最短路径算法的不足与另一种最短路径算法的相对优点争论的结果.生物学家用来表示基因和基因组之间相似性的基本概念是用算法定义的.经济学家表达的对组合拍卖在实践中可行性的关注，部分地源于这些拍卖实际上包含难计算的搜索问题作为特殊情况.而且算法概念不仅局限于已知的和长期存在的问题，人们在广泛领域内提出的新颖问题中经常看到这些思想的影响.雅虎的一位科学家在一次午餐上告诉我们，他们的用户广告服务系统一旦深入下去能够被描述成一组以网络流为模型的问题.我们在去纽约的旅途中偶然遇到一位以前的学生，现在正在做大型医院人事协议工作的管理顾问，也对我们说过类似的事情.
问题的关键不只是算法有很多的应用.更深刻的看法认为一般地算法作为一门学科是深入观察计算机科学领域的有力手段.算法问题构成计算机科学的核心，但它们出现时很少被清楚地表示成精确的数学问题.相反地，它们出现时常常把大量零乱的特殊应用细节、某些本质的东西和某些无关紧要的东西混杂在一起.结果是算法研究包括两个基本的部分: 获取问题纯粹的数学核心和根据问题的结构确定合适的算法设计技术.这两部分相互作用: 你愈能自如地使用丰富的算法设计技术，你愈开始能够认出隐藏在计算机科学之外的零乱问题中的纯粹形式描述.那么，如果充分发挥其作用，算法思想不仅为表述清楚的问题提供解答，而且是你纯粹地表达基本问题的语言.
这本书的目标是传达这种研究算法的方法，这是一个设计过程，它从在广泛的计算应用中提出的问题开始、建立在对算法设计技术理解的基础之上、并且最终发展对这些问题的有效解决.我们试图探讨各种算法思想在计算机科学中的作用，并把这些思想与我们能够设计分析算法的精确定义的问题的范围联系起来.换句话说，什么是促使提出这些问题的基本来源? 如何选择描述它们的具体方法? 如何在不同的场合认出哪一种设计原理是适合的?
与此相一致地，我们的目标是对下述问题提出建议和忠告: 如何在来自不同计算领域的复杂问题中确定纯粹的算法问题的形式描述，进而如何为所得到的问题设计有效的算法.理解巧妙复杂的算法的最好方法常常是重新构造从初始的简单方法到最终解决的一系列想法——包括错误的开始和行不通的办法.我们的讲解风格不是从问题陈述直接到算法，而是认为应该更好地反映我们和我们的同事们实实在在考虑这些问题的方法.
综览
本书供已学完两学期基于程序设计的导引性计算机科学系列（标准的“CS1/CS2”课程）的学生使用, 在这些课程中他们已经写过实现基本算法、使用离散结构(如, 树和图)并应用基本数据结构（如, 数组、表、队列和栈）的程序. 由于CS1/CS2与第一门算法课程的界面不是完全标准的, 为了使本书是自给自足的, 我们在开始部分包含某些院校学过CS1/CS2的学生熟悉的内容, 而在另一些院校这些内容包括在第一门算法课程的教学大纲中. 因此, 这些材料可以用来复习、也可以用来作为新的材料. 我们包含这些材料是希望本书在假设必备的先修知识方面具有更大的灵活性, 能够在更广的课程安排中使用.
〖1〗 算 法 设 计〖1〗 前言按照上面勾画的思路, 我们用取自计算机科学及相关学科许多领域内的问题开发基本的算法设计技术. 这里举几个典型的例子, 我们相当详细地讨论了来自下述领域的应用, 它们包括系统与网络（超高速缓存、交换、因特网上的域间路由选择）, 人工智能（规划、对策、Hopfield网络）, 计算机视觉（图像分割）, 数据挖掘（变更点检测、聚类）, 运筹学（航线调度）和计算生物学（序列比对、RNA二级结构）.
计算难解性的概念, 特别是NP完全性, 在书中起重要作用. 这与如何考虑完整的算法设计过程是一致的. 有时一个有趣的应用问题有有效的解法, 有时它被证明是NP完全的. 为了给出一个新的算法问题的完全定位, 人们应该能够同样熟练地探讨这两个方面. 由于计算机科学中的许多天然的问题是NP完全的, 因而开发处理难问题的方法已经成为算法研究中极为重要的课题. 本书充分地反映了这个课题. 不应把发现一个问题是NP完全的看做事情的结束, 而应当看做鼓励我们开始去寻找近似算法、启发式局部搜索算法或易解的特殊情况. 书中详细地介绍这三种方法.
练习与带解答的练习
本书的一个重要特点是收集了大量的练习. 全书各章总共包括200多个练习, 它们差不多都是我们在康奈尔大学讲授这门课时在课外作业或考试中开发并经过教学检验的. 我们把这些练习看做本书极为重要的部分, 并按我们处理材料的整体方式组织它们. 它们中大多数包括从计算机科学或其他领域的应用中提出问题的详细文字描述, 部分练习是实践课文中讨论的东西: 提出必要的概念和形式描述, 设计算法, 然后分析这个算法并证明其正确性（我们认为对一道练习的完整答案包括所有下述内容: 完整的算法说明, 运行时间的分析和正确性的证明）. 这些问题的思想大部分来自我们多年来与从事各种领域工作的人的讨论, 在某些情况下这些讨论有助于我们同时达到把在其他地方没有见过的有趣的（虽然是容易处理的）算法应用记录下来的目的.
为了帮助做这些练习, 每一章有一节的标题为“带解答的练习”, 这一节有一个或多个问题, 并描述如何详细地陈述解答. 因此, 用于每一个带解答的练习的讨论明显地比只写出完整的正确解答所需要的篇幅长得多（换句话说, 明显地比当把这些问题布置为课外作业时, 为了获得满分所需要的篇幅长得多）. 当然, 和正文的其他部分一样, 在这一节中的讨论是试图说明这个较长过程的道理, 通过这个过程能够考虑这种类型的问题并最终给出精确解答的详细描述.
关于用这些练习做课外作业有两点值得说明. 首先, 练习大体上按照由易到难的顺序排列, 但这只是一个粗略的指导并且建议不要把它看得太认真: 因为大部分练习是作为我们的本科生课程的课外作业设计的, 每一章的练习中有很大一部分的难度实际上相差不多. 其次, 除编号最小的几个外, 练习需要投入一些时间, 把问题的描述与这一章的算法技术联系起来, 然后设计需要的算法. 我们在本科生课程中每周大约布置3道这样的练习.
教学特色与补充材料
除练习和带解答的练习之外, 本书还有一些其他的教学特色以及帮助教学使用的其他补充材料.
正如早先指出的, 书中大量的节用来描述算法问题（包括它的背景和动机）和它的算法设计与分析. 为了反映这种风格, 这些节都统一地按照下述小节系列组织: “问题”， 在这一小节描述问题并给出精确的形式定义；“设计算法”, 在这一小节用合适的设计技术开发算法；“分析算法”, 这一小节证明这个算法的性质并分析它的效率. 这些小节在正文中用羽毛图标突出出来. 当继续讨论问题的推广或进一步分析算法时, 添加另外的小节. 这种结构的目的是使用相对统一的叙述风格——从初步讨论一个在计算应用中产生的问题一直到详细地分析解决它的方法.
能够得到支持本书的若干补充材料. 教师指南完成所有的练习, 提供每一道练习的完整解答. 还有由普林斯顿大学Kevin Wayne开发的讲演幻灯片, 幻灯片按照本书章节的顺序, 因而可以用做以本书为基本教材的课程的讲授基础. 这些文件可以从www.aw.com上得到. 关于教授注册和密码, 请搜索“Kleinberg”或“Tardos”的网址, 或者与你的AddisonWesley地区代表接触.
最后, 我们非常乐意收到对本书的反馈. 特别是像在任何一本这么厚的书中一样, 毫无疑问本书也有错误. 对错误的意见和报告可以通过电子邮件送给我们, 地址是algbook@cs.cornell.edu, 请在邮件的主题栏中注明“feedback”.
各章的大纲
第1章从介绍几个典型的算法问题开始. 我们一开始就是稳定匹配问题, 因为我们觉得它比任何抽象的讨论能够更具体更讲究地提出算法设计中的基本问题: 稳定匹配受到一个自然但复杂的现实世界问题的启发, 人们可以从这个问题中抽象出一个有趣的问题陈述和解决这个问题的惊人的有效算法. 第1章的剩余部分讨论5个“典型问题”, 它们预示着本课程的主题. 有意思的是这5个问题都是独立集问题的变种或特殊情况, 但一个能够用贪心算法解决, 一个能够用动态规划解决, 一个能够用网络流解决, 一个（独立集问题本身）是NP完全的, 还有一个是PSPACE完全的. 面对紧密相关的问题可能有各种不同的复杂性是本书重要的主题曲, 而且当本书前进一步时这5个问题中的一个作为里程碑再次出现.
第2章和第3章包括前面说的与CS1/CS2课程系列的界面. 第2章介绍在分析算法中使用的关键的数学定义和概念, 以及隐藏在它们后面发人深省的原理. 这一章开始时非形式地观察“一个问题是容易计算的”是什么意思, 并把多项式时间作为效率的形式概念. 然后更形式地讨论函数的增长率和渐近分析, 并对在算法分析中经常出现的函数以及它们的一般应用提供指导. 第3章包括使用图所必需的基本定义和基本算法, 对书中的许多问题图是极为重要的. 一些基本的图论算法在CS1/CS2课程系列的后期常常已经被学生实现, 但在这里仍值得在更广阔的算法设计的环境中介绍这些材料. 特别地, 我们讨论图的基本定义、图的遍历技术（如宽度优先搜索和深度优先搜索）以及有向图概念（包括强连通性和拓扑排序）.
第2章和第3章还要介绍将在全书用于实现算法的许多基本数据结构, 更高级的数据结构在随后的章中介绍. 我们接触数据结构的方法是, 当为了实现书中开发的算法需要它们的时候引进它们. 因此, 虽然这里介绍的许多数据结构可能是学过CS1/CS2系列的学生所熟悉的, 但是我们的着重点是更广阔的算法设计分析环境中的这些数据结构.
第4章到第7章包括4个主要的算法设计技术: 贪心算法, 分治法, 动态规划和网络流. 使用贪心算法的挑战是需要判断它们什么时候好用, 什么时候不好用. 我们围绕证明贪心算法正确性的方法的分类方式介绍这个主题. 这一章介绍了贪心算法的若干主要应用, 包括最短路径、无向的和有向的生成树、聚类以及压缩. 关于分治法, 我们从讨论解表示运行时间界限的递推关系的策略开始, 然后说明精通这些递推关系能够如何指导设计改进若干基本问题直接方法的算法, 包括排名比较、平面上最邻近点对的计算以及快速傅里叶变换. 接下去我们开发动态规划, 从隐藏在它后面的递归直觉开始, 随后通过应用建立愈来愈有表现力的递推表达式, 这些表达式是在这些应用中自然提出的. 这一章最后讨论了两个基本问题的动态规划方法: 序列比对及其在计算生物学中的应用, 图中的最短路径及其与因特网路由协议的联系. 最后, 我们介绍网络流问题的算法, 在这一章我们把很多注意力用来讨论大量不同的网络流应用. 就算法课程中包括网络流而言, 学生往往并不欣赏能够应用网络流的问题的广泛范围, 我们试图公正地对待它在用途上的多面性, 介绍在负载均衡、调度、图像分割以及其他若干问题上的应用.
第8章和第9章介绍计算难解性. 我们把主要的注意力放在NP完全性上, 按主题组织基本的NP完全问题, 这样有助于学生在遇到新问题时选择用于归约的问题. 我们给出若干相当复杂的NP完全性证明, 指导学生如何构造复杂的归约. 我们还考虑NP完全性之外的计算难度的类型, 特别是PSPACE完全性. 我们发现这是强调难解性并非到NP完全性为止的有价值的方法, PSPACE完全性也构成人工智能中某些核心概念——规划和对策——的基础, 否则将找不到它们在算法地形图中的位置.
第10章到第12章包括处理难计算问题的3个主要方法: 识别结构上的特殊情况, 近似算法和局部搜索启发式算法. 讨论易解特殊情况的一章强调在实际中产生的NP完全问题的实例很可能不像最坏情况那样难, 因为它们常常含有某些可以在设计有效算法时利用的结构. 我们阐述当限制在树结构输入上时NP完全问题常常可以如何有效地求解, 并以讨论图的树分解结束. 然而这个主题更加适合研究生课程而不是本科生课程, 它是一项具有相当实际效用的技术, 但很难找到这方面学生可以接受的参考文献. 关于近似算法的一章既讨论设计有效算法的过程, 又讨论为了获得好的算法界限需要很好地理解最优解的工作. 作为近似算法的设计方法, 我们集中在贪心算法, 线性规划以及称为“定价法”的第三种方法, 后者吸收了前两种方法的思想. 最后, 我们讨论局部搜索启发式算法, 包括Metropolis算法和模拟退火算法. 在本科生算法课程中常常不包括这个主题, 因为这些算法的可证性能保证知道得很少. 然而它们在实践中被广泛地使用, 我们认为学生值得对这些算法有所了解, 而且也包括一些能够证明性能保证的情况.
第13章介绍随机化在算法设计中的应用. 关于这个主题已经写了几本很好的研究生水平的书. 我们在这里的目标是提供对一些方法更紧凑的介绍, 学生能够采用这些方法运用随机技术, 并且只需要在本科生离散数学课程中获得的概率基础知识.
本书的使用
本书主要计划用于本科生的第一门算法课程, 但它也可以用作导论性研究生课程的基础.
当我们在本科生水平上使用本书时, 一节大约花一次课的时间; 当一节的内容一次课讲不完时（例如, 当一节提供进一步的应用作为额外的例子时）, 我们把这些额外的材料作为学生课外阅读的补充材料. 我们跳过带星号的节; 当这些节包含重要的话题时, 它们对这个问题发展很少是非常重要的, 而且有时它们也是比较难的. 我们还倾向在本书的前半部每一章跳过一、两节（例如, 我们倾向跳过4.3、 4.7-4.8、 5.5-5.6、 6.5、 7.6和7.11节）. 从第11章到第13章, 我们大约讲授每一章中的一半.
值得强调的最后一点是: 不要把后几章看做“高级的”, 从而认为它们超出本科生算法课程的范围, 我们按这样的目标设计了这几章, 即每一章的前几节应该是本科生可以接受的. 我们自己的本科生课程包括所有这些章的材料, 因为我们觉得这些主题在本科生水平上都有重要的位置.
最后, 我们基本上把第2章和第3章处理成复习前面课程的材料; 但是, 正如上面讨论过的那样, 这两章的使用很大程度上依赖于每一门具体课程与它的先修要求的关系.
最终的课程大纲大致如下: 第1章; 第2~8章（除4.3, 4.7~4.9, 5.5~5.6, 6.5, 6.10, 7.4, 7.6, 7.11和7.13节外）; 第9章（简要地）; 第10章, 10.1和10.2节; 第11章, 11.1, 11.2, 11.6和11.8节; 第12章, 12.1~12.3节; 以及第13章, 13.1~13.5节.
本书自然也支持导论性的研究生算法课程. 我们认为这门课程应该引导学生去研究算法设计中当前重要课题的所有不同领域. 在这里我们发现强调明确地描述问题也是有用的, 因为学生很快就要试图在许多不同的子领域内确定他们自己的研究问题. 对这种类型的课程, 我们包括第4章和第6章中的后几个话题（4.5~4.9和6.5~6.10节）, 第7章的全部（比较迅速地通过前几节）, 很快地介绍第8章中的NP完全性（因为许多研究生新生在本科生时已经见过这个问题）, 然后把剩余的时间用在第10~13章. 虽然我们在导论性研究生课程中的重点是在更高级的节上, 但我们发现有这样一本完整的书对学生来说是有用的, 可以用来作为复习或充实基础知识的参考, 因为上这种课程的学生有不同的本科基础.
最后, 本书可以用来支持研究生、研究人员和计算机专业人员的自学, 如果他们希望获得如何在他们自己的工作中使用具体算法设计技术的灵感的话. 不少研究生和同僚已经用这种方式使用本书的部分内容.
致谢
这本书是在我们连续讲授算法课程的基础上写成的. 多年来, 这门课随着这个领域的成长而成长, 并且反映了在这期间帮助形成它的康奈尔同仁的影响, 他们是Juris Hartmanis, Monika Henzinger, John Hopcroft, Dexter Kozen, Ronit Rubinfeld和Sam Toueg. 我们要更广泛地感谢康奈尔所有的同事对本书的素材以及有关这个领域本质的无数次更广泛的讨论.
参与这门课的所有人员对本书的形成提供极大的帮助. 感谢我们的本科生和研究生教学的助教们： Siddharth Alexander, Rie Ando, Elliot Anshelevich, Lars Backstrom, Steve Baker, Ralph Benzinger, John Bicket, Doug Burdick, Mike Connor, Vladimir Dizhoor, Shaddin Doghmi, Alexander Druyan, Bowei Du, Sasha Evfimievski, Ariful Gani, Vadim Grinshpum, Ara Hayrapetyan, Chris Jeuell, Igor Kats, Omar Khan, Mikhail Kobyakov, Alexei Kopylov, Brian Kulis, Amit Kumar, Yeonwee Lee, Henry Lin, Ashwin Machanavajjhala, Ayan Mandal, Bill McCloskey, Leonid Meyerguz, Evan Moran, Niranjan Nagarajan, Tina Nolte, Travis Ortogero, Martin Pál, Jon Peress, Matt Piotrowski, Joe Polastre, Mike Priscott, Qi Xin, Venu Ramasubramanian, Aditya Rao, David Richardson, Brian Sabino, Rachit Siamwalla, Sebastian Silgardo, Alex Slivkins, Chaitanya Swamy, Perry Tam, Nadya Travinin, Sergei Vassilvitskii, Matthew Wachs, Tom Wexler, ShanLeung Maverick Woo, Justin Yang和Misha Zatsman. 他们中的许多人对本书提出有价值的看法、建议和评论. 我们还要感谢上这些课的所有学生, 他们在这几年中对本书早期的手稿提出评论和反馈.
本书在过去几年的进展主要得益于在教学中使用本书出版前手稿的同僚们的反馈和建议. Anna Karlin在本书形成过程的早期就大胆地采用我们的手稿做她在华盛顿大学的课程教材, 继她之后又有不少人用它做教材或讲课的素材, 他们是Paul Beame, Allan Borodin, Devdatt Dubhashi, David Kempe, Gene Kleinberg, Dexter Kozen, Amit Kumar, Mike Molloy, Yuval Rabani, Tim Roughgarden, Alexa Sharp, Shanghua Teng, Aravind Srinivasan, Dieter van Melkebeek, Kevin Wayne, Tom Wexler和Sue Whitesides. 我们十分感激他们提供的材料和建议, 我们对内容的许多修订就来自这些材料和建议. 我们要再一次感谢Kevin Wayne, 他制作了与本书相关的补充材料, 使今后的教师使用本书更加方便.
另外在书中对具体问题的处理方式也反映了同僚们的影响. 对这些贡献我们无疑会有许多遗漏, 不过我们要特别感谢Yuri Boykov, Ron Elber, Dan Huttenlocher, Bobby Kleinberg, Evie Kleinberg, Lillian Lee, David McAllester, Mark Neeman, Prabhakar Raghavan, Bart Selmen, David Shmoys, Steve Strogatz, Olga Veksler, Duncan Watts和Ramin Zabih.
在过去的一年多里与Addison Wesley出版社合作得非常愉快. 首先我们要感谢Matt Goldstein在这个过程中的所有建议和指导, 他还帮助我们把大量的评论材料综合进改进本书的具体计划. 我们早期与Susan Hartman关于本书的交谈也是非常有价值的. 我们感谢Addison Wesley出版社的Matt和Susan, 以及Michelle Brown, Marilyn Lloyd, Patty Mahtani和Maite SuarezRivas, Windfall软件公司的Paul Anagnostopoulos和Jacqui Scarlott, 感谢他们在本书出版的编辑、制作和管理方面所做的工作. 我们再一次感谢Paul和Jacqui熟练的排版. 我们感谢Joyce Wells为本书设计封面, Dartmouth出版社Nancy Murphy绘制插图, Ted Laux制作索引, 以及Carol Leyba和Jennifer McClain的校对.
我们感谢Anselm Blumer(Tufts University), Richard Chang(University of Maryland, Baltimore County), Kevin Compton(University of Michigan), Diane Cook(University of Texas, Arlington), Sariel HarPeled(University of Illinois, UrbanaChampaign), Sanjeev Khanna (University of Pennsylvania), Philip Klein(Brown University), David Matthias(Ohio State University), Adam Meyerson(UCLA), Michael Mitzenmacher(Harvard University), Stephan Olariu(Old Dominion University), Mohan Paturi (UC San Diego), Edgar Ramos (University of Illinois, UrbanaChampaign), Sanjay Ranka (University of Florida, Gainesville), Leon Reznik (Rochester Instute of Technology), Subhash Suri (UC Santa Barbara), Dieter van Melkebeek (University of Wisconsin, Madison)和Bulent Yener (Rensselaer Polytechnic Institute), 他们慷慨地花时间对手稿做出详细而思想深刻的评论, 这些评论给本书的最终版本带来无数大大小小的改进.
最后, 我们感谢我们的家人——Lillian和Alice, 以及David, Rebecca和Amy. 我们感激他们的支持、忍耐和在这里无法用任何感谢表达的许多其他贡献.
本书的写作开始于20世纪90年代后期不合理的繁荣之中, 那时计算技术的光芒对我们许多人来说似乎暂时地穿越传统上被流行文化领域中的名人和其他各色人物占领的地方（这可能只是我们的想象）. 现在, 广告宣传和股市价格都已回到现实中几年了, 人们能够意识到计算机科学在某些方面被这段时期永远地改变了, 而在另一些方面它又保持不变: 强劲的刺激从一开始就成为这个领域的特征, 现在依然如此的强烈和迷人, 公众对信息技术的迷恋依旧非常强烈, 计算之所及继续扩展到新的学科. 因此, 对由于许多不同原因被吸引到这个学科中的所有学生, 我们希望你们在可能遇到计算的任何地方发现这本书是令人愉快和有用的指南.
Jon Kleinbeg
va Tardos
Ithaca, 2005作者介绍 Authors InformationJon Kleinberg是康奈尔大学计算机科学教授. 1996年获麻省理工学院博士学位. 荣获美国国家科学基金会(NSF)事业(Career)奖, 海军研究局((ONR)青年调查研究员(Young Investigator)奖, IBM杰出创新(Outstanding Innovation)奖, 国家科学院主动研究(Initiatives in Research)奖, Packard基金会和Sloan 基金会的研究基金, 以及康奈尔大学工程学院与计算机科学系的教学奖.
Kleinberg的研究集中在算法, 特别是与网络结构与信息、信息科学的应用、优化、数据挖掘以及计算生物学有关的算法. 他在网络分析中使用集线器和授权的工作对形成最新一代因特网搜索引擎的基础起了很大的作用.
va Tardos是康奈尔大学计算机科学教授. 1984年获匈牙利布达佩斯Ets大学博士学位. 她是美国艺术与科学院成员和ACM会员, 荣获美国国家科学基金会(NSF)总统青年调查研究员(Presidential Young Investigator)奖, Fulkerson奖, Guggenheim基金会, Packard基金会和Sloan 基金会的研究基金, 以及康奈尔大学工程学院与计算机科学系的教学奖.
Tardos的研究兴趣集中在图和网络问题的算法设计与分析. 她由于在网络流算法和网络问题的近似算法方面的工作而闻名. 最近的工作主要是算法博弈论, 这是一个与设计自私用户使用的系统和算法有关的新兴领域.
