分治算法详解

什么是分治算法?

分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题,这些子问题相互独立且与原问题性质相同。求出子问题的解,就可得到原问题的解。即一种分目标完成程序算法,简单问题可用二分法完成。

基本思想

当我们求解某些问题时,由于这些问题要处理的数据相当多,或求解过程相当复杂,使得直接求解法在时间上相当长,或者根本无法直接求出。对于这类问题,我们往往先把它分解成几个子问题,找到求出这几个子问题的解法后,再找到合适的方法,把它们组合成求整个问题的解法。如果这些子问题还较大,难以解决,可以再把它们分成几个更小的子问题,以此类推,直至可以直接求出解为止。这就是分治策略的基本思想。

分治算法的具体应用

二分搜索
大整数乘法
棋盘覆盖
合并排序
快速排序
线性时间选择
最接近点对问题
循环赛日程表
汉诺塔

应用实例

找出伪币
给你一个装有16个硬币的袋子。16个硬币中有一个是伪造的,并且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这个伪造的硬币。为了帮助你完成这一任务,将提供一台可用来比较两组硬币重量的仪器,利用这台仪器,可以知道两组硬币的重量是否相同。比较硬币1与硬币2的重量。假如硬币1比硬币2轻,则硬币1是伪造的;假如硬币2比硬币1轻,则硬币2是伪造的。这样就完成了任务。假如两硬币重量相等,则比较硬币3和硬币4。同样,假如有一个硬币轻一些,则寻找伪币的任务完成。假如两硬币重量相等,则继续比较硬币5和硬币6。按照这种方式,可以最多通过8次比较来判断伪币的存在并找出这一伪币。

另外一种方法就是利用分而治之方法。假如把16硬币的例子看成一个大的问题。第一步,把这一问题分成两个小问题。随机选择8个硬币作为第一组称为A组,剩下的8个硬币作为第二组称为B组。这样,就把16个硬币的问题分成两个8硬币的问题来解决。第二步,判断A和B组中是否有伪币。可以利用仪器来比较A组硬币和B组硬币的重量。假如两组硬币重量相等,则可以判断伪币不存在。假如两组硬币重量不相等,则存在伪币,并且可以判断它位于较轻的那一组硬币中。最后,在第三步中,用第二步的结果得出原先16个硬币问题的答案。若仅仅判断硬币是否存在,则第三步非常简单。无论A组还是B组中有伪币,都可以推断这16个硬币中存在伪币。因此,仅仅通过一次重量的比较,就可以判断伪币是否存在。

假设需要识别出这一伪币。把两个或三个硬币的情况作为不可再分的小问题。注意如果只有一个硬币,那么不能判断出它是否就是伪币。在一个小问题中,通过将一个硬币分别与其他两个硬币比较,最多比较两次就可以找到伪币。这样,16硬币的问题就被分为两个8硬币(A组和B组)的问题。通过比较这两组硬币的重量,可以判断伪币是否存在。如果没有伪币,则算法终止。否则,继续划分这两组硬币来寻找伪币。假设B是轻的那一组,因此再把它分成两组,每组有4个硬币。称其中一组为B1,另一组为B2。比较这两组,肯定有一组轻一些。如果B1轻,则伪币在B1中,再将B1又分成两组,每组有两个硬币,称其中一组为B1a,另一组为B1b。比较这两组,可以得到一个较轻的组。由于这个组只有两个硬币,因此不必再细分。比较组中两个硬币的重量,可以立即知道哪一个硬币轻一些。较轻的硬币就是所要找的伪币。

应用场景

运用分治策略解决的问题一般来说具有以下特点:
1、原问题可以分解为多个子问题
这些子问题与原问题相比,只是问题的规模有所降低,其结构和求解方法与原问题相同或相似。
2、原问题在分解过程中,递归地求解子问题
由于递归都必须有一个终止条件,因此,当分解后的子问题规模足够小时,应能够直接求解。
3、在求解并得到各个子问题的解后
应能够采用某种方式、方法合并或构造出原问题的解。
不难发现,在分治策略中,由于子问题与原问题在结构和解法上的相似性,用分治方法解决的问题,大都采用了递归的形式。在各种排序方法中,如归并排序、堆排序、快速排序等,都存在有分治的思想。

下面用分治算法的特点来解决汉诺塔问题,具体实现代码如下:

package com.common.utils;/*** @ClassName Hanoitower* @Description:  分治算法,用java解决汉诺塔问题* @Author: mischen* @date: 19:57 2022/11/30* @Version 1.0*/
public class Hanoitower {public static void main(String[] args) {char [] arr={'A','B','C'};hanoitower(4,'A','B','C');}public static void hanoitower(int num,char a,char b,char c){if (num==1){//盘数为1,做一次搬迁,从A移动到C柱System.out.println("第1个盘从"+a+"移动到"+c+"盘");}else{//盘数大于1//先从a盘最上面的盘值最下面的盘之间的所有盘,移动到b盘,C盘作为中间盘hanoitower(num-1,a,c,b);//把最底下的那个盘,从a盘移动到c盘System.out.println("第"+num+"个盘从"+a+"移动到"+c+"盘");//把b盘的所有盘,移动到c盘上hanoitower(num-1,b,a,c);}}
}