文档介绍：第十章动态规划§1 多阶段决策过程最优化问题举例§2 基本概念、基本方程与最优化原理§3 动态规划的应用(1) §4 动态规划的应用(2) §1 多阶段决策过程最优化问题举例例1 最短路径问题下图表示从起点 A到终点 E之间各点的距离。求 A到E的最短路径。 B A C BD B CD E C 4 123 123 12 32 2164724 83 86756 1 10 6 4 3751 §1 多阶段决策过程最优化问题举例用穷举法的计算量:如果从 A到E的站点有 k个,除 A、E之外每站有 3个位置则总共有 3 k-1×2条路径; 计算各路径长度总共要进行(k+1) 3 k-1×2次加法以及 3 k- 1× 2-1 次比较。随着 k 的值增加时,需要进行的加法和比较的次数将迅速增加; 例如当 k=20 时,加法次数为 ×10 15次, 比较 ×10 14次。若用 1亿次/秒的计算机计算需要约 508 天。§1 多阶段决策过程最优化问题举例讨论: 1、以上求从 A到E的最短路径问题,可以转化为四个性质完全相同,但规模较小的子问题,即分别从 D i、C i、B i、A到E的最短路径问题。第四阶段:两个始点 D 1和D 2,终点只有一个; 表 10-1 分析得知:从 D 1和D 2到E的最短路径唯一。 EE E 本阶段最优终点(最优决策) 10* 6 本阶段各终点(决策) 10 6 到E的最短距离 D 1 D 2本阶段始点(状态) 阶段 4 第三阶段:有三个始点 C 1,C 2,C 3,终点有 D 1,D 2,对始点和终点进行分析和讨论分别求 C 1,C 2,C 3到D 1,D 2的最短路径问题: 表 10-2 分析得知:如果经过 C 1,则最短路为 C 1 -D 2 -E; 如果经过 C 2,则最短路为 C 2 -D 2 -E; 如果经过 C 3,则最短路为 C 3 -D 1 -E。§1 多阶段决策过程最优化问题举例 6+6=12 5+6=11 6+6=12 D 2 D 1D 2 D 2 D 1本阶段最优终点(最优决策) 8+10=18 7+10=17 1+10=11 本阶段各终点(决策) 12 11 11 到E的最短距离 C 1 C 2 C 3本阶段始点(状态) 阶段 3 第二阶段:有 4个始点 B 1,B 2,B 3,B 4,终点有 C 1,C 2,C 3。对始点和终点进行分析和讨论分别求 B 1,B 2,B 3,B 4到C 1,C 2,C 3的最短路径问题: 表 10-3 分析得知:如果经过 B 1,则走 B 1 -C 2 -D 2 -E; 如果经过 B 2,则走 B 2 -C 3 -D 1 -E; 如果经过 B 3,则走 B 3 -C 3 -D 1 -E; 如果经过 B 4,则走 B 4 -C 3 -D 1 -E。§1 多阶段决策过程最优化问题举例 6+11=17 2+11=13 3+11=14 1+11=12 C 3 1+11=12 7+11=18 8+11=19 5+11=16 C 2 C 1C 2 C 3 C 3 C 3 本阶段最优终点(最优决策) 2+12=14 4+12=16 4+12=16 7+12=19 本阶段各终点(决策) 12 13 14 12 到E的最短距离 B 1 B 2 B 3 B 4 本阶段始点(状态) 阶段 2 第一阶段:只有 1个始点 A,终点有 B 1,B 2,B 3,B 4。对始点和终点进行分析和讨论分别求 A到B 1,B 2,B 3,B 4的最短路径问题: 表 10-4 最后,可以得到:从 A到E的最短路径为 A B 4 C 3 D 1 E §1 多阶段决策过程最优化问题举例 2+12=14 B 4 3+14=17 B 3 3+13=16 B 2 B 1C 2本阶段最优终点(最优决策) 4+12=16 本阶段各终点(决策) 12 到E的最短距离 A 本阶段始点(状态) 阶段 1 以上计算过程及结果