分治：怎样拆解问题，逐个击破？

分治：怎样拆解问题，逐个击破？

迭代的算法策略可以一步步逼近最终答案，效率非常高。想要提高效率，其实还有另一种完全不同的思路，就是把大问题分拆成很多个小问题，再各个击破。

这就是我们要说的，算法中的“分治”策略。

说起分治，你可能会想到战国时期，秦灭六国的故事。

那个时候，七雄割据天下。关东六国都忌惮秦国，进行了合纵联盟。秦国想统一天下，但却不能一下吃掉其他六雄，于是使出“连横”的外交手段，瓦解了六国的联盟，然后分而治之。

这就是在大问题不能解决的情况下，把它分解成一些小问题，逐个解决的思想。

算法领域，也有这么一些算法，采用了把大问题分解成小问题的策略来进行计算。我们管它们叫“分治算法”。

我们就来说说分治算法是怎么提高效率的。

1. 分治算法：拆大为小的回溯算法

虽然秦灭六国背后的道理，也是“大问题拆成小问题”，但请注意，分治算法和我们通常说的“分治”相比，有很大的区别。要想真正理解这种算法，我们需要先正本清源，看看分治算法和我们平时说的“分治”有什么本质的不同。

先说答案，分治算法有“回溯”的过程，而平时说的分治是没有的。

什么是回溯呢？咱们来看一个例子。

假设你是中国网球公开赛的总裁判。今年的比赛，有64位选手参加。而你的任务是执法比赛，决出决战。

比赛选手很多，两两比赛肯定要很多场。而你想偷个懒，想出了一个外包的办法。

你把64位选手平分成两个半区，每个半区32位选手，每个半区分别外包给另外两个裁判去负责。他们接下来怎么做你不管，只要他们告诉你每个半区的胜者是谁，你接下来，就只执法这两个胜者之间的一场比赛，就能决出胜负了。

办法挺好！

结果这两个裁判也很懒。他们每个人也把工作分成了两份，交给下层的4个裁判去做，自己只负责一场比赛。接下去的4个裁判也很懒，继续分解外包工作。

最后一层的裁判，手里只有两个选手，不用外包了，打一场吧。决出胜者之后，这些裁判再把结果逐层汇报给上级。

这个过程不难理解。而且我猜你一定发现了，这个过程中有一个特点，就是所有裁判面对的问题、执行的操作非常相似。

如果我们要把这个过程写成算法的话，只需要写一小段程序，描述一个裁判要做的操作就行了。

这个程序只有两个功能，一个是分解，把执法比赛的任务外包；另一个是合并，把外包后得到的答案，也就是两个半区各自的胜者，以比赛的方式决出胜者，作为输出。

而在程序把问题分解成两个小一点的子问题的时候，因为子问题和原问题的结构相同，程序会调用它自己。自己循环调用自己，这就形成一个嵌套循环的结构。每个层级中遇到的问题规模，都比上一个层级小，直到规模小到可以直接通过比较得到答案。

这个嵌套循环调用自己的过程，就叫“回溯”。

回溯的好处你可能也听出来了，就是省了好多事儿。如果没有回溯，算法工程师就要把每层拆解的过程都一层层地写出来。有了回溯，你教会计算机做一层拆解，它就会自己进行多层的拆解。

这是算法的分治策略，和我们生活中说“分治”的本质不同。

分治算法是通过回溯，不断分解同样的问题，直到问题小到可以直接解决，然后再把小问题的解，合并成原来问题解的算法策略。

而秦灭六国呢，里面只有拆大为小，却没有回溯的过程，所以它和算法的分治策略不是一回事。

2. 保证分治算法有效的条件

那是不是每个问题都能通过分解、合并的方法，用分治策略解决呢？

当然不是。这个问题里其实包含了两层，一个是能不能用，一个是用了之后求解快不快。

先说说能不能的问题。

还记得之前说过的背包模型吗？一个背包有固定承重，比如只能装64公斤的东西。现在有64件物品，每件重量和价值都不同，我们该带哪些物品能把总价值最大化呢？

假设咱们还用跟网球赛类似的分治策略，把32件物品分配到上半区，32件物品放到下半区，每个半区背包的承受重量，也不断平均分配。

那么最后的子问题就成了：有一个载重1公斤的背包，和1件物品，放还是不放？这样一来，问题就出现了。可能有物品价值连城，但重量是2公斤，背包放不了，很多物品就这么被放弃了。你最后选出来的那些物品，并不是价值最大的组合。

