算法设计与分析4-5.pdf

动态规划 (Dynamic Programming) 基本思想和使用条件基本思想和使用条件 动态规划算法的设计步骤动态规划算法的设计步骤 应用实例应用实例 小结 1 基本思想和使用条件基本思想和使用条件 例1 求从始点到终点的最短路径 d,15 d,11 SS1 66 dd,99 33 BB1 99 uu,22 22 TT1 u,13 4 A1 4 u,5 3 C1 5 SS2 7 uu,88 33 BB22 66 dd,33 4 TT2 d,10 5 A2 2 u,7 4 C2 3 SS3 4 dd,66 33 BB3 22 uu,77 7 TT3 d,11 9 A3 1 d,5 1 C3 7 SS4 4 u,7 2 BB4 4 u,1 1 TT4 u,10 3 A4 5 u,4 3 C4 6 S5 BB5 T5 2 基基 本本 思思 想想 解解：：判断序列判断序列 F (C ) min{C T ) l l m m ( ) min{ ( )} F Bk Bk Cl +F Cl l F (A ) min{A B +F (B )} jj jj k k kk F (S ) min{S A +F (A )} i i j j j 任何最短路径的子路径都是相对于子路径任何最短路径的子路径都是相对于子路径 的始点和终点的最短路径 为找到一条最短路径只需从T 开始进行多 j 步判断步判断 3 使用条件使用条件－－优化原则优化原则 一个最优决策序列的任何子序列本身一定是相对于 子序列的初始和结束状态的最优的决策序列 例2 求总长模10的最小路径 d,1 2 u,6 2 u,4 2 u,2 2 S T 5 5 5 5 最优解最优解：下下、下下、下下、下下 动态规划求解：下、上、