动态规划

在科学和工程领域，从规划最短旅行路线到解码生命蓝图，许多最具挑战性的问题都涉及数量惊人的可能性。试图通过检查每个选项来找到最佳解决方案，在计算上往往是不可行的。本文介绍动态规划，这是一种为应对这种组合爆炸而设计的强大算法策略。它通过将艰巨的任务分解为可管理的子问题，提供了一种系统性的优化方法。在接下来的章节中，您将首先在“原理与机制”中深入探讨该方法背后的核心思想，探索最优性原理和递推关系等概念。然后，在“应用与跨学科联系”中，您将了解其在现实世界中的各种用途，从计算生物学到控制理论，揭示一个单一而优雅的概念如何为解决各种难题提供通用语言。

想象一下，你正试图找到从洛杉矶开车到纽约市的最佳路线。你可以尝试所有可能的路径，这是一项真正令人难以置信的任务。或者，你也可以更聪明一些。你可能会意识到，如果最佳路径恰好经过芝加哥，那么从芝加哥到纽约市的那段路程也必须是这两座城市之间的最佳路径。这个简单、听起来几乎显而易见的想法，是一种被称为​​动态规划​​的深奥算法策略的基石。这是一种通过将复杂问题分解成更简单的部分来解决它们的艺术，并且至关重要的是，要记住这些部分的解，这样你就永远不必重复求解。

这个原理，被正式称为​​贝尔曼最优性原理​​（Bellman Principle of Optimality），是动态规划的灵魂。它告诉我们，一个最优解是由其子问题的最优解构建而成的。让我们踏上一段旅程，看看这个单一而优雅的想法如何演变成一个强大的工具包，用以解决科学和工程领域的各种问题。

让我们从一个经典谜题开始：​​划分问题​​。给你一个正整数集合，比如 $\{1, 5, 11, 5\}$，问你是否能将它们分成两组，使得两组的和完全相等。在我们的例子中，你可以做到：$\{5, 5, 1\}$ 的和是 11，另一组就是 $\{11\}$。

计算机如何系统地解决这个问题呢？总和是 $1+5+11+5 = 22$。如果可以划分，每组的和必须是总和的一半，即 11。问题现在变成了：我们能否从这些数中找到一个子集，其和恰好为 11？这就是著名的​​子集和​​问题。

暴力方法是尝试所有可能的子集，但子集的数量呈指数增长。这时动态规划就派上用场了。我们不直接问那个大问题，而是提出一系列更小的相关问题。我们建立一个知识表格，一种“备忘单”。让我们定义一个状态 $P(i, j)$，它是一个简单的真/假问题：“仅使用我们集合中的前 $i$ 个数，是否可能凑成和 $j$？”。

我们的集合是 $\{1, 5, 11, 5\}$。让我们看看 $P(2, 6)$ 是如何确定的。我们在问：仅使用前两个数 $\{1, 5\}$，能否凑成和 6？为了回答这个问题，我们考虑第二个数 5。我们有两个选择：

1. ​​不使用 5。​​ 如果我们不使用它，我们就必须能用第一个数 $\{1\}$ 凑成和 6。这由 $P(1, 6)$ 表示。
2. ​​使用 5。​​ 如果我们使用它，我们需要用第一个数 $\{1\}$ 凑成剩下的和，即 $6 - 5 = 1$。这由 $P(1, 1)$ 表示。

如果这两种可能性中任何一种为真，那么 $P(2, 6)$ 就为真。在这种情况下，$P(1, 6)$ 为假（你不能用一个 1 凑成 6），但 $P(1, 1)$ 为真。所以，$P(2, 6)$ 为真！这个逻辑规则，被称为​​递推关系​​，是动态规划的引擎。它允许我们根据已经找到的答案，一次一个单元格地填充整个知识表格。

$P(i, j) = P(i-1, j) \lor P(i-1, j - s_i)$

这里，$s_i$ 是第 $i$ 个数。我们最初问题的最终答案就是 $P(4, 11)$ 的值。

这种填表方法似乎非常高效。对于 $n$ 个项目和一个目标和 $T$，我们填充一个 $n \times T$ 的表格。所需时间与表格大小成正比，大约是 $O(nT)$。这看起来像一个多项式，在计算机科学的世界里，这通常意味着“快”。但这里有一个微妙而美丽的欺骗性。

