主要内容主要内容:7.17.1多阶段决策问题多阶段决策问题7.2 7.2 动态规划的基本概念和基本原理动态规划的基本概念和基本原理7.3 7.3 动态规划应用举例动态规划应用举例第第 七七 章章 动动 态态 规规 划划例例 求解最短路问题 分阶段的最短路径 ： C1T 3 - : B1C1T 4 - ：A2B1C1T 7 - -： QA2B1C1T 11 Q-A3B1C1T 11 Q-A3B2C2T 11最短路径 34476117811最短路径解的特点 1、可以将全过程求解分为若干阶段求解；-多阶段决策问题多阶段决策问题 2、在全过程最短路径中，将会出现阶段的最优路径；-递推性递推性 3、前面的终点确定，后面的路径也就确定了，且与前面的路径（如何找到的这个终点）无关；-无后效性无后效性 3、逐段地求解最优路径，势必会找到一个全过程最优路径。-动态规划动态规划7.17.1多阶段决策问题多阶段决策问题 动态规划是解决多阶段最优决策的方法, 由美国数学家贝尔曼(R. Bellman) 于 1951年首先提出; 1957年贝尔曼发表动态规划方面的第一部专著“动态规划”, 标志着运筹学的一 个新
