算法之于程序员就如习武之人的内功心法，尽管学习时间长，见效慢，但行走江湖之人未有不精通内功者。固然种种外功门派众多变化万端，但内功精湛之人却能够做到以无招胜有招，以四两拨千斤。哪怕是再普通的招式，都能够化腐朽为神奇。

算法之于程序设计也有同样的功效，精通算法理论的程序员，往往能够在很短的时间内写出简洁高效的程序，其代码用赏心悦目来形容也毫不为过。算法，不仅仅是一套理论范式，更是一种思维方式。正如吴军博士在《计算之魂》中所言：“计算机科学的精髓，就是计算思维，即按照计算机的方式思考问题的能力。”

计算之魂（《数学之美》《浪潮之巅》等畅销书作者吴军博士新作）京东好评率99%无理由退换京东配送官方店￥91.2购买

而计算思维，在算法这门每一位程序员的必修课中，就体现的淋漓尽致。正如江湖豪杰都深谙武林秘籍的重要性一样，想要学好算法，同样离不开一本精心编写的教材。

在算法领域，恰恰有这么一本书堪称是算法学习中的《易筋经》，不仅蜚声海外，被哈佛，斯坦福，普林斯顿各大名校采用，在豆瓣也获得了9.0的高分，这本书就是《算法设计》。

▲程序员的绝世心法，《算法设计》

一本来自康奈尔大学的经典算法教材

作为世界顶级的私立研究型大学，同时也是美国著名的常春藤盟校之一，康奈尔大学的计算机系同样享誉全球，在年的U.S.News的排名中，康奈尔大学的计算机科学位列全美第五。在这样一个学术圣地，自然也是大神云集。《算法设计》的的两位作者乔恩·克莱因伯格（JonKleinberg）以及伊娃·塔多斯（vaTardos）就是其中的两位佼佼者。

算法设计（异步图书出品）京东好评率98%无理由退换京东配送官方店旗舰店￥59.5购买

克莱因伯格于年本科毕业于康奈尔大学，年在麻省理工学院获得博士学位，年，他获得了国际数学联盟所颁发的内万纳奖，获得该奖项足以见得克莱因伯格深厚的数学理论功底。

更为可贵的是，克莱因伯格同样擅长解决工程问题，他被评价为“以解决重要而且实际的问题并能够从中发现深刻的数学思想而著称”。克莱因伯格的研究跨越了从计算机网络由到数据挖掘再到生物结构比对等诸多领域。在当今计算机领域的若干重要课题中，他都作出了重要的贡献。在这其中，他最为人称道的成就是“小世界理论”和万维网搜索算法。由他所设计的HITS算法，更是启发了Google的PageRank算法的诞生。在算法理论的领域，克莱因伯格的成就可见一斑。

▲乔恩·克莱因伯格

本书的另一位作者塔多斯同样是康奈尔大学计算机科学系教授。年，塔多斯于匈牙利的罗兰大学攻读博士学位。从年起，她开始担任康奈尔大学计算机科学系的院长。年，塔多斯当选为美国国家工程院、文理科学院和美国哲学学会的院士。

塔多斯不仅是富尔克森奖、乔治·B·丹齐格奖、哥德尔奖和EATCS奖的获得者，在年，她更是被授予了IEEE约翰·冯·诺依曼奖章。塔多斯的研究兴趣主要集中在图和网络问题的算法设计和分析上。她因在网络流算法和网络问题的近似算法方面的工作而闻名。

▲伊娃·塔多斯

两位在计算机领域成就斐然的杰出作者，为这样一部优秀算法教材的成书，打下了坚实的学术背景。

经典教材是怎样炼成的

对于一部优秀的算法教材而言，仅仅有理论背景深厚的作者加持是远远不够的，毕竟一本基础教材也许用不上多么高深的理论，对于读者而言，更为重要的是材料内容的组织，编写的思路以及案例的设计。而这部教材在这些方面可以说都做到了极致，这也是它为什么能够历经时间的考验而长盛不衰的重要原因。

以问题为导向，引导读者由浅入深地学习算法理论，是横贯本书的设计思想。作者没有一上来就填鸭式的按部就班一个个介绍算法，相反，作者以一个简单的例子入手，采用启发式教学，一步步将读者带入算法博大精深的理论殿堂，同时将复杂的理论适度延后，阅读起来甚至会产生读小说一般的快感。在美亚上，众多读者留言“这是自己少有的完全通读下来的算法书籍”。下面对书中的内容组织略举一二，来让读者能够更好的理解横贯本书的算法设计思想。

稳定匹配问题

在本书的一开始，作者首先引入了一个生活中常见的经典案例——“稳定匹配问题”，即，是否可以设计一个具有自身强制力的匹配机制，比如求婚或者招聘，使得每位候选人都不会选择毁约呢？作者通过这样一个案例，来向我们展示算法设计的主要流程。

