文档介绍：第六章 动态规划
238
203
第六章 动态规划
Chapter 6
Dynamic Programming
§
最短路径问题
。求A到E的最选择决策dk,dk+1,…,dn所产生的过程指标。动态规划要求过程指标具有可分离性，即
Vk,n(xk, dk,dk+1,…,dn)=vk(xk,dk)+Vk+1(xk+1,dk+1,…,dn)
称指标具有可加性，或
Vk,n(xk, dk,dk+1,…,dn)=vk(xk,dk)×Vk+1(xk+1,dk+1,…,dn)
第六章 动态规划
206
203
称指标具有可乘性。
最优指标函数fk(xk)：从状态xk出发，对所有的策略Pk,n，过程指标Vk,n的最优值，即
对于可加性指标函数，上式可以写为
对于可乘性指标函数，上式可以写为
以上式子称为动态规划最优指标的递推方程，是动态规划的基本方程。
终端条件：为了使以上的递推方程有递推的起点，必须要设定最优指标的终端条件，即确定最后一个状态n下最优指标fn(xn)的值。
C1
阶段5
阶段4
阶段3
阶段2
阶段1
2
5
10
8
5
6
9
3
12
11
13
4
10
6
10
14
12
1
5
2
C2
E
D2
B2
B3
B1
A
D1
C3
利用以上基本概念，。
将问题分成五个阶段，第k阶段到达的具体地点用状态变量xk表示，例如：x2=B3表示第二阶段到达位置B3，等等。这里状态变量取字符值而不是数值。
将决策定义为到达下一站所选择的路径，例如目前的状态是x2=B3，这时决策允许集合包含三个决策，它们是
第六章 动态规划
207
203
D2(x2)=D2(B3)={B3®C1, B3®C2, B3®C3}
最优指标函数fk(xk)表示从目前状态到E的最短路径。终端条件为
f5(x5)=f5(E)=0
其含义是从E到E的最短路径为0。
第四阶段的递推方程为：
从f5(x5)到f4(x4)的递推过程用下表表示：
x4
D4(x4)
x5
v4(x4,d4)
v4(x4,d4)+f5(x5)
f4(x4)
最优决策d4*
D1
D1®E
E
5
5+0=5*
5
D1®E
D2
D2®E
E
2
2+0=2*
2
D2®E
其中*表示最优值，在上表中，由于决策允许集合D4(x4)中的决策是唯一的，因此这个值就是最优值。
由此得到f4(x4)的表达式。由于这是一个离散的函数，取值用列表表示：
f4(x4) 的表达式
x4
f4(x4)
最优决策d4*
D1
5
D1®E
D2
2
D2®E
第三阶段的递推方程为：
从f4(x4)到f3(x3)的递推过程用表格表示如下：
x3
D3(x3)
x4
v3(x3,d3)
v3(x3,d3)+f4(x4)
f3(x3)
最优决策d3*
C1
C1®D1
C1®D2
D1
D2
3
9
3+5=8*
9+2=11
8
C1®D1
C2
C2®D1
C2®D2
D1
D2
6
5
6+5=11
5+2=7*
7
C2®D2
C3
C3®D1
C3®D2
D1
D2
8
10
8+5=13
10+2=12*
12
C3®D2
第六章 动态规划
208
203
由此得到f3(x3)的表达式：
x3
f3(x3)
最优决策d3*
C1
8
C1®D1
C2
7
C2®D2
C3
12
C3®D2
第二阶段的递推方程为：
从f3(x3)到f2(x2)的递推过程用表格表示如下：
x2
D2(x2)
x3
v2(x2,d2)
v2(x2,d2)+f3(x3)
f2(x2)
最优决策d2*
B1
B1®C1
B1®C2
B1®C3
C1
C2
C3
12
14
10
12+8=20*
14+7=21
10+12=22
20
B1®C1
B2
B2®C1
B2®C2
B2®C3
C1
C2
C3
6
10
4
6+8=14*
10+7=17
4+12=16
14
B2®C1
B3
B3®C1
B3®C2
B3®C3