基本介紹
- 中文名：分治策略
- 類型：策略
- 步驟：分解，解決，合併
- 隸屬：算法
基本定義,分治法步驟,典型例題,
基本定義
這種算法設計策略叫做分治法。 如果原問題可分割成k個子問題，1<k≤n ，且這些子問題都可解，並可利用這些子問題的解求出原問題的解，那么這種分治法就是可行的。由分治法產生的子問題往往是原問題的較小模式，這就為使用遞歸技術提供了方便。在這種情況下，反覆套用分治手段，可以使子問題與原問題類型一致而其規模卻不斷縮小，最終使子問題縮小到很容易直接求出其解。這自然導致遞歸過程的產生。分治與遞歸像一對孿生兄弟，經常同時套用在算法設計之中，並由此產生許多高效算法。 分治法所能解決的問題一般具有以下幾個特徵：
該問題的規模縮小到一定的程度就可以容易地解決；
該問題可以分解為若干個規模較小的相同問題，即該問題具有最優子結構性質。
利用該問題分解出的子問題的解可以合併為該問題的解；
該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子子問題。
上述的第一條特徵是絕大多數問題都可以滿足的，因為問題的計算複雜性一般是隨著問題規模的增加而增加；第二條特徵是套用分治法的前提，它也是大多數問題可以滿足的，此特徵反映了遞歸思想的套用；第三條特徵是關鍵，能否利用分治法完全取決於問題是否具有第三條特徵，如果具備了第一條和第二條特徵，而不具備第三條特徵，則可以考慮用貪心法或動態規劃法。第四條特徵涉及到分治法的效率，如果各子問題是不獨立的，則分治法要做許多不必要的工作，重複地解公共的子問題，此時雖然可用分治法，但一般用動態規劃法較好。
分治法步驟
分解：將原問題分解為若干個規模較小，相互獨立，與原問題形式相同的子問題；
解決：若子問題規模較小而容易被解決則直接解，否則遞歸地解各個子問題；
合併：將各個子問題的解合併為原問題的解。
它的一般的算法設計模式如下：
Divide-and-Conquer(P)
1. if |P|≤n0
2. then return(ADHOC(P))
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時，問題已容易直接解出，不必再繼續分解。ADH
OC(P)是該分治法中的基本子算法，用於直接解小規模的問題P。因此，當P的規模不超過n0時，直接用算法ADHOC(P)求解。
算法MERGE(y1,y2,...,yk)是該分治法中的合併子算法，用於將P的子問題P1 ,P2 ,...,Pk的相應的解y1,y2,...,yk合併為P
的解。
根據分治法的分割原則，原問題應該分為多少個子問題才較適宜？各個子問題的規模應該怎樣才為適當？這些問題很難予以肯定的回
答。但人們從大量實踐中發現，在用分治法設計算法時，最好使子問題的規模大致相同。換句話說，將一個問題分成大小相等的k個子問題的處理方法是行之有效的。許多問題可以取k=2。這種使子問題規模大致相等的做法是出自一種平衡(balancing)子問題的思想，它幾乎總是比子問題規模不等的做法要好。
典型例題
例1：二分查找
在對線性表的操作中，經常需要查找某一個元素線上性表中的位置。此問題的輸入是待查元素x和線性表L，輸出為x在L中的位置或者x不在L中的信息。比較自然的想法是一個一個地掃描L的所有元素，直到找到x為止。這種方法對於有n個元素的線性表在最壞情況下需要n次比較。一般來說，如果沒有其他的附加信息，在有n個元素的線性表中查找一個元素在最壞情況下都需要n次比較。下面我們考慮一種簡單的情況。假設該線性表已經排好序了，不妨設它按照主鍵的遞增順序排列（即由小到大排列）。在這種情況下，我們是否有改進查找效率的可能呢？
如果線性表里只有一個元素，則只要比較這個元素和x就可以確定x是否線上性表中。因此這個問題滿足分治法的第一個適用條件；同時我們注意到對於排好序的線性表L有以下性質：比較x和L中任意一個元素L[i]，若x=L[i]，則x在L中的位置就是i；如果x<L[i]，由於L是遞增排序的，因此假如x在L中的話，x必然排在L[i]的前面，所以我們只要在L[i]的前面查找x即可；如果x>L[i]，同理我們只要在L[i]的後面查找x即可。無論是在L[i]的前面還是後面查找x，其方法都和在L中查找x一樣，只不過是線性表的規模縮小了。這就說明了此問題滿足分治法的第二個和第三個適用條件。很顯然此問題分解出的子問題相互獨立，即在L[i]的前面或後面查找x是獨立的子問題，因此滿足分治法的第四個適用條件。
於是我們得到利用分治法在有序表中查找元素的算法。
function Binary_Search(L,a,b,x);
begin
if a>b then return(-1)
else begin
m:=(a+b) div 2;
if x=L[m] then return(m)
else if x>L[m]
then return(Binary_Search(L,m+1,b,x));
else return(Binary_Search(L,a,m-1,x));
end;
end;
在以上算法中，L為排好序的線性表，x為需要查找的元素，b,a分別為x的位置的上下界，即如果x在L中，則x在L[a..b]中。每次我們用L中間的元素L[m]與x比較，從而確定x的位置範圍。然後遞歸地縮小x的範圍，直到找到x。
例2：快速排序
快速排序的基本思想是基於分治法的。對於輸入的子序列L[p..r]，如果規模足夠小則直接進行排序，否則分三步處理：
分解(Divide)：將輸入的序列L[p..r]劃分成兩個非空子序列L[p..q]和L[q+1..r]，使L[p..q]中任一元素的值不大於L[q+1..r]中任一元素的值。
合併(Merge)：由於對分解出的兩個子序列的排序是就地進行的，所以在L[p..q]和L[q+1..r]都排好序後不需要執行任何計算L[p..r]就已排好序。
這個解決流程是符合分治法的基本步驟的。因此，快速排序法是分治法的經典套用實例之一。
程式代碼如下：
program kspv;
const n=7;
type
arr=array[1..n] of integer;
var
a:arr;
i:integer;
procedure quicksort(var b:arr; s,t:integer);
var i,j,x:integer;
begin
i:=s;j:=t;x:=b[i];
repeat
while (b[j]>=x) and (j>i) do j:=j-1;
if j>i then begin b[i]:=b[j];i:=i+1;end;
while (b[i]<=x) and (i<j) do i:=i+1;
if i<j then begin b[j]:=b[i];j:=j-1; end
until i=j;
b[i]:=x;
i:=i+1;j:=j-1;
if s<j then quicksort(b,s,j);
if i<t then quicksort(b,i,t);
end;
begin
write('input data:');
for i:=1 to n do read(a[i]);
quicksort(a,1,n);
write('output data:');
for i:=1 to n do write(a[i]:6);
writeln;
end.
例3：歸併排序
歸併就是將多個有序的數列合成一個有序的數列。將兩個有序序列合併為一個有序序列叫二路歸併(merge).歸併排序就是n長度為1的子序列,兩兩歸併最後變為有序的序列。
程式代碼如下：
program gbpx;
const maxn=7;
type arr=array[1..maxn] of integer;
var a,b,c:arr;
i:integer;
procedure merge(r:arr;l,m,n:integer;var r2:arr);
var i,j,k,p:integer;
begin
i:=l;j:=m+1;k:=l-1;
while (i<=m)and (j<=n) do
begin
k:=k+1;
if r[i]<=r[j] then begin r2[k]:=r[i];i:=i+1 end
else begin r2[k]:=r[j];j:=j+1 end
end;
if i<=m then
for p:=i to m do begin k:=k+1;r2[k]:=r[p] end;
if j<=n then
for p:=j to n do begin k:=k+1;r2[k]:=r[p] end;
end;
procedure mergesort( var r,r1:arr;s,t:integer);
var k:integer; c:arr;
begin
if s=t then r1[s]:=r[s] else
begin
k:=(s+t) div 2;
mergesort(r,c,s,k);
mergesort(r,c,k+1,t);
merge(c,s,k,t,r1)
end;
end;
begin
write('Enter data:');
for i:= 1 to maxn do
read(a[i]);
mergesort(a,b,1,maxn);
for i:=1 to maxn do
write(b[i]:9);
end.
