分治算法：

  • 一、基本概念
  • 二、基本思想及策略
  • 三、分治法使用场景
    • 五、分治法的复杂性分析
    • 六、可使用分治法求解的一些经典问题
    • （1）二分搜索
    • （2）大整数乘法
    • （3）Strassen矩阵乘法
    • （4）棋盘覆盖
    • （5）合并排序
    • （6）快速排序
    • （7）线性时间选择
    • （8）最接近点对问题
    • （9）循环赛日程表
    • （10）汉诺塔详解
      • 汉诺塔公式：ans=2^n^-1
      • 牛牛的汉诺塔

)

一、基本概念

在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)……

任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的排序问题，当n=1时，不需任何计算。n=2时，只要作一次比较即可排好序。n=3时只要作3次比较即可，…。而当n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。

二、基本思想及策略

分治法的设计思想是：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
　　分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。
　　如果原问题可分割成k个子问题，1<k≤n，且这些子问题都可解并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。

三、分治法使用场景

分治法所能解决的问题一般具有以下几个特征：
　　1) 该问题的规模缩小到一定的程度就可以容易地解决
　　2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。
　　3) 利用该问题分解出的子问题的解可以合并为该问题的解；
　　4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。
　　第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；
　　第二条特征是应用分治法的前提它也是大多数问题可以满足的，此特征反映了递归思想的应用；、
　　第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。
　　第四条特征涉及到分治法的效率，如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。
　　四、分治法得基本步骤
　　分治法在每一层递归上都有三个步骤：
　　step1 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；
　　step2 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题
　　step3 合并：将各个子问题的解合并为原问题的解。
　　它的一般的算法设计模式如下：
　　Divide-and-Conquer§
　　1. if |P|≤n0
　　2. then return(ADHOC§)
　　3. 将P分解为较小的子问题 P1 ,P2 ,…,Pk
　　4. for i←1 to k
　　5. do yi ← Divide-and-Conquer(Pi) △ 递归解决Pi
　　6. T ← MERGE(y1,y2,…,yk) △ 合并子问题
　　7. return(T)
　　其中|P|表示问题P的规模；n0为一阈值，表示当问题P的规模不超过n0时，问题已容易直接解出，不必再继续分解。ADHOC§是该分治法中的基本子算法，用于直接解小规模的问题P。因此，当P的规模不超过n0时直接用算法ADHOC§求解。算法MERGE(y1,y2,…,yk)是该分治法中的合并子算法，用于将P的子问题P1 ,P2 ,…,Pk的相应的解y1,y2,…,yk合并为P的解。

五、分治法的复杂性分析

一个分治法将规模为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）Strassen矩阵乘法

（4）棋盘覆盖

（5）合并排序

（6）快速排序

（7）线性时间选择

（8）最接近点对问题

（9）循环赛日程表

（10）汉诺塔详解

在汉诺塔游戏中，有三个分别命名为A、B、C得塔座，几个大小各不相同，从小到大一次编号得圆盘，每个原盘中间有一个小孔。最初，所有得圆盘都在A塔座上，其中最大得圆盘在最下面，然后是第二大，以此类推.

【算法】分治算法-编程知识网
　　　　游戏的目的是将所有的圆盘从塔座A移动到塔座B;塔座C用来防止临时圆盘,游戏的规则如下:
　　　　1、一次只能移动一个圆盘
　　　　2、任何时候都不能将一个较大的圆盘压在较小的圆盘上面.
　　　　3、除了第二条限制,任何塔座的最上面的圆盘都可以移动到其他塔座上.
　　汉诺塔问题解决思想:
　　　　在解决汉诺塔问题时,事实上,我们不是关心圆盘1开始应该挪到哪个塔座上,而是关心最下面的圆盘4.当然,我们不能直接移动圆盘4,但是圆盘4最终将从塔座A移动到塔座B.按照游戏规则,在移动圆盘4之前的情况一定如下图
【算法】分治算法-编程知识网
　　 我们仍将分析,如何将前三个圆盘从A移动到C,然后圆盘4从A移动到B,前三个圆盘从C再移动到B.
　　但是上面的步骤可以重复利用!例如将三个圆盘从A移动到C,那么应该先将前两个圆盘从A移动到B,然后将圆盘3从A移动到C,最后将前两个圆盘从B移动到C.
　　持续简化这个问题,最终我们将只需要处理一个圆盘从一个塔座移动到另一个塔座的问题.
我们先来想一下我们人类应该怎样操作吧。

