a d~9 5 3 e、12 g 5 6 C 图42
1 2 3 4 图 4-2 6 8 4 7 12 4 4 1 a d b e h t g c f s 3 4 11 3 6 9 5 5 3
问题可归结为四阶段决策问题,用动 态规划方法求解如下: (解法一)分步计算法 (从第4阶段开始) ①当k=4时,ih或g,j=t;f(t)=0 若i=h,则 f:(h)=mmn+/()}=cm+/f(0)=5+0,(h)=t
问题可归结为四阶段决策问题，用动 态规划方法求解如下： （解法一）分步计算法 （从第4阶段开始） ①当k=4时，i=h或g，j=t；f5 (t)=0 若i=h，则 f h c f j c f t j h t i j h t j t = + = + = + = = ( ) min ( ) ( ) 5 0, ( ) * 4 5 5 4
若=g,则 f(g)=m+/()}=cm+/(0)=3+0=0./=t ②当k=3时,i=d或e;jh或g 若=d则 f()=-mh+1()}=mnm h, g Icas +f(gi 9+5 min =11,j3(a)=g 8+3
当k=3时，i=d或e,f；j=h或g f g c f j c f t j t i j g t j t = + = + = + = = = * 4 5 5 4 ( ) min ( ) ( ) 3 0 0, j d g c f g c f h f d c f j d g d h i j j h g = = + + = + + = + = = 11, ( ) 8 3 9 5 min ( ) ( ) ( ) min ( ) min * 3 4 4 4 , 3 若i=g，则 若i=d,则
若i=e,则 Ceh +fi(h) f,(e)=min ci+ f())=min h J=n, g Ice +f8) 7+5 min 12. 3(e)=h 2+3 若i=千则 f3()=mimn+()}=c+f4(g) J=8 5+3=8,j3()=g
若i=e,则 j e h c f g c f h f e c f j eg eh i j j h g = = + + = + + = + = = 12, ( ) 12 3 7 5 min ( ) ( ) ( ) min ( ) min * 3 4 4 4 , 3 若i=f,则 j f g f f ci j f j cf g f g j g = + = = = + = + = 5 3 8, ( ) ( ) min ( ) ( ) * 3 3 4 4
③当k=2时,i=a或b,c;j=d或e,f; 若=a,则 +f3(d f2(a)=min cu+f(i)=min +f( 3+11 min =12;j2(a)=f 4+8
当k=2时，i=a或b，c；j=d或e，f； 若i=a，则 j a f c f f c f d f a c f j a f a d i j j d f = = + + = + + = + = = 12; ( ) 4 8 3 11 min ( ) ( ) ( ) min ( ) min * 2 3 3 3 , 2