动态规划原理

玻尔百科

核心要点

最优性原理指出，任何最优路径都由最优子路径组成，这使得复杂问题可以被分解为更小的、序列化的决策。
贝尔曼方程将一个状态的价值表示为即时成本与最优未来价值之间的权衡，在连续时间下，该方程转化为汉密尔顿-雅可比-贝尔曼（HJB）偏微分方程。
求解HJB方程可以得到价值函数和最优反馈控制律——一种依赖于状态的策略，它对未预见的干扰具有鲁棒性。
动态规划应用广泛，从解决背包问题和旅行商问题等离散问题，到工程学和经济学中的连续最优控制。

引言

在科学、工程乃至日常生活中，如何随时间做出最优决策是一个根本性的挑战。无论是规划一次穿越全国的旅行、管理一个投资组合，还是引导一艘航天器，我们常常面临一系列艰巨的选择，其中每一步都会影响未来的所有可能性。仅仅选择眼前最佳选项的简单贪心策略，往往会导致次优的长期结果。本文通过介绍动态规划原理来解决长期序贯优化的核心问题，这是一个将复杂问题分解为可管理阶段的强大框架。

本次探索分为两个主要部分。在第一章“原理与机制”中，我们将剖析动态规划的理论核心，从 Richard Bellman 的最优性原理和价值函数的概念开始。我们将看到这一逻辑如何被形式化为贝尔曼方程，以及其在连续时间下的强大对应物——汉密尔顿-雅可比-贝尔曼（HJB）方程。在这一理论基础之后，第二章“应用与跨学科联系”将展示该原理非凡的通用性，说明同一个核心思想如何为经典的计算机科学难题、控制工程中的基本问题，乃至计算生物学中的挑战提供解决方案。

原理与机制

最优性原理：一段旅程的逻辑

想象一下，你正在计划从洛杉矶到纽约的最短公路旅行路线。假设你规划的最优路线途经芝加哥。最优性原理提出了一个简单而深刻的观察：你的路线中从芝加哥到纽约的那一段，其本身必须是连接这两座城市的最短路线。如果不是这样——即如果存在一条从芝加哥到纽约的更快捷的路径——你只需将这段更优的路径拼接到你的总计划中，就能获得一条从洛杉矶出发的更短的总行程。因此，任何最优路径都由更小的最优子路径构成。这个由数学家 Richard Bellman 倡导的绝妙而简单的思想，构成了动态规划的核心。它使我们能够将一个异常复杂的长期问题分解为一系列级联的、更小且更易于管理的短期决策。

价值函数：未来的神谕

为了让这个原理变得实用，我们需要一种方法来量化在任何给定时刻我们所处情况的“好坏程度”。我们引入一个核心概念，称为价值函数，通常表示为 $V(t,x)$ 。可以把它想象成一个神谕。如果你的系统在时间 $t$ 处于状态 $x$ （比如，你在城市 $x$ ），价值函数 $V(t,x)$ 会告诉你从那一刻到旅程结束可能实现的绝对最佳结果——即可达到的最小成本或最大回报。对于我们的公路旅行而言， $V(\text{星期二, 芝加哥})$ 将代表到达纽约所需的最短剩余驾驶时间。价值函数神奇地将所有未来的最优决策封装在一个数字中。动态规划的全部目标就是发现这个函数。如果我们拥有了它，在任何时刻做出正确的选择就变得简单明了：我们只需采取能将我们引向具有最有利未来价值的状态的行动。

贝尔曼方程：跨越时间的对话

Bellman 将这一逻辑转化为一个优美而强大的数学表述，现在被称为动态规划原理（DPP）。假设我们在时间 $t$ 处于状态 $x$ 。我们通过施加一个持续时间为 $h$ 的控制 $u$ 来做出选择。这个行动会产生一个即时成本，由一个形如 $\int_t^{t+h} \ell(x_s, u_s) ds$ 的积分给出，其中 $\ell$ 是运行成本函数。在这段短暂的时间结束后，我们到达一个新的状态 $x_{t+h}$ 。根据定义，从这个新状态出发，未来可能的最优成本是 $V(t+h, x_{t+h})$ 。因此，我们最初选择所产生的总成本是即时成本与最优未来成本之和。为了达到最优，我们的初始选择必须是使这个和最小化的那个选择。

