* 1运筹学OPERATIONS RESEARCH* 2第八章 动态规划1多阶段决策最优化问题举例2基本概念、基本方程与最优化原理3离散确定性动态规划求解4离散随机性动态规划求解5一般数学规划模型的动态规划解法* 31多阶段决策过程最优化问题举例例1 最短路径问题 下图表示从起点A到终点E之间各点的距离。求A到E的最短路径。BACBDBCDEC4123123123221647248386756110637 51* 4用穷举法的计算量: 如果从A到E的站点有k个，除A、E之外每站有3个位置则总共有3k-12条路径； 计算各路径长度总共要进行 (k+1) 3k-12次加法以及3k-12-1次比较。随着 k 的值增加时，需要进行的加法和比较的次数将迅速增加； 例如当 k=20时，加法次数为 4.25508339662271015 次，比较 1.37260754729771014 次。若用1亿次/秒的计算机计算需要约508天。* 5讨论： 1、求从A到E的最短路径问题，可以转化为四个性质完全相同，但规模较小的子问题，即分别从Di 、Ci、Bi、A到E的最短路径问题。 第四阶段：两个始点D1和D
