动态规划是运筹学的一个分支。与其说动态规划是一种算法，不如说是一种思维方法来得更贴切。因
为动态规划没有固定的框架，即便是应用到同一道题上，也可以建立多种形式的求解算法。
第七章 动 态 规 划
第一讲 概念及最短路问题
动态规划（Dynamic Programming）是20世纪50年代由美国数学家贝尔曼（Richard Bellman）及他的学生们一同建立和发展起来的一种解多阶段决策问题的优化方法。
所谓多阶段决策问题是指一类活动过程。它可按时间或空间把问题分为若干个相互联系的阶段。在每一阶段都要作出选择（决策），这个决策不仅仅决定这一阶段的效益，而且决定下一阶段的初始状态，从而决定整个过程的走向（从而称为动态规划）。每当一阶段的决策一一确定之后，就得到一个决策序列，称为策略。所谓多阶段决策问题就是求一个策略，使各个阶段的效益总和达到最优。
先声明：下面研究的解决多阶段的决策问题的最优化的称之为动态规划的数学方法，仅仅是一种解决问题的思路，而不是一种算法。这一点与线性规划不同。线性规划是一种算法。
下面从一典型的例子去说明动态规划的基本思想与原理：
某地要从A向F地铺设一条输油管道，各点间连线上的数字表示距离。问应选择什么路线，可是总距离最短？
C1 5 2 8 D1 4 3 3 B1 5 C2 4 6 E 1 4
5 6 A D2 8 3 2 F C3 5 7 1 3
E2 4 B2 8 D 3 3 7 4
C4 第一阶段 第二阶段 第三阶段 第四阶段 第五阶段
图7-1 先引入几个符号与概念：
（1） 阶段与阶段变量：先把问题从中间站B，C，D，E用空间位置分成5个阶段，阶段用阶段变量k来描述，k=1,表示第一阶段，k=2表示第二阶段，?
（2） 状态与状态变量：每一阶段的左端点（初始条件）集合称为本阶段的状态（即开始的客观条件，或称阶段初态）。如第三阶段有四个状态S3 =｛C1 ,C2，C3，C4｝, 第四阶段有三个状态 S4=｛D1, D2 , D3｝, ?
描述过程状态的变量称为状态变量：用小写s1 ,s2 ,s3 ?表示第一，第二，第三?阶段的状态变量。当处在状态C2时，我们可记
1
s3= C2
正像离散型R.V“X=2”代表一事件一样。
(3) 决策与决策变量：如当处于C2状态时，下一步怎么走？如何选择路线？即如何决策。是走向D1，还是走向D2？当过程处于某一阶段的某一状态时，可以作出不同的决策（或选择），从而确定下一阶段的状态，这种决定（或选择）叫决策。如选择D2，记
u3（C2）= D2
说，当处于C2状态时，下一步的决策为D2。
其中uk(sk)表示第k阶段当状态处于sk时的决策变量。
一般地，用Dk(sk)表示第k阶段从状态sk出发的允许决策集合。如
D3(C2)=｛D1 ，D2｝
显然，uk(sk)∈Dk(sk)。
（4）策略与最优策略：每一阶段产生一个决策，5个阶段的决策就构成一个决策序列： u1(s1)，u2(s2)，u3(s3)，u4(s4)，u5(s5)
称为一策略。所谓策略是指按一定的顺序排列的决策组成的集合，也称决策序列。 这里的最短路径成为最优策略。
动态规划就是在允许策略集中选最优策略。
（5）状态转移方程：是描述由第k阶段到第k+1阶段状态转移规律的关系式。
sk?1=Tk(sk,uk) 上例中状态转移方程为： sk?1=uk(sk)
（6）指标函数与最优指标函数：用于衡量所选定策略优劣的数量指标称为指标函数。相当于动态的目标函数，最后一个阶段的目标函数就是总的目标函数。它分阶段指标函数和过程指标函数。阶段指标函数是指第k阶段，从状态sk出发，采用决策uk时的效益，用
dk(sk,uk)表示。最优指标函数是指从第k阶段状态sk采用最优策略到过程终止时的最佳
效益值，用fk(sk)表示。
例如：d（C2, D1）是指由C2出发，下一阶段的决策是D1的两点间的距离。即 d（C2, D1）=4。f2(B1)表示从B1到F的最短距离。 整个问题即为f1(A)=？
1． 逆序递推法：
倒退着从F向A走，每倒退一步，思想上问自己：“从现在出发，退向何处？到F的距离最短？”我们分5步来解决问题：
（1） k=5时
2
下求f5(s5)=？此时状态集S5=｛E1，E2｝，故分情况讨论，先说f5(E1)=？若最佳路径从A出发通过E1的话，由 E1到终点F的最短距离为
f5(E1)=5
?同理，f5(E2)=3。 （只有唯一的选择）故最优决策为：u5(E1)=F，u5(E2)=F
?（2） k=2时 下求f4(s4) =？由于S4=｛D1, D2 , D3｝，下分四种情况进行讨论：
f?d4(D1,E1)?f5(E1)??4(D1)=min ?d(D,E)?f(E)?= min
?3?4??41252??5?3??=7, f?d4(D2,E1)?f5(E1)??4(D2)=min ??d?= min
?6?4?4(D2,E2)?f5(E2)??2?3??=5, f?d4(D3,E1)?f5(E1)??1?44(D3)=min ??d(D(E?= min
??43,E2)?f52)??3?3??=5, (3) k=3时 S3 =｛C1 ,C2，C3，C4｝,
f(C??d3(C1,D1)?f4(D1)??31)=min ?d?5?7?3(C1,D2)?f?= min
4(D2)??8?5??=12, 同理，f(C， u?32)=103(C2)= D2. f?3(C3)=8， u3(C3)= D2. f， u?3(C4)=93(C4)= D3.
（4）k=4时 S2=｛B1, B2｝
??d2(B1,C1)?f3(C1)??fBdf??2?12?2(1)=min ?2(B1,C2)?3(C2)?= min
??3?10??=13, ?d2(B1,C3)?f3(C3)????6?8??同理，f u?2(B2)=15， 2(B2)= C3.
（5）k=1时， S1=｛A｝
f?d1(A,B1)?f2(B1)???4?13?1(A)=min ??d?= min
1(A,B2)?f2(B2)??5?15??=17, 再按计算顺序的反推可得最优策略：
u??1(A)= B1. u2(B= C2. u?(C?1)32)= D2. u4(D2)= E2. 从而得最优路径：
A—B1 —C2 — D2—E2 —F
u?4(D1)= E1. u?4(D2)= E2. u?4(D3)= E1. u?3(C1)= D1. u?2(B1)= C2. u?1(A)= B1. u?5(E2)= F. 3
最短距离为
f1(A)=17。
由上面的过程可以看出，在求解的各个阶段利用了第k段和第k+1段的如下关系：
?fk(sk)?min?dk(sk,uk)?fk?1(sk?1)}k?5,4,3,2,1(7.3a)uk ?f(s)?0(7.3b)?66这种递推关系称为动态规划的基本方程。（7.3b）式称为边界条件。 2． 逆向标号法
每退到一站，看终点F，找最短路径及最短路径的距离，标号。画路径。
（12）
C1 5 2 （7） 8 （13） （10） 4 D1 3 （4） 3 B1 5 C2 4 （17 ） 6 5 E 1 4
（5） （ 8 ） 6 A D2 8 3 2 3 ） F （C3 15 5 （ ） 7 1 3
E2 5） 4 （ B2 （ 9 ） 8 D 3 3 7 4
C4 图 7-2 此时的（？）？=最优指标函数值f. 得最优路径：
A—B1 —C2 — D2—E2 —F 总距离为 17. 3． 顺序递推法：
此法类似于逆序递推法。从起点A向终点F倒退。
（1）k=1时，f0(A)=0，此为初始条件。退向允许决策集S1=｛B1, B2 ｝此时退向B1时看
起点A，最短距离为f1(B1)=4，此时路径（或最优决策）是唯一的：u1(B1)=A；记
??f1(B2)?5?f1(B1)?4，同理， ?????u1(B2)?A?u1(B1)?A（2）k=2时，直接用递推式：
?f2(C1)?d(B1,C1)?f1(B1)?2?4?6 ??u(C)?B211? 4
???f2(C2)?min??d(B1,C2)?f1(B1)??3?4???d(B??min?2,C2)?f1(B2)??8?5???7
?u?2(C2)?B1???f2(C3)?min??d(B1,C3)?f1(B1)??6?4??d(B2,C3)?f??min????101(B2)??7?5?
?u?2(C3)?B1??f2(C4)?d(B2,C4)?f1(B2)?7?5?12?u?C 2(4)?B2（3）k=3时。
???d(?fC1,D1)?f2(C1)??5?3(D1)?min???min?6????d(C2,D1)?f2(C2)??4?7??11
?u?3(D1)?C?1,u3(D1)?C2类似的
??f3(D2)?12?u?(D)， ?f3(D3)?14?32?C2?u?3(D3)?C 3同理，
??f4(E1)?14?f4(?u? ， ?E2)?144(E1)?D1?u? 4(E2)?D2最后
??f5(F)?17?u?
5(F)?E2逆推最优策略：A—B1 —C2 — D2—E2 —F。 与前相同。 全部计算情况如图7-3
（6）
C1 5 2 （11） （ 4 ） 8 3 （7） 4 D1 3 （14） B1 4 C 2 5 6 5 （ 12 ） E 1 4 A （ 10 ） 6 （ 17 ） 3 D8 2 2 （ ） F 5 （ 5 ） C7 3 14 1 3 14E 2 B 4 （ ） 2 （ 12 ） 8 D 3 3 7 4 C 4
5