在拿到这个问题之后，我们要做的第一件事，就是要把它尽可能地形式化，即将文字描述，转换为数学语言。文字描述往往是粗糙的，模糊的，不利于后续的算法设计与分析，为了解决这个问题，我们需要数学的帮助。

正如伽利略所言：“宇宙这本大书是用数学语言写就的。”采用数学语言将问题尽可能形式化，能够精确清晰地描述出问题的本质，这是我们在算法分析和设计中，很容易忽视但是又十分重要的一个步骤。在将问题形式化之后，我们就可以考虑一些简单而具体的例子便于让我们进行直观思考。在这个例子中，作者考虑的是两位未婚男士和两位未婚女士的稳定匹配问题。

在将问题形式化之后，我们就需要为其设计算法。每一个算法的提出都无法一下就做到完美，相反，算法设计的初期往往只是从简单具体的例子中提炼出的一些宏观的观念和思想。我们可以从作者对上述例子的分析略窥一二。

首先，考虑初始情况，所有人都未婚。那么，一个直观的想法是：如果一位未婚男士向他偏好列表里排位最高的女士求婚，那么这样的匹配能成为稳定匹配吗？答案显然是否定的，因为对于这位女士来说，可能某个时刻会有她更喜欢的男士对她求婚。但是如果这位女士直接拒绝男士，那也有可能具有风险，因为接下来可能没有比这位男士更好的人出现了。所以一个自然的想法就是这一个配对进入中间状态：订婚。

其次，接下来，考虑中间状况，一部分人订婚，一部分人没有订婚。假如一位男士是自由的，那么当他向他的偏好列表排名第一的女士求婚时，如果这位女士也是自由的，那么她就会接受；如果这位女士已经订婚，那么她就会在这位求婚的男士和她已经订婚的男士中间选择一位，同时另一个人变为自由。

最后，算法将在没有人自由时停止，此时所有的订婚都被宣布为最终结果。

上述算法的设计从简单的例子入手，很直观但是却很有效。揭示了算法设计过程中的一般思路。

设计完算法之后，并不意味着这个问题已经被解决，相反，分析算法同样是相当重要的一步。在对算法分析的过程中，我们需要问自己：

算法的边界情况是怎样的？

算法的计算复杂度是多少？

算法会在我们想要的结果上收敛吗？

这些都是很重要但是又很容易被忽视的问题，但是对于保证算法的有效性和可靠性却必不可少。在这个例子中，作者经过一系列分析，最终证明该算法最终可以产生稳定的匹配。

上述的例子虽然很简单，但是却直观地展现出了算法设计的完整流程。算法设计并不仅仅包括算法设计的阶段，问题的形式化，对算法的分析，都至关重要却又极易被忽视。在接下来的算法介绍中，作者都采用这样的流程来分析和解决问题，为培养读者的设计算法的能力提供了良好的示范。

从区间调度到竞争设施位置问题

在开篇的稳定匹配问题让我们得以一窥算法设计的流程之后，作者进一步提出了5个典型的问题，它们分别是：区间调度问题，加权区间调度问题，二分匹配问题，独立集问题，以及竞争设施位置问题。这些问题可不是随意提出的，相反经过作者精心地设计和选择。这五个问题都非常重要和典型，对于它们的研究分别推动了算法几个不同的关键理论的发展。

区间调度问题：对应于贪心算法，采用目光短浅的规则，每次只考虑局部最优。也许贪心算法在很多情况下并不能成为全局最优解，但是能够让我们对基本问题的结构有所领悟。

加权区间调度问题：对应于动态规划,通过迭代的方式，找到全局最优解。

二分匹配问题：对应于图论以及网络流问题，通过归纳的方式建立越来越大的匹配，此过程中选择性回溯。

独立集问题：对应于NP完全问题，这类问题不存在已知的有效算法解。

竞争设施位置问题：对应于PSPACE完全问题，这一类问题涉及大量的博弈和规划问题，其中很多是人工智能领域基本问题。

在上述问题中，前三个问题可以通过越来越精妙的算法技术解决，第四个问题是一个转折点，意味着没有有效算法可以解决，最后一个问题则更加困难。

就这样，本书从宏观到微观，循循善诱，从实际案例从问题出发，一步步为我们搭建了一个完整的算法体系。作者的设计之精心，用心之良苦，可见一斑。

结语：你真的需要这样一部算法教材

在算法领域公认的经典教材中，能与本书相提并论的，也许只有《算法导论》了，然而《算法导论》如字典般厚重的篇幅，以及晦涩的理论，让无数读者望而生畏。

然而这部《算法设计》，却在理论深度与可读性之间，找到了一个完美的平衡，更不用提其平易近人娓娓道来的语言风格，仿佛一位长者在一步步引领你走入算法的大门。在阅读本书的过程中，我时时为作者精妙的问题设计以及高屋建瓴的总结所惊叹，受益匪浅。我相信这本书对于同样在学习算法的你，也会是很好的良师益友。

文章作者：Behemoth审校孙英刘雅思

—END—