动态规划入门(论文)分析.pdf
《动态规划入门(论文)分析.pdf》由会员分享,可在线阅读,更多相关《动态规划入门(论文)分析.pdf(3页珍藏版)》请在三一文库上搜索。
1、动态规划思想入门 作者:陈喻( 2008 年 10 月 7 日) 关键字:动态规划,最优子结构,记忆化搜索 引言 动态规划 (dynamic programming)是运筹学的一个分支,是求解决策过程 (decisionprocess)最优 化的 数 学 方法 。20世纪 50年代 初 美 国 数 学家 R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优 化问题时,提出了著名的最优化原理(principle of optimality),把多阶段过程 转化为一系列单阶段问题,逐个求解,创立了解决这类过程优化问题的新方法 动态规划。 195
2、7 年出版了他的名著Dynamic Programming,这是该领 域的第一本著作。 动态规划问世以来,在经济管理、生产调度、工程技术和最优控制等方面得 到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载 等问题,用动态规划方法比用其它方法求解更为方便。 虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题,但是一些与 时间无关的静态规划 (如线性规划、非线性规划 ),只要人为地引进时间因素,把 它视为多阶段决策过程,也可以用动态规划方法方便地求解。 动态规划的基本思想 动态规划是: 将待求的问题分解成若干个相互联系的子问题,先求解子问题, 然 后从这些子问题的解得
3、到原问题的解;对于重复出现的子问题, 只在第一次遇到 的时候对它直接求解, 并把答案保存起来, 让以后再次遇到是直接引用答案,不 必从新求解,其实质是分治思想和解决冗余。 例 1:求 AB 的最短路径 图 1 这是一个利用动态规划思想的经典问题,通过直接观察图 1 我们可以枚举出 20 多条路径,并可以计算出其中最短的路径长度为16 用动态规划的思想来分析,我们可以把这个问题转换成下面这个模型 图 2 阶段:根据问题的特点和需要, 将问题按时间或空间特征分解为若干相互联系的 阶段。在本例中,我们根据空间特性将问题分成了6 个阶段。 状态: 各阶段的开始条件,本例中,A,B,CP这些节点都属于状态,表示从 该点到 B的最短路径,在这里我们计做S(i),表示从第 i个节点(状态)到 B的最 短路径 决策:某阶段状态确定后,从该状态到下阶段某状态的选择。比如S(A),它可以 选择通过 C到达B,也可以选择通过 D到达B。 状态转移方程:系统由某阶段的一个状态转变到下一阶段的另一状态称状态转 移,体现转移规律的方程称状态转移方程。在本例中,我们不难推出 S(A)=MINS(C)+4,S(D)+3,S(C)=MINS(E)+5,S(F)+3 S(B)=0,由此我 们可以得出状态转移方程(i)=MINS(j)+Vij(j为与i相邻接的节点, Vij 表示邻接 状态 决策 阶段
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 动态 规划 入门 论文 分析
链接地址:https://www.31doc.com/p-4743794.html