这个推理过程引出了著名的贝尔曼方程：

$V(t,x) = \inf_{u(\cdot) \text{ on } [t,t+h]} \left\{ \int_t^{t+h} \ell(x_s, u_s) ds + V(t+h, x_{t+h}) \right\}$

这个方程代表了现在与未来之间的一场对话。它断言，当前所处特定情况的价值，取决于为下一步小行动所付出的成本与你随后所处情况的价值之间的最佳权衡。

如果世界是不确定的呢？如果我们的车可能会在结冰的路面上打滑，或者随机出现交通堵塞呢？在随机世界中，施加一个控制不会导致一个确定的未来状态，而是导致一个关于未来状态的完整概率分布。原理保持不变，但我们现在关注的是*期望*未来成本。贝尔曼方程通过引入对未来结果的期望（用 $\mathbb{E}$ 表示）而优雅地适应了这种情况：

$V(t,x) = \inf_{u(\cdot)} \mathbb{E} \left\{ \int_t^{t+h} \ell(X_s, u_s) ds + V(t+h, X_{t+h}) \right\}$

其逻辑并未动摇；我们只是对宇宙所有可能的随机变化进行平均。

从原理到引擎：汉密尔顿-雅可比-贝尔曼方程

贝尔曼方程是一个优美的原理，但以上述形式存在时，它并不是一个实用的计算工具。真正的魔力发生在我们考虑一个无穷小的时间步长，即令 $h \to 0$ 时。借助微积分的魔力——特别是泰勒级数，以及在随机情况下的伊藤公式——这种不同时间点之间的关系转变为一个单一时间点的微分方程。这就是强大的汉密尔顿-雅可比-贝尔曼（HJB）方程。

对于一个随机问题，其推导过程是通过使用伊藤公式展开 $V(t+h, X_{t+h})$ ，并将其代入贝尔曼方程。经过一些代数变换并取极限后，我们发现价值函数 $V$ 必须满足一个特定的偏微分方程（PDE）。一个典型的HJB方程具有以下形式：

$-\frac{\partial V}{\partial t} = \inf_{a \in A} \left\{ \underbrace{\ell(x,a) + \nabla_x V \cdot b(x,a)}_{\text{Hamiltonian}} + \underbrace{\frac{1}{2} \text{Tr}(\sigma(x)\sigma(x)^T \nabla_x^2 V)}_{\text{Diffusion term}} \right\}$

被最小化的表达式称为哈密尔顿量，这个概念借鉴自经典力学，它捕捉了运行成本 $\ell$ 与由系统确定性动态 $b$ 引起的价值变化之间的瞬时权衡。扩散项涉及 $V$ 的二阶空间导数（即海森矩阵 $\nabla_x^2 V$ ），它代表了由不确定性带来的额外成本——一种由随机噪声 $\sigma$ 引入的“风险溢价”。HJB方程巧妙地将随时间寻找最优路径这一抽象问题，转化为在状态空间上求解一个偏微分方程的具体问题。

控制者手册：反馈的力量

求解HJB方程类似于绘制一幅“成本地貌”的拓扑图。一旦我们拥有了价值函数 $V(t,x)$ ，我们就掌握了决策的终极指南。但HJB方程带给我们的东西更为珍贵。方程中的最小化步骤 $\inf_{a \in A} \{ \dots \}$ 不仅定义了方程本身，还为我们指明了在每个点 $(t,x)$ 上，究竟是哪个控制动作 $a^*(t,x)$ 实现了该最小值。

这就产生了一个最优反馈控制律，或称为策略。它是一本完整的操作手册，宣告着：“无论你在哪里 ( $x$ )，无论现在是什么时间 ( $t$ )，这都是你当下应该做的最好的事情。”这与开环控制有着深刻的不同，后者是一个从起点到终点预先计算好的行程计划。反馈策略是鲁棒的；如果你因未预见的干扰而偏离轨道，它会自动告诉你从新位置出发的最佳新行动。HJB框架自然而然地产生了这些强大的、依赖于状态的策略。

杰作的实践：里卡提方程的优雅

