文档介绍：10 动态规划
1
免费机票旅游加拿大
西 东
2
多种解法
单向搜索
双向搜索
动态规划
3
图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）
4
思路
先看第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}；
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}；
P(D) D 1 B 2 A
2 3
5
P(B) E C
4 P(C)
P(E) F P(F)
6
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)。
…
7
选择数据结构，将每条路经的长度存在数组中。
东西方向上的道路长度存在两维数组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
8
南北方向上道路长度存至数组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}};
9
为了计算方便，将图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
10