一个输入的“大小”是什么？在复杂性理论中，它不是数字的大小，而是写下它们所需的比特数。数字 1,000,000 只用 7 位数字写成，但它的值很大。表示一个整数 $T$ 所需的比特数与 $\log(T)$ 成正比。

我们算法的运行时间是 $O(nT)$。它在 $T$ 的数值大小上是多项式的，但在 $T$ 的比特长度上是指数级的（因为 $T$ 大约是 $2^{\log T}$）。这就是为什么这类算法被称为​​伪多项式​​算法。它们仅在所涉及的数字相当小的时候才快。

为了清楚地看到这一点，想象我们改变规则。如果我们用一元制表示数字，其中 5 写成 ‘11111’ 呢？现在，数字 $T$ 的大小就是它的值。输入长度本身与 $T$ 成正比。突然之间，我们的 $O(nT)$ 运行时间变成了输入长度的真正多项式函数！完全相同的算法，仅仅通过改变我们衡量输入的方式，就从技术上的“慢”（指数级）跃升为“快”（多项式）。这揭示了复杂性的本质与表示语言深度相关。

动态规划的力量远不止于数字谜题。它是一个通用的优化框架。考虑比较两个 DNA 序列的问题，这是现代生物学的基石。我们希望找到比对它们的最佳方式，以突出它们的相似性，这可能暗示着共同的进化历史。

假设我们想比对 AW 和 CAW。我们可以建立一个类似的表格，其中单元格 $H(i, j)$ 存储第一个序列的前 $i$ 个字母与第二个序列的前 $j$ 个字母之间最佳比对的分数。为了计算 $H(i, j)$，我们有三个选择：

1. 比对第 $i$ 个和第 $j$ 个字符。分数为 $H(i-1, j-1)$ 加上这次特定匹配或错配的分数。
2. 将第 $i$ 个字符与一个空位比对。分数为 $H(i-1, j)$ 减去一个空位罚分。
3. 将第 $j$ 个字符与一个空位比对。分数为 $H(i, j-1)$ 减去一个空位罚分。

我们只需取这三个选项中的最大值。这个递推关系再次从最优子解中构建出最优解。

该框架的真正美妙之处在于其灵活性。我们是在比较两个密切相关的基因，需要将它们从头到尾进行比对（​​全局比对​​）吗？那么我们必须对开头或结尾的任何空位进行罚分。我们通过用逐渐增大的空位罚分来初始化表格的第一行和第一列来实现这一点。这迫使最优路径从一个角落延伸到另一个角落。

或者我们是在两个长而分化的蛋白质中寻找一个小的、保守的功能区域（​​局部比对​​）吗？在这种情况下，我们希望比对可以从任何地方开始和结束。我们通过两个简单而巧妙的调整来实现这一点：我们将第一行和第一列初始化为零（不因开始新的比对而罚分），并且我们在递推关系中加入第四个选择：零。这意味着如果比对分数变为负数（不利），算法可以简单地放弃它，从头开始一个新的，分数为 0。这使得它能够找到得分最高的相似性岛屿，无论它在哪里。

同样的核心引擎，配以不同的“游戏规则”（初始化和递推），解决了两个根本不同的生物学问题。如果在某一步，两个选择给出了完全相同的最高分呢？这仅仅意味着不存在唯一的最佳比对；自然界找到了多个同样好的解决方案。

每个伟大的理论都有其局限性，理解这些局限性与理解理论本身同样富有洞察力。动态规划的魔力取决于将问题分解为独立子问题的能力。当子问题纠缠在一起时会发生什么？

考虑预测 RNA 分子如何折叠的问题。一个 RNA 序列可以折回自身，通过碱基配对形成复杂的三维结构。对于许多结构，我们可以使用动态规划。从位置 $i$到 $j$ 的序列片段的折叠可以分解为独立的子问题：配对区域内部发生了什么，以及外部发生了什么。这种可分解性导致了高效的多项式时间算法。

