在阶段2：S 2 可以取 B 1 , B 2 中任意一个，对应的有
f2(B 1 ) m in d d ((B B 1 1 ,,C C 2 1 ) ) ff1 1 ( (C C 1 2 )) m in 6 5 8 5 1 1
f2(B 2)m in d d ((B B 2 2 ,,C C 2 1) ) ff1 1( (C C 1 2 )) m in 9 8 8 5 1 4
1 最短路径问题
1 最短路径问题
【例1】设在E城的某公司要从S城运送一批
货物，两城之间有公路相连（见图 1(a)），
其中
A i( i 1 ,2 ,3 ) ,B j(j 1 ,2 ) ,C l( l 1 ,2 )
是可以供选择的途经站点，各点连线上的数
字表示相邻站点间的距离。现在的问题是选择
一条由S到E的路径，使得所经过的路径最短。
(b)
1 最短路径问题

在任一阶段开始时所处的位置称为状态变量，
在阶段k的状态变量记为 ，例S k 如 为S 3阶
段3的状态变量，可以取为
A1, A2 , A3中任
意一个。
当某一个状态给定后，需要做出决策以确定下
一步的状态，描述决策的变量称为决策变量，
在阶段k的决策变量记为 X k 。例如在阶段2的
变量为 X k ( S k ) 时点 S k 与 X k ( S k ) 间的距离；记 f k ( S k )
为在阶段k由点 S k 到终点E的最短路径的长度。本例
中要求的是 f 4 ( S ) 。 在阶段1：S 1 可以取 C 1 , C 2 中任意一个，对应的有
f1(C 1)5,f1(C 2)8
1 最短路径问题
当段数很多时，枚举法的计算量将极其庞大。
现在换个思路，寻找由S到E的最短路径。先
把最短路径问题所考虑的过程分为4个阶段：
由S到 Ai(i 1,2,3) 为第1阶段；
由 Ai(i 1,2,3) 到Bj ( j 1,2)
为第2阶段；
由 Bj ( j 1,2) 到Cl (l 1,2)
为第3阶段；
动态规划方法
动态规划（Dynamic Programming）同前 面介绍过的线性规划方法不同，它不是一种算法，而 是考察问题的一种途径。动态规划是一种求解多阶段 决策问题的系统技术。由于动态规划不是一种特定的 算法，因而它不像线性规划那样有一个标准的数学表 达式和明确定义的一组规则，动态规划必须对具体问 题进行具体的分析处理。动态规划在自然科学和社会 科学等各个领域都有着广泛的应用，并且获得了显著 的效果。
由 Cl (l 1,2) 到E为第4阶段。
1 最短路径问题
我们称由某点到终点的阶段数k为阶段变量，
如由Cl(l 1,2) 到E的阶段数为1（这时记由C到
E的阶段数为1，它与第1阶段是不同的概念），
由
Bj(到j E1,2的) 阶段数为2（这时记由B到
E的阶段数为2），等等。可见阶段变量的取
值正好与实际进行的阶段相反（图（b））。
这一名著。本章将简要介绍动态 规划的思想方法及其应用。
——动态规划解决问题的基本思路是：把整体比 较复杂的大问题划分成一系列较易于解决的小问 题，通过逐个求解，最终取得整体最优解。这种 “分而治之，逐步调整”的方法，在一些比较难 以解决的复杂问题中已经显示出优越性。
——所谓多阶段决策过程是指这样一类活 动过程：一个决策过程可以分为若干个相 互联系的阶段，每个阶段都需要作一定的 决策，但是每个阶段最优决策的选择不能 只是孤立地考虑本阶段所取得的效果如何， 必须把整个过程中的各个阶段联系起来考 虑，要求所选择的各个阶段决策的集合— —策略，能使整个过程的总效果达到最优。
状态取 S2 B2 时的决策变量记为 X 2 ( B 2 ) ，X 2 ( B 2 ) 可取为 C 1 , C 2 。若 X2(B2)C2 ，则表示由 B 2 到 C 2 ，从而决定了下一步的状态是C 2 。
1 最短路径问题
为了寻找由起点S到E终点的最短路径，我
们考察前面用枚举法找到的第1条最短路径：
动态规划
1 最短路径问题 2 贝尔曼最优化原理 3 WinQSB软件应用
动态规划是解决多阶段决策问题 的一种方法. 1951年，美国数学 家贝尔曼（R.Bellman， 1920～1984）研究了一类多阶
段决策问题的特征，提出了解决
这类问题的基本原理。在研究、 解决了某些实际问题的基础上， 他于1957年出版了《动态规划》
1 最短路径问题
从 B 1 出发到终点E最短路径为“B1C1E ”，
决策变量 X2*(B1) C1 ；
从B 2 出发到终点E最短路径为“B2C1E ”，
决策变量 X2*(B2)C1 ； 在阶段3：S 3 可以取 A1, A2, A3 中任意一个， 对应的有
f3 (A 1 ) m in d d ( (A A 1 1 ,,B B 2 1 ) ) ff2 2 ( (B B 1 2 ) ) m in 5 6 1 1 4 1 1 7 ; f3 (A 2 ) m in d d ( (A A 2 2 ,,B B 2 1 ) ) ff2 2 ( (B B 1 2 ) ) m in 6 8 1 1 4 1 1 9 ; f3 (A 3 ) m in d d ( (A A 3 3 ,,B B 2 1 ) ) ff2 2 ( (B B 1 2 ) ) m in 4 7 1 1 4 1 1 8
S A 1 B 1 C 1 E
容易看出：子路径“A 1 B 1 C 1 E ” 也应
是从A 1 出发到终点E的所有路径中最短的一条。
这个现象启发我们从阶段1开始，逐段逆向地
求出各点到终点E的最短路径，最后求得由起 点S到终点E的最短路径，这就是动态规划的
基本思想。
1 最短路径问题
以 d(Sk,Xk(Sk)) 表示在阶段k的状态变量为 S k 、决策
1 最短路径问题
(a) (b)
1 最短路径问题
分析：如果用枚举法，将有12条不同的路
径，每条路径对应一个由S到E的路径距离，
其中最小值所对应的路径即为最短路径。本 问题的最短路径有3条，路程均为21个单位：
第1条：S A 1 B 1 C 1 E 第2条：S A 3 B 1 C 1 E 第3条：S A 3 B 2 C 1 E