贪心算法、分治算法、动态规划算法间的比较 doc

题目：贪心算法、分治算法、动态规划算法间的比较

贪心算法：贪心算法采用的是逐步构造最优解的方法。在每个阶段，都在一定的标准下做出一个看上去最优的决策。决策一旦做出，就不可能再更改。做出这个局部最优决策所依照的标准称为贪心准则。 分治算法：分治法的思想是将一个难以直接解决大的问题分解成容易求解的子问题，以便各个击破、分而治之。

动态规划：将待求解的问题分解为若干个子问题，按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。 二、算法间的关联与不同 1、分治算法与动态规划

分治法所能解决的问题一般具有以下几个特征： ① 该问题的规模缩小到一定程度就可以容易地解决。

② 该问题可以分为若干个较小规模的相似的问题，即该问题具有最优子结构性质。

③ 利用该问题分解出的子问题的解可以合并为该问题的解。 ④ 该问题所分解出的各个子问题是相互独立的且子问题即之间不包含公共的子问题。

上述的第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；第二条特征是分治法应

用的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用；第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑贪心算法或动态规划算法；第四条特征涉及到分治法的效率，如果各个子问题不是独立的，则分治法要做许多不必要的工作，重复地解公共的子问题。这类问题虽然可以用分治法解决，但用动态规划算法解决效率更高。

当问题满足第一、二、三条，而不满足第四条时，一般可以用动态规划法解决，可以说，动态规划法的实质是：

分治算法思想+解决子问题冗余情况

2、贪心算法与动态规划算法

多阶段逐步解决问题的策略就是按一定顺序或一定的策略逐步解决问题的方法。分解的算法策略也是多阶段逐步解决问题策略的一种表现形式，主要是通过对问题逐步分解，然后又逐步合并解决问题的。 贪心算法每一步都根据策略得到一个结果，并传递到下一步，自顶向下，一步一步地做出贪心决策。

动态规划算法的每一步决策给出的不是唯一结果，而是一组中间结果，而且这些结果在以后各步可能得到多次引用，只是每走一步使问题的规模逐步缩小，最终得到问题的一个结果。

举例：如图1有一三角形数塔，求一自塔顶到塔底的路径，要求该路径上结点的值的和最大。

图1 图2

贪心算法解题过程：自顶向下从第一层9开始，到第二层，选数值较大的15，第三层，在可选路径中选数值较大的8,同理，第四层选9，第五层选10，这样就确定了一条路径：9→15→8→9→10。 动态规划算法接题过程：如图2，阶段1：自第五层开始，对经过第四层的2的路径，在第五层的19、7中选择数值较大的19，同理，对经过第四层18的路径，选10，对经过第四层9的路径，选10，对经过5的路径选16。以上是一次决策过程，也是一次递推过程和降阶过程。因为以上的决策结果将5阶数塔问题变为4阶子问题，递推出第四层与第五层和为:

21(2+19),28(18+10),19(9+10),21(5+16)

用同样的方法还可以将4阶数塔问题变为3阶数塔问题，……，最后得到1阶数塔问题，这样也确定了一条路径：9→12→10→18→10，就是真个问题的最优解。

显然，以上数塔问题用贪心算法得不到最优解，这里只是用作与动态规划算法的比较。

三、适用条件

贪心算法：①贪心选择性质：在求解一个问题的过程中，如果再

每一个阶段的选择都是当前状态下的最优选择，即局部最优选择，并且最终能够求得问题的整体最优解，那么说明这个问题可以通过贪心选择来求解，这时就说明此问题具有贪心选择性质。②最优子结构性质：当一个问题的最优解包含了这个问题的子问题的最优解时，就说明该问题具有最优子结构。

分治算法：见二、算法间的关联与不同中的①②③④。

动态规划： (1) 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。 (2) 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。（3）有重迭子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。

四、优势：采用动态规划方法，可以高效地解决许多用贪婪算法或分而治之算法无法解决的问题。但贪心算法也有它的优势：构造贪心策略不是很困难，而且贪心策略一旦经过证明成立后，它就是一种高效的算法。

参考文献：《算法设计与分析》武汉大学出版社，2007，第五章贪心算法

《算法设计与分析》清华大学出版社，2006，第四章基本算法策略 图1、图2来自http://wenku.http://www.wodefanwen.com//view/419024b81a37f111f1855bf8.html

本文来源：https://www.bwwdw.com/article/sekd.html