当前位置:首页 >> 计算机软件及应用 >>

动态规划(DP)的使用条件


动态规划的适用条件
任何思想方法都有一定的局限性,超出了特定条件,它就失去了作用。 同样,动态规划也并不是万能的。适用动态规划的问题必须满足最优化 原理和无后效性。

1.最优化原理(最优子结构性质) 最优化原理可这样阐述:一个最优化策略具有这样的性质,不论过去状 态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构 成最优策略。简而言之,一个最优化策略的子策略总是最优的。一个问 题满足最优化原理又称其具有最优子结构性质。

图2 例如图 2 中,若路线 I 和 J 是 A 到 C 的最优路径,则根据最优化原理, 路线 J 必是从 B 到 C 的最优路线。 这可用反证法证明: 假设有另一路径 J'是 B 到 C 的最优路径, A 到 C 的路线取 I 和 J'比 I 和 J 更优, 则 矛盾。 从而证明 J'必是 B 到 C 的最优路径。 最优化原理是动态规划的基础,任何问题,如果失去了最优化原理的支 持,就不可能用动态规划方法计算。动态规划的最优化理在其指标函数

的可分离性和单调性中得到体现。 根据最优化原理导出的动态规划基本 方程是解决一切动态规划问题的基本方法。 可以看出,例 1 是满足最优化原理的。 2.无后向性 将各阶段按照一定的次序排列好之后,对于某个给定的阶段状态,它以 前各阶段的状态无法直接影响它未来的决策, 而只能通过当前的这个状 态。换句话说,每个状态都是过去历史的一个完整总结。这就是无后向

性,又称为无后效性。
如果用前面的记号来描述无后向性,就是:对于确定的 xk,无论 p1,k-1 如何,最优子策略 pkn*是唯一确定的,这种性质称为无后向性。 [例 3] Bitonic 旅行路线问题 欧几里德货郎担问题是对平面给定的 n 个点确定一条连结各点的、 闭合 的最短游历路线问题。图 3(a)给出了七个点问题的解。Bitonic 旅行路线 问题是欧几里德货郎担问题的简化,这种旅行路线先从最左边开始,严 格地由左至右到最右边的点,然后再严格地由右至左到出发点,求路程 最短的路径长度。图 3(b)给出了七个点问题的解。

图3 这两个问题看起来很相似。但实质上是不同的。为了方便讨论,我将每 个顶点标记了号码。由于必然经过最右边的顶点 7,所以一条路(P1-P2) 可以看成两条路(P1-7)与(P2-7)的结合。所以,这个问题的状态可以 用两条道路结合的形式表示。我们可以把这些状态中,两条路中起始顶 点相同的状态归于一个阶段,设为阶段[P1,P2]。 那么,对于 Bitonic 旅行路线问题来说,阶段[P1,P2]如果可以由阶段 [Q1,Q2]推出, 则必须满足的条件就是:P1<Q1 或 P2<Q2。 例如, 阶段[3,4] 中的道路可以由阶段[3,5]中的道路加一条边 4-5 得出,而阶段[3,5]的状 态却无法由阶段[3,4]中的状态得出,因为 Bitonic 旅行路线要求必须严 格地由左到右来旅行。所以如果我们已经知道了阶段[3,4]中的状态,则 阶段[3,5]中的状态必然已知。因此我们可以说,Bitonic 问题满足无后向

性,可以用动态规划来解决。
有些问题乍一看好像有后向性, 但如果按照某种合理的方式重新划分阶 段,就可以发现其本质上是无后向性的,所以关键是阶段的合理划分, 这一点将在动态规划的技巧中详细阐述。

3.子问题的重叠性 在例 1 中我们看到, 动态规划将原来具有指数级复杂度的搜索算法改进 成了具有多项式时间的算法。其中的关键在于解决冗余,这是动态规划 算法的根本目的。动态规划实质上是一种以空间换时间的技术,它在实 现的过程中,不得不存储产生过程中的各种状态,所以它的空间复杂度 要大于其它的算法。以 Bitonic 旅行路线问题为例,这个问题也可以用 搜索算法来解决。动态规划的时间复杂度为 O(n2),搜索算法的时间复 杂度为 O(n!) ,但从空间复杂度来看,动态规划算法为 O(n2),而搜索 算法为 O(n),搜索算法反而优于动态规划算法。选择动态规划算法是因 为动态规划算法在空间上可以承受,而搜索算法在时间上却无法承受, 所以我们舍空间而取时间。 设原问题的规模为 n,容易看出,当子问题树中的子问题总数是 n 的超 多项式函数,而不同的子问题数只是 n 的多项式函数时,动态规划法显 得特别有意义,此时动态规划法具有线性时间复杂性。所以,能够用动 态规划解决的问题还有一个显著特征:子问题的重叠性。这个性质并不 是动态规划适用的必要条件,但是如果该性质无法满足,动态规划算法 同其他算法相比就不具备优势。


赞助商链接
相关文章:
1D1D动态规划优化初步
1D/1D 动态规划优化初步所谓 1D/1D 动态规划, 指...现在要求使用最少的代价将所有玩具装箱,箱子的个...第一种可能可以通过树形 DP 解决,问题就在于第二种...
动态规划题库
动态规划题库 - DP Problem Set 顺序对齐 源程序名 可执行文件名 输入文件名 输出文件名 ALIGN.??? (PAS,C,CPP) ALIGN.EXE ALIGN.IN AL...
动态规划入门1
动态规划入门1 - 动态规划入门( 动态规划入门(一) DP 基本思想 具体实现 经典题目 分类: POJ 2011-08-07 17:58 22 人阅读 评论(0) 收藏 举报 动态规划( ...
dp概叙
dp概叙_IT/计算机_专业资料。动态规划入门 1.动态规划概述 1.1 什么是动态...要求求出给出顶点的最短路径。 此题十分典型,可以使用图的最短路径算法。但是...
AC自动机上的DP
AC自动机上的DP - [ADN.cn][Library]Summary 动态规划总结 by Amber 1. Pku 3691 DNA repair 题意为给你一些病毒串,然后给你一个目...
dp优化 - 用单调性优化动态规划
竞赛试 题,探讨单调性在动态规划优化中神奇的应用。...可以想到前面单 调队列的一个限制条件。 ③ 来看一...[i ]) 现在的式子比较简洁,我们将 Dp 的式子合...
DP
曼好的介绍dp的教材的。。很好呢。。。隐藏>> 动态规划入门 §1.引例例 1...经测试 N=100 时,速度仍相当快完全符合要求。 从上分析可以看出,此题难度随行...
运用“teachdp”宏求解动态规划
运用“teachdp”宏求解动态规划_数学_自然科学_专业资料。运用“teachdp”宏求解动态规划1 2 实验报告书写格式 动态规划算法的实现 ---以背包问题为例 以背包问题为...
基于连通性状态压缩的动态规划问题
条满足要求的回路. 算法分析 【划分阶段 这是一个典型的基于棋盘模型的问题,棋盘模型的特殊结 划分阶段】 划分阶段 棋构,使得它成为连通性状态压缩动态规划问题最...
彻底弄懂最短路径问题
Floyd 算法另一种理解 DP, 为理论 爱好者准备的,...(贝尔曼,动态 规划提出者)和 Ford(福特)提出了从...算法适用条件 ? 1.单源最短路径(从源点 s 到...
更多相关标签: