贰.1.6 分治法、动态规划与贪心算法的区别

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

01.分治法

分治法(Divide-and-Conquer) : 将原问题划分成n个规模较小而结构、且与原问题相似的子问题,递归地解决这些子问题,然后再合并其结果,就得到原问题的解。

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

  • 分解(Divide):将原问题分解成一系列子问题;

  • 解决(Conquer):递归地解决各个子问题。若子问题足够小,则直接求解。

  • 合并(Combine):将子问题的结果合并成原问题的解。

快速排序是一个典型分治法的例子。

02.动态规划

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

  • 描述最优解的结构

  • 递归定义最优解的值

  • 按自底向上的方式计算最优解的值

  • 由计算出的结果构造一个最优解

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

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

最优子机构:如果问题的一个最优解中包含了子问题的最优解,则该问题具有最优子机构。

重叠子问题:子问题的空间要很小,也就是用来求解原问题的递归算法反复地解同样的子问题,而不是总是在产生新的子问题。对两个子问题来说,如果它们确实是相同的子问题,只是作为不同问题的子问题出现的话,则它们是重叠的。

一句话总结分治法与动态规划的区别: 分治法 —— 各子问题独立;动态规划 —— 各子问题重叠。

引自《算法导论》:

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

延伸阅读(建议必读)

华为实战题

有一座独木桥,长度为L,青蛙每跳一次的最大距离为M,最小距离为S,桥上有N个石墩,石墩不会落在两端只在桥中间,桥墩位置数组为Postions,青蛙很不喜欢站在石墩上。问:青蛙最少要几步能过桥,而且满足落在石墩上的次数最少。

举例输入:L=10,S=1,M=3,N=5,Positions=[2,4,5,7,9] 应该输出:2

//todo

03.贪心算法

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

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

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

贪心算法是通过做一系列的选择来给出某一问题的最优解。对算法中的每一个决策点,做一个当时看起来是最佳的选择。这一点是贪心算法不同于动态规划之处。在动态规划中,每一步都要做出选择,但是这些选择依赖于子问题的解。因此,解动态规划问题一般是自底向上,从小子问题处理至大子问题。贪心算法所做的当前选择可能要依赖于已经做出的所有选择,但不依赖于有待于做出的选择或子问题的解。

因此,贪心算法通常是自顶向下地做出贪心选择,不断地将给定的问题实例归约为更小的问题。贪心算法划分子问题的结果,通常是仅存在一个非空的子问题。