但 RNA 可以形成一种称为​​伪结​​的棘手结构。当碱基配对交叉时，就会发生这种情况，例如，当核苷酸 $i$ 与 $j$ 配对，而 $k$ 与 $l$ 配对，顺序为 $i k j l$。突然之间，从 $k$ 到 $j$ 的区域不再独立于从 $i$ 到 $k$ 的区域，因为 $i$ “越过” $k$ 与 $j$ 配对。整齐的分解被破坏了。

这对我们的算法来说是灾难性的。问题的复杂性爆炸式增长。它从可在多项式时间（如 $O(n^3)$）内解决，转变为 ​​#P-困难​​，这是一类被认为远非任何高效算法所能及的计数问题。它变得和计算任意图中完美匹配的数量一样困难。这不仅仅是需要一个更聪明的递推关系的问题，就像我们在序列比对中为高级的​​仿射空位罚分​​（空位的成本取决于其长度）所做的那样。伪结从根本上打破了我们简单的 DP 状态所依赖的局部性假设。问题的结构本身已经改变，使其处于巨大的计算鸿沟的另一边。

在现实世界中，我们使用的并不总是“最佳”解决方案。用于局部比对的 Smith-Waterman 算法保证能找到最优答案，但用它来将一个短基因与整个人类基因组进行比较将花费永恒的时间。这就是像 ​​BLAST​​（基础局部比对搜索工具）这样的启发式算法发挥作用的地方。BLAST 牺牲了最优性的保证，换来了惊人的速度。它的工作原理是找到非常短的、精确或高分的匹配（“种子”），然后只扩展这些有希望的区域。这是一个聪明的赌博：通过只关注最有可能的位置，它避免了完整 DP 矩阵的详尽、逐单元格的工作，使大型数据库搜索变得可行。

即使在严格的 DP 世界里，也存在实践智慧的空间。子集和的标准算法需要一个大小为 $O(nT)$ 的表格，这会消耗大量内存。但仔细观察递推关系 $P(i, j) = P(i-1, j) \lor P(i-1, j - s_i)$，就会发现要计算第 $i$ 行，我们只需要来自第 $(i-1)$ 行的信息。我们不需要一次性保留所有 $n$ 行！通过只使用两行（当前行和前一行），或者甚至使用一个巧妙地向后迭代的循环只使用一行，我们可以将内存需求从 $O(nT)$ 减少到仅 $O(T)$。这是一个完美的例子，说明了对问题内部依赖结构的更深理解如何能带来显著的实际收益。

从在图中找到最短路径到折叠 RNA 分子，从打包背包到比对基因组，动态规划证明了一个简单思想的力量：不要重复解决同一个问题。通过将复杂分解为简单，并建立一个解的库，它提供了一种系统性的方式来探索广阔的可能性空间，并发现其中的最优路径。它告诉我们，即使是最令人生畏的旅程，也可以一步一个脚印，通过一个个被牢记的小步骤来征服。

我们已经了解了动态规划的核心：将一个大问题分解成更小的、重叠的部分，每个部分只解决一次，并将结果存储在表格中以备将来使用，这是一个简单而深刻的思想。这种在贝尔曼最优性原理指导下的“记忆的艺术”，看似一个巧妙的编程技巧，但它的意义远不止于此。它是一种基本的推理方式，回响在从计算复杂性的抽象世界到工程学的实际挑战，乃至生命蓝图本身的各种领域中。现在，让我们踏上旅程，探索其中一些联系，看看这个美妙的思想如何为解决看似无关的难题提供一种通用语言。

在科学和物流领域，许多最诱人的问题都是我们所说的“组合”问题。它们涉及从数量多得惊人的可能性中选择最佳组合。思考著名的旅行商问题 (TSP)。一颗卫星需要从一个地面站网络收集数据，每个站点只访问一次，然后返回起点。目标很简单：找到最短的可能路线。如果有 $n$ 个站点，可能的路线数量约为 $(n-1)!$，这个数字增长得如此之快，以至于即使对于一个中等规模的 20 个站点，一台每秒检查十亿条路线的计算机也需要比宇宙年龄还长的时间才能找到最佳路线。暴力破解不仅效率低下，而且根本不可能。

