动态规划.ppt
《动态规划.ppt》由会员分享,可在线阅读,更多相关《动态规划.ppt(25页珍藏版)》请在三一文库上搜索。
1、,1.5 动态规划,动态规划是一类多阶段决策过程的最优化方法。 基本方法是:按阶段把一个大问题化成一系列相互有联系的子问题,建立相应的递推公式,解一系列的子问题,最后求得整个问题的最优解。,例 最短路问题,一、动态规划的基本概念和基本方法,7,11,7,8,4,6,3,4,0,11,1,2,3,4,阶段,从A到E的路有:,求A到E的最短路。,4,5,7,8,9,10,12,13,1. 概念, 阶段:,根据时间或空间划分。, 状态:,某阶段出发的位置。,既是某支路本阶段的起点,又是前一阶段的终点。,本例按空间分成4个阶段,本例4个阶段的状态集:, 状态变量 sk :,描述状态的变量。,#, 决策
2、:,从给定状态到下一阶段某状态的选择。, 决策变量 xk=xk(sk):,描述决策的变量。,如:,有:, 状态转移方程:描述状态转移规律的函数关系, 策略:决策序列,2,4,如:,本例共有18个策略,欲从中选出最优策略(路长最短者)。, k 子策略:,策略中,从第k个决策开始到最后一个决策所成之子序列。,如:, 报酬函数: 一决策对应的“费用”,记为,如:,2,5, 目标(指标)函数:衡量策略好坏的函数。,从 出发到终点的目标函数记为:,视 为确定状态, 是变化的。, 从 出发到终点的最优目标值:,相应的策略为所求的最优策略 最短路。,对应的策略为 到终点最优子策略。,2,6,2. 最优化原理
3、,例中:有最优策略,即,A到E的最短路,路长为,子策略:, B2到E的最短路,路长为, C1到E的最短路,路长为,2,7,#,最优策略有性质最优化原理:,无论过去的状态和决策如何,对某确定的状态,余下的决策必须构成最优子策略。,或,对某状态而言,该状态到终点的最优策略只与后面的选择有关,与前面的选择无关。,或,已知现在,将来与过去无关。,即后部子问题的最优策略是父问题的最优子策略。,2,8,#,利用该原理得寻优方法:,子问题:,先求出“最小子问题”中,各状态到E的最优子策略,,将问题化成一系列相互有联系的子问题,,再求出“次小子问题”中(第3阶段),各状态到 E的最优子策略,如此向前推进,而每
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 动态 规划
链接地址:https://www.31doc.com/p-3128855.html