首页 > 代码库 > 分治法、动态规划、贪心算法区别

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

1.分治法

算法思想:将原问题划分成若干个规模较小而结构与原问题相似的子问题,递归的解决这些子问题,然后再合其结果,就得到原问题的解

特征:

  • 该问题的规模缩小到一定的程度就很容易解决
  • 该问题可以分解为若干个规模较小的相同问题,即改问题具有最优子结构性质
  • 利用该问题分解出的子问题的解可以合并为该问题的解;
  • 该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子问题

2.动态规划

算法思想:与分治法相似,也是通过组合子问题的解而解决整个问题。区别是,动态规划适用于分解得到的子问题往往不是相互独立的。在这种情况下如果采用分治法,有些子问题会被重复计算多次,动态规划通过记录已解决的子问题,可以避免重复计算。

步骤:

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

要素:最优子结构、重叠子问题

动态规划通常用于求解最优化问题,在这类问题中可能有多个可行解,最终得到的是其中一个最优解。

3.贪心算法

算法思想:通过做一系列的选择来给出某一问题的最优解,对算法中的每一个决策点,做一个当时(看起来)是最优的选择。这种启发式的策略并不是总能产生出最优解。

步骤:

将优化问题转化成这样的一个问题,即先做出选择,在解决剩下的一个子问题

证明原问题总是有一个最优解是做贪心选择得到的,从而说明贪心选择的安全性

说明在作出贪心选择后,剩余的子问题具有这样一个性质。即如果将问题的最优解和我们所做的贪心选择联合起来,可以得出原问题的一个最优解。

要素:贪心选择性质、最优子结构性质

贪心选择性质:一个全局最优解可以通过局部最(贪心)选择来达到。

在动态规划中,每一步都要做出选择,但这些选择依赖于子问题的解。因此,解动态规划问题一般是自底向上,从小到大。在贪心算法中,我们所做的选择总是当前看似最佳的选择,然后再解决之后所出现的子问题。贪心算法所做的当前选择可能依赖于已作出的选择,但不依赖于做出的选择或子问题的解。贪心策略是自顶向下的,不断的将给定的问题规约为更小的问题。

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