动态规划

最优化原理

1951年美国数学家R．Bellman等人，根据一类多阶段问题的特点，把多阶

段决策问题变换为一系列互相联系的单阶段问题，然后逐个加以解决。一些静

态模型，只要人为地引进“时间”因素，分成时段，就可以转化成多阶段的动

态模型，用动态规划方法去处理。与此同时，他提出了解决这类问题的“最优

化原理”(Principle of optimality)：

“一个过程的最优决策具有这样的性质：即无论其初始状态和初始决策如

何，其今后诸策略对以第一个决策所形成的状态作为初始状态的过程而言，必

须构成最优策略”。简言之，一个最优策略的子策略，对于它的初态和终态而

言也必是最优的。

这个“最优化原理”如果用数学化一点的语言来描述的话，就是：假设为

了解决某一优化问题，需要依次作出n个决策D1，D2，?，Dn，如若这个决策序

列是最优的，对于任何一个整数k，1 < k < n，不论前面k个决策是怎样的，以

后的最优决策只取决于由前面决策所确定的当前状态，即以后的决策Dk+1，

Dk+2，?，Dn也是最优的。

最优化原理是动态规划的基础。任何一个问题，如果失去了这个最优化原

理的支持，就不可能用动态规划方法计算。能采用动态规划求解的问题都需要

满足一定的条件：

(1) 问题中的状态必须满足最优化原理；

(2) 问题中的状态必须满足无后效性。

所谓的无后效性是指：“下一时刻的状态只与当前状态有关，而和当前状

态之前的状态无关，当前的状态是对以往决策的总结”。

问题求解模式

动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通

过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同

时确定了完成整个过程的一条活动路线(通常是求最优的活动路线)。如图所示

。动态规划的设计都有着一定的模式，一般要经历以下几个步骤。

初始状态→│决策１│→│决策２│→?→│决策ｎ│→结束状态

图1 动态规划决策过程示意图

(1)划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。在划

分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无

法求解。

(2)确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况

用不同的状态表示出来。当然，状态的选择要满足无后效性。

(3)确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，

状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定

了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两段

各状态之间的关系来确定决策。

(4)寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终

止条件或边界条件。

算法实现

动态规划的主要难点在于理论上的设计，也就是上面4个步骤的确定，一旦

设计完成，实现部分就会非常简单。使用动态规划求解问题，最重要的就是确

定动态规划三要素：问题的阶段,每个阶段的状态以及从前一个阶段转化到后一

个阶段之间的递推关系。递推关系必须是从次小的问题开始到较大的问题之间

的转化，从这个角度来说，动态规划往往可以用递归程序来实现，不过因为递

推可以充分利用前面保存的子问题的解来减少重复计算，所以对于大规模问题

来说，有递归不可比拟的优势，这也是动态规划算法的核心之处。确定了动态

规划的这三要素，整个求解过程就可以用一个最优决策表来描述，最优决策表

是一个二维表，其中行表示决策的阶段，列表示问题状态，表格需要填写的数

据一般对应此问题的在某个阶段某个状态下的最优值（如最短路径，最长公共

子序列，最大价值等），填表的过程就是根据递推关系，从1行1列开始，以行

或者列优先的顺序，依次填写表格，最后根据整个表格的数据通过简单的取舍

或者运算求得问题的最优解。下面分别以求解最大化投资回报问题和最长公共

子序列问题为例阐述用动态规划算法求解问题的一般思路

动态规划

在数学与计算机科学领域，动态规划用于解决那些可分解为重复子问题（overlapping subproblems，想想递归求阶乘吧）并具有最优子结构（optimal substructure，想想最短路径算法）（如下所述）的问题，动态规划比通常算法花费更少时间。

上世纪40年代，Richard Bellman最早使用动态规划这一概念表述通过遍历寻找最优决策解问题的求解过程。1953年，Richard Bellman将动态规划赋予现代意义，该领域被IEEE纳入系统分析和工程中。为纪念Bellman的贡献，动态规划的核心方程被命名为贝尔曼方程，该方程以递归形式重申了一个优化问题。

在“动态规划”（dynamic programming）一词中，programming与“计算机编程”（computer programming）中的programming并无关联，而是来自“数学规划”（mathematical programming），也称优化。因此，规划是指对生成活动的优化策略。举个例子，编制一场展览的日程可称为规划。 在此意义上，规划意味着找到一个可行的活动计划。

?

概述

图1 使用最优子结构寻找最短路径：直线表示边，波状线表示两顶点间的最短路径（路径中其他节点未显示）；粗线表示从起点到终点的最短路径。

不难看出，start到goal的最短路径由start的相邻节点到goal的最短路径及

start到其相邻节点的成本决定。

最优子结构即可用来寻找整个问题最优解的子问题的最优解。举例来说，寻找图上某顶点到终点的最短路径，可先计算该顶点所有相邻顶点至终点的最短路径，然后以此来选择最佳整体路径，如图1所示。

一般而言，最优子结构通过如下三个步骤解决问题：

a) 将问题分解成较小的子问题；

b) 通过递归使用这三个步骤求出子问题的最优解；

c) 使用这些最优解构造初始问题的最优解。

子问题的求解是通过不断划分为更小的子问题实现的，直至我们可以在常数时间内求解。

图2 Fibonacci序列的子问题示意图：使用有向无环图（DAG, directed acyclic graph）而非树表示重复子问题的分解。

为什么是DAG而不是树呢？答案就是，如果是树的话，会有很多重复计算，下面有相关的解释。

一个问题可划分为重复子问题是指通过相同的子问题可以解决不同的较大问题。例如，在Fibonacci序列中，F3 = F1 + F2和F4 = F2 + F3都包含计算F2。由于计算F5需要计算F3和F4，一个比较笨的计算F5的方法可能会重复计算F2两次甚至两次以上。这一点对所有重复子问题都适用：愚蠢的做法可能会为重复计算已经解决的最优子问题的解而浪费时间。

为避免重复计算，可将已经得到的子问题的解保存起来，当我们要解决相同的子问题时，重用即可。该方法即所谓的缓存（memoization，而不是存储memorization，虽然这个词亦适合，姑且这么叫吧，这个单词太难翻译了，简直就是可意会不可言传，其意义是没计算过则计算，计算过则保存）。当我们确信将不会再需要某一解时，可以将其抛弃，以节省空间。在某些情况下，我们甚至可以提前计算出那些将来会用到的子问题的解。

总括而言，动态规划利用：

1) 重复子问题

2) 最优子结构

3) 缓存

动态规划通常采用以下两种方式中的一种两个办法：

自顶向下：将问题划分为若干子问题，求解这些子问题并保存结果以免重复计算。该方法将递归和缓存结合在一起。

自下而上：先行求解所有可能用到的子问题，然后用其构造更大问题的解。该方法在节省堆栈空间和减少函数调用数量上略有优势，但有时想找出给定问题的所有子问题并不那么直观。

为了提高按名传递（call-by-name，这一机制与按需传递call-by-need相关，复习一下参数传递的各种规则吧，简单说一下，按名传递允许改变实参值）的效率，一些编程语言将函数的返回值“自动”缓存在函数的特定参数集合中。一些语言将这一特性尽可能简化（如Scheme、Common Lisp和Perl），也有一些语言需要进行特殊扩展（如C++，C++中使用的是按值传递和按引