本文共 1053 字，大约阅读时间需要 3 分钟。

动态规划的算法策略必须要从数学上的某个定理说起：

如果某个决策满足最优化，那么在这个决策的某个阶段性状态下，它的基于当前状态下的剩余决策也是最优的。

如果一个决策在任一阶段性状态下，它的基于当前状态下的剩余决策总是最优的，那么这个决策在整体上是最优的。

这里面有几个非常要注意的条件：

a：首先我们要确定我们的问题是在基于多阶段的情况下

b：问题是在多阶段下寻求某种最优的状态

c：需要验证上面定理的判定是正确的

在基于上面的数学思想建立算法的时候，每个决策阶段都是基于以前的决策进行计算的，所以每个阶段都不是相互独立的，都需要基于以前的决策进行计算，计算的过程中会多次使用以前阶段的计算结果。为了方便称呼，多次结算的阶段称为重叠子问题。最优决策的每个阶段都是基于当前状态下的剩余决策最优称为最优决策的最优子结构性质。算法的关键是通过记录最优子结构的计算结果来避免重复计算来降低算法的时间复杂度，但是由于保存最优子结构的计算结果，算法的空间复杂度在升高。而采用动态规划算法时，时间复杂度还是很不错的，不过空间会有内存溢出的危险。

基于上面的表述，我们可以得到一些相关的信息，建立我们的算法了。步骤如下：

a：建立多阶段的状态方程，刻画其基于任一状态下的决策方程（必须多阶段）

b：递归地定义最优值（生成递归算法）

c：以自底向上或者从顶到下的方式计算最优值（计算最优值）

d：根据最优值信息构造最优解（计算最优值状态下的多阶段决策）

基本模型

(1)确定问题的决策对象。 (2)对决策过程划分阶段。 (3)对各阶段确定状态变量。 (4)根据状态变量确定费用函数和目标函数。 (5)建立各阶段状态变量的转移过程，确定状态转移方程。

状态转移方程的一般形式：

f(Sk)=opt{f(Sk-i)+L[Sk-i,Ck-i]} ; 其中L[Sk-i,Ck-i]表示在状态Sk-i的情况下，剩余策略选择Ck-i时会得到最优策略Sk。

初始状态和结束状态一般情况下都是从第一步或者是第k步选取。方程可以描述从0开始构造策略，也可以从最优策略寻找初始状态，这两种方式都是可以的。

动态规划策略的要点：

1：多阶段的问题，或者多个状态构成的问题

2：在问题计算的要求上是要求某种意义上的最优

3：可以刻画基于多阶段的状态方程（最需要根据当时情况进行判断）

4：判断是否满足最优子结构的性质（根据数学上的描述）

5：写出递归函数，形成递归算法

6：计算最优值

7：计算形成最优值的每阶段选择

转载地址：http://vrpdi.baihongyu.com/