资源描述：
《第四章动态规划-PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、1第四章动态规划有许多问题，用穷举法才能得到最佳解。苦输入量n稍大一些，计算量太大，特别对渐近时间复杂性为输入量的指数函数的问题，计算机无法完成。采用动态规划（Dynamicprogramming）能得到比穷举法更有效的算法。动态规划的指导思想是，在每种情况下，列出各种可能的局部解，从局部解中挑出那些有可能产生最佳的结果而扬弃其余，从而大大缩减了计算量。2动态规划遵循的“最佳原理”简而言之，“一个最优策略的子策略总是最优的”。动态规划是运筹学的一个分支，它是解决多阶段决策过程最优化的一种方法，大约产生于50年代，由美国数学家贝尔曼（R·Bellman）等人，根据一类多阶段
2、决策问题的特点，把多阶段决策问题变换为一系列互相联系单阶段问题，然后逐个加以解决。3动态规划开始只是应用于多阶段决策性问题，后来渐渐被发展为解决离散最优化问题的有效手段，进一步应用于一些连续性问题上。然而，动态规划更像是一种思想而非算法，它没有固定的数学模型，没有固定的实现方法，其正确性也缺乏严格的理论证明。因此，一直以来动态规划的数学理论模型是一个研究的热点。4贝尔曼，RRichardBellman(1920～1984)美国数学家，美国全国科学院院士，动态规划的创始人。1920年8月26日生于美国纽约。1984年3月19日逝世。1941年在布鲁克林学院毕业，获理学士学位
3、，1943年在威斯康星大学获理学硕士学位，1946年在普林斯顿大学获博士学位。1946～1948年在普林斯顿大学任助理教授,1948～1952年在斯坦福大学任副教授,1953～1956年在美国兰德公司任研究员，1956年后在南加利福尼亚大学任数学教授、电气工程教授和医学教授。 贝尔曼因提出动态规划而获美国数学会和美国工程数学与应用数学会联合颁发的第一届维纳奖金（1970），卡内基－梅隆大学颁发的第一届迪克森奖金(1970)，美国管理科学研究会和美国运筹学会联合颁发的诺伊曼理论奖金(1976)。1977年贝尔曼当选为美国艺术与科学研究院院士和美国工程科学院院士。5贝尔曼
4、因在研究多段决策过程中提出动态规划而闻名于世。1957年他的专著《动态规划》出版后，被迅速译成俄文、日文、德文和法文，对控制理论界和数学界有深远影响。贝尔曼还把不变嵌入原理应用于理论物理和数学分析方面，把两点边值问题化为初值问题，简化了问题的分析和求解过程。1955年后贝尔曼开始研究算法、计算机仿真和人工智能，把建模与仿真等数学方法应用到工程、经济、社会和医学等方面，取得许多成就。贝尔曼对稳定性的矩阵理论、时滞系统、自适应控制过程、分岔理论、微分和积分不等式等方面都有过贡献。 贝尔曼曾是《数学分析与应用杂志》及《数学生物科学杂志》的主编，《科学与工程中的数学》丛书的主
5、编。已出版30本著作和7本专著，发表了600多篇研究论文。第一节单源最短路问题891.1引言101112第二节矩阵连乘问题穷举搜索法是容易想到的解法，算法列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，由此找出一种所需乘次数最少的计算次序。然而这样做计算量太大。131415第三节资源分配问题某公司有资金4百万元向A、B、C三个项目追加投资，各个项目可以有不同的投资额（以百万元为单位），相应的效益值如下表，问怎样分配资金，使总效益值最大？16171819第四节非线性规划第五节多机系统的可靠性设计第六节背包问题第七节流水作业车间调度应用一：图像压缩图象的变
6、位压缩存储格式将所给的象素点序列{p1,p2,…,pn},0≤pi≤255分割成m个连续段S1,S2,…,Sm。第i个象素段Si中(1≤i≤m)，有l[i]个象素,且该段中每个象素都只用b[i]位表示。设则第i个象素段Si为设，则hib[i]8。因此需要用3位表示b[i],如果限制1l[i]255，则需要用8位表示l[i]。因此，第i个象素段所需的存储空间为l[i]*b[i]+11位。按此格式存储象素序列{p1,p2,…,pn}，需要位的存储空间。图象压缩问题要求确定象素序列{p1,p2,…,pn}的最优分段，使得依此分段所需的存储空间最少。每个分段的长度不超过2
7、56位。图像压缩设l[i]，b[i]，是{p1,p2,…,pn}的最优分段。显而易见，l[1]，b[1]是{p1,…,pl[1]}的最优分段，且l[i]，b[i]，是{pl[1]+1,…,pn}的最优分段。即图象压缩问题满足最优子结构性质。设s[i]，1≤i≤n，是象素序列{p1,…,pn}的最优分段所需的存储位数。由最优子结构性质易知：其中算法复杂度分析：由于算法compress中对k的循环次数不超这256，故对每一个确定的i，可在时间O(1)内完成的计算。因此整个算法所需的计算时间为O(n)。应用二：电路布线在一块电路板的
