登录以参加训练计划

动态规划

动态规划程序设计是解最优化问题的一种途径、一种方法，而不是一种特殊算法。

不像前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。

动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。

因此我们在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。

我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论，逐渐学会并掌握这一设计方法。

第一节 动态规划的基本模型

一、多阶段决策过程的最优化问题

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

例1 最短路径问题

给出一个地图（如下），地图中的每个顶点代表一个城市，两个城市间的一条连线代表道路，连线上的数值代表道路的长度。现在想从城市A到达城市E，怎样走路程最短？最短路程的长度是多少？

【算法分析】

从点A到点E的最短路径问题，可以通过将整个过程划分为多个阶段来解决。这里，我们将A到E的过程分为四个阶段，并使用阶段变量K来表示这些阶段。具体分析如下：

【分析过程】

1. 将A到E的全过程分成四个阶段，阶段变量K。
2. 第1阶段有一个初始状态A，有两个选择的支路：A-B1 和 A-B2。
3. 第2阶段有两个初始状态B1和B2，B1有三条可供选择的支路，B2有两条可供选择的支路。

使用 DK(Xk, Xk+1) 表示在第K阶段由初始状态Xk到下一阶段的初始状态Xk+1的路径距离，FK(X) 表示从第K阶段的X到终点E的最短距离。利用倒推的方法求解A到E的最短距离。

【具体计算过程】

S1: K=4

[ F4(D1)=3, \quad F4(D2)=4, \quad F4(D3)=31 ]

S2: K=3

[ F3(C1) = \min(D3(C1, D1) + F4(D1), D3(C1, D2) + F4(D2)) ] [ = \min(5 + 3, 6 + 4) = 8 ]

[ F3(C2) = D3(C2, D1) + F4(D1) = 5 + 3 = 8 ]

[ F3(C3) = D3(C3, D3) + F4(D3) = 8 + 3 = 11 ]

[ F3(C4) = D3(C4, D3) + F4(D3) = 3 + 3 = 6 ]

S3: K=2

[ F2(B1) = \min(D2(B1, C1) + F3(C1), D2(B1, C2) + F3(C2), D2(B1, C3) + F3(C3)) ] [ = \min(1 + 8, 6 + 8, 3 + 11) = 9 ]

[ F2(B2) = \min(D2(B2, C2) + F3(C2), D2(B2, C4) + F3(C4)) ] [ = \min(8 + 8, 4 + 6) = 10 ]

S4: K=1

[ F1(A) = \min(D1(A, B1) + F2(B1), D1(A, B2) + F2(B2)) ] [ = \min(5 + 9, 3 + 10) = 13 ]

因此，由A点到E点的全过程最短路径为 A→B2→C4→D3→E，最短路程长度为13。

从以上过程可以看出，每个阶段中，都求出了本阶段的各个初始状态到终点E的最短距离。当逆序倒推到过程起点A时，便得到了全过程的最短路径和最短距离。

二、动态规划的基本概念

1. 阶段和阶段变量 用动态规划求解一个问题时，需要将问题的全过程恰当地分成若干个相互联系的阶段，以便按一定的次序去求解。描述阶段的变量称为阶段变量，通常用k表示。阶段的划分一般是根据时间和空间的自然特征来划分，同时阶段的划分要便于把问题转化为多阶段决策过程。如例9.1中，可将其划分为4个阶段，即 k=1, 2, 3, 4。

在上述的多阶段决策问题中，各个阶段采取的决策一般来说是与阶段有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，因此有“动态”的含义。我们称这种解决多阶段决策最优化的过程为动态规划程序设计方法。