分治法，动态规划及贪心算法区别

黑尘子 2017-05-22

展开全文

转自：http://hxrs./blog/1055478

分治法，动态规划法，贪心算法这三者之间有类似之处，比如都需要将问题划分为一个个子问题，然后通过解决这些子问题来解决最终问题。但其实这三者之间的区别还是蛮大的。

1.分治法

分治法（divide-and-conquer）：将原问题划分成n个规模较小而结构与原问题相似的子问题；递归地解决这些子问题，然后再合并其结果，就得到原问题的解。

分治模式在每一层递归上都有三个步骤：

分解（Divide）：将原问题分解成一系列子问题；
解决（conquer）：递归地解各个子问题。若子问题足够小，则直接求解；
合并（Combine）：将子问题的结果合并成原问题的解。

合并排序（merge sort）是一个典型分治法的例子。其对应的直观的操作如下：

分解：将n个元素分成各含n/2个元素的子序列；
解决：用合并排序法对两个子序列递归地排序；
合并：合并两个已排序的子序列以得到排序结果。

2. 动态规划法

动态规划算法的设计可以分为如下4个步骤：

描述最优解的结构
递归定义最优解的值
按自底向上的方式计算最优解的值
由计算出的结果构造一个最优解

分治法是指将问题划分成一些独立地子问题，递归地求解各子问题，然后合并子问题的解而得到原问题的解。与此不同，动态规划适用于子问题独立且重叠的情况，也就是各子问题包含公共的子子问题。在这种情况下，若用分治法则会做许多不必要的工作，即重复地求解公共的子问题。动态规划算法对每个子子问题只求解一次，将其结果保存在一张表中，从而避免每次遇到各个子问题时重新计算答案。

适合采用动态规划方法的最优化问题中的两个要素：最优子结构和重叠子问题。

最优子结构：如果问题的一个最优解中包含了子问题的最优解，则该问题具有最优子结构。

重叠子问题：适用于动态规划求解的最优化问题必须具有的第二个要素是子问题的空间要很小，也就是用来求解原问题的递归算法课反复地解同样的子问题，而不是总在产生新的子问题。对两个子问题来说，如果它们确实是相同的子问题，只是作为不同问题的子问题出现的话，则它们是重叠的。

“分治法：各子问题独立动态规划：各子问题重叠”

算法导论：动态规划要求其子问题既要独立又要重叠，这看上去似乎有些奇怪。虽然这两点要求听起来可能矛盾的，但它们描述了两种不同的概念，而不是同一个问题的两个方面。如果同一个问题的两个子问题不共享资源，则它们就是独立的。对两个子问题俩说，如果它们确实是相同的子问题，只是作为不同问题的子问题出现的话，是重叠的，则它们是重叠的。

3. 贪心算法

对许多最优化问题来说，采用动态规划方法来决定最佳选择有点“杀鸡用牛刀”了，只要采用另一些更简单有效的算法就行了。贪心算法是使所做的选择看起来都是当前最佳的，期望通过所做的局部最优选择来产生出一个全局最优解。贪心算法对大多数优化问题来说能产生最优解，但也不一定总是这样的。

贪心算法只需考虑一个选择（亦即，贪心的选择）；在做贪心选择时，子问题之一必须是空的，因此只留下一个非空子问题。

贪心算法与动态规划与很多相似之处。特别地，贪心算法适用的问题也是最优子结构。贪心算法与动态规划有一个显著的区别，就是贪心算法中，是以自顶向下的方式使用最优子结构的。贪心算法会先做选择，在当时看起来是最优的选择，然后再求解一个结果子问题，而不是先寻找子问题的最优解，然后再做选择。

贪心算法是通过做一系列的选择来给出某一问题的最优解。对算法中的每一个决策点，做一个当时看起来是最佳的选择。这一点是贪心算法不同于动态规划之处。在动态规划中，每一步都要做出选择，但是这些选择依赖于子问题的解。因此，解动态规划问题一般是自底向上，从小子问题处理至大子问题。贪心算法所做的当前选择可能要依赖于已经做出的所有选择，但不依赖于有待于做出的选择或子问题的解。因此，贪心算法通常是自顶向下地做出贪心选择，不断地将给定的问题实例归约为更小的问题。贪心算法划分子问题的结果，通常是仅存在一个非空的子问题。

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

转自：http://blog.csdn.NET/penzo/article/details/6001314

区别：
动态规划
全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解。
条件：最优子结构；重叠子问题。
方法：自底向上构造子问题的解。
例子：子序列最大和问题，滑雪问题

贪心算法
条件：每一步的最优解一定依赖上一步的最优解。
方法：从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。
存在问题：
（1）不能保证求得的最后解是最佳的；
（2）不能用来求最大最小解的问题；比如钱币分为1元3元4元，要拿6元钱，贪心的话，先拿4，再拿两个1，一共3张钱；实际最优却是两张3元就够了。
“贪心”特性：它对解空间树的遍历不需要自底向上，而只需要自根开始，选择最优的路，一直走到底就可以了。这样，与动态规划相比，它的代价只取决于子问题的数目，而选择数目总为1。
例子：哈夫曼树，钱币组合，设置雷达问题
========================
联系：
（1）都是一种递推算法；
（2）贪心和动态规划本质上是对子问题树的一种修剪。两种算法要求问题都具有的一个性质就是“子问题最优性”。即组成最优解的每一个子问题的解，对于这个子问题本身肯定也是最优的。