在这里，动态规划前来救援，它不是通过检查每一条路线，而是分阶段地思考问题。我们不问“什么是最佳的完整路线？”，而是问一个更温和的问题：“从起点出发，访问一个特定的站点子集 $S$，并最终到达站点 $j$ 的最佳路径是什么？”让我们将这条路径的成本称为 $D(S, j)$。那么，我们如何找到这个成本呢？嗯，任何这样的路径都必须是从集合 $S$ 中的某个其他站点 $i$ 到达站点 $j$ 的。而到达站点 $i$ 的路径必须是访问集合 $S \setminus \{j\}$ 的最优路径。如果不是，我们就可以换上那条更好的子路径，从而创建一条通往 $j$ 的更好的整体路径，这就产生了矛盾！

这就是最优性原理在起作用。它给了我们一个递推关系：成本 $D(S, j)$ 是通过查看所有可能的倒数第二个站点 $i$，并取 $D(S \setminus \{j\}, i) + C_{ij}$ 的最小值来找到的，其中 $C_{ij}$ 是从 $i$ 到 $j$ 的直接旅行成本。我们从下往上构建我们的解决方案，从长度为一的路径开始，然后是长度为二的路径，以此类推，直到我们得到所需长度的所有路径的成本。虽然总复杂度仍然是指数级的，但它将一个不可能的阶乘搜索减少到大约 $O(n^2 2^n)$ 的量级，使得这个问题对于几十个城市而不是仅仅几个城市是可解的。

同样的逻辑也适用于其他资源分配难题。想象一个总容量为 $W$ 的云服务器和一份包含 $n$ 个任务的列表，每个任务都有特定的资源需求。我们能否找到一个任务子集，恰好用完所有容量？这就是子集和问题。同样，对所有 $2^n$ 个子集进行暴力检查太慢了。但我们可以建立一个简单的表格，对每个状态 $(i, j)$ 问一个“是/否”问题：“仅使用前 $i$ 个任务，我们能否实现总资源使用量恰好为 $j$？”对于 $(i, j)$ 的答案是“是”，如果我们可以用前 $i-1$ 个任务已经凑成和 $j$，或者如果我们能用前 $i-1$ 个任务凑成和 $j - s_i$ 并且现在我们包括了任务 $i$。这个简单的检查填满了一个大小为 $n \times W$ 的表格。注意这里的转折：算法的运行时间 $O(nW)$ 取决于容量 $W$ 的数值大小。如果 $W$ 非常大，即使任务数量很少，算法也很慢。这就是我们所说的伪多项式算法，这是一个美妙的微妙之处，提醒我们在定义问题的“大小”时要精确。同样的结构也是解决著名的背包问题的基础，甚至构成了设计巧妙的近似方案的起点，这些方案用一点点最优性的损失换取了巨大的速度提升。

也许动态规划最引人注目的跨学科成功是在计算生物学领域。DNA 双螺旋结构的发现揭示了生命是由一个四字母的字母表写成的：A、C、G、T。但要理解这本书记载的故事——基因——我们需要能够阅读和比较它们。

一个基本任务是序列比对。人类和黑猩猩的血红蛋白基因有多相似？要回答这个问题，我们需要将它们的 DNA 序列排列起来，并计算匹配、错配和空位的数量。找到最佳比对——即最大化相似度的比对——是一个优化问题。解决方案是一个优雅的动态规划算法，对于全局比对称为 Needleman-Wunsch 算法，对于局部比对称为 Smith-Waterman 算法。我们构建一个二维网格，一个序列沿顶部，另一个序列沿侧面。网格中的每个单元格 $(i, j)$ 将存储第一个序列的前 $i$ 个字符与第二个序列的前 $j$ 个字符之间最佳比对的分数。$(i, j)$ 处的分数仅取决于三个相邻单元格中的分数：$(i-1, j)$、$(i, j-1)$ 和 $(i-1, j-1)$，分别对应于引入一个空位或比对下一对字符。

通过从左上角开始填充这个表格，我们保证能在右下角找到最优比对分数。这个规模是惊人的。要比对两条人类染色体，每条约 2.5 亿个核苷酸长，DP 表将有超过 $6 \times 10^{16}$ 个单元格。即使每个单元格的计算很简单，总操作数也可以达到数百万亿。这推动了高性能计算的创新。因为 DP 表上一个反对角线上的所有单元格只依赖于先前反对角线上的单元格，所以它们都可以并行计算。这种“波前”计算非常适合现代图形处理器 (GPU) 的架构，让生物学家能够在可行的时间内完成这些大规模比对。

