chap7_动态规划

动态规划的三个实施步骤

什么是动态规划

动态规划（Dynamic Programming）是一种解决复杂问题的算法思想，它通常用于求解最优化问题。动态规划的核心思想是将复杂问题分解成较简单的子问题，并通过子问题的最优解推导出原问题的最优解。

动态规划的三个实施步骤

动态规划的实施步骤通常包括以下三个阶段：

1. 划分阶段：将原问题划分成若干个子问题，通过划分可以简化问题的复杂度。

2. 确定状态：定义状态表示问题的不同阶段和状态，以及状态之间的关系。状态的选择对最终解决问题的效率和准确性有很大影响。

3. 推导方程：根据子问题的最优解和状态之间的关系，推导出原问题的最优解，并通过递推和迭代求解。

下面将详细介绍每个步骤。

1. 划分阶段

在划分阶段，我们需要将原问题划分成若干个子问题。通常，问题的划分可以基于以下两种方式之一：

• 递归划分：将原问题拆分成规模更小的相同类型的子问题，直到问题规模较小，可以直接得到解答。

• 迭代划分：通过迭代的方式，逐步处理原问题的不同阶段，每个阶段都可以看作是一个子问题。

划分阶段可以大大减少问题的复杂度，使得问题的求解更加可行和高效。

2. 确定状态

确定状态是动态规划的核心步骤，它需要定义状态并建立状态之间的关系。状态表示问题的不同阶段和状态，以及状态之间的关联关系。

在确定状态时，通常需要考虑以下几个因素：

• 问题的边界状态：例如，问题的起始状态和最终状态。

• 中间状态的定义：例如，问题的中间阶段的状态。 • 状态之间的转移方程：即状态之间的关联关系，包括过程中的选择和决策。

通过合理地确定状态，可以将复杂问题简化成易于求解的子问题，并能够快速推导出原问题的最优解。

3. 推导方程

在推导方程阶段，我们通过子问题的最优解和状态之间的关系，推导出原问题的最优解。

根据问题的具体特点和状态定义，推导方程可以采用不同的方式，例如：

• 递推方程：通过递归地求解子问题，逐步推导出原问题的最优解。

[理学]第七章动态规划精品合集

第七章动态规划

规划问题的最终⽬的就是确定各决策变量的取值，以使⽬标函数达到极⼤或极⼩。在线性规划和

⾮线性规划中，决策变量都是以集合的形式被⼀次性处理的；然⽽，有时我们也会⾯对决策变量需分期、分批处理的多阶段决策问题。所谓多阶段决策问题是指这样⼀类活动过程：它可以分解为若⼲个

互相联系的阶段，在每⼀阶段分别对应着⼀组可供选取的决策集合；即构成过程的每个阶段都需要进

⾏⼀次决策的决策问题。将各个阶段的决策综合起来构成⼀个决策序列，称为⼀个策略。显然，由于

各个阶段选取的决策不同，对应整个过程可以有⼀系列不同的策略。当过程采取某个具体策略时，相

应可以得到⼀个确定的效果，采取不同的策略，就会得到不同的效果。多阶段的决策问题，就是要在

所有可能采取的策略中选取⼀个最优的策略，以便得到最佳的效果。动态规划（dynamic programming）同前⾯介绍过的各种优化⽅法不同，它不是⼀种算法，⽽是考察问题的⼀种途径。动态规划是⼀种求

解多阶段决策问题的系统技术，可以说它横跨整个规划领域（线性规划和⾮线性规划）。当然，由于动态规划不是⼀种特定的算法，因⽽它不象线性规划那样有⼀个标准的数学表达式和明确定义的⼀组规则，动态规划必须对具体问题进⾏具体的分析处理。在多阶段决策问题中，有些问题对阶段的划分具

有明显的时序性，动态规划的“动态”⼆字也由此⽽得名。动态规划的主要创始⼈是美国数学家贝尔

曼（Bellman）。20世纪40年代末50年代初，当时在兰德公司（Rand Corporation）从事研究⼯作的贝尔曼⾸先提出了动态规划的概念。1957年贝尔曼发表了数篇研究论⽂，并出版了他的第⼀部着作《动态规划》。该着作成为了当时唯⼀的进⼀步研究和应⽤动态规划的理论源泉。1961年贝尔曼出版了他的第⼆部着作，并于1962年同杜瑞佛思（Dreyfus）合作出版了第三部着作。在贝尔曼及其助⼿们致⼒于发展和推⼴这⼀技术的同时，其他⼀些学者也对动态规划的发展做出了重⼤的贡献，其中最值得⼀提的

