算法设计动态规划概要.pptx
《算法设计动态规划概要.pptx》由会员分享,可在线阅读,更多相关《算法设计动态规划概要.pptx(45页珍藏版)》请在咨信网上搜索。
1、算法设计及其应用算法设计及其应用第六章:动态规划算法(国际大学生程序设计竞赛辅导教程)(国际大学生程序设计竞赛例题解(三))动态规划概述l运筹学运筹学(Operations Research)是系统工程最是系统工程最重要的理论基础之一重要的理论基础之一,运筹学所研究的问题可运筹学所研究的问题可简单地归结为简单地归结为:“依照给定条件和目标依照给定条件和目标,从众多从众多方案中选择最佳方案方案中选择最佳方案.”而动态规划是运筹学的而动态规划是运筹学的重要分支之一重要分支之一,它是解决多阶段决策过程最优它是解决多阶段决策过程最优化的一种方法化的一种方法.动态规划概述l动态规划简单的来说就是:采用分
2、治的策略把动态规划简单的来说就是:采用分治的策略把求最优解问题分解为求若干个子问题的最优解,求最优解问题分解为求若干个子问题的最优解,子问题也递归的分解为子问题的组合,通过递子问题也递归的分解为子问题的组合,通过递归递推等方法,把原问题最优解与局部子问题归递推等方法,把原问题最优解与局部子问题最优解联系起来,以求最后的解。这些局部子最优解联系起来,以求最后的解。这些局部子问题之间可能有重叠,就是某个子问题可能需问题之间可能有重叠,就是某个子问题可能需要求解多次,因此需要将子问题及其解记录下要求解多次,因此需要将子问题及其解记录下来,这样对每个子问题只需求解一次,从而提来,这样对每个子问题只需求
3、解一次,从而提高了效率。高了效率。动态规划概述l一般来说,寻找最优解的算法都具有指一般来说,寻找最优解的算法都具有指数时间的复杂度,因此算法的优化显得数时间的复杂度,因此算法的优化显得十分重要;但是有一类特殊的最优化问十分重要;但是有一类特殊的最优化问题,我们通常可以找到具有多项式时间题,我们通常可以找到具有多项式时间的复杂度的算法,这种方法就是我们下的复杂度的算法,这种方法就是我们下面要介绍的动态规划。面要介绍的动态规划。动态规划的常用名词l(1)状态状态(state)对于一个问题,所有可能到达的情况(包括初始情况对于一个问题,所有可能到达的情况(包括初始情况和目标情况)都称为这个问题的一个
4、状态。和目标情况)都称为这个问题的一个状态。l(2)状态变量状态变量(sk)对每个状态对每个状态k关联一个状态变量关联一个状态变量sk,它的值表示状态,它的值表示状态k所对应的问题的当前解值。所对应的问题的当前解值。l(3)决策决策(decision)决策是一种选择,对于每一个状态而言,你都可以选决策是一种选择,对于每一个状态而言,你都可以选择某一种路线或方法,从而到达下一个状态。择某一种路线或方法,从而到达下一个状态。动态规划的常用名词l(4)决策变量决策变量(dk)在状态在状态k下的决策变量下的决策变量dk的值表示对状态的值表示对状态k当当前所做出的决策。前所做出的决策。l(5)策略策略策
5、略是一个决策的集合,在我们解决问题的时策略是一个决策的集合,在我们解决问题的时候,我们将一系列决策记录下来,就是一个策候,我们将一系列决策记录下来,就是一个策略,其中满足某些最优条件的策略称之为最优略,其中满足某些最优条件的策略称之为最优策略。策略。动态规划的常用名词l(6)状态转移函数状态转移函数(t)从一个状态到另一个状态,可以依据一定的规则来前从一个状态到另一个状态,可以依据一定的规则来前进。我们用一个函数进。我们用一个函数t来描述这样的规则,它将状态来描述这样的规则,它将状态i和决策变量和决策变量di映射到另一个状态映射到另一个状态j,记为,记为t(i,di)=j。l(7)状态转移方程
6、状态转移方程(f)状态转移方程状态转移方程f描述了状态变量之间的数学关系。一般描述了状态变量之间的数学关系。一般来说,与最优化问题相应,状态转移方程表示来说,与最优化问题相应,状态转移方程表示si的值的值最优化的条件,或者说是状态最优化的条件,或者说是状态i所对应问题的最优解值所对应问题的最优解值的计算公式,用代数式表示就是:的计算公式,用代数式表示就是:lsi=f(sj,dj)|i=t(j,dj),对决策变量,对决策变量dj所有可行的取值所有可行的取值)l1951年美国数学家年美国数学家R.Bellman等人,根据一等人,根据一类多阶段问题的特点,把多阶段决策问题变换类多阶段问题的特点,把多
7、阶段决策问题变换为一系列互相联系的单阶段问题,然后逐个加为一系列互相联系的单阶段问题,然后逐个加以解决。一些静态模型,只要人为地引进以解决。一些静态模型,只要人为地引进“时时间间”因素,分成时段,就可以转化成多阶段的因素,分成时段,就可以转化成多阶段的动态模型,用动态规划方法去处理。动态模型,用动态规划方法去处理。最优化原理最优化原理l解决这类问题的解决这类问题的“最优化原理最优化原理”(Principle of optimality):):“一个过程的最优决策具一个过程的最优决策具有这样的性质:即无论其初始状态和初始决策有这样的性质:即无论其初始状态和初始决策如何,其今后诸策略对以第一个决策
8、所形成的如何,其今后诸策略对以第一个决策所形成的状态作为初始状态的过程而言,必须构成最优状态作为初始状态的过程而言,必须构成最优策略策略”。l简言之,一个最优策略的子策略,对于它的初简言之,一个最优策略的子策略,对于它的初态和终态而言也必是最优的。态和终态而言也必是最优的。最优化原理l这个这个“最优化原理最优化原理”如果用数学化一点的语言来描述如果用数学化一点的语言来描述的话,就是:假设为了解决某一优化问题,需要依次的话,就是:假设为了解决某一优化问题,需要依次作出作出n个决策个决策D1,D2,Dn,如若这个决策序列是,如若这个决策序列是最优的,对于任何一个整数最优的,对于任何一个整数k,1k
9、n,不论前面,不论前面k个个决策是怎样的,以后的最优决策只取决于由前面决策决策是怎样的,以后的最优决策只取决于由前面决策所确定的当前状态,即以后的决策所确定的当前状态,即以后的决策Dk+1,Dk+2,Dn也是最优的。也是最优的。l最优化原理是动态规划的基础。任何一个问题,如果最优化原理是动态规划的基础。任何一个问题,如果失去了这个最优化原理的支持,就不可能用动态规划失去了这个最优化原理的支持,就不可能用动态规划方法计算。方法计算。何为动态规划l动态规划是运筹学的一个分支。与其说动态规划是一动态规划是运筹学的一个分支。与其说动态规划是一种算法,不如说是一种思维方法来得更贴切。因为动种算法,不如说
10、是一种思维方法来得更贴切。因为动态规划没有固定的框架,即便是应用到同一道题上,态规划没有固定的框架,即便是应用到同一道题上,也可以建立多种形式的求解算法。许多隐式图上的算也可以建立多种形式的求解算法。许多隐式图上的算法,例如求单源最短路径的法,例如求单源最短路径的Dijkstra算法、广度优先算法、广度优先搜索算法,都渗透着动态规划的思想。还有许多数学搜索算法,都渗透着动态规划的思想。还有许多数学问题,表面上看起来与动态规划风马牛不相及,但是问题,表面上看起来与动态规划风马牛不相及,但是其求解思想与动态规划是完全一致的。其求解思想与动态规划是完全一致的。动态规划适于解决何种问题l只适于解决一定
11、条件的最优策略问题。只适于解决一定条件的最优策略问题。l所谓所谓“满足一定条件满足一定条件”主要指:主要指:l(1)状态必须满足最优化原理;状态必须满足最优化原理;l(2)状态必须满足无后效性。状态必须满足无后效性。l所谓的无后效性是指:所谓的无后效性是指:“过去的决策只能通过当前状态影响过去的决策只能通过当前状态影响未来的发展,当前的状态是对以往决策的总结未来的发展,当前的状态是对以往决策的总结”。l这个特征说明什么呢?它说明动态规划适于解决当前决策和这个特征说明什么呢?它说明动态规划适于解决当前决策和过去状态无关的问题。状态,出现在策略的任何一个位置,它的过去状态无关的问题。状态,出现在策
12、略的任何一个位置,它的地位都是相同的,都可以实施同样的决策。这就是无后效性的内地位都是相同的,都可以实施同样的决策。这就是无后效性的内涵。涵。动态规划适于解决何种问题l这个特征说明什么呢?它说明动态规划适这个特征说明什么呢?它说明动态规划适于解决当前决策和过去状态无关的问题。状态,于解决当前决策和过去状态无关的问题。状态,出现在策略的任何一个位置,它的地位都是相出现在策略的任何一个位置,它的地位都是相同的,都可以实施同样的决策。这就是无后效同的,都可以实施同样的决策。这就是无后效性的内涵。性的内涵。采用动态规划解题的优点l动动态态规规划划的的最最大大优优势势在在于于它它具具有有极极高的效率高的
13、效率;l可获一系列解可获一系列解;l算法清晰简便,程序易编易调等。算法清晰简便,程序易编易调等。动态规划的逆向思维法l逆逆向向思思维维法法是是指指从从问问题题目目标标状状态态出出发发倒倒推推回回初初始始状状态态或或边边界界状状态态的的思思维维方方法法。如如果果原原问问题题可可以以分分解解成成几几个个本本质质相相同同、规规模模较较小小的的问问题题,很很自自然然就就会会联联想想到到从从逆逆向向思思维维的的角角度度寻寻求求问问题题的的解决。解决。l动动态态规规划划不不是是分分治治法法:关关键键在在于于分分解解出出来来的的各各个子问题的性质不同。个子问题的性质不同。动态规划的逆向思维法l分治法要求各个
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 设计 动态 规划 概要
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【丰****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【丰****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。