文档介绍：第11章 动态规划
2011-12-13 6A-017
1
2
图1
D
A
G
C
K
B
N
P
O
M
J
F
H
E
L
I
3
1
2
3
4
5
2
1
4
3
2
3
1
4
2
2
1
2
2
2
3
3
4
4
阶段1
阶段2
阶段3
阶段4
阶段5
任务：
P是出发点，从P到A，求最短路径（图1）
3
思路
先看第5阶段，到达A点有两条路
B A，需要2km
C A，需要3km B 2 A P(A)
令 P(B) 3
从P A的最短路径为P(A)； C
从P B的最短路径为P(B)； P(C)
从P C的最短路径为P(C) …… 5阶段
P(A) = min{P(B)+2, P(C)+3}；
P(B) = min{P(D)+1, P(E)+2}；
P(C) = min{P(E)+5, P(F)+4}；
4
P(A) = min{P(B)+2, P(C)+3}；
P(B) = min{P(D)+1, P(E)+2}；
P(C) = min{P(E)+5, P(F)+4}；
P(D) D 1 B 2 A
2 3
5
P(B) E C
4 P(C)
P(E) F P(F)
5
P(N) = 2;
P(O) = 3;
上述递推公式告诉我们，要求P(A)需要先求出阶段5中的P(B)和P(C)；要求 P(B) (或者P(C)），又要先求出阶段4中的 P(D) 和 P(E) (或P(F)和P(E))……
显然，要依照上述递推过程求解，需要倒过来，从P(P)出发，先求出第一阶段的P(O)和P(N)，再求第二阶段的P(K)，P(L)，P(M)；……，最后得到P(A)。
…
6
选择数据结构，将每条路经的长度存在数组中。
东西方向上的道路长度存在两维数组h[4][3]中规定数组的第一维为行号，第二维为列号。
3
1
2
3
4
5
2
1
4
3
2
3
h[4][3] = { {3,2,3}, {2,1,4}, {3,4,5}, {3,1,2} };
0
1
2
1
0
2
3
7
南北方向上道路长度存至数组v[3][4]中，也规定第一维为行号，第二维为列号。
0
1
2
3
2
1
0
2
2
3
4
4
1
2
4
1
2
2
3
v[3][4] = {{2, 2, 3, 4},{4, 1, 2, 4},{1, 2, 2, 3}};
8
为了计算方便，使地图更好地与二维数组对应，下面将图1改为图2
h[3][0]
h[3][1]
h[3][2]
h[2][0]
h[2][1]
h[2][2]
h[1][0]
h[1][1]
h[1][2]
h[0][0]
h[0][1]
h[0][2]
v[2][0]
v[2][1]
v[2][2]
v[2][3]
v[1][0]
v[1][1]
v[1][2]
v[1][3]
v[0][0]
v[0][1]
v[0][2]
v[0][3]
(3, 3)
0
2
1
3
2
1
3
y
x
图2
9
求解过程为从(0, 0)到(3, 3)求最短路径问题
定义二维数组，P[4][4]={{0,0,0,0},{0,0,0,0},{0,0,0,0},{0,0,0,0}},
第一维为行，第二维为列。这时：
P(O)为P[0][1]；P(N)为P[1][0]；…P(A)为P[3][3]，以下为分阶段递推求解过程。
对于阶段1:
P[0][0] = 0;
P[0][1] = P[0][0]+h[0][0