【算法】分治四步走

• 2021 年 3 月 26 日
• 筆記
• 算法

分治法在每一层递归上都有三个步骤：
1 ) 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题
2 ) 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题
3 ) 合并：将各个子问题的解合并为原问题的解。

分治四步走

1. 明确分解策略：明确大问题通过怎样的分解策略一步步分解为最终的小问题，之后我们需要根据分解策略明确函数的功能。
   比如说，我们的分解策略如果是折半分解，那么我们的函数就需要有范围域来确定分解范围；如果是递减分解，那么我们的函数需要有计数，来记录递减分解结果。

   比如说，快速排序的大的问题可以分解为就是将n个元素摆到正确位置，汉诺塔的大的问题就是将n个圆盘由下而上摆到正确位置。

2. 寻找最小问题：最小问题也就是大问题的最简化版本，问题的起始状态，最小子问题即是出口。

3. 解决次小问题：使用分解策略将大问题分解为次小的问题。次小问题也就是介于最小问题与大问题之间的问题，比最小问题稍稍大那么一点，这使得次小问题具有解决大问题的通用性，即 可以通过次小问题找到大问题的通解。由次小问题得到解决方法。

   比如说，快速排序的次小问题就是将一个元素摆到正确位置，汉诺塔的次小问题就是将一个最下面的圆盘摆到正确位置。

4. 合并次小问题：这个按照问题需要进行添加。

明确分解策略

第一步，明确怎么把大的问题一步步分解为最终的小问题；并明确这个函数的功能是什么，它要完成什么样的一件事。
分解策略：大问题 = n * 小问题。如果大问题是一个数组，那么小问题就是数组中的一个元素。

比如说，快速排序算法的大问题就是将数组中的n个元素进行排序摆放到正确的位置，那么分解而成的小问题就是将数组中的一个元素摆放到正确的位置。
而汉诺塔的大问题就是将A柱子上的n个盘子借用B柱子由大到小放在C柱子上，那么分解而成的小问题就是将A柱子上的最底下的最大盘子借用B放在C柱子上。

而这个功能，是完全由你自己来定义的。也就是说，我们先不管函数里面的代码是什么、怎么写，而首先要明白，你这个函数是要用来干什么的。

例如：找出一个数组中的最大值
要做出这个题，
第一步，要明确我们的分解策略，这里我的分解策略是折半分解；
既然分解策略是折半分解，那么我们即将要写出的这个函数必须指明分解范围，不然没有办法进行折半分解。

明确分解策略：大问题=从n个元素中找到最大的数字，折半分解，小问题=从2个元素比较大小找到最大数字。

//找出一个数组中的最大值
// 明确分解策略：大问题=从n个元素中找到最大的数字并返回，折半分解，小问题=从2个元素比较大小找到最大数字并返回。
int f(int[] nums, int l, int r) {
    
}

寻找最小问题（初始条件）

分治就是在函数实现的内部代码中，将大问题不断的分解为次小问题，再将小问题进一步分解为更小的问题。所以，我们必须要找出分治的结束条件，即 给定一个分解的阈值，不然的话，它会一直分解自己，无穷无尽。

• 必须有一个明确的结束条件。因为分治就是有“分”有“并”，所以必须又有一个明确的点，到了这个点，就不用“分解下去”，而是开始“合并”。

第二步，我们需要找出当参数为何值、分解到何种程度时，分治结束，之后直接把结果返回。
（一般为初始条件，然后从初始条件一步一步扩充到最终结果）

注意：这个时候我们必须能根据这个参数的值，能够直接知道函数的结果是什么。

让我们继续完善上面那个最大函数。
第二步，寻找最小问题：
当l>=r时，即 分解到只剩一个元素了，我们能够直接知道f(l)就是最大值；
那么递归出口就是l>=r时函数返回f(l)。
如下：

// 明确分解策略：大问题=从n个元素中找到最大的数字并返回，折半分解，小问题=从2个元素比较大小找到最大数字并返回。
int f(int[] nums, int l, int r) {

      // 寻找最小问题：最小问题即是只有一个元素的时候
      if (l >= r) {
            return nums[l];
      }
}

当然，当l>=r时，我们也是知道f(r)等于多少的，f(r)也可以作为递归出口。分治出口可能并不唯一的。

解决次小问题

第三步，之前我们明确了分解策略，现在正是使用的时候了，我们需要使用这个分解策略，将大问题分解为次小问题。这样就能一步步分解到最小问题，然后作为函数出口。

• 最小问题：分解至只剩一个元素，l>=r，f(l)即为最大值
• 分解策略：折半分解，f(nums, l, r) → f(nums, l, (l+r)/2) , f(nums, (l+r)/2+1, r)

分治：

• 分：将f(nums, l, r) → f(nums, l, (l+r)/2) , f(nums, (l+r)/2+1, r)了。这样，问题就由n缩小为了n/2，我们只需要找到这n/2个元素的最大值即可。就这样慢慢从f(n),f(n/2)“分”到f(1)。
• 并：这样就可以从1，一步一步“并”到n/2,n…

