-
分治算法
鎖定
- 中文名
- 分治算法
- 別 名
- 分治法
- 適用領域
- 計算機科學;數學
- 應用學科
- 計算機;數學
分治算法基本思想
當我們求解某些問題時,由於這些問題要處理的數據相當多,或求解過程相當複雜,使得直接求解法在時間上相當長,或者根本無法直接求出。對於這類問題,我們往往先把它分解成幾個子問題,找到求出這幾個子問題的解法後,再找到合適的方法,把它們組合成求整個問題的解法。如果這些子問題還較大,難以解決,可以再把它們分成幾個更小的子問題,以此類推,直至可以直接求出解為止。這就是分治策略的基本思想。
分治算法二分法
利用分治策略求解時,所需時間取決於分解後子問題的個數、子問題的規模大小等因素,而二分法,由於其劃分的簡單和均勻的特點,是經常採用的一種有效的方法,例如二分法檢索。
分治算法解題步驟
分治法解題的一般步驟(如圖1):
(1)分解,將要解決的問題劃分成若干規模較小的同類問題;
(2)求解,當子問題劃分得足夠小時,用較簡單的方法解決;
(3)合併,按原問題的要求,將子問題的解逐層合併構成原問題的解。
分治算法應用實例
下面通過實例加以説明:
分治算法找出偽幣
給你一個裝有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。比較這兩組,可以得到一個較輕的組。由於這個組只有兩個硬幣,因此不必再細分。比較組中兩個硬幣的重量,可以立即知道哪一個硬幣輕一些。較輕的硬幣就是所要找的偽幣。
分治算法求最值
void maxmin1(int A[],int n,int *max,int *min) { int i; *min=*max=A[0]; for(i=0;i <= n;i++) { if(A[i]> *max) *max= A[i]; if(A[i] < *min) *min= A[i]; } }
上面這個算法需比較2(n-1)次。能否找到更好的算法呢?我們用分治策略來討論。
把n個元素分成兩組:
A1={A[1],...,A[int(n/2)]}和A2={A[INT(N/2)+1],...,A[N]}
例如有下面一組元素:-13,13,9,-5,7,23,0,15。用分治策略比較的算法如下:
void maxmin2(int A[],int i,int j,int *max,int *min) /*A存放輸入的數據,i,j存放數據的範圍,初值為0,n-1,*max,*min 存放最大和最小值*/ { int mid,max1,max2,min1,min2; if (j==i) { 最大和最小值為同一個數; return; } if (j-1==i) { 將兩個數直接比較,求得最大和最小值; return; } mid=(i+j)/2; 求i~mid之間的最大最小值分別為max1,min1; 求mid+1~j之間的最大最小值分別為max2,min2; 比較max1和max2,大的就是最大值; 比較min1和min2,小的就是最小值; }
分治算法棋盤覆蓋
題目:在一個(2^k)*(2^k)個方格組成的棋盤上,有一個特殊方格與其他方格不同,稱為特殊方格,稱這樣的棋盤為一個特殊棋盤。我們要求對棋盤的其餘部分用L型方塊填滿(注:L型方塊由3個單元格組成。即圍棋中比較忌諱的愚形三角,方向隨意),且任何兩個L型方塊不能重疊覆蓋。L型方塊的形態如下:
題目的解法使用分治法,即子問題和整體問題具有相同的形式。我們對棋盤做一個分割,我們可以看到棋盤被切成4個一樣大小的子棋盤,特殊方塊必定位於四個子棋盤中的一個。這樣對於每個子棋盤又各有一個“特殊方塊”,我們對每個子棋盤繼續這樣分割,直到子棋盤的大小為1為止。
用到的L型方塊需要(4^k-1)/3 個,算法的時間是O(4^k),是漸進最優解法。
#include<stdio.h> //#include<conio.h> //#include<math.h> int title=1; int board[64][64]; void chessBoard(inttr,inttc,intdr,intdc,intsize) { int s,t; if(size==1) return; t=title++; s=size/2; if(dr<tr+s&&dc<tc+s) chessBoard(tr,tc,dr,dc,s); else { board[tr+s-1][tc+s-1]=t; chessBoard(tr,tc,tr+s-1,tc+s-1,s); } if(dr<tr+s&&dc>=tc+s) chessBoard(tr,tc+s,dr,dc,s); else { board[tr+s-1][tc+s]=t; chessBoard(tr,tc+s,tr+s-1,tc+s,s); } if(dr>=tr+s&&dc<tc+s) chessBoard(tr+s,tc,dr,dc,s); else { board[tr+s][tc+s-1]=t; chessBoard(tr+s,tc,tr+s,tc+s-1,s); } if(dr>=tr+s&&dc>=tc+s) chessBoard(tr+s,tc+s,dr,dc,s); else { board[tr+s][tc+s]=t; chessBoard(tr+s,tc+s,tr+s,tc+s,s); } } void main() { int dr=0,dc=0,s=1,i=0,j=0; printf("printinthesizeofchess:\n"); scanf("%d",&s); printf("printinspecalpointx,y:\n"); scanf("%d%d",&dr,&dc); if(dr<s&&dc<s) { chessBoard(0,0,dr,dc,s); for(i=0;i<s;i++) { for(j=0;j<s;j++) { printf("%4d",board[i][j]); } printf("\n"); } } else printf("thewrongspecalpoint!!\n"); getch(); }
分治算法應用場景
運用分治策略解決的問題一般來説具有以下特點:
1、原問題可以分解為多個子問題
這些子問題與原問題相比,只是問題的規模有所降低,其結構和求解方法與原問題相同或相似。
2、原問題在分解過程中,遞歸地求解子問題
由於遞歸都必須有一個終止條件,因此,當分解後的子問題規模足夠小時,應能夠直接求解。
3、在求解並得到各個子問題的解後
應能夠採用某種方式、方法合併或構造出原問題的解。