分治算法 divide and conquer

如何理解分治算法？

分治算法的核心思想其实就是四个字，分而治之 ，也就是将原问题划分成 n 个规模较小，并且结构与原问题相似的子问题，递归地解决这些子问题，然后再合并其结果，就得到原问题的解。

分治和递归的区别:

• 分治算法是一种处理问题的思想，递归是一种编程技巧

分治算法的递归实现中，每一层递归都会涉及这样三个操作：

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

分治算法能解决的问题，一般需要满足下面这几个条件：

• 原问题与分解成的小问题具有相同的模式；
• 原问题分解成的子问题可以独立求解，子问题之间没有相关性，这一点是分治算法跟动态规划的明显区别
• 具有分解终止条件，也就是说，当问题足够小时，可以直接求解；
• 可以将子问题合并成原问题，而这个合并操作的复杂度不能太高，否则就起不到减小算法总体复杂度的效果了。

谈一谈大规模计算框架MapReduce中的分治思想

如果订单数据存储在类似 GFS 这样的分布式系统上，当 10GB 的订单被划分成多个小文件的时候，每个文件可以并行加载到多台机器上处理，最后再将结果合并在一起，这样并行处理的速度也加快了很多。不过，这里有一个点要注意，就是数据的存储与计算所在的机器是同一个或者在网络中靠的很近（比如一个局域网内，数据存取速度很快），否则就会因为数据访问的速度，导致整个处理过程不但不会变快，反而有可能变慢。

实际上，MapReduce 框架只是一个任务调度器，底层依赖 GFS 来存储数据，依赖 Borg 管理机器。它从 GFS 中拿数据，交给 Borg 中的机器执行，并且时刻监控机器执行的进度，一旦出现机器宕机、进度卡壳等，就重新从 Borg 中调度一台机器执行。

四种算法思想比较分析

贪心、回溯、动态规划可以归为一类，而分治单独可以作为一类，因为它跟其他三个都不大一样。为什么这么说呢？

• 前三个算法解决问题的模型，都可以抽象成我们今天讲的那个多阶段决策最优解模型
• 分治算法解决的问题尽管大部分也是最优解问题，但是，大部分都不能抽象成多阶段决策模型

回溯算法是个“万金油”。基本上能用的动态规划、贪心解决的问题，我们都可以用回溯算法解决。

• 回溯算法相当于穷举搜索。穷举所有的情况，然后对比得到最优解
• 回溯算法的时间复杂度非常高，是指数级别的，只能用来解决小规模数据的问题

尽管动态规划比回溯算法高效，但是，并不是所有问题，都可以用动态规划来解决。

• 能用动态规划解决的问题，需要满足三个特征，最优子结构、无后效性和重复子问题。
  • 在重复子问题这一点上，动态规划和分治算法的区分非常明显。
    • 分治算法要求分割成的子问题，不能有重复子问题
    • 动态规划正好相反，动态规划之所以高效，就是因为回溯算法实现中存在大量的重复子问题。

贪心算法实际上是动态规划算法的一种特殊情况

• 它解决问题起来更加高效，代码实现也更加简洁。
• 它可以解决的问题也更加有限，需要满足三个条件：
  • 最优子结构
  • 无后效性
  • 贪心选择性: 通过局部最优的选择，能产生全局的最优选择。 每一个阶段，我们都选择当前看起来最优的决策，所有阶段的决策完成之后，最终由这些局部最优解构成全局最优解。

贪心：一条路走到黑，就一次机会，只能哪边看着顺眼走哪边 回溯：一条路走到黑，无数次重来的机会，还怕我走不出来 (Snapshot View) 动态规划：拥有上帝视角，手握无数平行宇宙的历史存档， 同时发展出无数个未来 (Versioned Archive View)

上一篇 « 贪心算法 greedy algorithm 下一篇 » 回溯算法