作者：進(jìn)階的HelloWorld
在計(jì)算機(jī)科學(xué)中，分支算法是一種很重要的算法。任何一個(gè)可以用計(jì)算機(jī)求解的問題所需的計(jì)算時(shí)間都與其規(guī)模有關(guān)。問題的規(guī)模越小，越容易直接求解，解題所需的計(jì)算時(shí)間也越少。把一個(gè)復(fù)雜的問題分成兩個(gè)或更多的相同或相似的子問題，再把子問題分成更小的子問題……直到最后子問題可以簡(jiǎn)單的直接求解，原問題的解即子問題的解的合并。這個(gè)技巧是很多高效算法的基礎(chǔ)，如排序算法(快速排序，歸并排序)，傅立葉變換(快速傅立葉變換)。這篇文章從概念、算法策略、使用場(chǎng)景、經(jīng)典案例、算法步驟等角度簡(jiǎn)要介紹了分治算法的作用并在經(jīng)典案例中也給出了相應(yīng)的代碼。
文章轉(zhuǎn)載自 微信公眾號(hào) 五分鐘學(xué)算法（id: CXYxiaowu）
??分治算法，根據(jù)字面意思解釋是“分而治之”，就是把一個(gè)復(fù)雜的問題分成兩個(gè)或更多的相同或相似的子問題，再把子問題分成更小的子問題……直到最后子問題可以簡(jiǎn)單的直接求解，原問題的解即子問題的解的合并。
??分治策略：對(duì)于一個(gè)規(guī)模為 n 的問題，若該問題可以容易地解決（比如說規(guī)模 n 較?。﹦t直接解決，否則將其分解為 k 個(gè)規(guī)模較小的子問題，這些子問題互相獨(dú)立且與原問題形式相同，遞歸地解這些子問題，然后將各子問題的解合并得到原問題的解。
??在平時(shí)日常生活中，分治思想也是隨處可見的。例如：當(dāng)我們打牌時(shí)，在進(jìn)行洗牌時(shí)，若牌的數(shù)目較多，一個(gè)人洗不過來，則會(huì)將牌進(jìn)行分堆，單獨(dú)洗一小堆牌是相對(duì)容易的，每一堆牌都洗完之后再放到一起，則完成洗牌過程。
??（1）該問題的規(guī)?？s小到一定的程度就可以容易地解決。
??（2）該問題可以分解為若干個(gè)規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。
??（3）利用該問題分解出的子問題的解可以合并為該問題的解。
??（4）該問題所分解出的各個(gè)子問題是相互獨(dú)立的，即子問題之間不包含公共的子問題。
分治法在每一層遞歸上都有三個(gè)步驟：
??（1）分解：將原問題分解為若干個(gè)規(guī)模較小，相互獨(dú)立，與原問題形式相同的子問題。
??（2）求解：若子問題規(guī)模較小而容易被解決則直接解，否則遞歸地解各個(gè)子問題。
??（3）合并：將各個(gè)子問題的解合并為原問題的解。
Divide-and-Conquer(P)
if |P| ≤ n0
then return(ADHOC(P))
將P分解為較小的子問題 P1 ,P2 ,...,Pk
for i←1 to k
do yi ← Divide-and-Conquer(Pi) △ 遞歸解決Pi
T ← MERGE(y1,y2,...,yk) △ 合并子問題
return(T)
??其中，|P| 表示問題 P 的規(guī)模，n0 為一閾值，表示當(dāng)問題 P 的規(guī)模不超過 n0 時(shí)，問題已容易直接解出，不必再繼續(xù)分解。ADHOC(P) 是該分治法中的基本子算法，用于直接解小規(guī)模的問題 P。因此，當(dāng) P 的規(guī)模不超過n0 時(shí)直接用算法 ADHOC(P) 求解。算法 MERGE(y1,y2,…,yk) 是該分治法中的合并子算法，用于將 P 的子問題 P1 ,P2 ,…,Pk 的相應(yīng)的解 y1 , y2 ,…, yk 合并為 P 的解。
??二分查找是典型的分治算法的應(yīng)用。需要注意的是，二分查找的前提是查找的數(shù)列是有序的。
算法流程：
??（1）選擇一個(gè)標(biāo)志 i 將集合分為二個(gè)子集合。
??（2）判斷標(biāo)志 L(i) 是否能與要查找的值 des 相等，相等則直接返回。
??（3）否則判斷 L(i) 與 des 的大小。
??（4）基于判斷的結(jié)果決定下步是向左查找還是向右查找。
??（5）遞歸繼續(xù)上面的步驟。
??通過二分查找的流程可以看出，二分查找是將原有序數(shù)列劃分為左右兩個(gè)子序列，然后在對(duì)兩個(gè)子序列中的其中一個(gè)在進(jìn)行劃分，直至查找成功。
代碼實(shí)現(xiàn)：
#include<string.h>
#include<stdio.h>
int k;
int binarysearch(int a[],int x,int low,int high)//a表示需要二分的有序數(shù)組（升序），x表示需要查找的數(shù)字，low，high表示高低位
{
if(low>high)
{
return -1;//沒有找到
}
int mid=(low+high)/2;
if(x==a[mid])//找到x
{
k=mid;
return x;
}
else if(x>a[mid]) //x在后半部分
{
binarysearch(a,x,mid+1,high);//在后半部分繼續(xù)二分查找
}
else//x在前半部分
{
binarysearch(a,x,low,mid-1);
}
}
int main()
{
int a[10]={1,2,3,4,5,6,7,8,9,10};
printf('請(qǐng)輸入需要查找的正數(shù)字：\n');
int x;
scanf('%d',&x);
int r=binarysearch(a,x,0,9);
if(r==-1)
{
printf('沒有查到\n');
}
else
{
printf('查到了,在數(shù)列的第%d個(gè)位置上\n',k+1);
}
return 0;
}
問題描述：
??有1，2，3，4個(gè)數(shù)，問你有多少種排列方法，并輸出排列。
問題分析：
??若采用分治思想進(jìn)行求解，首先需要把大問題分解成很多的子問題，大問題是所有的排列方法。那么我們分解得到的小問題就是以 1 開頭的排列，以 2 開頭的排列，以 3 開頭的排列，以 4 開頭的排列?，F(xiàn)在這些問題有能繼續(xù)分解，比如以 1 開頭的排列中，只確定了 1 的位置，沒有確定 2 ，3 ，4 的位置，把 2，3，4 三個(gè)又看成大問題繼續(xù)分解，2 做第二個(gè)，3 做第二個(gè)，或者 4 做第二個(gè)。一直分解下去，直到分解成的子問題只有一個(gè)數(shù)字的時(shí)候，不能再分解。只有一個(gè)數(shù)的序列只有一種排列方式，則子問題求解容易的多。
代碼實(shí)現(xiàn)：
public class Test {
public static void main(String[] args) {
int[] arr = { 1, 2, 3, 4 };
fullSort(arr, 0, arr.length - 1);
}
public static void fullSort(int[] arr, int start, int end) {
// 遞歸終止條件
if (start == end) {
for (int i : arr) {
System.out.print(i);
}
System.out.println();
return;
}
for (int i = start; i <= end; i++) {
swap(arr, i, start);
fullSort(arr, start + 1, end);
swap(arr, i, start);
}
}
private static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
??歸并排序：歸并（Merge）排序法是將兩個(gè)（或兩個(gè)以上）有序表合并成一個(gè)新的有序表，即把待排序序列分為若干個(gè)子序列，每個(gè)子序列是有序的。然后再把有序子序列合并為整體有序序列。即先劃分為兩個(gè)部分，最后進(jìn)行合并。
歸并排序
偽代碼：
算法 MergeSort(A, p, r)
輸入：數(shù)組A[p...r]
輸出：有序數(shù)組A
if(p < r)
then q <- (p+r)/2//折半劃分
MergeSort(A, p ,q)//子問題1
MergeSort(A, p ,q)//子問題2
Merge(A, p ,q, r)//合并求解
代碼實(shí)現(xiàn)：
public class MergeSort {
//兩路歸并算法，兩個(gè)排好序的子序列合并為一個(gè)子序列
public void merge(int []a,int left,int mid,int right){
int []tmp=new int[a.length];//輔助數(shù)組
int p1=left,p2=mid+1,k=left;//p1、p2是檢測(cè)指針，k是存放指針
while(p1<=mid && p2<=right){
if(a[p1]<=a[p2])
tmp[k++]=a[p1++];
else
tmp[k++]=a[p2++];
}
while(p1<=mid) tmp[k++]=a[p1++];//如果第一個(gè)序列未檢測(cè)完，直接將后面所有元素加到合并的序列中
while(p2<=right) tmp[k++]=a[p2++];//同上
//復(fù)制回原素組
for (int i = left; i <=right; i++)
a[i]=tmp[i];
}
public void mergeSort(int [] a,int start,int end){
if(start<end){//當(dāng)子序列中只有一個(gè)元素時(shí)結(jié)束遞歸
int mid=(start+end)/2;//劃分子序列
mergeSort(a, start, mid);//對(duì)左側(cè)子序列進(jìn)行遞歸排序
mergeSort(a, mid+1, end);//對(duì)右側(cè)子序列進(jìn)行遞歸排序
merge(a, start, mid, end);//合并
}
}
}
??快速排序的基本思想：當(dāng)前待排序的無序區(qū)為 A[low..high] ，利用分治法可將快速排序的基本思想描述為：
（1）分解：
??在A[low..high]中任選一個(gè)記錄作為基準(zhǔn)(pivot)，以此基準(zhǔn)將當(dāng)前無序區(qū)劃分為左、右兩個(gè)較小的子區(qū)間R[low..pivotpos-1) 和 R[pivotpos+1..high] ，并使左邊子區(qū)間中所有記錄的關(guān)鍵字均小于等于基準(zhǔn)記錄(不妨記為pivot)的關(guān)鍵字 pivot.key，右邊的子區(qū)間中所有記錄的關(guān)鍵字均大于等于pivot.key，而基準(zhǔn)記錄pivot則位于正確的位置( pivotpos )上，它無須參加后續(xù)的排序。
（2）求解：
??通過遞歸調(diào)用快速排序?qū)ψ?、右子區(qū)間R[low..pivotpos-1]和R[pivotpos+1..high]快速排序。
（3）合并：
??因?yàn)楫?dāng)'求解'步驟中的兩個(gè)遞歸調(diào)用結(jié)束時(shí)，其左、右兩個(gè)子區(qū)間已有序。對(duì)快速排序而言，'組合'步驟無須做什么，可看作是空操作。
快速排序
代碼實(shí)現(xiàn)：
#include <iostream>
using namespace std;
void QuickSort(int arr[], int low, int high){
if (high <= low) return;
int i = low;
int j = high + 1;
int key = arr[low];
while (true)
{
/*從左向右找比key大的值*/
while (arr[++i] < key)
{
if (i == high){
break;
}
}
/*從右向左找比key小的值*/
while (arr[--j] > key)
{
if (j == low){
break;
}
}
if (i >= j) break;
/*交換i,j對(duì)應(yīng)的值*/
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
/*中樞值與j對(duì)應(yīng)值交換*/
int temp = arr[low];
arr[low] = arr[j];
arr[j] = temp;
QuickSort(arr, low, j - 1);
QuickSort(arr, j + 1, high);
}
漢諾塔（Hanoi Tower）問題也是一個(gè)經(jīng)典的遞歸問題，該問題描述如下：
漢諾塔問題：古代有一個(gè)梵塔，塔內(nèi)有三個(gè)座A、B、C，A座上有64個(gè)盤子，盤子大小不等，大的在下，小的在上。有一個(gè)和尚想把這個(gè)盤子從A座移到B座，但每次只能允許移動(dòng)一個(gè)盤子，并且在移動(dòng)過程中，3個(gè)座上的盤子始終保持大盤在下，小盤在上。
① 如果只有 1 個(gè)盤子，則不需要利用 B 塔，直接將盤子從 A 移動(dòng)到 C 。
② 如果有 2 個(gè)盤子，可以先將盤子 2 上的盤子 1 移動(dòng)到 B ；將盤子 2 移動(dòng)到 C ；將盤子 1 移動(dòng)到 C 。這說明了：可以借助 B 將 2 個(gè)盤子從 A 移動(dòng)到 C ，當(dāng)然，也可以借助 C 將 2 個(gè)盤子從 A 移動(dòng)到 B 。
③ 如果有 3 個(gè)盤子，那么根據(jù) 2 個(gè)盤子的結(jié)論，可以借助 C 將盤子 3 上的兩個(gè)盤子從 A 移動(dòng)到 B ；將盤子 3 從 A 移動(dòng)到 C ，A 變成空座；借助 A 座，將 B 上的兩個(gè)盤子移動(dòng)到 C 。
④ 以此類推，上述的思路可以一直擴(kuò)展到 n 個(gè)盤子的情況，將將較小的 n-1個(gè)盤子看做一個(gè)整體，也就是我們要求的子問題，以借助 B 塔為例，可以借助空塔 B 將盤子A上面的 n-1 個(gè)盤子從 A 移動(dòng)到 B ；將A 最大的盤子移動(dòng)到 C ， A 變成空塔；借助空塔 A ，將 B 塔上的 n-2 個(gè)盤子移動(dòng)到 A，將 C 最大的盤子移動(dòng)到 C， B 變成空塔。。。
代碼實(shí)現(xiàn)：
public static void hanoi(int n, String sourceTower, String tempTower, String targetTower) {
if (n == 1) {
//如果只有一個(gè)盤子1，那么直接將其從sourceTower移動(dòng)到targetTower
move(n, sourceTower, targetTower);
} else {
//將（盤子n-1~盤子1）由sourceTower經(jīng)過targetTower移動(dòng)到tempTower
hanoi(n - 1, sourceTower, targetTower, tempTower);
//移動(dòng)盤子n由sourceTower移動(dòng)到targetTower
move(n, sourceTower, targetTower);
//把之前移動(dòng)到tempTower的（盤子n-1~盤子1），由tempTower經(jīng)過sourceTower移動(dòng)到targetTower
hanoi(n - 1, tempTower, sourceTower, targetTower);
}
}
//盤子n的從sourceTower->targetTower的移動(dòng)
private static void move(int n, String sourceTower, String targetTower) {
System.out.println('第' + n + '號(hào)盤子 move:' + sourceTower + '--->' + targetTower);
}
??分治法將規(guī)模為 n 的問題分成 k 個(gè)規(guī)模為 n／m 的子問題去解。設(shè)分解閥值 n0 = 1 ，且 adhoc 解規(guī)模為 1 的問題耗費(fèi) 1 個(gè)單位時(shí)間。再設(shè)將原問題分解為 k 個(gè)子問題以及用 merge 將 k 個(gè)子問題的解合并為原問題的解需用 f(n) 個(gè)單位時(shí)間。用T(n)表示該分治法解規(guī)模為 |P| = n 的問題所需的計(jì)算時(shí)間，則有：
??T（n）= k T(n/m) + f(n)
文章作者：進(jìn)階的HelloWorld
聯(lián)系客服
