一、基本概念
动态规划过程是:每次决策依赖于当前状态,又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的,所以,这种多阶段最优化决策解决问题的过程就称为动态规划。
二、基本思想与策略
基本思想与分治法类似,也是将待求解的问题分解为若干个子问题(阶段),按顺序求解子阶段,前一子问题的解,为后一子问题的求解提供了有用的信息。在求解任一子问题时,列出各种可能的局部解,通过决策保留那些有可能达到最优的局部解,丢弃其他局部解。依次解决各子问题,最后一个子问题就是初始问题的解。
由于动态规划解决的问题多数有重叠子问题这个特点,为减少重复计算,对每一个子问题只解一次,将其不同阶段的不同状态保存在一个二维数组中。
与分治法最大的差别是:适合于用动态规划法求解的问题,经分解后得到的子问题往往不是互相独立的(即下一个子阶段的求解是建立在上一个子阶段的解的基础上,进行进一步的求解)。
三、适用的情况
能采用动态规划求解的问题的一般要具有3个性质:
(1) 最优化原理:如果问题的最优解所包含的子问题的解也是最优的,就称该问题具有最优子结构,即满足最优化原理。
(2) 无后效性:即某阶段状态一旦确定,就不受这个状态以后决策的影响。也就是说,某状态以后的过程不会影响以前的状态,只与当前状态有关。
(3)有重叠子问题:即子问题之间是不独立的,一个子问题在下一阶段决策中可能被多次使用到。(该性质并不是动态规划适用的必要条件,但是如果没有这条性质,动态规划算法同其他算法相比就不具备优势)
四、求解的基本步骤
动态规划所处理的问题是一个多阶段决策问题,一般由初始状态开始,通过对中间阶段决策的选择,达到结束状态。这些决策形成了一个决策序列,同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线)。如图所示。动态规划的设计都有着一定的模式,一般要经历以下几个步骤。
初始状态→│决策1│→│决策2│→…→│决策n│→结束状态
图1 动态规划决策过程示意图
(1)划分阶段:按照问题的时间或空间特征,把问题分为若干个阶段。在划分阶段时,注意划分后的阶段一定要是有序的或者是可排序的,否则问题就无法求解。
(2)确定状态和状态变量:将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然,状态的选择要满足无后效性。
(3)确定决策并写出状态转移方程:因为决策和状态转移有着天然的联系,状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策,状态转移方程也就可写出。但事实上常常是反过来做,根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。
(4)寻找边界条件:给出的状态转移方程是一个递推式,需要一个递推的终止条件或边界条件。
一般,只要解决问题的阶段、状态和状态转移决策确定了,就可以写出状态转移方程(包括边界条件)。
实际应用中可以按以下几个简化的步骤进行设计:
(1)分析最优解的性质,并刻画其结构特征。
(2)递归的定义最优解。
(3)以自底向上或自顶向下的记忆化方式(备忘录法)计算出最优值
(4)根据计算最优值时得到的信息,构造问题的最优解
五、算法实现的说明
动态规划的主要难点在于理论上的设计,也就是上面4个步骤的确定,一旦设计完成,实现部分就会非常简单。
使用动态规划求解问题,最重要的就是确定动态规划三要素:
(1)问题的阶段 (2)每个阶段的状态
(3)从前一个阶段转化到后一个阶段之间的递推关系。
递推关系必须是从次小的问题开始到较大的问题之间的转化,从这个角度来说,动态规划往往可以用递归程序来实现,不过因为递推可以充分利用前面保存的子问题的解来减少重复计算,所以对于大规模问题来说,有递归不可比拟的优势,这也是动态规划算法的核心之处。
确定了动态规划的这三要素,整个求解过程就可以用一个最优决策表来描述,最优决策表是一个二维表,其中行表示决策的阶段,列表示问题状态,表格需要填写的数据一般对应此问题的在某个阶段某个状态下的最优值(如最短路径,最长公共子序列,最大价值等),填表的过程就是根据递推关系,从1行1列开始,以行或者列优先的顺序,依次填写表格,最后根据整个表格的数据通过简单的取舍或者运算求得问题的最优解。
f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+P(n,m)}
代码 for(j=1; j<=m; j=j+1) // 第一个阶段 xn[j] = 初始值; for(i=n-1; i>=1; i=i-1)// 其他n-1个阶段 for(j=1; j>=f(i); j=j+1)//f(i)与i有关的表达式 xi[j]=j=max(或min){g(xi-1[j1:j2]), ......, g(xi-1[jk:jk+1])}; t = g(x1[j1:j2]); // 由子问题的最优解求解整个问题的最优解的方案 print(x1[j1]); for(i=2; i<=n-1; i=i+1) { t = t-xi-1[ji]; for(j=1; j>=f(i); j=j+1) if(t=xi[ji]) break; }
转自 http://www.cnblogs.com/steven_oyj/archive/2010/05/22/1741374.html
相关推荐
Apollo规划算法介绍
对于学习ACM搞算法的初步学习和拓展思路有很大的帮助!是学习算法的好帮手!
主要介绍了Python基于动态规划算法计算单词距离的方法,实例分析了Python动态规划算法的实现与使用技巧,具有一定参考借鉴价值,需要的朋友可以参考下
主要介绍了java动态规划算法——硬币找零问题,结合实例形式分析了java动态规划算法——硬币找零问题相关原理、实现方法与操作注意事项,需要的朋友可以参考下
动态规划(Dynamic Programming,简称DP)是一种算法设计技巧,它通过将复杂问题分解为更小的子问题来解决问题,并且避免了子问题的重复计算。这种方法通常适用于具有重叠子问题和最优子结构特性的问题。动态规划在...
详细介绍动态规划算法,包括动态规划五部曲。使用动态规划解决经典问题,例如爬楼梯、打家劫舍问题、单词拆分问题、买卖股票问题等 动态规划是一种算法设计技术,它通过将问题分解为重叠的子问题并利用已经解决的子...
动态规划是解决最优化问题的基本方法,本文介绍了动态规划的基本思想和基本步骤,并通过几个实例的分析,研究了利用动态规划设计算法的具体途径。
动态规划算法的讲解,介绍了动态规划算法的原理、思想及设计思路,并结合具体的实例进行了讲述。
这里是对动态规划法的介绍,是专门学习了算法设计与分析这本书后收藏的ppt,如果大家需要可以下载看看
主要介绍了Java矩阵连乘问题(动态规划)算法,结合实例形式分析了java实现矩阵连乘的算法原理与相关实现技巧,需要的朋友可以参考下
主要介绍了JavaScript程序设计高级算法之动态规划,结合实例形式分析了javascript动态规划算法的原理、实现技巧与相关使用注意事项,需要的朋友可以参考下
01背包问题动态规划 背包问题介绍算法实现
主要介绍了Python基于动态规划算法解决01背包问题,结合实例形式分析了Python动态规划算法解决01背包问题的原理与具体实现技巧,需要的朋友可以参考下
此ppt介绍了解决TSP(旅行商问题)的三种算法:动态规划、蚁群算法、遗传算法
动态规划的入门介绍,将问题分解 考虑从最优路径上的任意一点出发 和原问题有什么关系? 设f[i][j]表示开始到第i行第j个点的路径权值和的最大值 那么我们不难得到这样的关系 f[i][j]= max(f[i-1][j],f[i][j-1]) +a...
《规划算法》目录: 第Ⅰ部分 介绍性的资料 第1章 绪论 1.1 从规划(的过程)到规划(的结果) 1.2 实例与应用 1.3 规划的基本组成 1.4 算法、规划器与规划 1.4.1 算法 1.4.2 规划器 1.4.3...
动态规划算法原理详细解读,里面介绍的很详细
引入了评估策略优劣程度的策略评估方法,并通过策略改进和策略迭代算法,寻找最优除此之外,还可以通过值迭代算法代替策略迭代来求解最优。3、动态规划解决规划(Plan
介绍动态规划的算法原理,和应用动态规划算法解决背包问题等实际问题的例子。还有解决这些问题的C语言程序,该资料是本校的ACM竞赛培训材料,相信对于大家提高编程能力有用
动态规划思想的介绍(矩阵连乘问题,最长公共子序列,流水线作业调度问题,0-1背包问题)。算法课使用的ppt,可结合我的博客算法专栏一起看。有详细代码。