动态规划初步.docx

目录
1、 引言
2、 动态规划的基本原理




3、 动态规划解题的实际应用

\ = 12, 3 [ C3D2 + S(D2), [10 + S(D2), [10 + 2 J
S(C1)=8 且如果到达q，则下一站应到达D1 ；
S(C2)=7 且如果到达C2，则下一站应到达D2 ；
S(C3)=12 且如果到达C3，则下一站应到达D2 ；
由此，可以计算S(B.)：
I B1C1 S(B ) = min \ B C
1 [ B1C2
+ %
+ S(C2) \
+ S(C：) J
I12 +S(C1)
min <14 + S(C ) \ =
[10 + S(C：) J
12+8
min < 14 + 7 \
10 + 12
=20,
B1 t C1
s(B2)=
B2C1+ S(C1)
min < B C + S(C ) \ =
[B2C2 + S(C2) J
6 + S(C1)
min<10 +S(C )\=
[4 + S(C32) J
6+8
min < 10 + 7 \
4 + 12
=14,
B2 t C1
II B3C1 S(B ) = min < B C
3 ["
+ S(C1)
+ S(C「\ =
+ S(C：) J
13+S(C1)
min <12 + S(C ) \ =
[11 + S(C：) J
13+8
min < 12 + 7 \
11 + 12
=19,
B3 t C2
即
S(B1)=20 且如果到达B］，则下一站应到达C1 ；
S(B2)=14 且如果到达B2，则下一站应到达C1 ；
S(B3)=19 且如果到达B3，则下一站应到达C2 ；
由此，可以计算S(A)：
S(A)=
I AB1 min < AB
I 2
I AB
l 3
+ S(B1)
+ S(B2) \ =
+ S(B：) J
2 + S(B1)
min < 5 + S(B ) \ =
[1 + S(B：) J
min <
2 + 20
5 + 14
1 + 19
\ = 19,
最后，可以得到：从A到E的最短路径为At B2t C1 t D1 t E
以上计算过程及结果，，可以看到，以上方法不仅得到了从A到D的 最短路径，同时，也得到了从图中任一点到E的最短路径。
（鸟汽32如3 3
1既云D2 2
B3 11 C3 10

以上过程，仅用了 18次加法，11次比较，计算效率远高于穷举法。

由例可以看出，动态规划问题具有以下基本特征：
1、 问题具有多阶段决策的特征。阶段可以按时间划分，也可以按空间划分。
2、 每一阶段都有相应的“状态”与之对应，描述状态的量称为“状态变量”。
3、 每一阶段都面临一个决策，选择不同的决策将会导致下一阶段不同的状态，同时， 不同的决策将会导致这一阶段不同的目标函数值。
4、 每一阶段的最优解问题可以递归地归结为下一阶段各个可能状态的最优解问题，各 子问题与原问题具有完全相同的结构。能否构造这样的递推归结，是解决动态规划问题的关 键。这种递推归结的过程，称为“不变嵌入”。
为了将以上特征形式化，我们提出以下动态规划的基本概念。
阶段k:表示决策顺序的离散的量，阶段可以按时间或空间划分。
状态sk:能确定地表示决策过程当前特征的量。状态可以是数量，也可以是字符，数 量状态可以是连续的，也可以是离散的。
状态变量xk :表示每一状态可以取不同值的变量。
决策(Decision)dk :从某一状态向下一状态过度时所做的选择。决策是所在状态的函 数，记为dk(xk)。
决策允许集合Dk(xk)：在状态xk下，允许采取决策的全体。
状态转移方程xk+1=T(xk,dk)：某一状态以及该状态下的决策，与下一状态之间的函数 关系。
阶段指标函数vk(xk,dk)：从状态xk出发，选择决策dk所产生的第k阶段指标。
过程指标函数V(xk,dk,dk+1,„,dn):从状态xk出发，选择决策dk，dk+1，…,dn所产生的过
程指标。动态规划要求过程指标具有可分离性，即
V (x , d ,d ”…,d )=v (x ,d )+V _(x 2 ”…,d )
k,n k k k+ 1 n k k k k+ 1 k+ 1 k+ 1 n
称指标具有可加性，或
V (\, q,q，…,d )=v (x d )XV