第二节 最优化原理与动态规划PPT讲稿.ppt
《第二节 最优化原理与动态规划PPT讲稿.ppt》由会员分享,可在线阅读,更多相关《第二节 最优化原理与动态规划PPT讲稿.ppt(32页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第二节第二节 最优化原理与动态最优化原理与动态规划规划第1页,共32页,编辑于2022年,星期二一、动态规划方法导引一、动态规划方法导引 1.1.全全枚枚举举法法或或穷穷举举法法。共共有有18条条可可能能路路线线,进进行行比较,求得最优路线比较,求得最优路线Q A3 B1 C1T。QTA1A2A3B1B2B3C1C224374642442514633334第2页,共32页,编辑于2022年,星期二2.“.“局局部部最最优优路路径径”法法:选选择择当当前前最最短短途途径径,“逢近便走逢近便走”。所所取取决决策策必必是是Q A1 B2 C2T,全全程程长长度度是是13。QTA1A2A3B1B2B3
2、C1C224374642442514633334第3页,共32页,编辑于2022年,星期二全枚举法全枚举法计算工作量将会十分庞大。计算工作量将会十分庞大。局部最优求出的解不一定是最优解。局部最优求出的解不一定是最优解。第4页,共32页,编辑于2022年,星期二3.动态规划方法就是从终点逐段向始点方向寻找最短路线的方法。解题步骤如下:把问题划分为几个阶段。按阶段顺序首先考虑最后阶段如第四阶段的最优决策,也就是走哪条路线最短。按阶段顺序依次考虑第三、第二,第一阶段的最优决策,为此只需确定每一阶段上各初始点的最优决策即可。第5页,共32页,编辑于2022年,星期二用动态规划方法逐段求解时,每个阶段上
3、的求优方法基本相同,而且比较简单,每一阶段的计算都要利用上一阶段的计算结果,因而减少了很多计算量。阶段数愈多,这种效果愈明显。第6页,共32页,编辑于2022年,星期二二、动态规划解题二、动态规划解题 标号法标号法:最短路径:最短路径:Q A3 B1 C1TQTA1A2A3B1B2B3C1C224374642442514633334阶段阶段1阶段阶段2阶段阶段3阶段阶段40,T3,T4,T4,C17,C26,C111,B1,B28,B18,B111,A3 第7页,共32页,编辑于2022年,星期二三、动态规划的基本概念。三、动态规划的基本概念。1.阶段阶段(stage)和阶段变量。和阶段变量。
4、把所给问把所给问题恰当地划分为题恰当地划分为若干个相互联系又有区别若干个相互联系又有区别的子问的子问题,称之为多段决策问题的题,称之为多段决策问题的阶段阶段。QTA1A2A3B1B2B3C1C224374642442514633334第8页,共32页,编辑于2022年,星期二用以描述阶段的变量叫作用以描述阶段的变量叫作阶段变量阶段变量,一般以,一般以k表示阶段量表示阶段量阶段数阶段数k的编号法有两种:的编号法有两种:(1)(1)顺序编号;顺序编号;(2)(2)逆序编号法。逆序编号法。QTA1A2A3B1B2B3C1C224374642442514633334第9页,共32页,编辑于2022年,
5、星期二2.状态状态(state)、状态变量和可能状态集、状态变量和可能状态集(1)状态与状态变量。状态与状态变量。QTA1A2A3B1B2B3C1C224374642442514633334第10页,共32页,编辑于2022年,星期二(2)动态规划维数动态规划维数。(3)可能状态集:可能状态集:用用S(sk)表示。表示。QTA1A2A3B1B2B3C1C224374642442514633334第11页,共32页,编辑于2022年,星期二3.3.决策决策(decision)、决策变量和允许决策集合、决策变量和允许决策集合(1)决策决策。QTA1A2A3B1B2B3C1C224374642442
6、514633334第12页,共32页,编辑于2022年,星期二(2)决策变量决策变量:xk=xk(sk)决决策策变变量量xk(sk)的的允允许许决决策策集集用用Dk(sk)表表示示,xk(sk)Dk(sk)允许决策集合实际是决策的约束条件。允许决策集合实际是决策的约束条件。QTA1A2A3B1B2B3C1C224374642442514633334第13页,共32页,编辑于2022年,星期二4.策略和允许策略集合策略和允许策略集合策略策略(Policy)全过程策略全过程策略指具有指具有n个阶段全部过程,个阶段全部过程,简称策略简称策略。表示为表示为 x1(s1),x2(s1),xn(sn)。k
7、后后部子过程策略部子过程策略,表示为表示为pk(xk)QTA1A2A3B1B2B3C1C224374642442514633334第14页,共32页,编辑于2022年,星期二(2)允许策略集合允许策略集合记作记作P。最优策略最优策略:从允许策略集中,找出的具有最优从允许策略集中,找出的具有最优效果的策略。效果的策略。QTA1A2A3B1B2B3C1C224374642442514633334第15页,共32页,编辑于2022年,星期二5.状态转移方程状态转移方程(状态转移律状态转移律):多阶段决策过程的发展:多阶段决策过程的发展就是用就是用阶段状态的相继演变阶段状态的相继演变来描述的。来描述的
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第二节 最优化原理与动态规划PPT讲稿 第二 优化 原理 动态 规划 PPT 讲稿
限制150内