文档介绍：动态规划
四会中学刘宗凡
多阶段决策过程最优化问题
在现实生活中,有一类活动的过程,由于它的特殊性,可将过程分成若干个互相联系的阶段,在它的每一阶段都需要作出决策,从而使整个过程达到最好的活动效果。因此各个阶段决策的选取不能任意确定,它依赖于当前面临的状态,又影响以后的发展。当各个阶段决策确定以后,就组成一个决策序列,因此也就确定了整个过程的一条活动路线。这种把一个问题看做是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程,这种问题称为多阶段决策最优化问题。
引子:最短路径问题
下图给出了一个地图,地图中每个顶点代表一个城市,两个城市间的连线代表道路,连线上的数值代表道路长度。
现在,我们想从城市a到达城市E。怎样走才能使得路径最短,最短路径的长度是多少?
穷举法(回溯法)
3*9*6*2=342条路径
路径增多,将呈几何级数增长
每次除了已经访问过的城市外,其他城市都要访问,所以时间复杂度为O(n!),这是一个“指数级”的算法。
在求b1到E的最短路径的时候,先求出从C2到E的最短路径;而在求从b2刭E的最短路径的时候,又求了一遍从C2刭E的最短路径。也就是说,从C2到E的最短路径求了两遍。同样可以发现,在求从Cl、C2刭E的最短路径的过程中,从Dl到E的最短路径也被求了两遍。而在整个程序中,从Dl到E的最短路径被求了四遍,这是多么大的一个浪费啊!如果在求解的过程中,同时将求得的最短路径的距离“记录在案”,以便将来随时调用,则可以避免这种重复计算。
C1
C3
D1
A
B1
B3
B2
D2
E
C2
2
5
1
12
14
10
6
10
4
13
11
12
3
9
6
5
8
10
5
2
求从A到E的最短路径问题,可以转化为三个性质完全相同,但规模较小的子问题,即分别从B1、B2、B3到E的最短路径问题。
记从Bi (i=1, 2, 3) 到E的最短路径为S(Bi),则从A到E的最短距离S(A)可以表示为:
同样,计算S(B1)又可以归结为性质完全相同,但规模更小的问题,即分别求C1,C2,C3到E的最短路径问题S(Ci) (i=1, 2, 3),而求S(Ci)又可以归结为求S(D1)和S(D2)这两个子问题。从图可以看出,在这个问题中,S(D1)和S(D2)是以知的,它们分别是:S(D1)=5,S(D2)=2
因而,可以从这两个值开始,逆向递归计算S(A)的值。
S(C1)=8 且如果到达C1,则下一站应到达D1;
S(C2)=7 且如果到达C2,则下一站应到达D2;
S(C3)=12 且如果到达C3,则下一站应到达D2;
S(B1)=20 且如果到达B1,则下一站应到达C1;
S(B2)=14 且如果到达B2,则下一站应到达C1;
S(B3)=19 且如果到达B3,则下一站应到达C2;
由此,可以计算S(A):
8
20
0
5
2
7
12
14
19
19
C1
C3
D1
A
B1
B3
B2
D2
E
C2
2
5
1
12
14
10
6
10
4
13
11
12
3
9
6
5
8
10
5
2
最后,可以得到:从A到E的最短路径为A B2 C1 D1 E。可以看到,以上方法不仅得到了从A到D的最短路径,同时,也得到了从图中任一点到E的最短路径。
动态规划的基本特征
1、问题具有多阶段决策的特征。阶段可以按时间划分,也可以按空间划分。
2、每一阶段都有相应的“状态”与之对应,描述状态的量称为“状态变量”。
3、每一阶段都面临一个决策,选择不同的决策将会导致下一阶段不同的状态,同时,不同的决策将会导致这一阶段不同的目标函数值。
4、每一阶段的最优解问题可以递归地归结为下一阶段各个可能状态的最优解问题,各子问题与原问题具有完全相同的结构。能否构造这样的递推归结,是解决动态规划问题的关键。这种递推归结的过程,称为“不变嵌入”。