DP 在生物学中的力量不仅限于简单地读取 DNA，还扩展到主动编写它。在合成生物学中，科学家设计定制的 DNA 序列，以便在细菌等宿主生物中产生特定的蛋白质。遗传密码是简并的：几个三字母的“密码子”可以编码同一个氨基酸。生物体有“密码子偏好”，偏爱某些密码子而不是其他密码子，这会影响蛋白质的生产速度。生物工程师的问题是选择一个密码子序列，该序列编码所需的蛋白质，最大化生产率（基于密码子权重），并且——至关重要的是——避免意外创建限制性内切酶可能切割的某些“禁用”序列。这是一个完美的 DP 问题。我们一次一个氨基酸地构建 DNA 序列。状态不仅要跟踪蛋白质中的位置，还要跟踪我们已经构建的 DNA 序列的最后几个核苷酸。这种对后缀的“记忆”使我们能够检查添加下一个密码子是否会创建一个禁用的基序。这是一个使用 DP 状态在全局优化中强制执行局部约束的美丽例子。

即使是宏大的进化历程也可以用这些工具来研究。为了重建生命之树，我们模拟性状（或 DNA 序列）如何随时间沿着假设树的分支变化。为了找到最可能的树，我们必须计算在模型给定的情况下，看到我们拥有的叶子（现代物种中）数据的概率。这需要对树内部节点上祖先所有可能的状态进行求和。暴力求和是不可能的。但是 Felsenstein 的剪枝算法，它是一种树上的动态规划形式，优雅地解决了这个问题。它计算每个节点的“部分似然”，从叶子开始向根部移动。该算法在数学上等同于图模型上的消息传递，显示了进化生物学、概率论和机器学习之间的深刻联系。

当我们回到动态规划的诞生地：控制理论时，它的故事就完整了。这是一门关于在一段时间内做出最优决策以引导一个系统——无论是机器人、飞机还是经济体——朝向期望目标的科学。

考虑线性二次调节器 (LQR)，这是现代控制的基石。目标是在不消耗过多能量的情况下将系统维持在目标状态附近。贝尔曼方程，DP 的核心，告诉我们如何现在做出最佳决策。它说，从今天开始的最优计划的总成本是今天行动的成本加上我们明天将处于的状态的最优成本。我们通过从未来向后推理来解决这个问题。在最终时间 $N$，“未来成本”仅仅是分配给我们最终状态的惩罚，$V_N(x) = x^\top Q_f x$。这提供了边界条件。从那里，我们可以计算时间 $N-1$ 的最优未来成本，然后是 $N-2$，依此类推，一直回到现在。这个向后扫描的过程为我们提供了一个完整的策略，告诉我们在任何时间、任何状态下应采取的最优行动。

但如果世界是不确定的呢？如果我们甚至不能完美地观察我们系统的状态，而只能通过嘈杂的传感器来观察呢？这是随机控制的领域，也正是 DP 揭示其终极力量和抽象性的地方。著名的​​分离原理​​提供了一个惊人优雅的答案。它告诉我们可以将问题分成两部分。首先，一个估计问题：使用我们嘈杂观测的历史来形成一个“信念状态”，即关于系统真实、隐藏状态的概率分布。这个信念状态根据一个滤波方程演化。其次，一个控制问题：将这个信念状态视为一个新系统的新的、完全可观察的状态，并在这个概率分布的空间上使用动态规划解决最优控制问题。

想一想这意味着什么。“状态”不再是一个点，而是一个完整的函数。价值函数是一个函数的函数。然而，贝尔曼原理的基本逻辑仍然成立。我们正在一个无限维的信念空间上执行动态规划。这种抽象的飞跃使我们能够找到最优策略来应对从有故障传感器的机器人运动到动荡市场中的金融投资等各种问题。

从在地图上寻找最短路径，到破译遗传密码，再到在太空中驾驶航天器，动态规划的线索贯穿始终。这证明了一个事实，即在科学中，最强大的思想往往是最简单和统一的。记忆的艺术，即通过站在其更小部分解决方案的肩膀上来解决问题的艺术，就是这样一个思想。