转自：http://blog.csdn.Net/intrepyd/article/details/4374856

写在前面

1. 本文内容对应《算法导论》(第2版)》第15章。

2. 主要介绍了动态规划算法的基本概念、适用问题，以及求解步骤。最后，简单地比较分析了贪心算法的基本思想。

3. 希望本文对您有所帮助，也欢迎您给我提意见和建议。

动态规划

基本概念

和分治法一样，动态规划（dynamic programming）是通过组合子问题的解而解决整个问题的。分治法是指将问题划分成一些独立地子问题，递归地求解各子问题，然后合并子问题的解而得到原问题的解。与此不同，动态规划适用于子问题不是独立的情况，也就是各子问题包含公共的子子问题。在这种情况下，若用分治法则会做许多不必要的工作，即重复地求解公共的子问题。动态规划算法对每个子子问题只求解一次，将其结果保存在一张表中，从而避免每次遇到各个子问题时重新计算答案。

动态规划适用问题

动态规划通常应用于最优化问题，即要做出一组选择以达到一个最优解。适合动态规划方法的最优化问题必须具备两个要素：最优子结构和重叠子问题。

2 最优子结构

用动态规划求解优化问题的第一步是描述最优解的结构。如果问题的一个最优解中包含了子问题的最优解，则该问题具有最优子结构。通常，可以利用自顶向下的思想来寻找最优子结构，即缩小原问题的规模，判断子问题的最优解是否是组成原问题最优解的一部分。

可以用无权最短路径和无权最长简单路径的例子，体会最优子结构的含义。假设p是从u到v的无权最短路径，那么p必定包含一个中间顶点w(可能是u或v)。如果p₁、p₂分别是u到w和w到v的无权最短路径，可以肯定，p将由p₁和p₂构成。因此，无权最短路径问题具有最优子结构。相反，假设p是u到v的无权最长简单路径，p₁和p₂分别是u到w和w到v的无权最长简单路径。因为p₁路径中可以包含顶点v，而p₂必定包含顶点v，所以当p₁和p₂合并时将形成环路，从而不能构成原问题的最优解p。用另一种方式看，在求解一个子问题时，对资源的使用(如这里的顶点)使得它们无法被另一个子问题所用。因此，无权最长简单路径问题不具有最优子结构，不能利用动态规划求解。

2 重叠子问题

适用于动态规划求解的最优化问题必须具有的第二个要素是子问题的空间要很小，也就是用来求解原问题的递归算法课反复地解同样的子问题，而不是总在产生新的子问题。对两个子问题来说，如果它们确实是相同的子问题，只是作为不同问题的子问题出现的话，则它们是重叠的。仍然以无权最短路径为例，两个相邻顶点间的无权最短路径，可以是包含这两个顶点的任意三个顶点的无权最短路径问题的重叠子问题。

动态规划求解步骤

动态规划算法的设计可以分为如下四个步骤：

1）描述最优解的结构。通过对最优解结构的分析，判断如何对原问题进行最优子结构划分。

2）利用子问题的最优解来递归定义一个最优解的值，这时递归求解的重要依据。

3）按自底向上的方式计算最优解的值。下层子问题的最优解通常被记录在表格中，供上层求解时查询。

4）由计算出的结果构造一个最优解。实际应用中，为了描述如何得到这个最优解，通常在自底向上的求解过程中，把每一个子问题中所作的选择保存在一个表格中。

最长公共子序列

以最长公共子序列为例，体会动态规划的求解过程。给定一个序列X=<x₁, x₂, …, x_m>，另一个序列Z=<z₁, z₂, …, z_k>是X的一个子序列，如果存在X的一个严格递增下标序列<i₁, i₂, …, i_k>，使得对所有的j=1, 2, …, k，有x_ij=z_j。在最长公共子序列（LCS，longest common subsequence）问题中，给定了两个序列X=<x₁, x₂, …, x_m>和Y=<y₁, y₂, …, y_n>，希望找出X和Y的最大长度公共子序列Z=<z₁, z₂, …, z_k>。

1）描述最优解的结构。尝试缩小原问题的规模，寻找最优子结构。这里，如果x_m= y_n，那么z_k =x_m= y_n且Z_k-1是X_m-1和Y_n-1的LCS；如果x_m≠y_n，那么z_k≠x_m蕴含Z是X_m-1和Y的一个LCS；如果x_m≠y_n，那么z_k≠y_n蕴含Z是X_m和Y_n-1的一个LCS。

2）利用上面的最优子结构，定义最优解的递归式。如果i=0，或j=0，那么c[i, j]=0；如果i, j>0且x_i=y_i，那么c[i, j]=c[i-1, j-1]+1；如果i, j>0且x_i≠y_i，那么c[i, j]=max(c[i, j-1], c[i-1, j])。这里，c[i, j]为序列X_i和Y_i的一个LCS的长度。

3）自底向上地计算LCS的长度，同时，记录LCS的元素。

4）根据上一步的结果，直接得到LCS及其长度。

* x_array,x_length: X序列及其长度

* y_array,y_length: Y序列及其长度

* b_array,b_length: 记录LCS的元素，b_length=min(x_length,y_length)

* 返回LCS长度

int dynamic_lcs(int *x_array, int x_length,

int *y_array, int y_length,

int *b_array, int b_length)

{

int i, j, k, lcs_length;

int **c_array=NULL;