让我们在整个工程学领域最著名的问题之一中见证这个引擎的运作：线性二次（LQ）调节器。目标很简单：将一个线性系统（其动态由矩阵 $A$ 和 $B$ 描述）引导至一个目标状态（通常是原点），同时最小化一个在状态偏差和控制努力上均为二次的成本。这个优雅的模型适用于无数现实世界的场景，从保持火箭直立到管理投资组合。

这个问题的HJB方程看起来相当令人生畏。然而，如果我们做一个有根据的猜测——一个*拟设*——即价值函数在状态上也是二次的，形式为 $V(t,x) = x^T P(t) x + c(t)$ ，奇迹就会发生。复杂的HJB偏微分方程坍缩为一组关于矩阵 $P(t)$ 和标量 $c(t)$ 的简单得多的常微分方程。 $P(t)$ 所满足的方程就是著名的矩阵里卡提方程：

$-\dot{P}(t) = A^T P(t) + P(t) A - P(t) B R^{-1} B^T P(t) + Q$

这个方程从由最终成本决定的终端条件 $P(T)=S$ 开始，在时间上向后求解。一旦我们得到了矩阵函数 $P(t)$ ，最优反馈控制就可以优雅地表示为 $u^*(t) = -R^{-1}B^T P(t) X_t$ 。这是现代控制理论的基石，它直接而自然地源于动态规划原理。标量项 $c(t)$ 代表了由随机噪声带来的不可约减的期望成本——这是生活在一个不确定世界中所付出代价的完美例证。

全局视角与绝对正确性

当与庞特里亚金极大值原理（PMP）等其他方法对比时，动态规划的威力变得更加显而易见。PMP是一种变分方法，它为最优性提供了必要条件。它识别出“极值”路径，在这些路径上，任何微小的局部变动都无法改善成本。这类似于在曲线上寻找斜率为零的点；它可能是一个最小值点、一个最大值点或一个拐点。

HJB方法，就其本质而言，是在寻求全局最优性。价值函数 $V(t,x)$ 代表了真正的最小成本，并且相应的验证定理证明，如果你找到一个满足HJB方程的控制策略，它不仅仅是一个局部候选解——它被保证是全局最优的。这提供了一个强大的充分性条件。

在成本地貌具有多个谷底的非凸问题中，这种差异尤为明显。想象一个像 $(u^2-1)^2$ 这样的控制成本函数，它在 $u=1$ 和 $u=-1$ 处有两个不同的极小值点。PMP可能会识别出一条使用了仅为局部最优的控制的路径。然而，HJB方程中的 inf 算子会无情地比较所有可能的控制选择，并在每一个点上挑选出绝对最佳的一个，从而避免了局部最优的陷阱。

那么，如果世界并不像我们的微积分所期望的那样平滑呢？如果价值函数存在导数不存在的扭折或尖角呢？HJB方程的经典推导会因此失效。然而，其基本原理是如此稳健，以至于数学家们对其进行了扩展。由 Crandall 和 Lions 发展的现代粘性解理论，提供了一种即使在价值函数不可微的情况下也能严格解释HJB方程的方法。这确保了 Bellman 的优美思想能够应用于更广泛的问题领域，包括那些具有退化扩散或非光滑数据的问题。它深刻地证明了一个原理的深远且持久的统一性，这个原理将一个简单的公路旅行谜题与随机控制的复杂数学联系在一起。

应用与跨学科联系

我们花了一些时间来理解动态规划的机制——这个将艰巨的旅程分解为一系列更小、可管理步骤的优雅思想。我们已经看到，记住到达每个里程碑的最佳方式——即最优性原理——如何让我们能够在不迷失于指数级增长的可能性荒野中的情况下，构建出最优路径的地图。这个原理不仅仅是解决计算机科学难题的一个聪明技巧；它是一个深刻而普遍的概念，在各种令人惊叹的领域中回响。它是对远见的数学表述。

现在，让我们踏上一段旅程，看看这个原理将我们带向何方，从日常生活的普通交易到现代科学与工程的宏大挑战。

审慎分配的艺术

生活中的许多决策都与资源分配有关。你预算有限，时间有限，或者容量固定，而你希望从中获得最大收益。正是在这些问题中，经典的“贪心”方法——即在每个时刻只选择最吸引人的选项——常常会误导我们。

