文档介绍：该【(二) 动态规划算法 】是由【1781111****】上传分享，文档一共【9】页，该文档可以免费在线阅读，需要了解更多关于【(二) 动态规划算法 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。:..二)动态规划算法-几个动态规划问题中的术语-阶段-状态-无后效性-决策-多阶段决策问题-策略-状态转移方程-最优化原理/最优子结构性质-动态规划引出-基本思想-适用情况-基本步骤-书面版-细讲-个人理解-备忘录算法-程序设计-思维过程-一般的算法设计模式-经典运用#先来说几个动态规划问题中的术语:动态规划(dynamicprogramming)是运筹学的一个分支,是求解决策过程(decisionprocess)最优化的数学方法。20世纪:..(multistepdecisionprocess)的优化问题时,提出了著名的最优化原理(principleofoptimality),把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解,创立了解决这类过程优化问题的新方法——动态规划。多阶段决策问题的图示##阶段把所给求解问题的过程恰当地分成若干个相互联系的阶段,以便于求解,过程不同,。在多数情况下,阶段变量是离散的,用k表示。此外,也有阶段变量是连续的情形。如果过程可以在任何时刻作出决策,且在任意两个不同的时刻之间允许有无穷多个决策时,阶段变量就是连续的。在前面的图中,第一个阶段就是点A,而第二个阶段就是点A到点B,第三个阶段是点B到点C,而第四个阶段是点C到点D。##状态状态表示每个阶段开始面临的不以人的主观意志为转移的自然或客观条件,也叫不可控因素。在上面的例子中,状态是某个阶段的开始位置,它不仅是该阶段一条道路的起点,也是前一阶段一条分支的终点。前面的例子(图)中,第一个阶段有一个状态即A,而第二个阶段有两个状态B1和B2,第三个阶段是三个状态C1,C2和C3,而第四个阶段又是一个状态D。:..一般,状态是离散的,但有时为了方便也将状态取成连续的。此外,每个阶段中的状态维度可以不同。状态变量当过程以所有可能的不同方式发展时,过程的每个部分的状态变量将在一定范围内取值。状态变量的值的集合称为状态集。##无后效性我们要求状态具有下面的性质:如果某阶段的状态一旦确定,则在这一阶段以后过程的发展变化仅与此阶段的状态有关,不受这阶段以前各段状态的影响,所有各阶段都确定时,整个过程也就确定了。换句话说,流程的每个实现都可以用一个状态序列来表示。在前面的示例中,每个阶段的状态是线条的起点。如果这些点的顺序确定了,那么整条线就完全确定了。从某一阶段后的线开始,给定该段起点时,不受前一条线(通过点)的影响。也就是说,未来与过去无关,当前的状态是此前历史(以往决策)的一个完整总结,过程的历史只能通过当前的状态去影响它的未来的发展,这个性质称为无后效性。(简单点说:过去只能通过影响现在,进而影响未来)##决策一个阶段的状态给定后,从那个状态演化到下一个阶段的状态的选择(动作)叫做决策。在最优控制中,也叫控制。在每个阶段都有几个决定可供选择。在许多问题中,决策可以自然地表示为一个数字或一组数字。不同的决策对应不同的价值观。描述决策的变量称为决策变量。因为状态不满足后效,所以在每个阶段选择决策时只需要考虑当前状态,而不需要考虑过程的历史。:..决策变量的范围称为允许决策集。初始状态→│决策1│→│决策2│→…→│决策n│→结束状态##多阶段决策问题如果一类活动过程可以分为若干个互相联系的阶段,在每一个阶段都需作出决策(采取措施),一个阶段的决策确定以后,常常影响到下一个阶段的决策,从而就完全确定了一个过程的活动路线,则称它为多阶段决策问题。各个阶段的决策构成一个决策序列,称为一个策略。每一个阶段都有若干个决策可供选择,因而就有许多策略供我们选取,对应于一个策略可以确定活动的效果,这个效果可以用数量来确定。策略不同,效果也不同,多阶段决策问题,就是要在可以选择的那些策略中间,选取一个最优策略,使在预定的标准下达到最好的效果.##策略由每个阶段的决策组成的序列称为策略。对于每一个实际的多阶段决策过程,可供选取的策略有一定的范围限制,这个范围称为允许策略集合。允许策略集合中达到最优效果的策略称为最优策略。##状态转移方程给定k阶段状态变量的值后,如果这一阶段的决策变量一经确定,第阶段的状态变量也就完全确定,即的值随和第阶段的决策的值变化而变化,那么可以把这一关系看成与确定的对应关系,用表示。这是从阶段到阶段状态转移方程的状态转移规律,称为状态转移方程。:..最优化原理/最优子结构性质最优性原理:问题最优策略的子策略也是最优的。一般可以理解为子问题的局部优化会导致整个问题的全局优化,即一个问题的最优解只取决于其子问题的最优解,子问题的非最优解对问题的解没有影响。?最优子结构性质:当一个问题的最优解包含着它的子问题的最优解时,就称此问题具有最优子结构性质。一个问题满足最优化原理也称其拥有最优子结构性质。##动态规划引出多阶段决策问题中,各个阶段采取的决策,一般来说是与时间有关的,决策依赖于当前状态,又随即引起状态的转移,一个决策序列就是在变化的状态中产生出来的,故有“动态”的含义,称这种解决多阶段决策最优化问题的方法为动态规划方法。#基本思想:动态规划算法通常用于求解最优性问题:在这类问题中,可能有多个可行解,每个可行解对应一个值,我们希望找到具有最优值的解。动态规划(DP:DynamicProgramming)是一种重要的程序设计手段,其基本思想是在对一个多阶段决策的问题,按照某一顺序,根据每一步所选决策的不同会引起状态的转移,最后会在变化的状态中获取到一个决策序列。动态规划是一种把多阶段过程转化为一系列单阶段问题,逐个求解的方法泛应用于生产调度、工程技术和最优控制等领域。:..相同点:都是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。?区别:分而治之的方法将问题分成独立的子问题,所以有些子问题会重复计算;动态规划法分解的子问题往往不是相互独立的,而是相互重叠的,从而避免了大量的重复计算。动态规划的实质是分治思想和解决冗余的结合:?将问题实例分解为更小的、相似的子问题?存储子问题的解,必要时找出得到的答案,避免重复计算子问题,从而得到一个多项式时间算法。用一个表格记录所有已解决的子问题的答案。不管子问题后面用不用,只要算过,结果都会填在表格里。这是动态规划方法的基本思想。具体的动态规划算法有很多,但都有相同的填充格式。一般来说,只要问题可以分成更小的子问题,并且原问题的最优解包含子问题的最优解(即满足最优化原理),就可以认为是用动态规划来求解的。动态规划算法的难点在于怎么将问题转化为能够利用动态规划算法来解决。当重复子问题的数目比较小时,动态规划的效果也会很差。#适用情况一般具有以下3个特征::..(或称:问题具有最优子结构的性质。是动态规划的基础)怎么分析问题是否满足?反证法!先假设由问题的最优解导出的子问题的解不是最优的→然后证明在这个假设下可构造出比原问题最优解更好的解→从而导致矛盾,:递归地分解问题时,产生的子问题并不总是独立的(很多子问题重复),一个子问题在下一阶段中可能被多次使用到。(该性质并不是动态规划适用的必要条件,但是如果没有这条性质,动态规划算法同其他算法相比就不具备优势)动态规划将原来具有指数级时间复杂度的搜索算法改进成了具有多项式时间复杂度的算法。其中的关键在于解决冗余,这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术,它在实现的过程中,不得不存储产生过程中的各种状态,所以它的空间复杂度要大于其它的算法。#基本步骤:##书面版(1)分析最优解的性质,并刻画其结构特征。//确定满足最优化原理、划分阶段、确定状态(2)递归地定义最优解。//确定状态转移方程(递推方程)(3)以自底向上或自顶向下(备忘录)的方式计算出最优值(4)根据计算最优值时得到的信息,从子问题的最优解逐步构造出整个问题的最优解步骤1-3是动态规划算法的基本步骤。在只需求出最优值的情形下,步骤4可以省略,步骤3中记录的信息也较少;若需要:..4,步骤3中记录的信息必须足够多,以便构造最优解。【问题描述】给定两个字符串A[m]、B[n],求它们的最长公共子序列C。1、刻画最优解的结构特征如果temp=A[m]=B[n],C=temp+max_mon_len(A[1,...,m-1],B[1,...,n-1]);如果A[m]!=B[n],则C=maxLen(max_mon_len(A[1,...,m],B[1,...,n-1]),max_mon_len(A[1,...,m-1],B[1,...n]))。2、递归的定义最优解的值设C[i,j]表示两个串A[i]与B[j]的最长公共子序列的长度,则ifi=j=0,C[i,j]=0;ifi,j>0andA[i]==B[j],C[i,j]=1+C[i-1,j-1];ifi,j>0andA[i]!=B[j],C[i,j]=max(C[i-1,j],C[i,j-1]).3、计算最优解##(划分阶段)o把原问题分解为若干个子问题,子问题和原问题形式相同或类似,只不过规模变小了。子问题都解决,原问题即解决。o子问题的解一旦求出就会被保存,所以每个子问题只需求解一次。:..问题。划分时,需要注意划分后的子问题一定要是有序的或者是可排序的,否则问题就无法求解。(多阶段决策问题)2.