文档介绍：动态规划完整
例 求解最短路问题
Ⅰ
Ⅱ
Ⅲ
Ⅳ
分阶段的最短途径
Ⅳ ： C1—T 3
Ⅲ --Ⅳ : B1—C1—T 4
Ⅱ--Ⅲ-过程，由依次进行的 n 个阶段决策构成的决策序列，简称策略，表示为 。从 k 阶段到第 n 阶段，依次进行的阶段决策构成的决策序列称为 k 部子策略,表示为 ，显然当 k=1时的 k 部子策略就是全过程策略。
(5) 状态转移方程
状态转移确定从一个状态到另一个状态的转移过程, 由状态转移方程描绘: sk+1 = T (sk, xk);
状态转移方程在大多数情况下可以由数学公式表达, 如: sk+1 = sk + xk；
(6) 指标函数
用来衡量策略或子策略或决策的效果的某种数量指标，就称为指标函数。它是定义在全过程或各子过程或各阶段上确实定数量函数。对不同问题，指标函数可以是诸如费用、本钱、产值、利润、产量、耗量、间隔 、时间、效用，等等。
用vk(sk , xk)表示第 k 段处于状态 sk且所作决策为 xk 时的指标，那么它就是第 k 段指标函数，简记为vk 。
用f(sk , xk)表示第k子过程的指标函数。表示处于第 k 段 sk 状态且所作决策为xk时，从 sk 点到终点的间隔 。由此可见， f(sk , xk)不仅跟当前状态 sk 有关，
〔2〕过程指标函数〔也称目的函数〕
〔1〕阶段指标函数〔也称阶段效应〕
还跟该子过程策略 pk(sk) 有关,严格说来，应表示为 fk(sk , pk(sk)) 。它是由各阶段的阶段指标函数 vk(sk , xk)累积形成的，对于 k 部子过程的指标函数可以表示为：
式中，表示某种运算，可以是加、减、、乘、除、开方等．
多阶段决策问题中，常见的目的函数形式之一是取各阶段效应之和的形式，即:
有些问题，如系统可靠性问题，其目的函数是取各阶段效应的连乘积形式，
(7) 最优解
用 fk* (sk) 表示第 k 子过程指标函数Fk(sk , pk(sk))在状态 sk 下的最优值，即:
称 fk(sk) 为第 k 子过程上的最优指标函数；与它相应的子策略 pk(sk) 称为状态 sk 下的最优子策略，记为 pk*(sk)
例 用动态规划求解最短路问题
最短路的求解:
阶段: 可分为4个阶段, k = 1, ..., 4。
状态: 可用城市编号, S1={Q}, S2={A1,A2,A3}, S3={B1,B2,B3}, S4={C1,C2}, S5={T}
决策: 决策变量也可用城市编号;
状态转移方程: sk+1= xk;
阶段指标函数：
过程指标〔阶段递推〕函数:
k = 4
f4 (C1) = 3, f4 (C2) = 4
k = 3
f3(B1)=min{1+f4(C1)=4*, 4+f4(C2)=8}=4
f3(B2)=min{6+f4(C1)=9, 3+f4(C2)=7*}=7
f3(B3)=min{3+f4(C1)=6*, 3+f4(C2)=7}=6
k = 2
f2(A1) = min{7+ f3(B1), 4+ f3(B2), 6+ f3(B3) } = min{11*, 11*, 12} = 11
f2(A2) = min{3+ f3(B1), 2+ f3(B2), 4+ f3(B3) } = min{7*, 9, 10 } = 7
f2(A3) = min{4+ f3(B1), 1+ f3(B2), 5+ f3(B3) } = = min{8*, 8*, 11 } = 8
k = 1
f1(Q) = min{2+f2(A1), 4+f2(A2), 3+f2(A3)} = min{13, 11*, 11* } = 11
最短路是：Q A2 B1 C1 T，p={A2,B1,C1,T}
Q A3 B1 C1 T ，p={A3,B1,C1,T}
Q A3 B2 C2 T ，p={A3,B2,C2,T}
整个过程的最优策略应具有这样的性质: 无论过去的状态和决策如何, 对前面的决策所形成的状态而言, 后续的诸决策必须构成最优策略；
上一条成立的条件是阶段递推函数严格单调。
二、动态规划的最优性原理
在例题中，求解最短道路的计算公式