我们每次操作都会这样问自己：我们需要将哪个柱子上的多少个盘子通过哪个柱子移动到哪个柱子上呢？

我们必须也只能用这么几个参数：

需要移动的盘子的总数，3个柱子。

所以函数头为：

void hanoi(int n, char x, char y, char z)

其中，n代表盘子总数，x，y，z代表柱子

hanoi(n, x, y, z)的意思就是：将n个在x柱子上的盘子通过y这个柱子移动到z这个柱子上。

那不就完了！

hanoi(n, ‘A’, ‘B’, ‘C’)就是这道问题的答案！

那么这一步的前一步是什么？

记住了，在求解f(n, other variables)的时候，我们直接默认f(n – 1, other variables)已经完了就可以了！这个在前面已经解释过了，在此不再鳌述。

我们将n-1个盘子当作一个整体：这就是类似于分治求解子问题的思想

那么，前一步也就是f(n – 1, other variables)显然是先将n -1 个在A柱子上的盘子通过C柱移动到B柱上，再将在A柱子上的编号为n的盘子移动到C柱上，再将B柱子上的n-1个盘子通过A柱移动到C柱上

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+7;
const ll mod=1e9+7;
ll cnt,n;
void move(ll id,char from,char to)
{printf ("step %lld: move %lld from %c->%c\n", ++cnt, id, from, to);
}
void hanoi(ll n,char x,char y,char z)
{if(n==0)return;hanoi(n-1,x,z,y);//把n-1个盘子全部从X经过z移动到y柱上move(n,x,z);//偷偷把第n个盘子从x移动到z上hanoi(n-1,y,x,z);//把n-1个盘子从y经过x移动到z柱上，结束
}int main()
{cin>>n;hanoi(n,'A','B','C');return 0;
}

汉诺塔公式：ans=2n-1

牛牛的汉诺塔

牛牛的汉诺塔
【算法】分治算法-编程知识网

输入：
3
【算法】分治算法-编程知识网

就是按照经典汉诺塔的写法写递归函数，然后再写一个结构体，巧妙地用数组把六种情况存起来即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+7;
const ll mod=1e9+7;
ll cnt,n;
struct node
{ll date[6];node(){memset(date,0,sizeof date);}//a->b 0//a->c 1//b->a 2//b->c 3//c->a 4//c->b 5
};
node dp[3][3][3][105];
bool vis[3][3][3][105];
node operator+(const node &a,const node &b)
{node c;for(ll i=0;i<=5;++i){c.date[i]=a.date[i]+b.date[i];}return c;
}
void moveto(ll x,ll y,node &temp)
{if(x==0&&y==1)++temp.date[0];if(x==0&&y==2)++temp.date[1];if(x==1&&y==0)++temp.date[2];if(x==1&&y==2)++temp.date[3];if(x==2&&y==0)++temp.date[4];if(x==2&&y==1)++temp.date[5];return;
}
node hanoi(ll a,ll b,ll c,ll n)//把a经过b移动到c柱上（第n个）
{if(vis[a][b][c][n])return dp[a][b][c][n];if(n==1){moveto(a,c,dp[a][b][c][n]);vis[a][b][c][n]=true;//标记一下return dp[a][b][c][n];}node temp;//普通的hanoi塔temp=temp+hanoi(a,c,b,n-1);//先把n-1个从a经过c移动到bmoveto(a,c,temp);//把第n个直接从a移动到ctemp=temp+hanoi(b,a,c,n-1);//再把刚刚那n-1个从b经过a移动到cvis[a][b][c][n]=true;//完成！return dp[a][b][c][n]=temp;
}
int main()
{cin>>n;node ans=hanoi(0,1,2,n);printf("A->B:%lld\n",ans.date[0]);printf("A->C:%lld\n",ans.date[1]);printf("B->A:%lld\n",ans.date[2]);printf("B->C:%lld\n",ans.date[3]);printf("C->A:%lld\n",ans.date[4]);printf("C->B:%lld\n",ans.date[5]);printf("SUM:%lld\n",(ll(1)<<n)-1);//公式ans=2^n-1
}

注：如果您通过本文,有(qi)用(guai)的知识增加了，请您点个赞再离开,如果不嫌弃的话,点个关注再走吧，日更博主每天在线答疑 ! 当然，也非常欢迎您能在讨论区指出此文的不足处，作者会及时对文章加以修正 !如果有任何问题，欢迎评论，非常乐意为您解答！( •̀ ω •́ )✧