分治策略

分治策略是對於一個規模為n的問題,若該問題可以容易地解決(比如說規模n較小)則直接解決,否則將其分解為k個規模較小的子問題,這些子問題互相獨立且與原問題形式相同,遞歸地解這些子問題,然後將各子問題的解合併得到原問題的解。

基本介紹

  • 中文名:分治策略
  • 類型:策略
  • 步驟:分解,解決,合併
  • 隸屬:算法
基本定義,分治法步驟,典型例題,

基本定義

這種算法設計策略叫做分治法。 如果原問題可分割成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)子問題思想,它幾乎總是比子問題規模不等的做法要好。

典型例題

在對線性表的操作中,經常需要查找某一個元素線上性表中的位置。此問題的輸入是待查元素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]中任一元素的值。
遞歸求解(Conquer):通過遞歸調用快速排序算法分別對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.
歸併就是將多個有序的數列合成一個有序的數列。將兩個有序序列合併為一個有序序列叫二路歸併(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.

相關詞條

熱門詞條

聯絡我們