Skip to content
返回搜索结果

动态规划

提出者
Richard Bellman
年份
1957
类型
Exact combinatorial optimization via recursive decomposition
类别
Mathematical programming

本文为机器翻译,尚未经过审校。 阅读英文原文

字号

它有什么作用?

动态规划(DP)是由Richard Bellman于1957年提出的一种精确优化技术,用于解决多阶段决策问题。它将复杂问题分解为简单、重叠的子问题,每个子问题只求解一次,并存储结果以避免重复计算。DP以最优性原理为基础,在问题表现出重叠子问题和最优子结构时,保证全局最优解。

方法背后的直觉

设想一下,要规划穿过一座城市的 shortest 路线,首先需要找出每对相邻交叉点之间的 shortest 路径,然后将这些小解决方案向上组合。不必从头开始重新探索所有可能的完整路线,而是重用预先计算好的局部答案。动态规划的工作方式相同:它缓存子问题的解,这样在构建完整答案时只需进行表查找,而无需重复繁重的计算。

历史学

Richard Bellman于1957年在兰德公司工作时创造了“动态规划”一词,故意选择“规划”一词来指代计划而非计算机编码。他陈述的最优性原理成为控制论、运筹学以及后来的强化学习的理论基础。经典的DP算法——Dijkstra的最短路径算法、Viterbi算法和Needleman-Wunsch序列比对算法——都直接源于Bellman的框架。

何时使用

当问题具有重叠子问题和最优子结构时,动态规划是适用的——这些特性在序列决策、资源分配、调度和字符串比对任务中很常见。它要求状态空间是完全可枚举且大小适中的;当状态变量很多或连续时,该方法会受到维度灾难的影响。对于状态空间难以处理的问题,近似DP或强化学习是更优选的替代方案。

局限与注意事项

  • 受维度灾难影响:内存和时间需求随状态变量数量呈指数级增长。
  • 需要对转移结构和奖励函数有完整的先验知识;在未知环境中不适用,除非进行近似。
  • 状态空间必须是离散的或可离散化的;连续高维问题需要牺牲精确度的近似方案。
  • 制定正确的状态表示和递推关系需要大量的特定问题洞察。

来源中的条件不能替代独立的科学审查或分析引擎的验证。

优势

  • 保证对满足最优性原理的问题给出精确的全局最优解。
  • 通过记忆化消除重复计算,在状态数量上实现多项式时间。
  • 产生明确的最优策略,而不仅仅是最优值,从而实现直接的决策支持。
  • 广泛应用于包括控制论、生物信息学、经济学和运筹学在内的各个领域。

应用

  • 网络中的最短路径和路由问题(Bellman-Ford、Dijkstra变体)。
  • 计算生物学中的序列比对(Needleman-Wunsch、Smith-Waterman算法)。
  • 运筹学中的最优资源分配和背包类组合问题。
  • 通过隐马尔可夫模型上的Viterbi算法进行语音和手写识别。
  • 经济学和工程学中的最优控制和多期投资组合优化。

使用方式

使用方式

1

整体优化问题表示为递推关系。对于每个状态 s 和决策阶段 n,价值函数 V_n(s) 等于即时最优奖励加上结果下一状态的折扣价值。这个Bellman方程形式化了最优性原理:任何最优路径的子路径本身也必须是最优的。

公式
V_n(s) = \max_{a \in A(s)} \left[ r(s,a) + \gamma V_{n-1}(T(s,a)) \right]
2

递推关系通过迭代或递归求解。在价值迭代中,V^*(s) 在所有状态下反复更新,直到收敛,使用当前估计的相邻状态值。每次更新都用可达到的最优即时奖励加上未来价值替换旧值,将最优性信息传播到整个状态空间。

公式
V^*(s) = \max_{a \in A(s)} \left[ r(s,a) + \gamma V^*(s') \right], \quad s' = T(s,a)
3

计算出的值存储在以状态为索引的表中。终端状态的基本值为零(或已知奖励),所有其他条目在子问题解决时填入。记忆化确保每个状态最多被评估一次,将指数级递归搜索降低到状态和阶段数量的多项式时间。

公式
\text{Table}[s] = \begin{cases} 0 & \text{if } s \in S_{\text{terminal}} \\ V^*(s) & \text{otherwise} \end{cases}
4

一旦价值表完成,最优策略 pi^*(s) 就通过简单的贪婪遍历恢复:对于每个状态,选择最大化即时奖励加上后继状态存储值的动作。这种单次遍历提取在计算上成本很低,并产生确定性的、全局最优的决策规则。

公式
\pi^*(s) = \arg\max_{a \in A(s)} \left[ r(s,a) + \gamma \, \text{Table}[T(s,a)] \right]

常见陷阱

  • 定义不足以表达的状态表示会导致不正确的递推关系和次优解。
  • 将自顶向下记忆化与自底向上制表混淆可能导致堆栈溢出错误或子问题评估顺序不正确。
  • 将DP应用于缺乏最优子结构的问题(例如,一般图中的最长路径)会无警告地产生不正确的结果。
  • 在累积奖励计算中忽略数值精度可能导致浮点实现中出现微妙的最优性错误。

常见问题

动态规划与分治法的区别是什么?

两者都将问题分解为子问题,但分治法假定子问题是独立的,自然地只求解一次。动态规划针对的是重叠子问题——同一个子问题出现在多个分支中——并记忆化结果以避免重复工作。如果没有重叠子问题,DP不会比直接递归带来计算优势。

何时应使用自顶向下记忆化而非自底向上制表?

自顶向下记忆化更容易直接从递推关系实现,并且只计算需要的子问题,有利于稀疏状态空间。自底向上制表避免了递归开销和堆栈限制,适用于稠密状态空间,并且在实践中通常更快。当需要计算的子问题集难以预测时选择自顶向下,当所有子问题都需要时选择自底向上。

动态规划与强化学习有何关系?

经典的DP需要一个完全已知的马尔可夫决策过程模型(转移概率和奖励)。强化学习将DP思想扩展到模型未知的环境,使用采样经验代替。Q学习和策略梯度方法等算法是近似DP过程,它们从交互中学习价值函数,而不是从显式模型中学习。

相关方法

参考文献

  1. Bellman, R. (1957). Dynamic Programming. Princeton University Press.

    ISBN:978-0-691-07951-6
    已复制。