`

动态规划法

阅读更多

动态规划法

 最优化原理

    1951年美国数学家R.Bellman等人,根据一类多阶段问题的特点,把多阶段决策问题变换为一系列互相联系的单阶段问题,然后逐个加以解决。一些静态模型,只要人为地引进“时间”因素,分成时段,就可以转化成多阶段的动态模型,用动态规划方法去处理。与此同时,他提出了解决这类问题的“最优化原理”(Principle of optimality):

    “一个过程的最优决策具有这样的性质:即无论其初始状态和初始决策如何,其今后诸策略对以第一个决策所形成的状态作为初始状态的过程而言,必须构成最优策略”。简言之,一个最优策略的子策略,对于它的初态和终态而言也必是最优的。

    这个“最优化原理”如果用数学化一点的语言来描述的话,就是:假设为了解决某一优化问题,需要依次作出n个决策D1,D2,…,Dn,如若这个决策序列是最优的,对于任何一个整数k,1 < k < n,不论前面k个决策是怎样的,以后的最优决策只取决于由前面决策所确定的当前状态,即以后的决策Dk+1,Dk+2,…,Dn也是最优的。

    最优化原理是动态规划的基础。任何一个问题,如果失去了这个最优化原理的支持,就不可能用动态规划方法计算。能采用动态规划求解的问题都需要满足一定的条件:

    (1) 问题中的状态必须满足最优化原理;

    (2) 问题中的状态必须满足无后效性。

    所谓的无后效性是指:“下一时刻的状态只与当前状态有关,而和当前状态之前的状态无关,当前的状态是对以往决策的总结”。

    问题求解模式

    动态规划所处理的问题是一个多阶段决策问题,一般由初始状态开始,通过对中间阶段决策的选择,达到结束状态。这些决策形成了一个决策序列,同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线)。如图所示。动态规划的设计都有着一定的模式,一般要经历以下几个步骤。

    初始状态→│决策1│→│决策2│→…→│决策n│→结束状态

    图1 动态规划决策过程示意图

    (1)划分阶段:按照问题的时间或空间特征,把问题分为若干个阶段。在划分阶段时,注意划分后的阶段一定要是有序的或者是可排序的,否则问题就无法求解。

    (2)确定状态和状态变量:将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然,状态的选择要满足无后效性。

    (3)确定决策并写出状态转移方程:因为决策和状态转移有着天然的联系,状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策,状态转移方程也就可写出。但事实上常常是反过来做,根据相邻两段各状态之间的关系来确定决策。

    (4)寻找边界条件:给出的状态转移方程是一个递推式,需要一个递推的终止条件或边界条件。

    算法实现

    动态规划的主要难点在于理论上的设计,也就是上面4个步骤的确定,一旦设计完成,实现部分就会非常简单。使用动态规划求解问题,最重要的就是确定动态规划三要素:问题的阶段,每个阶段的状态以及从前一个阶段转化到后一个阶段之间的递推关系。递推关系必须是从次小的问题开始到较大的问题之间的转化,从这个角度来说,动态规划往往可以用递归程序来实现,不过因为递推可以充分利用前面保存的子问题的解来减少重复计算,所以对于大规模问题来说,有递归不可比拟的优势,这也是动态规划算法的核心之处。确定了动态规划的这三要素,整个求解过程就可以用一个最优决策表来描述,最优决策表是一个二维表,其中行表示决策的阶段,列表示问题状态,表格需要填写的数据一般对应此问题的在某个阶段某个状态下的最优值(如最短路径,最长公共子序列,最大价值等),填表的过程就是根据递推关系,从1行1列开始,以行或者列优先的顺序,依次填写表格,最后根据整个表格的数据通过简单的取舍或者运算求得问题的最优解。下面分别以求解最大化投资回报问题和最长公共子序列问题为例阐述用动态规划算法求解问题的一般思路。

 

 

来自:http://c.chinaitlab.com/200909/793115.html

分享到:
评论

相关推荐

    动态规划法与分治法的区别

    动态规划法与分治法的区别、动态规划法与贪心法的区别、分枝限界法与回溯法的异同 动态规划法与分治法的区别 动态规划法和分治法都是将问题分解成小问题解决的算法,但它们之间有着很大的区别。首先,两者都将问题...

    近似串匹配问题 动态规划法——C++代码

    本主题将探讨如何利用动态规划法解决此类问题,并通过一个C++代码实例进行讲解。 近似串匹配指的是在主字符串(target string)中查找与模式字符串(pattern string)相似度较高的子串。这里的相似度可以是基于编辑...

    多段图的最短路径问题 动态规划法——C++代码

    本主题关注的是多段图的最短路径问题,通过动态规划法来求解。动态规划是一种利用子问题的最优解来构建全局最优解的算法设计策略,适用于解决具有重叠子问题和最优子结构的问题。 多段图是指一个图中的边不再仅连接...

    回溯法和动态规划法解01背包问题

    在提供的压缩包文件"Knapsack"中,可能包含了用某种编程语言实现的回溯法或动态规划法解01背包问题的源代码。由于代码未编译完成,你需要自行完成编译和运行,以验证和理解算法的具体实现。在调试和运行代码时,注意...

    最大子段和问题 蛮力法 分治法 动态规划法

    下面我们将深入探讨解决这一问题的三种主要方法:蛮力法、分治法和动态规划法。 1. **蛮力法**: 蛮力法是最直观的解法,通过遍历所有可能的子序列来找出最大和。对于长度为n的数组,我们需要检查n*(n+1)/2个子...

    南京邮电大学 算法设计与分析 陈慧南 实验二动态规划法实验报告

    在南京邮电大学的算法设计与分析课程中,动态规划法是解决最优化问题的重要算法策略之一,而实验二动态规划法实验报告主要涉及了动态规划在求解最长公共子序列(LCS)问题和矩阵连乘问题中的应用。以下是对这部分...

    动态规划法之多边形游戏问题

    动态规划法是计算机科学中解决复杂优化问题的一种高效策略,尤其在处理具有重叠子问题和最优子结构特征的问题时尤为适用。在这个“多边形游戏”问题中,我们可以假设玩家需要在一个多边形内进行某种操作,比如移动、...

    动态规划法解旅行商问题(TSP)问题的java实现

    ### 动态规划法解TSP 旅行商问题(TSP)是指一个旅行商需要访问一组城市,并希望找到一条最短路径,使得他可以访问所有这些城市一次后返回出发城市。这是一个经典的组合优化问题,在实际应用中有着广泛的应用背景,...

    程序设计--动态规划法

    动态规划法是计算机科学中一种重要的算法设计方法,主要用于解决最优化问题,它与分治法和贪心法有相似之处,但也具有独特的特点。在动态规划法中,问题被分解为一系列相互关联的子问题,这些子问题不是独立的,而是...

    动态规划法解0-1背包问题

    算法实验中用动态规划法解0-1背包问题,这里提供了源代码,仅供参考

    动态规划法求解0-1背包问题实验报告.pdf

    总结来说,动态规划法求解0-1背包问题的关键在于构建正确的状态转移方程,并通过填表的方式逐步计算出所有子问题的最大价值。这种思想不仅可以应用于背包问题,还可以广泛应用于其他优化问题,如最长公共子序列、...

    算法设计 C 最大子段和 动态规划法和分治法

    本文将深入探讨如何使用C语言实现最大子段和问题,以及如何运用动态规划法和分治法这两种高效策略来解决这一问题。 最大子段和(Maximum Subarray Problem)是计算数组中连续子数组的最大和的经典问题。在实际应用...

    动态规划法—最短路径

    动态规划法是一种强大的算法设计策略,它通过将复杂问题分解为子问题来求解,尤其在处理具有重叠子问题和最优子结构的问题时表现出色。在这个场景中,我们关注的是利用动态规划来解决有向图中的最短路径问题。在有向...

    蛮力法、分治法和动态规划法设计最大子段和问题的算法

    蛮力法、分治法和动态规划法设计最大子段和问题的算法,一、试分别利用蛮力法、分治法和动态规划法求解最大子段和问题,要求写出C/C++程序实现和算法的效率分析。程序运行结果要同时给出最大子段和的值以及由哪个子段...

    动态规划法解最长公共子序列

    1. 要求按动态规划法原理求解问题; 2. 两个序列数据通过键盘输入; 3. 要求显示结果。

    动态规划法求解多段图问题

    利用动态规划法快速、有效的求出一个5段图的由源点到汇点的最小成本路径。

    动态规划法解决0-1背包问题

    基于MATLAB平台,用动态规划法解决0-1背包问题,较为简单。参数分别为[物品重量,物品价值,背包容量,背包价值]

    矩阵连乘问题——动态规划法

    算法设计与分析,使用动态规划法解决矩阵连乘问题。内有MatrixChain、TraceBack、RecurMatrixChain-递归解决矩阵连乘问题等程序,非常超值啊!

Global site tag (gtag.js) - Google Analytics