想象一个收银员在找零。贪心的收银员总是会先给出面额最大的硬币。对于标准的货币系统，这完全没问题。但如果硬币的面额很奇特，比如说 $\{1, 6, 10, 15\}$ 呢？为了找零20个单位，贪心选择是先给一枚15单位的硬币，剩下的5个单位用五枚1单位的硬币支付，总共需要六枚硬币。这是一个局部最优的选择，但并非全局最优。一个更周到的收银员会发现，用两枚10单位的硬币只需两枚硬币就能完成任务。贪心选择一旦做出，就将收银员锁定在一条次优路径上。动态规划通过提出一个更有耐心的问题来解决这个问题：“对于每一个最高到20的数值，最佳的找零方式是什么？”通过首先构建较小金额的解，它发现通往20单位最优解的路径可能来自10单位的最优解，而不是5单位的解。

这个“收银员困境”是一大类问题的原型。想想在数据中心中跨服务器平衡任务的情景。你有一组计算任务，每个任务都有一定的“负载”，你想将其中一个子集分配给一台服务器，以在不超载的情况下尽可能地填满其容量。贪心方法可能会先分配最大的任务，这可能会留下一个尴尬的容量空间，让较小的任务无法填满。动态规划通过考虑其能实现的所有可能的总负载，找到了真正的最优装填方案。这是经典背包问题的一个变种，也是资源分配的典型问题。

无论资源是有限的还是看似无限的，同样的原理都适用。考虑一位架构师在设计一个服务器集群以处理每秒一定数量的传入请求。他们可以从几种类型的服务器中选择；一种类型可能以 $p_1$ 的成本处理 $c_1$ 个请求块，另一种以 $p_2$ 的成本处理 $c_2$ 个请求块，依此类推。目标是在最低成本下，精确地满足总需求。这就是完全背包问题，动态规划再次通过有条不紊地计算满足每一个直至目标的请求水平的最低成本来提供答案。在所有这些案例中，动态规划的成功在于它更看重目的地，而非旅程的速度，从而确保每一步都踏在一条真正的最优路径上。

序列的逻辑：从播放列表到基因组

世界不仅仅是关于积累事物，也关乎如何按顺序排列它们。一个项目中任务的最佳顺序是什么？一辆送货卡车的最有效路线是什么？一个物理过程中最可能发生的事件序列是什么？

让我们从一件有趣的事情开始：制作完美的播放列表。假设你有一组歌曲，并且对每对歌曲都有一个“过渡质量”分数——即一首歌到下一首的衔接效果如何。你想创建一个包含所有歌曲的播放列表，以最大化总质量。这关乎的不是包含哪些歌曲，而是播放它们的顺序。暴力检查所有 $N!$ 种排列是徒劳无功的。动态规划通过将“状态”定义为已播放歌曲的集合，而不仅仅是最后一首播放的歌曲，来解决这个问题。它为每个歌曲子集计算最佳质量的播放列表，并以该子集中的每一首可能的歌曲作为结尾。这个问题是计算机科学中最著名的挑战之一——旅行商问题（TSP）的一个友好的伪装，该问题要求找到访问一组城市并返回起点的最短可能路线。

正是这种用于排序歌曲的相同逻辑，是我们时代最伟大的生物学成就之一——基因组测序的核心。“鸟枪法测序”方法涉及将DNA打断成数百万个微小的、重叠的片段。挑战在于将它们按正确的顺序拼接起来。问题是找到所有这些片段的最短公共超串。这是如何做到的呢？我们可以将每个片段想象成TSP中的一个“城市”。从片段 $i$ “旅行”到片段 $j$ 所节省的“距离”是它们重叠部分的长度。找到最大化这些重叠以产生最短最终字符串的排列方式，与找到访问所有城市的最短路径完全类似。动态规划的状态是一个位掩码，代表我们已经组装的片段子集，其价值是该子集的最短超串的长度。这是一个令人叹为观止的例子，展示了一个单一的、抽象的算法思想如何为解开生命密码本身提供了钥匙。

