第七 动态规划.ppt

文档介绍：第七章动态规划




静态处理——线性规划
动态处理——动态规划
动态规划的基本概念





:问题要作出决策的步数,用k表示。
:各阶段开始的客观条件。记作sk。
S1={A},S2={B1,B2,B3}
:第k阶段到第k+1阶段所做的选择, 用uk(sk)表示。Dk(sk)表示第k 阶段从sk出发的决策集合。
在B1处,如果选择C2,则u2(B1)=C2。 D2(B1)={C1,C2,C3}
每阶段的决策系列构成策略。
: 第k阶段到第k+1阶段的路径。
:决策的效益量度。
阶段指标函数:用d(sk,uk)表示。
过程指标函数:
最优指标函数:
找出A到E的最短路径

划分阶段
I
IV
III
II
逆序求解
f4(D1)=5,f4(D2)=2
f3(C1)=8;f3(C2)=7; f3(C3)=12