如何理解分治思想

分治思想就是把复杂问题、拆分成诺干个相同的小问题，然后将问题逐步解决掉，合并到一起的过程，就是分治思想。简单来说，分治思想就是“分而治之”，将复杂问题拆分成诺干个相同的小问题进行解决。

那么如何实现分治思维去解决问题呢？首先分解的问题要与整个问题的规则要一致，否则就无法使用分治去解决问题，总体可总结为：

• 分解：将原问题分解为若干个规模较小，相对独立，与原问题形式相同的子问题。
• 解决：若子问题规模较小且易于解决时，则直接解。否则，递归地解决各子问题。
• 合并：将各子问题的解合并为原问题的解。

有哪些场景中使用到了分治去解决问题呢，在上文中我们讲解了排序、当时我们只讲解了冒牌排序、选择排序，插入排序，高级一点的排序并没有涉及到，因为像归并排序、推排序、快速排序涉及到更多的知识点需要去讲解和个人去了解堆概念和递归思想。今天应用的分治思想就是完全适用于归并排序，归并排序同时还要去理解递归思想。

如果对递归不理解的，需要去学习下，要不没办法继续下去，分治思想最著名的体现就是汉诺塔。

相信大家都玩过汉诺塔吧，那么汉诺塔是如何来的呢？

传说越南河内某间寺院有三根银棒，上串 64 个金盘。寺院里的僧侣依照一个古老的预言，以上述规则移动这些盘子；预言说当这些盘子移动完毕， 世界就会灭亡。这个传说叫做梵天寺之塔问题（Tower of Brahma puzzle）。但不知道是卢卡斯自创的这个传说，还是他受他人启发。 若传说属实，僧侣们需要二的64次方减去一步才能完成这个任务；若他们每秒可完成一个盘子的移动，就需要 5849 亿年才能完成。整个宇宙现在也不过 137 亿年。这就是汉诺塔的由来。

• 算法求解

解法的基本思想是递归。假设有 A、B、C 三个塔，A塔有N块盘，目标是把这些盘全部移到 C 塔。那么先把 A 塔顶部的N-1块盘移动到 B 塔，再把 A 塔剩下的大盘移到 C，最后把B塔的N-1块盘移到 C。

• 汉诺塔问题

从左到右有A、B、C三根柱子，其中A柱子 上面有从小叠到大的n个圆盘，现要求将A柱子上的圆盘移到C柱子上去，期间只有一个原则：一次只能移到 一个盘子且大盘子不能在小盘子上面，求移动的步骤和移动的次数

移动的规则：

1.每次只能移动一个圆盘；

2.大盘不能叠在小盘上面。

def hanoi(n, a, b, c):
    if n == 1:
        print(a, '-->', c)
    else:
        hanoi(n - 1, a, c, b)
        hanoi(1, a, b, c)
        hanoi(n - 1, b, a, c)


if __name__ == "__main__":
    print(hanoi(2, 'A', 'B', 'C'))

可以用无向图来表示汉诺塔, 在表示的时候会更加地直观和清晰, 虽然说理解上有一点点小难度.

现在规定, 每一个节点表示盘子的位置一种可能性, 每一条边表示一种移动的方法.

注: 这里不考虑在两个柱子之间的, 没有意义的, 来回移动的情况.

对于只有一个盘子的汉诺塔，可以表示为：

对于有两个盘子的汉诺塔, 可以表示为:

相互连接的三个三角形, 组成了一个较大三角形的三个角。

每一个节点的第二个字母表示更大的盘子, 且最初时没有被移动。

对于每一个顶端的小三角形, 表示两个盘子的一种移动的方法：

外围的三角形的每一个节点, 表示在一个柱子上盘子的所有分布可能.。

对于 h+1 个盘子, 就可以”复制” h 个盘子时候的三角形图, 然后拼成一个新的大三角形图, 稍微改动一下,