当然，并非所有的序列问题都如此复杂。考虑一下调度任务以最大化利润或生产力的日常挑战。给定一组潜在任务，每个任务都有开始时间、结束时间和价值，你必须选择一个时间上不重叠的子集，以最大化你的总价值。DP解决方案的关键洞见是首先按结束时间对任务进行排序。这为决策施加了一个自然的顺序。当你考虑每个任务时，你有一个简单的选择：要么包含这个任务，要么不包含。如果你包含它，你就将其价值加到你可以从在该任务开始前已完成的任务中获得的最优利润上。如果你不包含它，你的利润就是你能从之前的任务中获得的最大收益。通过在每一步做出最优选择，你就能构建出一个最优的时间表。

有时，规则的微小变化需要对状态进行更具创造性的定义。在一个诸如将钢筋切割成块出售的制造过程中，可能有一条规则，即对一根新钢筋的第一次切割会因为校准而浪费少量材料。对同一根钢筋的后续切割则没有浪费。一个仅基于钢筋剩余长度的简单DP状态已不再足够。我们需要知道更多信息。解决方案是丰富状态：我们定义两个价值函数，一个用于“新”钢筋的收益，另一个用于“已用”钢筋的收益。这说明了应用DP的艺术：在每一步正确识别出所有必要信息，以便为未来做出真正最优的决策。

连续统：从离散步骤到信念之波

到目前为止，我们的旅程都是由离散的步骤组成。但如果世界是连续的呢？如果我们正在控制一枚火箭，其中时间和空间是平滑流动的呢？在这里，动态规划原理经历了一次辉煌的转变。

考虑控制一个简单的物体，其位置 $x$ 随连续时间 $t$ 根据 $\dot{x}(t) = u(t)$ 变化，其中我们的控制 $u(t)$ 是我们对速度的选择。我们希望将物体引导至一个目标，同时最小化燃料（运行成本）和最终误差（终端成本）的组合。价值函数 $V(x,t)$ 代表了如果我们从时间 $t$ 的位置 $x$ 出发，可能达到的最小成本。Bellman 的最优性原理仍然成立：

V(x, t) = \min_{u} \left\{ \text{cost over a tiny time step } \Delta t + V(x + u \Delta t, t+\Delta t) \right\}

如果我们重新整理这个式子，除以 $\Delta t$ ，并取 $\Delta t \to 0$ 的极限，这个简单的递推关系就会演变成一个偏微分方程。这就是著名的汉密尔顿-雅可比-贝尔曼（HJB）方程。计算机科学家的数组查找变成了物理学家的偏导数。对选择的离散优化变成了对哈密尔顿函数的最小化。HJB方程是最优控制理论的灵魂，它支配着从机器人学、航空航天工程到经济规划的一切。这是用连续统的语言讲述的动态规划。

但如果世界不仅是连续的，而且还是不确定的呢？如果我们正在使用带噪声的传感器数据在火星上引导一辆探测车呢？我们不知道探测车的确切位置 $X_t$ 。相反，我们有一个信念状态 $\pi_t$ ，它是所有可能位置上的一个概率分布。这个信念就是我们的新“状态”。令人难以置信的是，动态规划原理可以被提升到这个抽象的、无限维的信念空间中。

我们的信念 $\pi_t$ 的演化本身就是一个随机过程，由滤波方程（如Kushner-Stratonovich方程）控制，随着新的、带噪声的观测数据的到来，这些方程会更新我们的概率分布。我们可以在这个信念空间上定义一个价值函数 $V(t, \pi)$ ，它代表在当前不确定性状态下可能取得的最佳结果。HJB方程现在变成了这个概率分布空间上的一个方程。它的二阶项源于观测的随机性，量化了信息的价值——即一个新的测量预计能在多大程度上改善我们的决策。这是不确定性下决策的数学核心，这一原理适用于医生诊断病人、投资者在动荡市场中航行，或人工智能学习与复杂世界互动。

从数硬币到在概率的迷雾中导航，动态规划原理揭示了其作为最优规划普适法则的本质。它教导我们，通往辉煌未来的道路，是通过理解当下所有可能形式的真正价值来构建的。它雄辩地证明了一种思想的美妙统一性，这种思想将逻辑学家的谜题、生物学家的密码和物理学家的宇宙联系在一起。