f2(3) = min[6+fs(5), 8+fs(6), 7+ fs(7)) =min[22*, 23, 24 } = 22f2(4) = min[5+fs(5), 7+fs(6), 8+fs(7)) =min[21*, 22, 25 } = 21k= 1fi(1) = min[5+f(2), 9+f2(3), 7+f(4)) =min[27*,31, 28 } = 27最短路是：1→2→5→8→10
f2 (3) = min{6+f3 (5), 8+f3 (6), 7+ f3 (7)} = min{22*, 23, 24 } = 22 f2 (4) = min{5+f3 (5), 7+f3 (6), 8+f3 (7)} = min{21*, 22, 25 } = 21 k = 1 f1 (1) = min{5+f2 (2), 9+f2 (3), 7+f2 (4)} = min{27*, 31, 28 } = 27 最短路是：1 → 2 → 5 → 8 → 10
计算效率分析对有7个阶段,每个阶段有5种状态的最短路径问题,用穷举法计算要进行56=15625次加法和3124次比较，而动态规划只需105次加法和84次比较，计算效率分别提高近150和40倍
计算效率分析: 对有 7 个阶段, 每个阶段有 5 种状态的最 短路径问题, 用穷举法计算要进行 5 6 = 15625 次加法和3124 次比较, 而动态规划 只需105次加法和 84 次比较, 计算效率分 别提高近150和40倍
动态规划的无后效性原则·对任何阶段 k,有Sh+1= T (Sk,uk), Sk+1仅取决于当前状态s,和当前决策u,与k阶段前的状态和决策无关,也即,k阶段以后的发展不受该阶段以前状态的影响,过去的历史只能通过当前状态来影响今后的发展
动态规划的无后效性原则 • 对任何阶段 k, 有sk+1= T (sk , uk ), sk+1仅取 决于当前状态sk和当前决策uk , 与 k 阶段 前的状态和决策无关, 也即, k 阶段以后的 发展不受该阶段以前状态的影响, 过去的 历史只能通过当前状态来影响今后的发 展
二、动态规划的最优性原理·整个过程的最优策略应具有这样的性质：无论过去的状态和决策如何,对前面的决策所形成的状态而言，后续的诸决策必须构成最优策略；上一条成立的条件是损益递推函数严格单调
• 整个过程的最优策略应具有这样的性质: 无 论过去的状态和决策如何, 对前面的决策所 形成的状态而言, 后续的诸决策必须构成最 优策略； • 上一条成立的条件是损益递推函数严格单 调。 二、动态规划的最优性原理
在例5.1中，用标号法求解最短路线的计算公式可以概括写成：f;(ss) = 0ft(Sk)=min. (gk(Sk,uk(Sk)+fk+(uk+ (Sk+1)ukEUk(Sk)k = 4,3,2,1其中，gk在这里表示从状态 Sk到由决策 uk所决定的状态 Sk+1 之间的距离。fs(ss)=0 是边界条件，表示全过程到第四阶段终点结束
在例5.1中，用标号法求解最短路线的计算公 式可以概括写成： = = + = + + + k 4,3,2,1 f (s ) min {g (s ,u (s )) f (u (s ))} f (s ) 0 k k k k k 1 k 1 k 1 u U (s ) k k 5 5 k k k 其中，gk 在这里表示从状态 sk 到由决策 uk 所决定的状态 sk+1 之间的距离。f5 (s5 )=0 是边 界条件，表示全过程到第四阶段终点结束