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

动态规划(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 的多项式函数时,动态规划法显 得特别有意义,此时动态规划法具有线性时间复杂性。所以,能够用动 态规划解决的问题还有一个显著特征:子问题的重叠性。这个性质并不 是动态规划适用的必要条件,但是如果该性质无法满足,动态规划算法 同其他算法相比就不具备优势。


赞助商链接
相关文章:
动态规划题目
动态规划题目_计算机软件及应用_IT/计算机_专业资料。动态规划相关题目 ...DP 的边界状态即为 dp[i][1] = sum[1][i]; 所要求的结果即为 dp[vil...
acm中dp问题简单入门讲解
31 1 第1章 1.1 简介 动态规划(dp) (标题采用 2 号黑体居中,下空 1 ...事实上,这要求在每次主循环中 我们以 v=V..0 的顺序推 f[v],这样才能...
DP算法与最大值原理的关系及其优越性
性 摘要 在最优控制中变分法、最大值原理以及动态规划(DP)是经常用到的 理论方法,其中,DP 法不仅是性能指标取极值最优控制问题的必要条件而且还 是充分条件。...
动态规划:从新手到专家
使用动态规划来解题只需要多项式时间 复杂度,因此它比回溯法、暴力法等要快许多...如果要求 在多项式时间内解决,那么该问题就很可能要用 DP来解。遇到这种情况, ...
动态规划 分类
动态规划 分类_计算机软件及应用_IT/计算机_专业资料。动态规划分类 1、背包模型...61.130.174.222/oblog3/user1/40/subject/index.html 1.dp 一定要边界条件...
DP(动态规划背包小讲)
DP 动态规划之背包先上题目吧: 有 N 件物品和一个容量为 V 的背包。第 i...关于背包容量的判断 for(v=m;v>=weight[i];v--)为什 么满足这个条件的背包...
动态规划
--- 1,什么是动态规划(DP)? 非常重要!,不要认为概念不重要,理解的深刻,你...[i , j]的含义 ) 我们要求的是 C[n , n] 初始条件: C[0 , j] = ...
动态规划训练专题
动态规划训练专题一、要求 1. 学习动态规划基本知识,掌握动态规划高级应用技巧,如: 状态压缩 DP,树形动态规划、坐标型动态规划、区间型动态规划、 集合类动态规划、...
动态规划初步
顺便一提,动态规划的英文缩写就是 DP。 ※递推法的时间复杂度=状态总数*每个...(j); break; //如果去掉 break,那么可以打印出满足条件的所有方案。 } } (...
dp的入门题目
DP基础 39页 1下载券 动态规划(DP)入门 15页 1下载券 入门-很经典的DP 74...输出样例】 3.000 3、密码锁 有一个炸弹被敌人设置了密码, 现在要求你来破解...
更多相关标签: