“动态规划” “贪心” “分治”的区别及联系

“动态规划” “贪心” “分治”的区别及联系

2019年11月5日 0 作者 Null NaN

“动态规划” “贪心” “分治”的区别及联系

本文由Sunset_Rl编写,现代为发表。

共性:

​ 三者都将一个大问题归纳划分为若干个相似子问题,通过求解子问题产生出全局最优解。

特性:

动态规划:

  1. 最优子结构:如果将整个问题划分为若干个决策阶段,则每个阶段的最优决策点都可由他前一个决策的最优决策点得来。
  2. 子问题重叠:这也是动态规划与分治的最大区别。同样是将大问题划分为若干个子问题去求解,而动态规划所划分出的子问题(也就是整个决策过程中的状态)直接是会有相互重复的部分,而正是动态规划避免了这部分重叠的子问题的重复计算。先求解最小的子问题,把结果存在表格中,在求解大的子问题时,直接从表格中查询小的子问题的解,避免重复计算,从而提高算法效率。

    例子:

    
    
    A * "1+1+1+1+1+1+1+1 =?" *
    A : "上面等式的值是多少"
    B : *计算* "8!"

    A *在上面等式的左边写上 "1+" *
    A : "此时等式的值为多少"
    B : *quickly* "9!"
    A : "你怎么这么快就知道答案了"
    A : "只要在8的基础上加1就行了"
    A : "所以你不用重新计算因为你记住了第一个等式的值为8!动态规划算法也可以说是 '记住求过的解来节省时间'"

    正是记住了自己某一子问题(子状态),才避免了与之有重叠部分且更大的子问题在重叠部分的重复计算。

  3. 无后效性:当前阶段的决策不会受到前阶段的影响。我并不关心我之前是如何到达我这个状态的,我仅关心我这一步能否做出最优决策(之前的每一个阶段都进行类似思考,最后将得出一个完成的全局决策)。例:****

    ​ ***某阶段的状态一旦确定,则此后过程的演变不再受此前各种状态及决策的影响****

    ​ 百度百科是这样定义的,是不是很苦涩,难懂。并且网上对这个名词的解释大多都是理论性的,不好理解,今天我们通过一个例子来看看什么是无后效性

    *现在有一个四乘四的网格,左上角有一个棋子,棋子每次只能往下走或者往右走,现在要让棋子走到右下角*

    假设棋子走到了第二行第三列,记为s(2,3),如下图,画了两条路线和一条不符合题意的路线,那么当前的棋子[s(2,3)位置]怎么走到右下角和之前棋子是如何走到s(2,3)这个位置无关[不管是黑色尖头的路线还是蓝色箭头的路线]

    换句话说,当位于s(2,3)的棋子要进行决策(向右或者向下走)的时候,之前棋子是如何走到s(2,3)这个位置的是不会影响我做这个决策的。之前的决策不会影响了未来的决策(之前和未来相对于现在棋子位于s(2,3)的时刻),这就是无后效性,也就是所谓的“未来与过去无关”

    img

看完了无后效性,那我们再来看看有后效性,还是刚才的例子,只不过现在题目的条件变了,现在棋子可以上下左右走但是不能走重复的格子

那么现在红色箭头就是一个合法的路线了,当我的棋子走到了s(2,3)这个位置的时候,要进行下一步的决策的时候,这时候的决策是受之前棋子是如何走到s(2,3)的决策的影响的,比如说红色箭头的路线,如果是红色箭头决策而形成的路线,那么我下一步决策就不能往下走了[因为题意要求不能走重复的格子],之前的决策影响了未来的决策,”之前影响了未来”,这就叫做有后效性

转自: https://blog.csdn.net/qq_30137611/article/details/77655707

分治:

  1. 最优子结构:与dp所相同
  2. 子问题不重叠:这也是其与dp所最大的不同点,分治把原问题分解为若干个子问题,自顶向下求解子问题,合并子问题的解,从而得到原问题的解。

贪心:

  1. 贪心在某种程度上也是“最优”子结构,只不过是根据当前的情况所得出的最优,相较于全局来说可能更糟。
  2. 全局问题由子问题一步步“贪心”得出。
标准分治 动态规划 贪心算法
适用类型 通用问题 优化问题 优化问题
子问题结构 每个子问题不同 很多子问题重复(不独立) 只有一个子问题
最优子结构 不需要 必须满足 必须满足
子问题数 全部子问题都要解决 全部子问题都要解决 只要解决一个子问题
子问题在最优解里 全部 部分 部分
选择与求解次序 先选择后解决子问题 先解决子问题后选择 先选择后解决子问题

详细辨析:https://www.cnblogs.com/codeskiller/p/6477181.html