335
技術社區[雲棲]
五大常用算法 之 分治法
一、基本概念
在計算機科學中，分治法是一種很重要的算法思想。字麵上的解釋是“分而治之”，就是把一個複雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題，直到最後子問題可以簡單的直接求解，原問題的解即子問題的解的合並。這個技巧是很多高效算法的基礎，如排序算法(快速排序，歸並排序)，傅立葉變換(快速傅立葉變換)等。
任何一個可以用計算機求解的問題所需的計算時間都與其規模有關。問題的規模越小，越容易直接求解，解題所需的計算時間也越少。例如，對於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(P):
if |P|≤n0
then return BASE(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的規模；n0為一閾值，表示當問題P的規模不超過n0時，問題已容易直接解出，不必再繼續分解。BASE(P)是該分治法中的基本子算法，用於直接解小規模的問題P。因此，當P的規模不超過n0時，直接用算法BASE(P)求解。算法MERGE(y1,y2,...,yk)是該分治法中的合並子算法，用於將P的子問題P1 ,P2 ,...,Pk的相應的解y1,y2,...,yk合並為P的解。
五、分治法的複雜性分析
一個分治法將規模為n的問題分成k個規模為n／m的子問題分而解之。設分解閥值n0=1，且BASE解規模為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）漢諾塔
七、依據分治法設計程序時的思維過程
實際上就是類似於數學歸納法，找到解決本問題的求解方程公式，然後根據方程公式設計遞歸程序。
1、一定是先找到最小問題規模時的求解方法；
2、然後考慮隨著問題規模增大時的求解方法；
3、找到求解的遞歸函數式後（各種規模或因子），設計遞歸程序即可。
八、舉例說明——漢諾塔問題（遞歸解決）
1、問題描述：
問題的曆史淵源：漢諾塔問題來自一個古老的傳說：在世界剛被創建的時候有一座鑽石寶塔（塔A），其上有64個金碟。所有碟子按從大到小的次序從塔底堆放至塔頂。緊挨著這座塔有另外兩個鑽石寶塔（塔B和塔C）。從世界創始之日起，婆羅門的牧師們就一直在試圖把塔A上的碟子移動到塔C上去，其間借助於塔B的幫助。每次隻能移動一個碟子，任何時候都不能把一個碟子放在比它小的碟子上麵。當牧師們完成任務時，世界末日也就到了。
問題提出：有三個塔(分別為A號，B號和C號)。開始時，有n個圓形盤以從上到下、從小到大的次序堆疊在A塔上。現要將A塔上的所有圓形盤，借助B塔，全部移動到C塔上，且仍按照原來的次序堆疊。
移動的規則：這些圓形盤隻能在3個塔間進行移動。一次隻能移動一個盤子，且任何時候都不允許將較大的盤子壓在比它小的盤子的上麵。
2、問題分析：
現在，我們具體討論一下漢諾塔問題的解法：
對於A塔上有n個圓形盤，要將n個圓形盤移動至C塔，則應先將n-1個圓形盤（從上到下，從小到大）移動到B塔，然後將A塔的第n個圓形盤移動至C塔。
然後，下麵的步驟就是將B塔的n-1個圓形盤移動至C塔的過程，其具體過程同上一步相似，先將n-2個圓形盤移動至A塔，然後再將B塔的第n-1個圓形盤移動至A塔。
依次遞歸類推，直到最後隻有一個圓形盤時截止。
首先，我們設置移動函數Move(int disc, char srcT, char dstT);
此函數聲明的意義是：將disc盤從srcT塔移動至dstT塔，並打印移動信息。
現在，我們設置函數Hanno(int N, char A, char B, char C);
此函數聲明的意義是：借助於B塔，將N個圓形盤從A塔移動至C塔。
那麼該函數所實現的步驟是：
如果N == 1：
====>>>
直接將N個圓形盤從A塔移動至C塔；
如果N != 1：
====>>>
（1）、首先，借助於C塔，將N-1個圓形盤由A塔移動至B塔，此處簡化為函數即為Hanno(N-1, A, C, B)；
（2）、然後，將A塔的第N個圓形盤移動至C塔，此處簡化為函數即為Move(N,A,C)；
（3）、最後，借助A塔，將N-1個圓形盤由B塔移動至C塔，此處簡化為函數即為Hanno(N-1,B,A,C)。
3、移動次數計算：
首先，設Count(n)為移動n個圓形盤所需的步數：
則有：
Count(1) = 1;
Count(n) = Count(n-1)*2 + 1;
即：Count(n) = 2^n -1;
4、代碼實現：
#include <stdio.h>
void Move(int n, char srcT, char dstT);
void Hanno(int N, char A, char B, char C);
int main(){
int n;
char t_first,t_second,t_third;
t_first = 'A';
t_second = 'B';
t_third = 'C';
printf("Please input the number of round-disc:\n");
scanf("%d",&n);
printf("The movement steps:\n");
Hanno(n,t_first,t_second,t_third);
return 0;
}
void Move(int n, char srcT, char dstT)
{
// printf("Move disc %d from tower %c to tower %c !\n", n, srcT, dstT);
printf("%c-->%c\n",srcT,dstT);
}
void Hanno(int N, char A, char B, char C)
{
if(N == 1)
Move(1,A,C);
else
{
Hanno(N-1,A,C,B);
Move(N,A,C);
Hanno(N-1,B,A,C);
}
}
當n=4時，所得到的結果為：
Please input the number of round-disc: 4 The movement steps: A-->B A-->C B-->C A-->B C-->A C-->B A-->B A-->C B-->C B-->A C-->A B-->C A-->B A-->C B-->C
最後更新：2017-04-03 05:39:52