动态规划的范例

动态规划是解决多阶段决策过程最优化问题的一种方法，而多阶段决策过程是指其活动过程可以按照时间进程分为若干相互联系的阶段，在每个阶段决策者都要进行决策，全部阶段的决策组成了一个决策序列。多阶段决策过程最优化问题的目标是要整个活动过程的总目标达到最优。由于每个阶段的决策都将影响到下一阶段的决策，甚至影响总目标，所以，决策者在每阶段决策时，不能只考虑本阶段最优，还需考虑对总目标的影响，从而作出使总目标达到最优的决策。

本质上，动态规划是一个递推方程，把问题的各阶段联系起来，保证每个阶段的最优可行解对于整个问题是可行的、也是最优的。动态规划的计算递推进行，以便让一个子问题的最优解作为下一个子问题的输入，当最后一个子问题求解完成，也就得到了整个问题的最优解。相比于线性规划和非线性规划方法，动态规划通过把一个多变量问题分解成若干个阶段，每个阶段是一个单变量（或少变量）的子问题，以求出这个多变量问题的最优解。这种分解的好处是每个阶段的优化问题涉及变量少，从计算上来说比同时处理多个变量更加简单。这种方法可用于解决最优路径问题、资源分配问题、生产计划与库存、投资、装载、排序等问题。下面通过一个最短路径问题介绍一下运用动态规划求解多阶段决策过程问题的思路和方法。

例4-1一位旅行者准备从A地前往H地，图4-1给出了从A地到H地所有可能的路径，B地至G地表示这些路径途中需要经过的城市，城市之间的数字表示两地之间的距离（百公里），请帮助旅行者选择一条最短路径。

图4-1　最短路问题

分析 在每个连续阶段选择最短路径，从而挑选出一条从A地到H地的路径，例如，A→D→G→H路经为15百公里。但是，采用这种方法得到的路径未必是最短路径，如A→D→F→H的路经是13百公里，要比15百公里更短些。由此可见，有时牺牲某一阶段的一点利益可能会在以后得到的更多。

对于这类问题，也可以用枚举法列出从A地到H地的所有路径，通过对比找出最短路径。但是，对于大的网络来说，采用枚举法的计算量将会大得难以处理。

下面采用动态规划来求解这个问题。首先，将这个问题分解成3个阶段，见图4-2。

图4-2　最短路问题

确定最短路径的一般思路是，从第一阶段开始，对每个阶段的所有终止点，计算出从起点到该阶段各终止点的最短距离，然后利用这些最短距离计算从起点到下一阶段所有终止点的最短距离，直至原问题的终止点。由于问题求解过程与活动发展进程顺序一致，所以将这种解法称为顺序解法。还有一种解法，其问题求解过程与活动发展进程顺序相反，将这种解法称为逆序解法。逆序解法将在后面介绍。

阶段1有三个终点，B地、C地和D地。各点距离A地只有一条路径。于是有：

从A地到B地的最短距离=5（百公里） （从A地出发）

从A地到C地的最短距离=4（百公里） （从A地出发）

从A地到D地的最短距离=3（百公里） （从A地出发）

阶段2有三个终点，E地、F地和G地。先考虑E地。从图4-2可以看出，E地可以经过B地或者C地2条不同路径到达。利用上一阶段得到的结果（从A地分别到达B地和C地的最短距离），再加上B地和C地分别到达E地的距离，就能确定出从A地到达E地的最短距离为：

由上可知，从A地出发到达E地，途中经C地的距离最短。

类似的，F地可以经过B地和D到达。因此有：

因此，从A地出发到达F地，途中经D地的距离最短。而G地可以经过B地、C地或D地到达，因此有：

从A地出发到达G地，途中经D地的距离最短。因此，在阶段2有：

从A地到E地的最短距离=8（百公里） （从C地出发）

从A地到F地的最短距离=8（百公里） （从D地出发）

从A地到G地的最短距离=6（百公里） （从D地出发）

阶段3只有一个终点H地。H地可以经过E地、F地或者G地3条不同路径到达。利用上一阶段得到的结果（从A地分别到达E地F地和G地的最短距离），再加上分别从E地、F地和G地到达H地的距离。于是有：

由上可知，从A地出发到达H地，途中经F地的距离最短。因此，在阶段3有：

从A地到H地的最短距离=13（百公里） （从F地出发）

由此可知，从A地到H地的最短距离是13百公里。为了得到最优路径，可以根据求解结果从后向前逆推，阶段3从F地出发到达H地，阶段2从D地出发到达F地，阶段1从A地出发到达D地，即最短路径为A→ D→F→H。

通过这个例子，可以看出动态规划方法的基本特性：

（1）计算从A地到当前阶段各终点的最短距离时，需要用到上一阶段的计算结果；

（2）每个阶段所做的计算都是该阶段可行路径的函数。

上面用顺序解法从阶段1到阶段3从前向后逐步计算，这个例子也可以用逆序解法从阶段3到阶段1从后向前逐步计算。无论是采用顺序解法，还是采用逆序解法，得到的解都是相同的。顺序解法较符合逻辑，但在动态规划文献中普遍采用逆序解法。逆序解法的求解思路与顺序解法刚好相反，从最后一个阶段开始，对每个阶段的所有起点，计算出该阶段所有起点至终点的最短距离，然后利用这些最短距离计算下一阶段所有起点至终点的最短距离，直至第一阶段。下面用逆序解法来求解例4-1。

阶段3有3个起点，从E地、F地和G地出发分别只有1条路径至H地。因此，阶段3的结果可归结为：

从E地到H地的最短距离=6（百公里） （连接至H地）

从F地到H地的最短距离=5（百公里） （连接至H地）

从G地到H地的最短距离=9（百公里） （连接至H地）

阶段2有3个起点，B地、C地和D地。先考虑B地，从图4-2可以看出，B地可以经过E地、F地或者G地3条不同路径到达H地，即利用从B地出发分别到达E地、F地和G地的距离再加上从E地、F地和G地出发至H地的最短距离，就能确定出从B地发到达H地的最短距离为：

由上可知，从B地出发到达H地，途中经F地的距离最短。类似的，C地可以经过E地或者G地2条不同路径到达H地。因此有：

因此，从C地出发到达H地，途中经E地的距离最短。最后，D地可以经过F地或者G地2条不同路径到达H地。于是有：

由上可知，从D地出发到达H地，途中经F地的距离最短。因此，在阶段2有：

从B地到H地的最短距离=9（百公里） （连接至F地）

从C地到H地的最短距离=10（百公里） （连接至E地）

从D地到H地的最短距离=10（百公里） （连接至F地）

阶段1只有一个起点，A地可以经过B地、C地或D地3条不同路径到达H地。利用从A地出发分别到达B地、C地和D地的距离再加上从B地、C地和D地出发至H地的最短距离，就能确定从A地出发到达H地的最短距离为：

因此，在阶段1有：

从A地到H地的最短距离=13（百公里） （连接至D地）

阶段1的结果表示从A地到H地的最短距离为13百公里，其最优解表示从A地出发至D地，阶段2的最优解表示从D地出发至F地，阶段3的最优解表示从F地出发至H地，即最短路径为A→D→F→ H，这个结果与顺序解法得到的最短路径是一样的。