第十二讲   动态规划

（教材： 第十二章   动态规划）

 1 2(本页) 3 4

三. 动态规划解题的简单例子

要通过简单例子理解动态规划解决问题的过程和步骤。

教材中的例：用动态规划方法求下图中从 到 的最短路。

（1） 划分阶段： 从 向 方向每前进一步我们称为一个阶段。从图中可见， 整个问题分成 5 个阶段。

（2） 确定状态变量：每个阶段开始时处于一个村镇，把第 个阶段开始时所在的村镇记为 ，称为第  个阶段的状态变量。 只可取 ； 可以取 、 或 ； 可以取 、 或 。每个阶段要选择下一步布线走向，称为该阶段的决策，记为 。例如当 时， 可以取 、 ；当 时， 可以取 、 或 。

（3） 确定状态转移规律：每个阶段开始时处于一个村镇 ，经过选择后将到达另一个村镇，这个村镇也就是下一个阶段开始时所处的村镇 。  和 以及 的关系按它们的含义可以写成：

。

上述方程的意义是：由上一个阶段的状态和上一阶段的决策可以确定下一个阶段的状态。

（4） 确定直接指标和最优后部过程指标： 的最优后部过程指标 就是从 到 的最短路径。直接指标是指该阶段所作决策的指标，当第 阶段的状态变量为   、所作的决策（即下一个村镇）为 时，直接指标就是村镇  与村镇 之间的距离 。

（5）确定最优后部过程指标的递推方程：对每一个阶段的每一种状态 ，它到 的最短路径 可以表示为一个递推方程：

上述 min 是对在状态 下所有可能的决策取的。上面大括号中的公式的意义：在状态 下，采取一个决策到下一个状态 ，其直接费用是 ，到了状态 后再沿着从 到 的最短路径到达 ，这个决策所化的代价是大括号中的公式。而从在状态 下所有可能的决策中选择最小者就是从状态  到 的最短路径 。为简便计，我们研究下面的例子。

〔例1〕求图中从 到 的最短路：

我们把例子中的各种量列成表格：

注解

 1 2(本页) 3 4