第四章动态规划.ppt

文档介绍：1
第四章动态规划
有许多问题,用穷举法才能得到最佳解。苦输入量n稍大一些,计算量太大,特别对渐近时间复杂性为输入量的指数函数的问题,计算机无法完成。采用动态规划(Dynamic programming)能得到比穷举法更有效的算法。动态规划的指导思想是,在每种情况下,列出各种可能的局部解,从局部解中挑出那些有可能产生最佳的结果而扬弃其余,从而大大缩减了计算量。
2
动态规划遵循的“最佳原理”简而言之,“一个最优策略的子策略总是最优的”。动态规划是运筹学的一个分支,它是解决多阶段决策过程最优化的一种方法,大约产生于50年代,由美国数学家贝尔曼(R·Bellman)等人,根据一类多阶段决策问题的特点,把多阶段决策问题变换为一系列互相联系单阶段问题,然后逐个加以解决。
3
动态规划开始只是应用于多阶段决策性问题,后来渐渐被发展为解决离散最优化问题的有效手段,进一步应用于一些连续性问题上。然而,动态规划更像是一种思想而非算法,它没有固定的数学模型,没有固定的实现方法,其正确性也缺乏严格的理论证明。因此,一直以来动态规划的数学理论模型是一个研究的热点。
4
贝尔曼,R Richard Bellman (1920~1984) 美国数学家,美国全国科学院院士,动态规划的创始人。1920年8月26日生于美国纽约。1984年3月19日逝世。1941年在布鲁克林学院毕业,获理学士学位,1943年在威斯康星大学获理学硕士学位,1946年在普林斯顿大学获博士学位。1946~1948年在普林斯顿大学任助理教授,1948~1952年在斯坦福大学任副教授,1953~1956年在美国兰德公司任研究员,1956年后在南加利福尼亚大学任数学教授、电气工程教授和医学教授。 贝尔曼因提出动态规划而获美国数学会和美国工程数学与应用数学会联合颁发的第一届维纳奖金(1970),卡内基-梅隆大学颁发的第一届迪克森奖金(1970),美国管理科学研究会和美国运筹学会联合颁发的诺伊曼理论奖金(1976)。1977年贝尔曼当选为美国艺术与科学研究院院士和美国工程科学院院士。
5
贝尔曼因在研究多段决策过程中提出动态规划而闻名于世。1957年他的专著《动态规划》出版后,被迅速译成俄文、日文、德文和法文,对控制理论界和数学界有深远影响。贝尔曼还把不变嵌入原理应用于理论物理和数学分析方面,把两点边值问题化为初值问题,简化了问题的分析和求解过程。1955年后贝尔曼开始研究算法、计算机仿真和人工智能,把建模与仿真等数学方法应用到工程、经济、社会和医学等方面,取得许多成就。贝尔曼对稳定性的矩阵理论、时滞系统、自适应控制过程、分岔理论、微分和积分不等式等方面都有过贡献。 贝尔曼曾是《数学分析与应用杂志》及《数学生物科学杂志》的主编,《科学与工程中的数学》丛书的主编。已出版30本著作和7本专著,发表了600多篇研究论文。
第一节单源最短路问题
9
引言
10