去。得到第k阶段的动态规划数学模型中目标函数优值的表达式为: f:(s)=min(d, (sk, xx)+f& ( skD) (6-5) 公式(6-5)中令x(s)=S4,特别是(6-5)中当k=n时,(最后一个阶段),因 为f(sn)=0,所以规定: x f (s,)=mind, (s,,x (6-6) 上面这个利用了第k阶段与k+1阶段之间递推关系的数学模型(6-5)称为动态规划 的递推公式或函数基本方程 6.3动态规划的求解方法 6.3.1动态规划递推公式的迭代解法 这个解法就是利用递推公式(6-5)直接求解,举例说明如下: 例6.3试用公式(6-5)求解§6.1例1种网络最短路线问题(图6-2) 解:先按建立模型的要求,确定阶段、状态、决策。将问题划分为四个阶段,状态 变量即为各阶段的始点。第一阶段的状态为A;第二阶段的状态为B1,B2;第三阶段 的状态为C1,C2;第四阶段的状态为D,D2。则所有状态均具有无后效性且能列举出 来。每阶段的决策允许集合与§6.2中建立公式(6-5)时所述一致,在此从略。反映第 k阶段与第k+1阶段的状态转移方程sA=84(s4,x4)可由示意图中点的推移过程反映 出这种函数关系,不一定非要表达成数学形式。最后,用于计算的递推公式便是(6-5) 迭代过程如下: k=4时,考虑点D1,D2分别到终点E的最短距离(s4),此时各有一条路D1→E 及D,→E,又因为k=4为最后一个阶段,所以由公式(6-6) S(D)=mind(D, E))=min 8)=8 f(D2)=mn{4(D2E)}=min9}=9 则D1到E的最短路线是8,路线为D1→E,对D2,也有x4(D2)=E k=3时,考虑从点C1,C2,C3到终点E的最短距离f(S),对点C1到E可经过D1 或D2两点,由公式(6-5) f3C)=min(4(C1,D1)+D)d3(C1,D2)+f4(D2)}=min{3+86+9}=11 即点C1到E的最短距离为11,最短路线为C1→D1→E,C1的决策为x3(C1)=D1。 同理,对点C2有去。得到第k 阶段的动态规划数学模型中目标函数优值的表达式为： = 1 k E ) C1 1 f k ( ) sk = min{dk (sk , xk ) + f k+1 (sk+1 )} （6-5） k = 1,2,"",n 公式（6-5）中令 xk ( ) sk = sk+1 ，特别是（6-5）中当k = n 时，（最后一个阶段），因 为 f n+1 ( ) sn+1 0，所以规定： f n (sn ) = min{dn (sn , xn )} （6-6） 上面这个利用了第 阶段与 阶段之间递推关系的数学模型（6-5）称为动态规划 的递推公式或函数基本方程。 k k +1 6.3 动态规划的求解方法 6.3.1 动态规划递推公式的迭代解法 这个解法就是利用递推公式（6-5）直接求解，举例说明如下： 例 6.3 试用公式（6-5）求解§6.1 例 1 种网络最短路线问题（图 6-2）。 解：先按建立模型的要求，确定阶段、状态、决策。将问题划分为四个阶段，状态 变量即为各阶段的始点。第一阶段的状态为 ；第二阶段的状态为 ， ；第三阶段 的状态为 ，C ；第四阶段的状态为 ，D 。则所有状态均具有无后效性且能列举出 来。每阶段的决策允许集合与§6.2 中建立公式（6-5）时所述一致，在此从略。反映第 阶段与第 阶段的状态转移方程 A 2 ( gk B1 B2 C 2 +1 D1 k k s , ) 1 k k = s x + 可由示意图中点的推移过程反映 出这种函数关系，不一定非要表达成数学形式。最后，用于计算的递推公式便是（6-5）。 迭代过程如下： k = 4 时,考虑点 D1，D2 分别到终点 E 的最短距离 ，此时各有一条路 及 ，又因为 为最后一个阶段，所以由公式（6-6） ( ) 4 4 f s D1 → E D2 → E k = 4 ( ) min{ ( , )} min{8} 8 f 4 D1 = d4 D1 E = = ( ) min{ ( , )} min{9} 9 f 4 D2 = d4 D2 E = = 则 D1到 的最短路线是 8，路线为 D1 → E ，对 D2 ，也有 x4 (D2 ) = E 。 k = 3时，考虑从点C1，C2 ，C3到终点 E 的最短距离 f 3 (s3 ) ，对点C1到 E 可经过 或 两点，由公式（6-5） D1 D2 f3 ( = min{d3 ( ) C1 , D1 + f 4 (D1 ),d3 (C1 , D2 ) + f 4 (D2 )} = min{3 + 8,6 + 9} = 11 即点C 到 E 的最短距离为 11，最短路线为C1 → D1 → E ，C1的决策为 3 1 1 x (C ) = D 。 同理，对点C2 有