为什么分治策略不好使了呢？因为这个问题不可以简单分解。所有的物品共享同样的背包空间，每个子问题本质上并不独立。这样强行分解成子问题，得到的答案合在一起，也不是原问题的答案。

也就是说，我们要确保问题可以分解成和原问题类似的子问题，并且这些子问题之间还相互独立，这时分治策略才能奏效。

说完能不能的问题，再说快不快的问题。

秦灭六国之所以要分治，是因为大问题解决不了。而算法分治策略的目的，不是要把一个不能解决的问题解决掉，而是要解决得更快。

咱举个例子，在计算机图形学中有个问题叫“碰撞检测”。就是说在一个计算机模拟的空间中，有很多物体。我们要判定任何两个物体有没有碰到。

说得通俗一点，就是在你玩电子游戏的时候，计算机要判定敌人的子弹有没有打到你头上。

解决这个问题可不容易，尤其是模拟的空间中物体很多的时候。

假设空间中有100个圆球在运动，咱们想知道它们之间哪些撞在了一起，就需要计算它们两两之间的距离。100个球总共的计算次数是4950次。如果物体的个数更大些，计算次数会以平方的形式上升。

平方的形式，复杂度就挺高了。如果用这种算法，游戏在进行得枪林弹雨时，你的画面肯定会卡。

采用分治的策略，就能让算法运行得更快些。

你可以想象一下。空间中的这100个球，不一定总是聚在一起。没准50个在左边，50个在右边。

咱们可以在中间画一条线，把空间分成两部分。这样两个空间相互分开，独立检测两个空间就好了。这么做，计算的次数可以从我们刚刚说的4950次，降低到2450次。再分割一次的话，计算次数还能下降到1200次。

但这不一定总能奏效。比如说我们在画线分割空间的时候，可能确定不了在哪里画线最好。我们想找到的位置，需要让两个空间里面球的数量尽量相同。那找到这个位置就需要额外的计算，这就是“分解”的时候计算成本的问题。

合并的时候，也有类似的问题。比如说你在分割空间的时候，可能会正好把某些球从中间割断。合并的时候，你发现这些球不属于任何一个子空间，要判断它们有没有发生碰撞，还得额外计算。这是合并结果的成本。

你看，分治中的两个重要操作，分解和合并，不是免费的。如果它们自身就要耗费很多次计算，那很可能分治策略提升不了效率，也不算是奏效了。

3. 分治算法能更快的特殊之处

分治算法还有一个特殊的地方，一定要跟你说说。

刚刚说的，减少基本操作的个数，这属于在“软件”上对算法效率进行提升。分治算法，还可以通过巧妙地利用“硬件”，让效率进一步提升。这就是“并行计算”。

什么意思呢？咱们回到网球比赛的问题里。如果每个裁判员是一个CPU的话。多个CPU可以共同协作，我们就能用更短的时间完成任务。这就是并行计算。

并行计算能让多个计算机的CPU同时为解决一个问题出力，但并不能减少总的操作数量。一个裁判要执法63场比赛。两个裁判也要执法63场比赛，总的复杂度没有变。但把任务分摊在两个CPU上，它们可以同时独立工作，完成任务的时间就可以减半。

为什么说这是分治算法特殊的地方呢？其他算法，比如我们上一讲说的迭代算法，能不能也并行在多个CPU上进行呢？

很可惜，不行。并不是所有算法都可以用并行计算的。

迭代算法要求每一步以前一步的结果作为出发点，按步骤、按顺序进行计算。如果让一个CPU计算前面的步骤，第二个CPU计算后面的步骤，两个CPU不能同时工作，就不是并行计算。

这里你就看到了，顺序计算和并行计算有本质上的差异。分治算法因为能把问题分解成独立的部分，所以和并行计算是天然的好朋友。

最近这些年，大数据在高科技领域掀起浪潮。数据量越大，处理起来的所花的步骤也就多。那为了能快速地对数据进行分析处理，就必须用分治算法。

划重点

1. 分治算法是通过回溯，不断分解同样的问题，直到问题小得可以直接解决，再把小问题的解合并成原来问题解的算法策略。

2. 确保要解决的问题能分解成与原问题类似的子问题，并且这些子问题之间相互独立，这时分治策略才能奏效。

3. 如果分解问题和合并结果计算不复杂，分治策略能减小算法的复杂度。

4. 分治策略开启了并行计算的大门，利用多CPU硬件上的优势，可以减少算法的运行时间。