// 明确分解策略：大问题=从n个元素中找到最大的数字并返回，折半分解，小问题=从2个元素比较大小找到最大数字并返回。
int f(int[] nums, int l, int r) {

      // 寻找最小问题：最小问题即是只有一个元素的时候
      if (l >= r) {
            return nums[l];
      }

      // 使用分解策略
      int lMax = f(nums, l, (l+r)/2);
      int rMax = f(nums, (l+r)/2+1, r);
}

第四步：解决次小问题。
上一步我们将大问题分解为了次小问题，那么这个次小问题怎么解决呢，解决这个次小问题，也是为我们接下来的分解提供问题的解决方案，所以不能大意。
解决次小问题的方法，就是比较两个次小问题的大小，得出最大的一个值，问题即可解决。

// 明确分解策略：大问题=从n个元素中找到最大的数字并返回，折半分解，小问题=从2个元素比较大小找到最大数字并返回。
int f(int[] nums, int l, int r) {

      // 寻找最小问题：最小问题即是只有一个元素的时候
      if (l >= r) {
            return nums[l];
      }

      // 使用分解策略
      int lMax = f(nums, l, (l+r)/2);
      int rMax = f(nums, (l+r)/2+1, r);

      // 解决次小问题：比较两个元素得到最大的数字
      return lMax > rMax ? lMax : rMax;
}

合并次小问题

这里的合并就是解决次小问题，即 比较两个元素得到最大的数字。

到这里，分治五步走就完成了，那么这个分治函数的功能我们也就实现了。
可能初学的读者会感觉很奇妙，这就能得到最大值了？
那么，我们来一步一步推一下。
假设n为数组中元素的个数，f(n)则为n个元素的最大值
f(1)只有一个元素，可以得到一个确定的值
f(2)比较f(1)的值，也能确定了
f(4)比较f(2)的值，也能确定下来了
…
f(n/2)
f(n)比较f(n/2)也能确定下来了
你看看是不是解决了，n都能分治得到结果！

实例

最大数

在一个数组中找最大的数字。

分解策略：对半分

从l到r中找到最大的一个元素。

// 明确分解策略：大问题=从n个元素中找到最大的数字并返回，折半分解，小问题=从2个元素比较大小找到最大数字并返回。
int f(int[] nums, int l, int r) {

      // 寻找最小问题：最小问题即是只有一个元素的时候
      if (l >= r) {
            return nums[l];
      }

      // 使用分解策略
      int lMax = f(nums, l, (l+r)/2);
      int rMax = f(nums, (l+r)/2+1, r);

      // 解决次小问题：比较两个元素得到最大的数字
      return lMax > rMax ? lMax : rMax;
}

汉诺塔

汉诺塔的传说

汉诺塔：汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着 64 片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

假如每秒钟一次，共需多长时间呢？移完这些金片需要 5845. 54 亿年以上，太阳系的预期寿命据说也就是数百亿年。真的过了 5845. 54 亿年，地球上的一切生命，连同梵塔、庙宇等，都早已经灰飞烟灭。

汉诺塔游戏的演示和思路分析:

1 ) 如果是有一个盘，A->C

如果我们有 n>= 2 情况，我们总是可以看做是两个盘 1 .最下边的盘 2. 上面的盘
2 ) 先把 最上面的盘A->B
3 ) 把最下边的盘A->C
4 ) 把B塔的所有盘 从 B->C

汉诺塔游戏的代码实现:

看老师代码演示:

package com.atguigu.dac;

public class Hanoitower {

    public static void main(String[] args) {
        hanoiTower(10, 'A', 'B', 'C');
    }
    
    //汉诺塔的移动的方法
    //使用分治算法
    // 明确分解策略：我们的问题是有n个盘子，可是如果是n个盘子的话我们不会分，不知道结果；如果盘子数量为1、2、3就好了，所以我们按盘子数依次减一分解
    public static void hanoiTower(int num, char a, char b, char c) {
        // 寻找最小问题：只有一个盘
        //如果只有一个盘
        if(num == 1) {
            System.out.println("第1个盘从 " + a + "->" + c);
        } else {
            // 解决次小问题：由于我们是按盘子数-1来进行分解的，所以次小问题是一个盘子和n-1个盘子的汉诺塔，将一个最下面的盘子摆放到正确的位置
            //如果我们有 n >= 2 情况，我们总是可以看做是两个盘 1.最下边的一个盘 2. 上面的所有盘
            //1. 先把 最上面的所有盘 A->B， 移动过程会使用到 c
            hanoiTower(num - 1, a, c, b);
            //2. 把最下边的盘 A->C
            System.out.println("第" + num + "个盘从 " + a + "->" + c);
            //3. 把B塔的所有盘 从 B->C , 移动过程使用到 a塔  
            hanoiTower(num - 1, b, a, c);
        }
    }
}