详情
算法详解系列图书共有4卷，本书是第4卷——NP-Hard问题算法。全书共有6章，主要介绍了快速识别NP-Hard问题的方法和处理NP的算法工具。本书的每一章均有小测验、章末习题，这为读者的自我检查以及进一步学习提供了方便。
本书提供了丰富而实用的资料，能够帮助读者提升算法思维能力。本书适合计算机专业的高校教师和学生，想要培养和训练算法思维与计算思维的IT专业人士，以及正在准备面试的应聘者和面试官阅读参考。
书名：算法详解（卷4）——NP-Hard问题算法
ISBN：978-7-115-60912-0
本书由人民邮电出版社发行数字版。版权所有，侵权必究。
您购买的人民邮电出版社电子书仅供您个人使用，未经授权，不得以任何方式复制和传播本书内容。
我们愿意相信读者具有这样的良知和觉悟，与我们共同保护知识产权。
如果购买者有侵权行为，我们可能对该用户实施包括但不限于关闭该帐号等维权措施，并可能追究法律责任。
著 [美]蒂姆•拉夫加登（Tim Roughgarden）
译 徐 波
责任编辑 武晓燕
人民邮电出版社出版发行 北京市丰台区成寿寺路11号
邮编 100164 电子邮件 315@ptpress.com.cn
网址 http://www.ptpress.com.cn
读者服务热线：(010)81055410
反盗版热线：(010)81055315
算法详解系列图书共有4卷，本书是第4卷，主要针对NP-Hard问题算法。全书共有6章，主要介绍了快速识别NP-Hard问题的方法和处理NP的算法工具。本书的每一章均有小测验、章末习题，这为读者的自我检查以及进一步学习提供了方便。
本书提供了丰富而实用的资料，能够帮助读者提升算法思维能力。本书适合计算机专业的高校教师和学生，想要培养和训练算法思维与计算思维的IT专业人士，以及正在准备面试的应聘者和面试官阅读参考。
本书是在我的在线算法课程基础之上编写的，是“算法详解”系列图书4卷中的第4卷。这个在线课程 2012 年起就定期发布，它建立在我在斯坦福大学讲授多年的本科课程的基础之上。在阅读本书之前，读者需要熟悉渐进性分析和大O表示法、图的搜索和最短路径算法、贪心算法和动态规划（以上内容在“算法详解”系列图书第1～3卷均有讲述）。
“算法详解”系列图书第4卷介绍了NP-Hard问题（后简称NP问题）以及相关的概念。
许多现实世界的问题都是NP问题，无法由“算法详解”系列图书前3卷所描述的始终快速且正确的算法所解决。当我们在工作中遇到NP问题时，必须在正确性或速度上做出妥协。我们将会看到实现“近似正确性”的快速启发式算法的旧技巧（例如贪心算法）和新技巧（例如局部搜索），及其在作业调度、社交网络的影响最大化和旅行商问题上的应用等。我们还将讨论开发明显快于穷举搜索的算法的旧技巧（例如动态规划）和新技巧（例如MIT和SAT解决程序）。这些技巧的应用包括旅行商问题、在生态网络中寻找信道通路以及美国的一家电视台在最近的一次高风险频谱拍卖中重新安置问题等。
本书还将训练读者快速识别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网站参与活动。
如果没有过去几年里我的算法课程中数以千计的参与者的热情和渴望，“算法详解”系列图书就不可能面世。我特别感谢那些为本书的早期草稿提供详细反馈的人：Tonya Blust、Yuan Cao、Leslie Damon、Tyler Dae Devlin、Roman Gafiteanu、Blanca Huergo、Jim Humelsine、Tim Kearns、Vladimir Kokshenev、Bayram Kuliyev、Clayton Wong、Lexin Ye和Daniel Zingaro。另外感谢提供技术建议的专家们：Amir Abboud、Vincent Conitzer、Christian Kroer、Aviad Rubinstein和Ilya Segal。
本书提供如下资源：
● 本书思维导图；
● 异步社区7天VIP会员。
要获得以上资源，您可以扫描下方二维码，根据指引领取。
作者和编辑尽最大努力来确保书中内容的准确性，但难免会存在疏漏。欢迎您将发现的问题反馈给我们，帮助我们提升图书的质量。
当您发现错误时，请登录异步社区（https://www.epubit.com/），按书名搜索，进入本书页面，点击“发表勘误”，输入勘误信息，点击“提交勘误”按钮即可（见下图）。本书的作者和编辑会对您提交的勘误进行审核，确认并接受后，您将获赠异步社区的100积分。积分可用于在异步社区兑换优惠券、样书或奖品。
我们的联系邮箱是contact@epubit.com.cn。
如果您对本书有任何疑问或建议，请您发邮件给我们，并请在邮件标题中注明本书书名，以便我们更高效地做出反馈。
如果您有兴趣出版图书、录制教学视频，或者参与图书翻译、技术审校等工作，可以发邮件给我们。
如果您所在的学校、培训机构或企业，想批量购买本书或异步社区出版的其他图书，也可以发邮件给我们。
如果您在网上发现有针对异步社区出品图书的各种形式的盗版行为，包括对图书全部或部分内容的非授权传播，请您将怀疑有侵权行为的链接发邮件给我们。您的这一举动是对作者权益的保护，也是我们持续为您提供有价值的内容的动力之源。
“异步社区”（www.epubit.com）是由人民邮电出版社创办的IT专业图书社区，于2015年8月上线运营，致力于优质内容的出版和分享，为读者提供高品质的学习内容，为作译者提供专业的出版服务，实现作者与读者在线交流互动，以及传统出版与数字出版的融合发展。
“异步图书”是异步社区策划出版的精品IT图书的品牌，依托于人民邮电出版社在计算机图书领域30余年的发展与积淀。异步图书面向IT行业以及各行业使用IT技术的用户。
大部分的算法入门图书，包括“算法详解”系列图书的第1卷到第3卷，都存在选择性偏向的问题。它们关注的是能够由精巧、快速的算法所解决的计算性问题。不管怎么说，还有什么比学习一种精妙的快速算法更有乐趣、更有成就感呢？好消息是许多基本的、实用的问题都可以归入这个范畴，包括排序、图的搜索、最短路径、哈夫曼编码、最小生成树、序列对齐等。但是，如果只介绍这些精心选择的问题而忽略那些让严肃的算法设计师和程序员深感头痛的计算性难题，无疑是不客观和不全面的。遗憾的是，有很多重要的计算性问题，包括在我们的项目中经常出现的一些问题，并不存在已知的快速算法。更糟的是，我们无法期待解决这些问题的算法能够在未来得到突破，因为它们已经被公认存在死结，无法由任何快速算法所解决。
意识到这个严峻的事实之后，我们很快就会想到两个问题。首先，当这类问题在我们的工作中出现时，怎么才能认识到它们的存在，以便相应地调整自己的期望值，避免花费大量的时间寻找注定是美梦泡影的算法呢？其次，如果这类问题对于我们的应用是非常重要的，我们应该如何调整自己的期望值，应该使用什么算法工具来实现它们呢？本书将提供这两个问题的详细答案。
高难度的计算性问题和容易解决的计算性问题看上去往往非常相似，对它们进行区分需要训练有素的敏锐目光。为了打好基础，我们首先回顾一个熟悉的老问题（最小生成树问题，MST），并把它与一个难度更大的相似问题（旅行商问题，TSP）进行比较。
可以由速度炫目的快速算法所解决的一个著名问题就是最小生成树（MST）问题（详见“算法详解”系列图书第3卷的第3章）。[1]
[1] 简单回顾一下图的概念。图G = (V, E)由两个部分组成：顶点集V和边集E。在无向图中，每条边e∈E对应于一个无序的顶点对{v, w}（写成e = (v, w)或e = (w, v)的形式）。在有向图中，每条边(v, w)是一个有序的顶点对，边的方向从v到w。顶点和边的数量| V |和| E |通常分别由n和m表示。
问题：最小生成树（MST）
输入：无向连通图G = (V, E)，它的每条边e∈E具有实数值的边成本ce。
输出：G的一棵生成树T⊆E，它具有最小的边成本之和
。
对于图G = (V, E)，如果它的每一对顶点v, w∈V在图中都存在一条从v到w的路径，那么图G就是连通图。G的生成树是边的一个子集T⊆E，子图(V, T)既是连通图又是无环图。例如在图1.1中，最小生成树由边(a, b)、(b, d)和(a, c)组成，边的总成本为7。
图1.1 无向连通图
一个图具有指数级数量的生成树，因此除了那些很小的图之外，用穷举搜索法寻找最小生成树是不现实的。[2]但是，MST问题可以由非常精妙的快速算法（例如Prim算法和Kruskal算法）解决。通过部署适当的数据结构（分别是堆和联合查找），这两种算法都能实现令人炫目的速度，运行时间能够达到O ((m + n) logn)，其中m和n分别是输入图中边和顶点的数量。
[2] 例如，著名Cayley组合公式说明了一个n个顶点的完全图（所有可能的
条边都存在）具有nn–2棵不同的生成树。当n≥50时，这个数字比已知宇宙中估计的原子数量还要大。
在“算法详解”系列图书第1卷到第3卷并没有出现但仍然在全书中占据重要地位的另一个著名问题就是旅行商问题（TSP）。它的定义几乎与MST问题相同，区别是在TSP中访问所有顶点的简单环路所构成的路线扮演了MST中生成树的角色。
问题：旅行商问题（TSP）
输入：无向完全图G = (V, E)，它的每条边e∈E都有一个实数值的成本ce。[3]
[3] 在完全图中，所有可能的条边都存在。G是完全图这个前提并不会使问题失去通用性，因为在任何输入图中，对于不存在的边，都可以用成本非常高的边补足，从而输入图无害地转化为完全图。
输出：G的一条路线T⊆E，它具有最小的边成本之和
。
路线的正式定义是对每个顶点正好访问1次的环路（每个顶点在路线中都有2条关联边）。
小测验1.1
在n≥3个顶点的TSP实例G = (V, E)中，存在多少条不同的路线T⊆E？（在下面的答案中，n ! = n× (n−1) × (n−2) ···2×1表示阶乘函数。）
（a）2n
（b）
（c）
（d）n !
（正确答案和详细解释参见第1.1.4节。）
如果所有其他方法都失败，TSP就只能通过对所有的路线（有限数量）进行穷举并找出其中的最佳路线来解决。我们可以尝试对一个较小的图进行穷举搜索。
小测验1.2
在图1.2中，具有最低边成本之和的那条路线的成本是多少？（每条边都用它的成本进行标注。）
图1.2 无向连通图
（a）12
（b）13
（c）14
（d）15
（正确答案和详细解释参见第1.1.4节。）
只有那些很小的实例，才能通过穷举搜索法解决TSP。我们能不能做得更好？是不是与MST问题相似，在指数级数量的旅行商路线中，也存在一种算法能够神奇地找到成本最低的那条路线呢？尽管这两个问题在表面上非常相似，但TSP的解决难度要远远大于MST问题。
我可以讲述旅行商故事的来龙去脉，但这对于解决TSP毫无益处。TSP实际上是一个相当基本的问题。当我们需要按照顺序完成一连串的任务，并且完成一项任务所需要的时间或成本依赖于以前的任务时，实际上就涉及了旅行商问题。
例如，任务可以表示为一家工厂中需要装配的汽车，装配一辆汽车所需要的时间等于一个固定的时间（单车装配时间）加上一个设置时间，后者取决于这辆汽车和前一辆汽车的工厂配置。以最快的速度装配所有的汽车可以简化为最大限度地降低设置时间之和，这个问题就是TSP。
以另一个完全不同的应用为例，假设我们已经收集了一个基因组的重叠片段，并想通过逆向工程推断出它最合理的顺序。根据一种“合理性措施”，为每对片段分配一个成本（例如，根据最长共同子串的长度），这个顺序问题也可以归类为TSP。[4]
[4] 这两个应用建模为旅行商路径问题很可能更为适合，因为它们的目标是计算一条最低成本访问每个顶点的无环路径（不回到起始顶点）。任何解决TSP的算法都可以很方便地转化为解决该问题路径版本的算法，反之亦然（参见问题1.7）。
受TSP的实际应用和美学作用所诱惑，许多在优化领域享有盛誉的智者从20世纪50年代早期开始就投入了巨大的精力和海量的计算来解决TSP的大型实例。[5]尽管几十年过去了，期间绞尽了无数天才的脑汁，人们无奈地发现：
[5] 对TSP的历史以及TSP的其他应用感兴趣的读者可以参阅The Travelling Salesman Problem: A Computational Study这本书的前4章，作者是David L. Applegate、Robert E. Bixby、Vašek Chvátal、William J. Cook（Princeton University Press，2006年）。
事实真相
在本书写作的时候（2020年），尚不存在TSP的快速算法。
“快速”算法的含义是什么呢？回顾“算法详解”系列第1卷，我们同意下面这个标准：
“快速算法”表示最坏情况下运行时间的增长速度相对于输入规模的增长速度较为缓慢的算法。
“增长缓慢”又是什么意思呢？对本系列的大部分算法而言，这个词的黄金标准表示算法的运行时间为线性时间或近似线性时间。对这类速度炫目的算法就不要心存幻想了。对n个顶点的TSP实例而言，连运行时间稳定在O(n100)的算法也不存在，甚至连O(n10 000)的算法也不可得。
对于这个悲凉的困境，存在两种不同的解释：（i）存在TSP的快速算法，只是还没有一个足够聪明的脑袋瓜把它想出来。（ii）不存在这样的算法。我们不知道哪种解释是正确的，但大多数专家更倾向后者。
推测
不存在TSP的快速算法。
早在1967年，Jack Edmonds就写道：
我猜测旅行商问题不存在好的算法。我的理由与其他所有数学猜测相同：（i）这是一种合理的数学可能性；（ii）我不知道答案。[6]
[6] 来自Jack Edmonds的论文“Optimum Branchings”（Journal of Research of the National Bureau of Standards，Series B，1967）。所谓“好的算法”，Edmonds的意思是算法的运行时间上界不超过输入规模的某个多项式函数。
遗憾的是，无解的魔咒并不仅限于TSP。我们将会看到其他很多非常实用的问题同样受到这个魔咒的困扰。
正确答案：（b）。在顶点顺序（共有n! 种）和路线（以某种顺序访问每个顶点各1次）之间存在一种直觉的对应，因此答案（d）是一种很自然的猜测。但是在这种对应关系中，每条路径都以不同的方式计数了2n次。
在每条路径中，起始顶点的n种选择各计数了1次，每条路线的两个旅行方向也各计数了1次。因此，路线总数就是
。例如，当n = 4时，就有3条不同的路线，如图1.3所示。
图1.3 3条不同的路径
正确答案：（b）。我们可以从顶点a开始对路线进行列举，并尝试其他3个顶点的全部6种可能的顺序，并理解路线结束时必须从最后一个顶点回到起始顶点。（实际上，这种列举对每条路线计数了2次，每个方向各一次）结果是：
最短的路线是第2条，总成本为13。
有些计算性问题要比其他问题更容易解决。NP问题的理论要点就是能够让我们通过一种精确的感觉把问题划分为“容易计算”（如MST）和“难以计算”（如TSP）。本书的读者既包括初涉这个话题的新手，也包括追求提升专业技能的高手。本节说明了如何学习本书的剩余部分，既提供了一些目标，也提出了一些约束。
在识别和处理NP问题时，读者当前的专业层次是什么？期望达到的层次又是什么？[7]
[7] 关于NP这个术语的由来，参见第1.6节。
第0层：“什么是NP问题？”
第0层表示对NP问题一无所知。读者完全没有听说过NP问题，并没有意识到许多实际上非常重要的计算性问题被公认为是无法由任何快速算法所解决的。如果我叙述得当，第0层的读者应该也能够看懂本书。
第1层：“哦，这个问题就是NP问题？我觉得我们要么重新规划这个问题，要么降低期望值，要么投入大量的资源解决这个问题。”
第1层就像鸡尾酒派对[8]的交谈一样，对NP问题略有所知，至少对它的含义有一些了解。例如，如果读者正在管理一个涉及某个算法或某个优化组件的软件项目，就需要在NP问题上至少达到第1层的专业能力。如果有一位成员遇到了NP问题并讨论接下来该怎么办时，也不至于茫然无措。为了把NP问题的专业技能提升到第1层，可以学习第1.3节、第1.4节和第1.6节。
[8] 我说的鸡尾酒派对自然是指那些充满书卷气的派对。
第2层：“哦，这个问题就是NP问题？给我一个机会发挥自己的算法天赋，看看我能够走得多远。”
软件工程师的精力在他的专业能力达到第2层时是最为过剩的，时刻想着丰富自己的工具箱来开发非常实用的算法，以解决或模拟NP问题。严肃的程序员应该争取达到这个层次（或者更高）。愉快的是，我们为解决“算法详解”系列图书第1～3卷的问题所开发的所有多项式时间的算法范例或多或少对解决NP问题有所益处。第2章和第3章的目标是使读者达到第2层的专业水准。第1.4节对此进行了概述，第6章提供了一个详细的案例分析，描述了第2层的工具箱在一个高风险应用中是如何发挥作用的。
第3层：“告诉我遇到了什么计算问题。【仔细倾听……】节哀，这是个NP问题。”
在第3层，我们可以快速识别在实际工作中所遇到的NP问题（在这个时候可以应用一些第2层水平的技能）。我们知道一些著名的NP问题，并知道如何证明其他问题也是NP问题。算法专家应该精通这个层次的技能。例如，当我向业界的同事、学生和工程师提供算法问题的建议时，也会用到一些第3层的知识。第4章提供了一个把技术水平提升至第3层的训练营，第1.5节对此进行了简单的介绍。
第4层：“允许我通过黑板向你解释P≠NP”猜想。
第4层也是最高级的层次，适合初显峥嵘的算法理论家和追求NP问题及P和NP问题的严格数学理解的人们。如果读者并没有被上面的说法所吓倒，可以认真阅读选修的第5章。
NP问题理论所提出的“容易和困难”二分法可以采用下面这种极度简化的定义：
容易↔可以由一种多项式时间的算法所解决。
困难↔在最坏情况下需要指数级的时间。
NP问题的这个总结忽略了一些重要的微妙之处（参见第1.3.9节）。但是多年之后，如果读者对NP问题的含义只记住了其中的几个词，那么这几个词就是NP问题的良好定义。
为了寻求“容易”问题的定义，我们可以回顾一些已知的著名算法（例如“算法详解”系列第1～3卷中的算法）的运行时间，如表1.1所示。
表1.1 部分著名算法的运行时间
| 问题 |
算法 |
运行时间 |
|---|---|---|
| 排序 |
MergeSort算法 |
O(n logn) |
| 强连通分量 |
Kosaraju算法 |
O(m + n) |
| 最短路径 |
Dijkstra算法 |
O[(m + n)logn] |
| MST |
Kruskal算法 |
O[(m + n)logn] |
| 序列对齐 |
NW算法 |
O(mn) |
| 所有顶点对的最短路径 |
Floyd-Warshall算法 |
O(n3) |
n和m的确切含义因问题而异，但不管在什么问题中都与输入规模密切相关。[9]这张表的要点在于：尽管这些算法的运行时间各不相同，但它们的上界都可以用输入规模的某个多项式函数表示。一般而言：
[9] 在排序中，n表示输入数组的长度。在4个图问题中，n和m分别表示顶点数和边数。在序列对齐问题中，n和m表示两个输入字符串的长度。
多项式时间的算法
多项式时间的算法是指最坏情况运行时间为O(nd)的算法，其中n表示输入规模，d是个常量（与n无关）。
上面所列出的6种算法都是多项式时间的算法（指数d相对较小）。[10]是不是所有自然算法的运行时间都是多项式时间呢？不是。例如，对于许多问题而言，穷举搜索的运行时间是输入规模的指数级（如第2页的脚注②所示）。我们到目前为止所学习的巧妙的多项式时间的算法都存在一些特殊之处。
[10] 记住，对数因子也可以用一个线性因子粗略地确定上界。例如，如果T(n) = O(n logn)，则T(n) = O(n2)也是成立的。
不要忘了，任何指数函数的最终增长速度都要远远快于任何多项式函数的。典型的多项式运行时间和指数级运行时间之间存在巨大的差距，即使是非常小的实例也是如此。稍后的插图（多项式函数100n2与指数函数2n的比较）就非常具有代表性。
摩尔定律表示某个特定价格下的计算力每过1～2年会翻一番。这是不是意味着多项式时间级的算法和指数级时间的算法之间的差别最终将会消失？实际上，答案正好相反！随着计算力的增长，我们对计算的期望值也随之上升。随着时间的推移，我们会考虑越来越大的输入规模，这样多项式运行时间和指数级运行时间的差距只会越来越大，如图1.4所示。
图1.4 越来越大的差距
假设我们具有固定的时间预算，例如一小时或一天。随着额外计算力的增加，可解决的输入规模又是如何增长的呢？对于一种多项式时间的算法，计算力每增加1倍，输入规模的增长是一个常数因子（例如从1 000 000增长到1 414 323）。[11] 当一种算法的运行时间与2n（其中n表示输入规模）成正比时，计算力每增加1倍，可解决的输入规模可能只增加了1（例如从1 000 000增加到1 000 001）！
[11] 在线性时间的算法中，可以解决的问题规模是原先的两倍。在二次方时间的算法中，可以解决的问题规模增长幅度是
≈ 1.414。在三次方时间的算法中，可以解决的问题的增长幅度是
≈ 1.26，接下来依此类推。
NP问题的理论把“容易的”问题定义为能够由一种多项式时间级的算法所解决的问题。或者说该算法可解决的输入规模（在固定的时间预算下）随着计算力的增加而呈现乘法级的增长：[12]
[12] 这个定义是Alan Cobham和Jack Edmonds（参见第6页的脚注）在20世纪60年代中期不谋而合地提出的。
多项式时间可解决的问题
对于某个计算性问题，如果存在一种多项式时间级的算法，对于每一种输入都能产生正确的结果，那么这个问题就是多项式时间可解决的问题。
例如，本节之初所列出的6个问题都是多项式时间可解决的问题。
从理论上说，在输入规模为n时运行时间为O(n100)的算法也可以看成多项式时间的算法（虽然没有实用价值），由这样的算法所解决的问题也可以称为多项式时间可解决的问题。根据这个理论，如果一个像TSP这样的问题不是多项式时间可以解决的，那么像O(n100)甚至O(n10 000)时间级的算法都是无法解决它的。
勇气、定义和边缘情况
通过“能够在多项式时间内解决”来判定问题是否容易并不完美。某个问题在理论上可能是能够解决的（通过一种理论上的多项式时间的算法），但在现实中是不可能的（根据我们经验上的快速算法的概念），或者是反过来的情况。任何人如果有勇气创建一个精确的数学定义（例如能够在多项式时间内解决）来表达一个含糊的现实世界概念（“容易通过现实世界的计算机解决”），就必须对这个定义的精确性和现实世界的含糊性之间的冲突做好心理准备。这种定义必须包含或排除某些边缘情况，而这些边缘情况在其他定义中可能并不存在。但是这个不足并不足以让我们忽略或排除这是一个良好的定义。与实际经验相符，能否在多项式时间内解决对于区分问题是“容易”还是“困难”意外地有效。通过半个世纪的研究和实践，我们可以充满信心地表示自然的多项式时间内可解决的问题一般都可以通过实用的通用算法所解决，而那些无法由多项式时间的算法所解决的问题一般需要更多的工作量和专业知识。
假设我们猜测一个像TSP这样的问题是“不容易的”，意思是无法由任何多项式时间的算法所解决（不管项数有多大）。我们怎样才能证明事实确是如此呢？当然，最有说服力的毫无疑问是通过无懈可击的数学证明。但是，TSP的状态至今仍然并不确定：没有人能够找到一种多项式时间的算法来解决它，也没有人能够证明这样的算法不存在。
在不知道是否存在可以解决问题的算法时，我们怎么才能创建一个理论来区分“容易处理”和“难以处理”的问题呢？NP问题背后的天才设想就是根据问题的相对（而不是绝对）困难性对它们进行区分。如果一个问题至少像其他大量无法解决的问题“一样困难”，我们就认为它是困难的。
解决TSP的大量失败尝试（第1.1.3节）间接证明了这个问题无法在多项式时间内解决。
困难的弱证据
如果TSP真的存在一种多项式时间的算法，无疑否定了无数才华横溢的天才在过去数十年殚精竭虑的努力。
我们能不能做得更好，也就是提供难处理性的更有说服力的论证方式？这就是NP问题的神奇和威力所在。大体思路就是说明像TSP这样的问题至少和许多不同科学领域的大量无法解决的问题一样困难。事实上，所有这些问题只要有一个发现了解决方案，剩余的问题随之也能够解决。这种论证方式表示TSP如果存在一种理论上的多项式时间的算法，那么这种算法也能自动解决其他那些未解决的问题！
困难的强证据
如果TSP存在一种多项式时间的算法，那么困扰了无数天才数十年的数以千计的难题也就随之迎刃而解了。
实际上，NP问题的理论说明了数以千计的问题（包括TSP）都是同一个问题的不同变型，它们都遭受了相同的计算厄运。如果我们尝试为一种像TSP这样的NP问题找到一种多项式时间的算法，事实上也就为这些数以千计的相关难题找到了算法。[13]
[13] 硬要说的话，数以百计（甚至千计）的天才大脑都无法得出TSP无法在多项式时间内解决的相反结论，反过来说明了事实上不存在这样的算法。区别在于证明问题的可解决性（通过无数问题的已知快速算法）要远比证明问题的不可解决性要容易得多。因此，如果TSP能够在多项式时间内解决，那么这么久还没有找到它的多项式时间的算法是件非常奇怪的事情。如果它不存在这样的算法，那么我们无法证明这一点是毫不意外的。
如果一个问题存在上面这层意思的难以处理的强证据，那么我们就称这个问题是NP问题。
NP问题（大体思路）
如果一个问题被认为至少与已经确认的许多难题一样困难，那么它就是NP问题。
第5.3.4节将会证明这个思路是100%准确的，但是在此之前，我们只能根据一个著名的数学猜想即P≠NP猜想来提供NP问题的一个临时定义。
读者也许听说过P≠NP猜想，它的准确含义是什么？第5.4节将会提供它的精确数学定义。现在，我们暂且用一种非正式的版本来应付急需这种定义的情况。
P≠NP猜想（非正式版本）
对一个问题的所有宣称的解决方案进行验证要比自己从头设计这样的解决方案要容易得多。
在这个猜想中，“P”和“NP”分别表示在多项式时间内可以从头解决的问题和在多项式时间内能够对解决方案进行验证的问题。关于它们的正式定义，请参阅第5章。
例如，对某人所提出的数独或聪明方格问题的解决方案进行验证要比想出它们的解决方案要容易得多。或者，在TSP中，对于某人所提出的旅行商路径，我们只要把它的边成本进行累加，就很容易证明它是良好的（例如总成本不超过1000）。但是，让我们在很短的时间内从头开始想出这样的路线却是很不容易的。因此，我们可以凭直觉认定P≠NP猜想是正确的。[14][15]
[14] 我们将会在问题5.2中看到P≠NP猜想相当于Edmond猜想，也就是说TSP无法在多项式时间内解决。
[15] P≠NP猜想的正确性为什么并不是显而易见的？因为多项式时间的算法范围之广令人难以想像，其中包含了大量天才的算法。（例如，“算法详解”系列第1卷第3章的脑洞爆炸式的低于3次方的Strassen矩阵乘法算法。）要证明这些数量近乎无限的候选算法都不能解决TSP是件非常困难的事情！
根据某种临时的定义，假设P≠NP猜想是成立的，如果一个问题不能由任何多项式时间的算法所解决，那么这个问题就是NP问题。
NP问题（临时定义）
一个计算性问题如果存在一种多项式时间的算法就会否定P≠NP猜想，那么它就是NP问题。
因此，任何NP问题（例如TSP）如果存在一种多项式时间的算法，就会自动说明P≠NP猜想是不成立的，从而揭晓一项虽然诱人但难以成真的算法悬赏：每个问题都有一种多项式时间的算法，它的解决方案可以在多项式时间内被识别。在P≠NP猜想为真这个很可能的情况下，没有任何NP问题是能够在多项式时间内解决的。在输入规模为n的情况下，甚至连运行时间为O(n100)或O(n10 000)的算法都不可能。
第1.3.3节“多项式时间可解决”这个定义只涉及确定性的算法。我们知道，随机化在算法设计中（例如在QuickSort算法中）也是一种强大的工具。那么，随机化的算法能够摆脱NP问题的桎梏吗？
推及到更普遍的情况，现在很火的量子算法又是什么情况呢？（随机化算法可以看成量子算法的一种特殊情况）。大规模的、通用的量子计算机（如果实现）可能会改变一些问题的命运，包括对大整数进行分解这样极端重要的问题。但是，分解问题并不被认为是NP问题，专家们推测即使是量子计算机也无法在多项式时间内解决NP问题。NP问题所提出的挑战不可能在短时间内被克服。[16]
[16] 大多数专家相信每种多项式时间的随机化算法都可以去随机化，转变为一种等价的多项式时间的确定性算法（也许是一种具有很大的运行时间上界的多项式算法）。如果确实如此，P≠NP猜想也自动适用于随机化的算法。
反之，大多数专家相信量子算法在本质上比传统算法更为强大（但尚未强大到能够在多项式时间内解决NP问题）。这无疑令我们吃惊和兴奋：还有多少是我们仍然不知道的？
本节之初的极简讨论表示“困难的”问题在最坏情况下需要指数级的时间才能解决。第1.3.7节的临时定义的表述又有所不同：所谓NP问题，就是在P≠NP猜想成立的前提下，无法由任何多项式时间的算法所解决的问题。
这两种定义之间的第1个分歧是NP问题只有在P≠NP猜想为真的前提下（这个问题的答案并未完全确认）才排除了能够在多项式时间内解决的可能性。如果这个猜想是不成立的，那么本书所讨论的几乎所有NP问题都能在多项式时间内解决。
第2个分歧在于即使P≠NP猜想这个大概率为真的事件确实是成立的，NP问题也只表示在最坏情况下解决这种问题需要超过多项式的时间（而不是指数级的时间）。[17]但是，对于大多数的自然NP问题，包括本书所研究的所有问题，专家们普遍认为它们在最坏情况下确实需要指数级的时间。这个想法可以由“指数级时间假设”所证实，这是P≠NP猜想的一种更强形式（参见第5.5节）。[18]
[17] 当输入规模为n时，运行时间上界大于多项式但低于指数级的例子包括
和
等。
[18] “算法详解”系列图书所研究的所有计算性问题的解决时间都不需要超过指数级，但其他问题却有可能需要。一个著名的例子是“停机问题”（halting problem），它无法在任何有限数量的时间内解决（何况是指数级时间），参见第5.1.2节。
最后，尽管我们所遇到的99%的问题属于“容易”（能够在多项式时间内解决）或“困难”（NP问题），但还有一些极为少见的问题位于两者之间。因此，容易和困难这种一分为二的方法能够覆盖现实中绝大多数重要的计算性问题，但并非全部。[19]
[19] 两个被认为既无法在多项式时间内解决也不是NP问题的重要问题是因数问题（确认一个整数存在一个重要的因数，或确认它不存在）和图同构问题（确定两个图除了顶点名称不同之外都是相同的）。这两个问题的算法都需要低于指数级的时间（但高于多项式的时间）。
假设我们确定了一个计算性问题，项目的成败系于其身。也许在过去几周中我们想尽了一切办法。我们知道所有的算法范例，理解书上的所有数据结构，掌握所有的零代价基本算法，但一切都无济于事。最后，我们意识到这并非是因为自己的方法有误或能力不济，而是因为这个问题是NP问题。虽然我们可以对过去几周所做的无用功感到释怀，但这并不能削弱这个问题对于项目的重要性。我们应该怎么办呢？
坏消息是NP问题是普遍存在的。随时可能会出现一个这样的问题困扰我们最近的项目。好消息是NP问题并不意味着宣判了死刑。在实践中，通过投入足够多的资源，应用足够复杂的算法逻辑，NP问题常常是可以解决的（但并不总是能够解决），至少能够近似地解决。
NP问题向算法设计师提出了挑战，并给我们的期望值浇了一盆冷水。我们无法指望会有一种通用的、快速的算法解决NP问题，这点与我们所看到的诸如排序、最短路径或序列对齐等问题截然不同。除非我们运气足够好，需要处理的输入要么很小、要么具有良好的结构，否则必然要消耗大量的资源才能解决这个问题，并且很可能需要做出某种妥协。
需要什么类型的妥协呢？NP问题排除了同时满足下面这三个优秀的属性（假设P≠NP猜想是正确的）的方法。
三个属性（无法同时拥有）
1．通用。算法能够处理该计算性问题的所有可能的输入。
2．正确。对于每个输入，算法都能够正确地解决问题。
3．快速。对于每个输入，算法都能够在多项式运行时间内完成。
相应地，我们可以从三种类型的妥协中做出选择：通用性的妥协、正确性的妥协和速度上的妥协。这三种策略都是非常实用的。
本节的剩余部分将详细说明这三种算法策略。随后的第2章和第3章将深入讨论后面两种策略。和往常一样，我们把注意力集中在强大、灵活的算法设计原则上，使之适用于范围极广的问题。我们应该把这些原则作为起点并对它们进行应用，并对自己需要解决的特定问题接受领域专家所提供的指导。
在NP问题上取得进展的一种策略是放弃通用算法，把注意力集中在与我们的应用相关的问题的特殊情况上。在最佳情况场景中，我们可以确认与输入有关的某种领域特定的约束，并设计一种总是能够正确、快速地处理这种输入子集的算法。“算法详解”系列第3卷的动态规划训练营的毕业生已经看到过这种策略的两个例子。
加权的独立子集问题。在这个问题中，输入是无向图G = (V, E)，每个顶点v∈V都有一个非负的权重wv。这个问题的目标是计算一个独立子集S⊆V，它具有最大的顶点权重之和
。所谓独立子集表示互不相邻的顶点子集S⊆V［对于每对v,w∈S，满足(v, w)
E］。例如，如果边表示冲突（例如两个人之间、两门课程之间等），独立子集就对应于不存在冲突的子集。这个问题一般而言是NP问题，如4.5节所述。当G是路径图（顶点为v1, v2, …, vn，边为(v1, v2), (v2, v3),…,(vn−1, vn)）这种特殊情况时，这个问题就可以使用一种动态规划算法在线性时间内解决。这个算法还可以进行扩展，使之适用于所有的无环图（参见“算法详解”系列第3卷的第4.3节）。
背包问题。在这个问题中，输入由2n+1个正整数所指定：n个物品价值v1, v2,…, vn，n个物品大小s1, s2,…, sn和背包容量C。这个问题的目标是计算物品的一个子集S⊆ { 1, 2,…, n}，在总大小
不超过C的前提下具有最大的物品价值之和
。换句话说，这个问题的目标是最大限度地榨取资源的价值。[20] 这个问题是NP问题，如第4.8节和问题4.7所述。这个问题存在一种O(nC)运行时间的动态规划算法。这是一种多项式时间的算法，适用于C的大小不超过n的一个多项式函数的特殊情况。
[20] 例如，对于哪些货物和服务，我们应该挥舞支票本榨取最大价值呢？或者在预算固定的前提下，有一组不同技术水平和不同薪资要求的求职者可供选择，我们应该选择谁呢？
背包问题的多项式时间算法？
为什么背包问题的O(nC)运行时间的算法并没有否定P≠NP猜想？因为它并不是一种多项式时间的算法。输入规模（需要的键击数量指定了计算机的输入）与一个数的位数成正比，而不是与这个数的大小成正比。为了与1 000 000这个数进行通信，并不需要一百万次键击，而是只需要7次（如果是二进制就需要20次）。例如，对于一个有n件物品的实例，如果背包容量是2n，所有物品的价值和大小都不超过2n，那么它的输入规模是O(n2)[O(n)个数各有O(n)个数字]。它的动态规划算法的运行时间是指数级的（与n·2n成正比）。
设计快速、正确的算法（用于特殊情况）的算法策略可以使用我们在“算法详解”系列图书第1卷到第3卷所开发的全部算法工具箱。由于这个原因，本书并未开辟专门的一章来讨论这种策略。但是，我们还会遇到一些NP问题的特殊情况，此时它们可以由多项式时间的算法所解决，例如旅行商问题、可满足性问题和图着色问题（参见问题1.8和问题3.12）。
第二种算法策略在时间优先的应用中特别流行，就是坚持算法的通用性并保证速度，但可以牺牲正确性。并不总是正确的算法有时又称启发性算法。[21]
[21] 在“算法详解”系列图书的第1卷到第3卷，多数情况下正确但并不总是正确的解决方案只有一个例子：布隆过滤器。这是一种小空间的数据结构，支持超级快速的插入和查找，其代价是偶尔会出现假阳性。
在理想情况下，启发式算法“在大多数情况下是正确的”。这意味着它必须满足下面这两个属性之一（或两者皆满足）：
正确性的放宽
1．算法对于“大多数的”输入是正确的。[22]
[22] 例如，布隆过滤器的一个典型实现具有2%的假阳性率，98%的查找是正确的。
2．算法对每个输入是“几乎正确的”。
第2个属性最容易用优化问题进行解释。这类问题的目标是计算具有最佳目标函数值（具有最低总成本）的可行解决方案（例如旅行商问题）。“几乎正确”表示这种算法所输出的可行解决方案的目标函数值接近最佳结果。例如在旅行商问题中，算法所产生的路线的总成本与实际最优的路线相差不远。
用于设计快速、准确算法的现有算法工具箱可以直接用于设计快速的启发性算法。例如，第2.1节～第2.3节描述了一些启发式贪心算法，范围包括作业调度和社交网络的影响最大化等。这些启发式算法附带了“近似正确”的证明，保证对于每个输入，算法输出的目标函数值与实际最佳的目标函数值之间只存在一个适度的常量因子的差距。[23]
[23] 有些作者称这种算法是“近似算法”，并把“启发式算法”这个术语保留给缺少近似正确性证明的算法。
第2.4节～第2.5节为我们的工具箱增加了局部搜索算法设计范例。局部搜索以及它的通用版本在实际处理许多NP问题时好用得令人难以置信。其中就包括了TSP，尽管局部搜索算法很少拥有令人信服的近似正确性保证。
最后一种策略适用于无法在准确性上做出妥协又不愿意考虑启发性算法的应用。一个NP问题的每种准确算法对于某些输入的运行时间必然会超过多项式时间（假设P≠NP猜想是成立的）。因此，我们的目标是设计一种尽可能快的算法，它至少要比原始的穷举搜索法要好得多。这意味着它必须满足下面这两种情况之一（或两者皆满足）。
多项式运行时间的放宽
1．算法在处理与应用相关的输入时一般较为快速（例如可以实现多项式运行时间）。
2．对于每个输入，算法的速度都要比穷举搜索快得多。
在第二种情况下，我们仍然预计算法对于某些输入会达到指数级的运行时间。不管怎么说，它终究是NP问题。例如，第3.1节对TSP使用了一种远胜于穷举搜索的动态规划算法，运行时间从O(n!)缩减为O(n2·2n)，其中n表示顶点的数量。第3.2节把随机化与动态规划相结合，在查找图的长路径问题上实现了O ((2e) k·m)的运行时间，远胜于穷举搜索的O(nk)，其中n和m分别表示输入图中顶点和边的数量，k表示目标路径长度，e = 2.718…。
在NP问题相对较严重的实例上取得进展一般需要额外的工具，这种工具并不拥有优于穷举搜索的运行时间保证，但在许多应用中却是意外好使。第 3.3 节～第3.5节概述了如何站在巨人的肩膀之上，这些“巨人”就是在过去数十年里为混合整数规划（MIP）和可满足性（SAT）问题开发了卓有成效的解决程序的专家们。许多属于NP问题的优化问题（例如TSP）都可以改编为混合整数规划问题。许多属于NP问题的可行性检查问题（例如对班级和教室的无冲突分配进行检查的问题）可以很方便地表达为可满足性问题。当我们面临一个可以很方便地由MIP或SAT表示的NP问题时，就可以应用解决这类问题的最新、最有效的程序。MIP或SAT的解决程序并不能保证在合理的时间内能解决我们的特定问题，毕竟这是NP问题。但是，它们代表了在实践中处理NP问题的最前沿技术。
如果读者追求的是NP问题第１层次的技术水平（第1.2节），最需要记住的概念如下。
与NP问题有关的三个事实
1．普遍存在：实际上重要的NP问题是随处可见的。
2．难以处理：以一个被广泛接受的数学猜想为前提，没有一个NP问题可以由任何一种既能保证正确性又能实现多项式运行时间的算法所解决。
3．并非死路一条：只要投入足够的资源，应用足够高级的算法逻辑，NP问题在实践中常常（但并不总是）能够解决，至少能够近似地解决。
我们怎么才能发现自己的工作中所出现的NP问题以便相应地调整自己的期望值，并放弃寻求一种通用、正确的快速算法呢？没人愿意花几个星期甚至几个月的时间努力否定P≠NP猜想却一无所获。
首先，了解一些简单和常见的NP问题的集合（例如第4章的19个问题）。在最简单的场景中，我们的应用可以归结为这些问题的其中之一。其次，强化对计算性问题进行转化的能力。把一个问题转化为另一个问题之后，就可以把后者在计算上的可处理性扩展到前者。反过来说，计算上的难以处理性可以按照相反的方向进行转化，也就是从前者扩展到后者。因此，为了证明我们所关注的一个计算性问题是NP问题，只需要把一个已知的NP问题转化为这个问题即可。
本节的剩余内容会对这些要点进行说明，并提供了一个简单的例子。第4章将对此进行深入的讨论。
如果一个任意的问题B至少和NP问题A一样困难，那么它也是个NP问题。“至少一样困难”这句话可以通过转化这个术语来表达。
转化
如果一个解决问题B的算法可以很方便地还原为解决问题A的算法，那么问题A就可以转化为问题B（见图1.5）。
图1.5 如果问题A转化为问题B，则A可以调用解决问题B的子程序来解决并且调用次数不超过多项式数量，再加上多项式时间的额外工作
当我们讨论NP问题时，“容易转化”意味着问题A可以通过调用解决问题B的子程序并且调用次数不超过多项式数量（相对于输入规模）来解决，另外包括一些多项式时间的额外工作（在子程序调用之外）。
紧跟时代的算法设计师总是会寻求问题转化的机会。若非迫不得已，谁愿意从头开始解决问题呢？“算法详解”系列图书第1~3卷中与第1.3.1节所列出的问题有关的例子如下所示。
熟悉的转化例子
1．在一个整数数组中寻找中位数的问题可以转化为对这个数组进行排序的问题。（对数组进行排序之后，返回最中间的那个元素就可以了。）
2．所有顶点对的最短路径问题可以转化为单源最短路径问题。（在输入图中，对每个可能的起始顶点调用一种单源最短路径算法。）
3．最长公共子序列问题可以转化为序列对齐问题。（对两个输入字符串调用一种序列对齐算法，每个插入的空位为1个扣分，两个不同符号导致的不匹配则为一个非常大的扣分。）[24]
[24] 记住，序列对齐问题的一个实例是由来自某个字母表Σ（类似{A,C,G,T}）的两个字符串、每对符号x,y ∈ Σ的扣分αxy和一个非负的空位扣分αgap所指定的。这个问题的目标是计算输入字符串具有最低总扣分的对齐方式。
这些转化站在力量的光明一面，承担着根据旧的算法创建新的快速算法的光荣任务，从而把计算上的可处理性向前推进了一步。例如，第1个转化是把MergeSort算法转化为一种O(nlogn)时间级的中位元素查找算法，或者按照更通用的说法，把任何T(n)时间级的排序算法转化为O(T(n))时间级的中位元素查找算法，其中n表示数组的长度。第2个转化是把单源最短路径的任何T(m,n)时间级的算法转化为所有顶点对的最短路径问题的O(n·T(m, n))时间级的算法，其中m和n分别表示边和顶点的数量。第3个转化把序列对齐问题的T(m, n)时间级的算法转化为最长公共子序列问题的O(T(m, n))时间级的算法，其中m和n分别表示两个输入字符串的长度。
小测验1.3
假设问题A可以通过最多调用问题B的子程序T1(n)次，并执行最多T2(n)的额外工作（除了子程序调用）来解决，其中n表示输入规模。假设有一个子程序能够在不超过T3(n)（输入规模为n）的时间内解决问题B，那么解决问题A所需要的时间是什么？（选择最正确的答案。假设一个程序至少必须使用一种零代价的操作来创建一个长度为s的输入以便进行子程序调用。）
（a）T1 (n) + T2(n) + T3(n)
（b）T1(n) ·T2(n) + T3(n)
（c）T1(n) ·T3(n) + T2(n)
（d）T1(n) ·T3 (T2(n)) + T2(n)
（关于正确答案和详细解释，参见第1.5.5节。）
小测验1.3显示了当问题A可以转化为问题B时，问题B的任何多项式时间的算法都可以转换为解决问题A的算法。[25]
[25] 如果小测验1.3中的函数T1 (n)、T2(n)和T3(n)的上界都是n的一个多项式函数，则它们的和、积和组合也是多项式函数。例如，如果
且
，其中a1、a2、d1和d2都是正的常数（与n无关），则
且
。
转化扩展了可处理性
如果问题A可以转化为问题B，并且问题B可以由一种多项式时间的算法所解决，则问题A也可以由一种多项式时间的算法所解决（见图1.6）。
图1.6 从问题B到问题A扩展了可处理性：如果问题A可以转化为问题B，并且问题B在计算上是可处理的，那么问题A在计算上也是可处理的
NP问题的理论则站在了力量的阴暗一面，“穷凶极恶”地使用转化对难处理性进行扩展（图1.7的相反方向）。我们反过来理解上面那种说法。假设问题A可以转化为另一个问题B。进一步假设A是个NP问题，意思是如果问题A存在一种多项式时间的算法，就会否定P≠NP猜想。如果问题B存在一种多项式时间的算法，那么问题A也自动会拥有一种多项式时间的算法（因为问题A可以转化为问题B），这样就否定了P≠NP猜想。换句话说，问题B也是个NP问题。
转化扩展了难处理性
如果问题A可以转化为问题B，并且问题A是NP问题，则问题B也是NP问题（见图1.7）。
图1.7 以相反的方向从问题A到问题B扩展难处理性：如果问题A可以转化为问题B，并且问题A在计算上是难处理的，那么问题B在计算上也是难处理的
因此，现在我们拥有了一种简单的两步骤方案来证明一个问题是NP问题。
如何证明一个问题是NP问题
为了证明问题B是NP问题：
1．选择一个NP问题A；
2．证明问题A可以转化为问题B。
实现第1个步骤需要对NP问题有所了解。第4章将介绍一些与此有关的概念。第2个步骤建立在对问题进行转化的技能之上。通过第4章的实践，这两个步骤的细节都能得到充实。下面我们回顾一个熟悉的问题：允许边长为负的单源最短路径问题，从而领悟这个方案的精要所在。
在单源最短路径问题中，输入由有向图G = (V, E)、每条边e∈E的实数值边长
和起始顶点s∈V所组成。路径的长度就是组成路径的每条边的长度之和。这个问题的目标是对于每个可能的目标顶点v∈V，计算G中一条从s到v的有向路径的最短长度dist(s, v)。（如果不存在这样的路径，dist(s, v)就被定义为+ ∞。）重要的是，这个问题允许边的长度为负。[26][27]例如，图1.8中从s出发的最短路径长度分别是：
[26] 记住，图的路径可能表示抽象的决策序列，并不一定是可以物理实现的。例如，如果我们想计算涉及买入和卖出的金融交易的利润序列，就相当于在边长可能为正或为负的图中寻找一条最短路径。
[27] 在只有非负边长的图中，单源最短路径问题才可以用速度炫目的Dijkstra算法解决（参见“算法详解”系列图书第2卷第3章）。
dist(s,s) = 0、dist(s,v) = 1和dist(s, t) = −4。
对于图1.9，该如何定义最短路径长度呢？
图1.8 从s出发的最短路径
图1.9 负环
这个图存在一个负环，负环是指边长之和为负的有向环。图1.9中存在一条单跳的长度为10的s–v路径。在这条路径的后面加上一个环路会产生一条5跳的s–v路径，总长度为8。再次加上这个环路会使总长度变成6，接下来依此类推。如果允许有环的路径，这个图就不存在最短的s–v路径。
一个显而易见的替代方案是禁止路径中出现环路，坚持每个顶点只能被访问1次。
问题：无环最短路径（CFSP）
输入：有向图G = (V, E)，起始顶点s∈V，并且每条边e∈E具有实数值的边长。
输出：对于每个顶点v∈V，计算G中具有最短长度的无环s–v路径。（如果G中不存在s–v路径，就输出+ ∞。）
遗憾的是，这个版本的问题是NP问题。[28]
[28] 这就解释了为什么Bellman-Ford算法（参见“算法详解”系列图书第3卷的第6章）以及其他每个多项式时间的最短路径算法只能解决这个问题的一种特殊情况（不存在负环的输入图，这种情况下最短路径自动是不包含环路的）。定理1.1说明了如果P ≠NP猜想是正确的，那么这些算法都无法正确地计算出通用的无环最短路径的长度。
定理1.1（无环最短路径是NP问题） 无环最短路径问题是NP问题。
关于辅助结论、定理等名词
在数学著作中，最重要的技术性陈述称为定理。辅助结论是一种帮助证明定理的技术性陈述（就像一个子程序帮助实现一个更大的程序一样）。推论是一种从已经被证明的结果中引导产生的陈述，例如一个定理的一种特殊情况。对于那些本身并不是特别重要的独立的技术性陈述，我们将使用命题这个术语。
我们可以根据第1.5.3节的两步骤方案来证明定理1.1。对于第1个步骤，我们将使用一个著名的NP问题，即有向汉密尔顿路径问题。
问题：有向汉密尔顿路径问题（DHP）
输入：有向图G = (V, E)，起始顶点s∈V和结束顶点t∈V。
输出：如果G中存在一条对图中的每个顶点v∈V正好访问1次的s–t路径（称为s–t汉密尔顿路径）就输出“是”，否则就输出“否”。
例如，在图1.10中，第1个图存在一条s–t汉密尔顿路径（虚线边），而第2个图不存在这样的路径。
图1.10 两个有向图
第4.6节证明了有向汉密尔顿路径问题是NP问题（同样使用了第1.5.3节的两步骤方案）。现在，我们直接采用它是NP问题这个结论，并把注意力集中在这个方案的第2个步骤，也就是把一个已知的NP问题（在此例中为有向汉密尔顿路径问题）转化为我们感兴趣的问题（无环最短路径问题）。
辅助结论1.1（DHP可以转化为CFSP） 有向的汉密尔顿路径问题可以转化为无环最短路径问题。
证明：我们如何使用一个解决无环最短路径问题的子程序来解决有向图的汉密尔顿路径问题呢（回顾图1.5）？假设已经有了后者的一个实例，由有向图G = (V, E)、起始顶点s∈V和结束顶点t∈V所指定。预想的无环最短路径子程序的输入包括一个图（这个可以提供，也就是输入图G）和一个起始顶点（同上）。这个子程序的输入不需要结束顶点，因此可以忽略t。但是，这个子程序的输入还需要实数值的边长，因此我们必须进行假设。我们可以欺骗这个子程序，给每条边一个负的边长，使子程序误以为长路径（例如一条s–t汉密尔顿路径）实际上是很短的。总而言之，转化过程如下（见图1.11）。
1．为每条边e∈E分配一个长度
。
2．使用预定的子程序计算无环最短路径，复用相同的输入图G和起始顶点s。
3．如果从s到t的一条最短无环路径的长度是−(|V| −1)就返回“是”，否则返回“否”。
为了证明这个转化是正确的，我们必须证明当输入图G包含了一条s–t汉密尔顿路径时返回“是”，否则返回“否”。在构建的无环最短路径实例中，一条无环s–t路径的最短长度等于-1乘以原输入图G中一条无环s–t路径的最大跳跃数量。一条无环s–t路径如果也是一条s–t汉密尔顿路径（以访问所有的|V|个顶点），那么它就具有|V| −1次跳跃，否则跳跃数量就会少一些。因此，如果G具有一条s–t汉密尔顿路径，则这个构建实例中从s到t的无环最短路径的长度就是− (|V| −1)，否则它的长度就会更长（即更小的负数）。不管是哪种情况，这种转化都能返回正确的答案。证毕。
图1.11 辅助结论1.1的证明中的转化例子。第1个图中的s–t汉密尔顿路径转化为一条长度为–8的无环s–t路径。第2个图中不存在s–t汉密尔顿路径，无环s–t路径的最短长度是–6
通过这个两步骤的方案，辅助结论 1.1 以及有向的汉密尔顿路径问题属于 NP问题证明了定理1.1。第4章将介绍这个方案的许多实际使用例子。
正确答案：（d）。初看上去，答案似乎是（c）：在最多T1 (n)个子程序调用中，每个调用最多执行T3(n)的操作。除了这些调用，这个算法最多执行T2 (n)的操作。因此总体运行时间不超过T1 (n) ·T3 (n) + T2 (n)。
对于问题之间的大多数自然转化，这种解释是正确的，包括第1.5.2节的3个例子。但是从理论上说，当输入规模为n时，一个转化可能会在输入大于n的情况下调用问题B的子程序。例如，假设一个转化以一个图为输入，并且由于某种原因，在调用问题B的子程序之前在这个图中增加了一些顶点或边。这样做的最坏后果是什么呢？由于这个转化在调用子程序之外最多执行T2 (n)个操作，因此它还需要时间记录问题B的规模不超过T2 (n)的输入。因此，问题B的T1 (n)次调用的每一个最多需要T3(T2(n))的操作，这样总体运行时间就是T1(n) ·T3(T2(n)) + T2(n)。
NP问题是一个相当偏向于理论的话题，同时也是职业算法设计师和严肃的程序员密切关注的一个话题。
在教科书和科研论文之外，计算机科学家为了更方便地进行交流，常常不是那么在乎精确的数学定义。有些类型的不准确说法会让人觉得我们是笨拙的新手，但也有一些类型的不准确说法却是能够被接受的。怎么才能知道具体是哪种不准确说法呢？这正是我现在想要说明的。
新手错误#1
认为“NP”表示“非多项式”[29]。
[29] 非多项式的首字母缩写也是NP。——译者注
只要能够避免这个新手错误，我们并不需要记住“NP”实际代表什么。[30]
[30] 那么，NP到底代表什么呢？第5.3节将详细说明这个缩写的历史渊源。不过为了照顾性急的读者，这里还是说一下，NP表示“非确定性的多项式时间”（nondeterministic polynomial time）。
新手错误#2
把一个问题表述为“NP问题”或“属于NP”，而不是“NP难题”（严格意义上讲）。
能够坚持到第5.3节的读者将会明白，是“NP问题”或“属于NP”实际上是件好事，而不是坏事。[31]因此，不要忘了“NP”后面的“难题”。
[31] 具体地说，它意味着如果有人递给我们一个万能的解决方案（例如一个完整的数独题），我们可以在多项式时间内验证它的正确性。
新手错误#3
认为NP问题无伤大雅，因为NP问题在实践中一般是可以解决的。
NP问题确实不是“死刑判决”，只要投入足够的人力和计算资源，许多实际应用中的NP问题是可以解决的。第6章提供了这方面的一个案例的深入分析。但是在很多应用中，由于NP问题所带来的挑战，计算性问题常常必须被修改甚至被放弃。（自然，人们报告自己成功解决NP问题的情况要远多于失败的情况！）如果实践中任何问题都是能够解决的，为什么启发式算法还这么有用呢？如果真是这样，现代的电子商务又是如何生存的呢？[32]
[32] 电子商务依赖于像RSA这样的加密系统，后者的安全性依赖于大型整数的因数分解在计算上是难以处理的。任何NP问题如果存在多项式时间的算法，就可以通过转化，立即形成一种多项式时间的因数分解算法。
新手错误#4
认为计算机科技的进步会帮助我们解决NP问题。
摩尔定律以及越来越大的输入规模只会放大这个问题，因为多项式算法的运行时间和非多项式算法的运行时间之间的差距只会越来越大（第1.3.2节）。量子计算机能够提高穷举搜索的效率，但仍然不足以在多项式时间内解决任何NP问题（第1.3.8节）。
新手错误#5
在错误的方向进行转化。
从问题A转化为问题B会把NP问题从A扩展到B，而不是相反的方向（对比图1.2和图1.3）。由于我们习惯于在进行转化时扩展可处理性而不是难处理性，因此这是最难避免的错误。每当我们认为已经证明了一个问题是NP问题时，要回过头来再三检查自己的转化是否处于正确的方向，也就是问题的转化方向要与难处理性的扩展方向相同。
接下来的3种说法，尽管它们并未被证明或者在理论上是不正确的，但实际上是能够被接受的。它们并不会动摇我们对NP问题的理解。
可接受的不准确说法#1
假设P≠NP猜想是正确的。
P≠NP猜想的状态仍然是开放的，尽管大多数专家相信它是正确的。尽管我们仍然期待自己的数学理解能够跟得上自己的直觉，但大多数人把这个猜想看成自然法则。
可接受的不准确说法#2
“NP问题”和“NP完全问题”这两个术语是可以互换使用的。
“NP完全问题”是一种特殊类型的NP问题，其细节是技术上的，将在第5.3节详述。它们的算法内涵是相同的：不管一个问题是NP完全问题还是NP问题，它都无法在多项式时间内解决（假设P≠NP猜想是正确的）。
可接受的不准确说法#3
NP问题可以概括为在最坏情况下需要指数级的时间。
这是对第1.3节开始处对NP问题的极度简化的解释。这种概括在理论上是不准确的（参见第1.3.9节），但是考虑到大多数专家对NP问题的想法，即使我们真的这么认为，也不会有人反对。
● 多项式时间的算法是指最坏情况运行时间为O(nd)的算法，其中n表示输入规模，d是个常量。
● 如果一个计算性问题存在一种多项式时间的算法，且对于每种输入都能正确地解决这个问题，那么这个问题就是能够在多项式时间内解决的。
● NP问题的理论相当于能够在多项式时间内解决的问题都是“容易的”。按照极度简化的定义，“困难的”问题就是在最坏情况下需要指数级的时间才能解决的问题。
● 按照非正式的定义，P≠NP猜想断定验证一个问题的解决方案要比从头设计这个问题的解决方案要容易得多。
● 按照非正式的定义，一个多项式时间的算法如果能解决一个计算性问题就相当于否定了P≠NP猜想，那么这个问题就是NP问题。
● 如果一个多项式时间的算法能够解决任何一个NP问题，那么它能够自动解决数以千计的相关难题，这些难题是过去数十年来无数才智之士穷其精力也无法解决的。
● NP问题是普遍存在的。
● 为了在NP问题上取得进展，算法设计师必须对通用性、正确性或速度之一做出妥协。
● 快速的启发性算法的运行速度很快，但它并不总是正确的。在设计这类算法时，贪心算法范例和局部搜索算法范例是极为实用的。
● 动态规划在一些NP问题上可以实现优于穷举搜索的结果。
● 混合整数编程和可满足性问题的解决程序组成了在实践中处理NP问题的前沿技术。
● 如果问题A可以通过调用问题B的子程序再加上多项式数量的额外工作解决，那么问题A就可以转化为问题B。
● 转化扩展了可处理性：如果问题A可以转化为问题B，并且B可以由一种多项式时间的算法所解决，那么A也可以由一种多项式时间的算法所解决。
● 转化在扩展难处理性时的方向与上面相反：如果问题A可以转化为问题B，并且A是NP问题，那么B也是NP问题。
● 为了证明问题B是NP问题：(i)选择一个NP问题A；(ii)证明A可以转化为B。
问题1.1 （S）假设我们所关注的一个计算性问题B是一个NP问题。下面哪些说法是正确的？（选择所有正确的答案。）
（a）NP问题是“死刑判决”，如果我们的应用存在问题B的一个相关实例，那就不必“枉费心机”了。
（b）如果老板指责我们没有找到问题B的一种多项式时间的算法，我们可以理直气壮地回应有数以千计的才华横溢之士也曾努力寻找问题B的解决方案，但他们也都失败了。
（c）我们不应该指望能够设计出一种对于该问题的每个实例都能在多项式时间内正确地予以解决的算法（除非我们明确地想要否定P≠NP猜想）。
（d）由于动态规划算法只适用于设计准确的算法，因此用它来解决问题B是没有意义的。
问题1.2 （S）下面哪些说法是正确的？（选择所有正确的答案。）
（a）MST问题在计算上是可处理的，因为一个图的生成树的数量相对于顶点的数量n和边的数量m是多项式级别的。
（b）MST问题在计算上是可处理的，因为一个图的一棵生成树的总成本最多只有m种可能性。
（c）穷举搜索并不能在多项式时间内解决TSP，因为一个图具有指数级数量的旅行商路线。
（d）TSP在计算上是难以处理的，因为一个图具有指数级数量的旅行商路线。
问题1.3 （S）下列哪些说法是正确的？（选择所有正确的答案。）
（a）如果P≠NP猜想是正确的，那么NP问题实际上是永远无法解决的。
（b）如果P≠NP猜想是正确的，那么没有一个NP问题可以由一种总是正确并且总能在多项式时间内完成的算法所解决。
（c）如果P≠NP猜想是错误的，那么NP问题实际上是可以解决的。
（d）如果P≠NP猜想是错误的，那么有些NP问题可以在多项式时间内解决。
问题1.4 （S）P≠NP猜想提示了哪些结论？（选择所有正确的答案。）
（a）解决NP问题的每种算法在最坏情况下的运行时间都超过多项式时间。
（b）解决NP问题的每种算法在最坏情况下的运行时间都是指数级时间。
（c）解决NP问题的每种算法的运行时间总是超过多项式时间。
（d）解决NP问题的每种算法的运行时间总是指数级时间。
问题1.5 （S）假设问题A可以转化为另一个问题B。下面哪些说法总是正确的？（选择所有正确的答案。）
（a）如果A能够在多项式时间内解决，则B也能够在多项式时间内解决。
（b）如果B是NP问题，则A也是NP问题。
（c）B也可以转化为A。
（d）B无法转化为A。
（e）如果问题B可以转化为另一个问题C，则A也可以转换为C。
问题1.6 （S）假设P≠NP猜想是正确的。关于背包问题（第1.4.2节）的下列说法哪些是正确的？（选择所有正确的答案。）
（a）所有物品的大小都是正整数并且小于或等于n5的特殊情况（其中n是物品的数量）是可以在多项式时间内解决的。
（b）所有物品的价值都是正整数并且小于或等于n5的特殊情况（其中n是物品的数量）是可以在多项式时间内解决的。
（c）所有物品的价值、所有物品的大小以及背包的容量都是正整数的特殊情况是可以在多项式时间内解决的。
（d）通用的背包问题不存在多项式时间的算法。
问题1.7 （H）旅行商路径问题（TSPP）的输入与TSP的输入相同，目标是计算一条访问每个顶点的无环最低成本路径（也就是不存在最终边的路径）。证明TSPP可以转化为TSP，反之亦然。
问题1.8 （H）这个问题描述了TSP的一个计算上可处理的特殊情况。考虑一个无环连通图T = (V, F)，它的每条边e∈F具有非负的长度ae≥0。定义TSP的一个对应树实例G = (V, E)，把每条边(v, w) ∈E的成本c vw设置为等于T中唯一的v–w路径Pvw的长度
。示例如图1.12所示。
图1.12 示例图
定义一个线性时间的算法，根据一个边长非负的无环连通图，输出对应树实例的一条最低成本的旅行商路线。然后证明这个算法是正确的。
问题1.9 用自己擅长的编程语言实现TSP的穷举搜索算法（如小测验1.2所示）。为自己的实现增加一个新变化，使实例中各边的成本都是独立的，并且统一随机分布于{ 1 , 2 ,…, 100 }这个集合中。在1分钟的时间内，我们的程序能够可靠地处理多大的输入规模？在1小时内又是如何呢？（关于测试用例和挑战数据集，可以参考algorithmsilluminated网站。）