第七章 动态规划方法建模

动态规划是由理查德·贝尔曼（Richard Bellman）所建立的，它是解最优化问题的一个特殊“技术”.我们这里用“技术”，是因为动态规划不是一个或一种特殊算法.

7.1 动态规划的基本概念

在生产和科学实验中，有一类活动的过程，由于它的特殊性，可将过程分为若干个互相联系的阶段，在它的每一个阶段都需要作出决策，从而使整个过程达到最好的活动效果.因此，各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展.当各个阶段决策确定后，就组成了一个决策序列，因此也就决定了整个过程的一条活动路线.这种把一个问题可看作是一个前后关联具有链状结构的多阶段过程（如图7.1）就称为多阶段决策过程，也称序贯决策过程.这种问题就称为多阶段决策问题.

在多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前的状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义.因此，把处理它的方法称为动态规划方法.但是，一些与时间没有关系的静态规划（如线性规划、非线性规划等）问题，只要人为地引进“时间”因素，也可把它视为多阶段决策问题，用动态规划方法来处理.

涉及到动态规划，总会有下面几个概念：

7.1.1 动态规划的基本概念

（１）阶段

把所给问题的过程，恰当地分为若干个相互联系的阶段，以便能按一定的次序求解.描述阶段的变量称为阶段变量，常用k表示.阶段的划分，一般是根据时间和空间的自然特征来划分，但要便于把问题的过程能转化成为多阶段决策的过程.

（２）状态

状态表示每个阶段开始所处的自然状况或客观条件，它描述了研究问题的状况，又称不可控因素.在最短路问题中，状态就是某阶段的出发位置.它既是该阶段某支路的起点，又是前一阶段某支路的终点.通常一个阶段有若干个状态（一般第一个阶段只有一个状态，它构成动态规划的递推方程的出口），每一个阶段的所有状态构成一个集合，叫做状态集合.用一个变量iS来描述在第i个阶段的状态集合上的取值，此变量iS称为状态变量（如7.2节中最短路问题中的iS，以及后面要介绍的背包问题、分割问题及设备更新问题中的参数）.

第7章 动态规划

动态规划是贝尔曼（Bellman）于20世纪50年代作为多段过程决策而提出来的，现已

在最优控制等许多领域获得广泛应用。动态规划是一种分段最优化方法，它既可用来求解约

束条件下的函数极值问题，也可用于求解约束条件下的泛函极值问题。它与极小值原理一样，

是处理控制矢量被限制在一定闭集内，求解最优控制问题的有效数学方法之一。

动态规划的核心是最优性原理，它首先将一个多段决策问题转化为一系列单段决策问

题，然后从最后一段状态开始逆向递推到初始段状态为止的一套求解最优策略的完整方法。

下面先介绍动态规划的有关基本概念，然后讨论离散型动态规划，再推广到连续型动态规划。

7.1多段决策问题及最优性原理

所谓多段决策问题，是指把一个多段决策过程按时间或空间顺序分为若干段，然后给每

一段作出“决策”，以使整个过程取得最优结果。如图7-1所示，对于中间的任意一段，例

如第k

+1段作出相应的“决策”（或控制）

ku

后，才能确定该段输入状态和输出状态间的

关系，即从

kx

处变化到

1+kx

的状态转移规律。在选择好每一段的“决策”（或控制）

ku

以

后，那么整个过程的状态转移规律从x

0经x

k一直到x

N（其中k

=1, 2,…，N

－1）也就

完全确定。全部“决策”的总体，称为“策略”。

当然，如果对每一段的决策都是按照使某种性能指标为最优的原则作出的，那么这就是

一个多段最优决策过程。显然，离散型最优控制系统的动态过程是一个多段最优决策过程的

典型例子。

容易理解，在多段决策过程中，每一段（如第1+k

段）的输出状态（

1+kx

）都仅仅与

该段的决策（

ku

）及该段的初始状态（

kx

）有关，而与前面各段的决策及状态的转移规律

无关。这种性质，称为无后效性。

动态规划是解决多段决策过程优化问题的一种强有力的工具。下面以最优路线问题为

例，来讨论动态规划求解多段决策问题。

设汽车从A城出发到B城，途中需穿越三条河流，它们各有两座桥梁P、Q可供选择

通过，如图7- 2所示。各段间的行车时间，已标注在相应段旁。问题是要选择一条行驶路