还真有这样一本经典书，那就是《算法设计》（Algorithm Design）。不知道有多少人关注过这本最为经典的算法入门书。
《算法设计》的目标是将这种方法带入算法研究，作为一个设计过程，它始于各种计算应用程序中出现的问题，构建在对算法设计技术理解的基础之上，最终得到这些问题的有效解决方案。我们试图探讨算法思想在计算机科学中的作用，并将这些思想与一些精确制定的问题联系起来，我们可以为它们设计算法并进行分析。换言之，导致这些问题的根本问题是什么？如何选择这些特定的方式来描述它们？如何认识到不同情况下适用哪些设计原则？为此，我们的目标是，建议如何在不同计算领域的复杂问题中识别算法问题的清晰描述形式，并针对由此产生的问题，建议如何设计有效的算法。通过重新理顺思路（包括错误的起点和死胡同），从最简单的初始方法到最终的解决方案，通常可以更好地理解复杂的算法。这导致了一种阐述风格，它不是描述从问题陈述到算法的最直接路径，但我们认为它更好地反映了我们和同事真正思考这些问题的方式。
算法设计
问题和带解答的练习
本书的一个重要特征是问题集。本书共包含 200 多个问题，这是我们在康奈尔大学教学课程的一部分，几乎所有问题都在课外作业中被开发，或者在课堂测验进行了考试。我们将问题视为本书的一个重要组成部分，并且让它们的结构与我们对内容的整体方法保持一致。其中大部分内容包含了一些问题的详细文字描述，这些问题出现在计算机科学应用领域或其他地方。部分问题是我们在教材中讨论的问题的实践：建立必要的符号和形式化，设计算法，然后分析这个算法并证明它是正确的。（我们认为这些问题的完整答案应该包括所有这些部分：带完整解释的算法、运行时间的分析和正确性的证明。）这些问题的想法很大程度上来自我们多年来与在不同领域工作的人们的讨论。而且，在某些情况下，这些问题也记录了一个有趣的（虽然是容易的）算法的应用，我们没有在其他任何地方看到过这些应用。
为了帮助解决这些问题，我们在每章中都加入了一节，名为“带解答的练习”，讨论一个或多个问题，并描述了如何形式化一个解。因此，专门针对每个带解答的练习的讨论，要比简单编写完整、正确的解决方案所需的时间长得多（换言之，如果将这些解决方案指定为课外作业题，那么所用的时间明显要比获得完全学分所需的时间长）。实际上，与本书的其余部分一样，这些节中的讨论应该看成是试图让人们了解一个更大的过程，通过这个过程可以考虑这种类型的问题，并最终形成精确解的详细说明。
关于在课程中使用这些问题作为作业，有两点值得一提。首先，问题大致按照难度增加的顺序排列，但这只是一个粗略的指导，建议不要过分看重它：因为大部分问题是专为本科生班的作业设计的，每章中的大部分问题在难度上实际上都差不多。其次，除编号最小的几个问题之外，其他问题都需要投入一些时间，既要将问题描述与这一章中的算法技术联系起来，又要实际设计必要的算法。在我们的本科课程中，每周大约布置 3 道这样的问题。
《算法设计》各章概要
本书第 1 章首先介绍一些有代表性的算法问题。一开始就是稳定匹配问题（stable matching problem），因为我们认为它比任何抽象的讨论更具体，也更优雅地提出了算法设计中的基本问题：稳定匹配是从自然但复杂的现实世界问题中提出的，从中可以抽象出一个有趣的问题陈述，以及一个令人惊讶的有效算法来解决这个问题。第 1 章的其余部分讨论 5 个“有代表性的问题”，这些问题预先展示了课程其余部分的主题。这 5 个问题是相互关联的，因为它们都是独立集问题（independent set problem）的变异或特殊情况。但一个可以通过贪心算法解决，一个可以通过动态规划解决，一个可以通过网络流解决，一个（独立集问题本身）是 NP 完全的，还有一个是PSPACE 完全的。密切相关的问题在复杂性方面可能有很大差异，这一事实是本书的一个重要主题，这 5 个问题作为里程碑，随着本书的推进而再次出现。
第 2 章和第 3 章包含前面提到的 CS1/CS2 课程系列的衔接。第 2 章介绍用于分析算法的关键数学定义和符号，以及它们背后的发人深省的原理。这一章首先非正式地概述计算易解问题的含义，并用多项式时间的概念作为效率的正式概念。然后，更正式地讨论函数的增长率和渐近分析，并对算法分析中常见函数及其标准应用提供指导。第 3 章介绍使用图所需的基本定义和算法原语，这些是本书中许多问题的核心。在 CS1/CS2 课程系列的后期，学生通常会实现许多基本图算法，但在更广泛的算法设计环境中提供这些材料是很有价值的。特别是，我们讨论了图的基本定义、图的遍历技术（如宽度优先搜索和深度优先搜索）以及有向图概念（包括强连通性和拓扑排序）。
第 2 章和第 3 章还介绍许多基本数据结构，它们将用于实现整本书中的算法。更高级的数据结构将在后续章中介绍。关于数据结构，我们会在实现本书中开发的算法需要时引入它们。因此，虽然这里介绍的许多数据结构对学过 CS1/CS2 系列的学生来说是很熟悉的，但我们的重点是在更广泛的算法设计和分析环境中使用这些数据结构。
第 4 章至第 7 章介绍 4 种主要的算法设计技术：贪心算法、分治法、动态规划和网络流。使用贪心算法的挑战在于判断它们何时好用，何时不好用。对这个主题的介绍，我们围绕对证明贪心算法正确的各种论据进行分类的方式来展开。第 4 章最后介绍贪心算法的一些主要应用，包括最短路径、无向生成树和有向生成树以及聚类和压缩。对于分治法，我们首先讨论一些策略，将递推关系求解为运行时间的界限。然后，我们展示对这些递推的熟悉程度可以如何指导算法的设计，这些算法改进了对许多基本问题的直接方法，包括排名比较、平面上最近点对的计算，以及快速傅里叶变换。接下来，我们开始介绍动态规划，从隐藏在它背后的递归直觉开始，然后通过它们自然产生的应用，构建越来越多有表现力的递推形式描述。第 6 章最后对两个基本问题的动态规划方法进行扩展讨论：序列比对及其在计算生物学中的应用；图中的最短路径及其与因特网路由协议的联系。最后，我们介绍网络流问题的算法，我们将这一章的重点放在讨论网络流的大量不同应用上。在算法课程中介绍网络流时，学生往往无法欣赏到它可以应用的广泛问题，我们试图通过介绍在负载均衡、调度、图像分割和许多其他问题中的应用，更好地展示它的多种能力。
第 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 章，第 4 章至第 8 章（不包括 4.3 节、4.7 节、4.8 节、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 章。虽然在研究生的导论性课程中，我们的重点是更高级的部分，但我们发现，对学生来说，有一本完整的书籍用于复习或补充背景知识是很有用的，因为学习这门课的学生的本科背景有所不同。
最后，本书支持研究生、研究人员或计算机专业人员自学，他们也许希望了解如何能够在自己的工作环境中使用特定的算法设计技术。一些研究生和同事已经以这种方式使用了本书的部分内容。
版式赏析
