前言

本书是在我的在线算法课程基础之上编写的，是“算法详解”系列图书4卷中的第4卷。这个在线课程 2012 年起就定期发布，它建立在我在斯坦福大学讲授多年的本科课程的基础之上。在阅读本书之前，读者需要熟悉渐进性分析和大O表示法、图的搜索和最短路径算法、贪心算法和动态规划（以上内容在“算法详解”系列图书第1～3卷均有讲述）。

本书涵盖的内容

“算法详解”系列图书第4卷介绍了NP-Hard问题（后简称NP问题）以及相关的概念。

处理NP问题的算法工具

许多现实世界的问题都是NP问题，无法由“算法详解”系列图书前3卷所描述的始终快速且正确的算法所解决。当我们在工作中遇到NP问题时，必须在正确性或速度上做出妥协。我们将会看到实现“近似正确性”的快速启发式算法的旧技巧（例如贪心算法）和新技巧（例如局部搜索），及其在作业调度、社交网络的影响最大化和旅行商问题上的应用等。我们还将讨论开发明显快于穷举搜索的算法的旧技巧（例如动态规划）和新技巧（例如MIT和SAT解决程序）。这些技巧的应用包括旅行商问题、在生态网络中寻找信道通路以及美国的一家电视台在最近的一次高风险频谱拍卖中重新安置问题等。

识别NP问题

本书还将训练读者快速识别NP问题，使读者不至于浪费时间试图为这类问题设计一种过于美好但难以成真的算法。读者将熟悉许多著名且基本的NP问题，范围包括可满足性问题、图形着色问题和汉密尔顿路径问题等。通过实践，读者将会掌握通过转化证明NP问题的技能。

关于本书内容的更详细概述，可以阅读每章的本章要点，它对每一章的内容特别是那些重要的概念进行了总结。本书的后记的标题是算法设计实战指南，从大局上概述了如何把本书所讨论的话题应用于具体的算法场景。

书中带星号的章节是难度较高的章节。时间较为紧张的读者在第一遍阅读时可以跳过这些章节，这并不会影响本书阅读的连续性。

“算法详解”系列图书前三卷所涵盖的主题

“算法详解”系列图书的第1卷讨论了渐进性表示法（大O表示法以及相关表示法）、分治算法和主方法，随机化的QuickSort及其分析以及线性时间的选择算法。“算法详解”系列图书的第2卷重点讨论了数据结构（堆、平衡搜索树、散列表、布隆过滤器）、图形基本单元（宽度和深度优先的搜索、连通性、最短路径）以及它们的应用（从去除重复到社交网络分析）。“算法详解”系列图书的第3卷则重点讨论了贪心算法（调度、最小生成树、集群、哈夫曼编码）和动态规划算法（背包、序列对齐、最短路径、最佳搜索树）。

读者的收获

精通算法需要大量的时间和精力，那为什么要学习算法呢？

成为更优秀的程序员

读者将学习一些令人炫目的用于处理数据的高速程序以及一些实用的数据结构，它们用于组织数据，可以直接部署到自己的程序中。实现和使用这些算法将扩展并提高读者的编程技巧。读者还将学习基本的算法设计范式，它们与许多不同领域的不同问题密切相关，并且可以作为预测算法性能的工具。这些“算法设计模式”可以帮助读者为自己碰到的问题设计新算法。

加强分析技巧

读者将获得大量对算法进行描述和推导的实践机会。通过数学分析，读者将对“算法详解”系列图书所涵盖的特定算法和数据结构有深刻的理解。读者还将掌握一些广泛用于算法分析的实用数学技巧。

形成算法思维

在学习了算法之后，很难发现有什么地方没有它们的踪影。无论是坐电梯、观察鸟群，还是管理自己的投资组合，甚至是观察婴儿的认知，算法思维如影随形。算法思维在计算机科学之外的领域，包括生物学、统计学和经济学，越来越实用。

融入计算机科学家的圈子

研究算法就像是观看计算机科学最近60年发展的精彩剪辑。当读者参加一场计算机科学界的鸡尾酒会，会上有人讲了一个关于Dijkstra算法的笑话时，你就不会感觉自己被排除在这个圈子之外了。在阅读了本系列图书之后，读者将了解许多这方面的知识。

在技术访谈中脱颖而出

在过去这些年里，有很多学生向我讲述了“算法详解”系列图书是怎样帮助他们在技术访谈中大放异彩的。

其他算法教材

“算法详解”系列图书只有一个目标：尽可能以读者容易接受的方式介绍算法的基础知识。读者可以把本书看成专家级算法教师的课程记录，老师以课程的形式传道解惑。

市面上还有一些非常优秀的更为传统、全面的算法教材，它们都可以作为“算法详解”系列关于算法的其他细节、问题和主题的有益补充。我鼓励读者探索和寻找自己喜欢的其他教材。另外，还有一些图书的出发点有所不同，它们偏向于站在程序员的角度寻找一种特定编程语言的成熟算法实现。网络中存在大量免费的这类算法的实现。

本书的目标读者

“算法详解”系列图书以及作为其基础的在线课程的整体目标是尽可能地扩展读者群体的范围。学习我的在线课程的人具有不同的年龄、背景、生活方式，有大量来自全世界各个角落的学生（包括高中生、大学生等）、软件工程师（包括现在的和未来的）、科学家和专业人员。

本书并不是讨论编程的，理想情况下读者至少应该熟悉一种标准编程语言（例如Java、Python、C、Scala、Haskell等）并掌握了基本的编程技巧。如果读者想要提高自己的编程技巧，那么可以学习一些非常优秀的讲述基础编程的免费在线课程。

我们还会根据需要通过数学分析帮助读者理解算法为什么能够实现目标以及它是怎样实现目标的。Eric Lehman和Tom Leighton关于计算机科学的数学知识的免费课程是极为优秀的，可以帮助读者复习数学记法（例如Σ和∀）、数学证明的基础知识（归纳、悖论等）、离散概率等更多知识。

其他资源

“算法详解”系列图书的在线课程当前运行于Coursera和EdX平台。另外，还有一些资源可以帮助读者根据自己的意愿提升对在线课程的体验。

● 视频。如果读者觉得相比阅读文字，更喜欢听和看，那么可以在视频网站的视频播放列表中观看。这些视频涵盖了“算法详解”系列的所有主题。我希望它们能够激发读者学习算法的持续热情。当然，它们并不能完全取代书的作用。

● 小测验。读者怎么才能知道自己是否完全理解了本书所讨论的概念呢？散布于全书的小测验及其答案和详细解释就起到了这个作用。当读者阅读这块内容时，最好能够停下来认真思考，然后继续阅读接下来的内容。

● 章末习题。每章的末尾都有一些相对简单的问题，用于测试读者对该章内容的理解程度。另外，还有一些开放性的、难度更大的挑战题。

● 章末习题的答案（分别用（H）或（S）提示难度）在本书的最后。读者可以与我联系或者通过下面的论坛相互交流，对章末习题进行探讨。

● 编程题。有几章的最后是一个推荐的编程项目，其目的是通过创建自己的算法工作程序，来培养读者对算法的完全理解。读者可以在algorithmsilluminated网站上找到数据集、测试用例以及它们的答案。

● 论坛。在线课程能够取得成功的一个重要原因是它们为参与者提供了互相帮助的机会，读者可以通过论坛讨论课程材料和调试程序。本系列图书的读者也有同样的机会，可以通过algorithmsilluminated网站参与活动。