这个大的三角形图就可以用来表示 h+1 个盘子时的情况了.

所以当有三个盘子时, 图形为：

A, b 和 c 表示三个柱子

按照从小到大的顺序, 从左到右地列出的盘子的位置.

最外面的三角形的边, 表示了盘子从一个柱子移动到另一个柱子最快的方式. 最大的三角形可以沿着中线分成三个次小的三角形, 就是上面由二级的汉诺塔组成三级的汉诺塔的逆向操作, 次小三角形相互之间的连线, 表示着最大的盘子的移动方式.

同理, 在这次三角形的也可以沿其中线分割成为三个次次三角形, 一样的, 次次小三角形相互之间的连线, 表示着次大的盘子的移动方式. 继续下去, 也就可以表示出一个汉诺塔的移动方式.

通常，对于具有 n 个盘子的图, 有3n个节点; 每个节点都有三条边连接着其他节点, 但是在顶点的的节点只却只有有两条边连接着其他节点.所以说总是下都可以将最小的盘子移动到另外两个柱子中的一个, 对于多数情况, 是可以在两个柱子间移动一个盘子, 除了所有的盘子都在一个柱子上. 边角的节点表示着所有的盘子都在一个柱子的情况, 即可以在 a, b 或 c 柱上堆满盘子, 显然只要三种. 对于n+1个盘子的图, 可以通过表示n给盘子的图 “复制” 三份, 组合在一起的. 因此也就很方便地表示了每一层的汉诺塔移动方式, 每一个次小的三角形表示次小的盘子的所有可能的移动方式和放置状态, 次小的三角形之间的连接表示了大盘子的三种可能的移动方式. 所以图形有3n+1个节点, 基本都有三个与之相连接的边,而顶点只有两个.

在盘子数比较多的时候, 汉诺塔的图像就会开始和分形图比较相似了.

该图较为清楚地表达了：

• 对于任意的全部盘子在一根柱子的情况下, 将所有盘子移动到另一个柱子的最短路径只有一个.
• 对于任意的两个盘子分布情况之间转换的时候, 只有一个或者两个不同的最短路径.
• 对于任意的盘子分布情况, 都有一个或者两个将所有盘子移动到任意一个柱子上的最长不相交路径.
• 对于任意的两个盘子分布情况之间转换的时候, 只有一个或者两个不同的最长不相交路径.
• 设Nh是将有h个盘子的塔, 将所有盘子从一个柱子移动到另一个柱子的非相交路径的数量(一开始盘子都在一个柱子上). 可以得出：

这里的

除了汉诺塔，还有其他的案例

• 归并排序
• 二分搜索
• 大整数乘法
• Strassen矩阵乘法
• 棋盘覆盖
• 快速排序
• 线性时间选择
• 最接近点对问题
• 循环赛日程表
• 青蛙跳台阶问题

分治法的复杂性分析

一个分治法将规模为n的问题分成k个规模为n／m的子问题去解。设分解阀值n0=1，且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间，则有： T（n）= k T(n/m)+f(n) 通过迭代法求得方程的解： 递归方程及其解只给出n等于m的方幂时T(n)的值，但是如果认为T(n)足够平滑，那么由n等于m的方幂时T(n)的值可以估计T(n)的增长速度。通常假定T(n)是单调上升的，从而当 mi≤n<mi+1时，T(mi)≤T(n)<T(mi+1)。

依据分治法设计程序时的思维过程

实际上就是类似于数学归纳法，找到解决本问题的求解方程公式，然后根据方程公式设计递归程序。

1、一定是先找到最小问题规模时的求解方法

2、然后考虑随着问题规模增大时的求解方法

3、找到求解的递归函数式后（各种规模或因子），设计递归程序即可。

我们通常使用分治思想去解决大数据量问题，以及可以给我们一个思考，当我们遇到无法解决的问题，可以将问题拆分开来，逐步解决，这样就可以实现赚它一个亿的小目标