第八章 动态规划 §1多阶段决策最优化问题举例 §2 基本概念、基本方程与最优化原理 §3 离散确定性动态规划求解 §41 离散随机性动态规划求解 §5一般数学规划模型的动态规划解法 2025/4/6
2025/4/6 2 第八章 动态规划 §1 多阶段决策最优化问题举例 §2 基本概念、基本方程与最优化原理 §3 离散确定性动态规划求解 §4 离散随机性动态规划求解 §5 一般数学规划模型的动态规划解法
§1 多阶段快策过程最优化问题举例 例1最短路径问题 下图表示从起点A到终点E之间各点的距离。求A到E的 最 短路径。 4 6 D 10 4 7 3 7 A B 2 E 2 2 D 2 6 6 3 3 3 5 B 2025/4/6
2025/4/6 3 §1 多阶段决策过程最优化问题举例 例1 最短路径问题 下图表示从起点A到终点E之间各点的距离。求A到E的 最 短路径。 A B B C D B C D E C 4 1 2 3 1 2 3 1 2 3 2 2 1 6 4 7 2 4 8 3 8 6 7 5 6 1 10 6 4 3 7 5 1
用穷举法的计算量： 如果从A到E的站点有k个，除A、E之外每站有3个位置则 总共有3k-1×2条路径： 计算各路径长度总共要进行(k+1)3k-1×2次加法以及 3k-1×2-1次比较。随着k的值增加时，需要进行的加法和比较 的次数将迅速增加； 例如当k=20时，加法次数为4.2550833966227×1015 次，比较1.3726075472977×1014次。若用1亿次/秒的计 算机计算需要约508天。 2025/4/6
2025/4/6 4 用穷举法的计算量: 如果从A到E的站点有k个，除A、E之外每站有3个位置则 总共有3 k-1×2条路径； 计算各路径长度总共要进行 (k+1) 3k-1×2次加法以及 3 k-1×2-1次比较。随着 k 的值增加时，需要进行的加法和比较 的次数将迅速增加； 例如当 k=20时，加法次数为 4.2550833966227×1015 次，比较 1.3726075472977×1014 次。若用1亿次/秒的计 算机计算需要约508天
局部最优不一定全局最优 如：本例中D-E的最短 2025/4/6
局部最优不一定全局最优 如:本例中D-E的最短 2025/4/6
动态规划的解题思路 把多(n)阶段的决策问题转化为求个具有递推 关系的单阶段决策问题 ■这些单阶段决策具有相似的性质. ■此例中考虑A到E的最短距离，可分为四个阶段 ,A到B,C,D,E ■每个阶段所处的状态，如：B有B1,B2,. ■考虑由此状态下，到E的最短距 ■逆序求解，先考虑D到E,再考虑C到E. ▣具有递推关系 2025/4/6
动态规划的解题思路 ◼ 把多(n)阶段的决策问题转化为求n个具有递推 关系的单阶段决策问题. ◼ 这些单阶段决策具有相似的性质. ◼ 此例中考虑A到E的最短距离,可分为四个阶段 ,A到B,C,D,E. ◼ 每个阶段所处的状态, 如: B 有B1,B2,. ◼ 考虑由此状态下,到E的最短距 ◼ 逆序求解,先考虑Di到E,再考虑Ci到E. ◼ 具有递推关系 2025/4/6