分治策略2課件

分治法的適用條件分治法所能解決的問題一般具有以下幾個特征：該問題的規(guī)?？s小到一定的程度就可以容易地解決；該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)利用該問題分解出的子問題的解可以合并為該問題的解；該問題所分解出的各個子問題是相互獨(dú)立的，即子問題之間不包含公共的子問題。1因為問題的計算復(fù)雜性一般是隨著問題規(guī)模的增加而增加，因此大部分問題滿足這個特征。這條特征是應(yīng)用分治法的前提，它也是大多數(shù)問題可以滿足的，此特征反映了遞歸思想的應(yīng)用能否利用分治法完全取決于問題是否具有這條特征，如果具備了前兩條特征，而不具備第三條特征，則可以考慮貪心算法或動態(tài)規(guī)劃。這條特征涉及到分治法的效率，如果各子問題是不獨(dú)立的，則分治法要做許多不必要的工作，重復(fù)地解公共的子問題，此時雖然也可用分治法，但一般用動態(tài)規(guī)劃較好。 使用分治法的前提是問題是可分治的。所謂可分治，是指滿足下列兩點：（1）可分解 問題能分解為更小、更容易解決的子問題。（2）可綜合 由子問題的綜合，可以解決真?zhèn)€問題。2分治法的基本步驟divide-and-conquer(P){if(|P|<=n0)adhoc(P);//解決小規(guī)模的問題

dividePintosmallersubinstancesP1,P2,...,Pk；//分解問題

for(i=1,i<=k,i++)yi=divide-and-conquer(Pi);//遞歸的解各子問題

returnmerge(y1,...,yk);//將各子問題的解合并為原問題的解}3人們從大量實踐中發(fā)現(xiàn)，在用分治法設(shè)計算法時，最好使子問題的規(guī)模大致相同。即將一個問題分成大小相等的k個子問題的處理方法是行之有效的。這種使子問題規(guī)模大致相等的做法是出自一種平衡(balancing)子問題的思想，它幾乎總是比子問題規(guī)模不等的做法要好。4分治法的復(fù)雜性分析一個分治法將規(guī)模為n的問題分成k個規(guī)模為n／m的子問題去解。設(shè)分解閥值n0=1，且adhoc解規(guī)模為1的問題耗費(fèi)1個單位時間。再設(shè)將原問題分解為k個子問題以及用merge將k個子問題的解合并為原問題的解需用f(n)個單位時間。用T(n)表示該分治法解規(guī)模為|P|=n的問題所需的計算時間，則有：5通過迭代法求得方程的解：注意：遞歸方程及其解只給出n等于m的方冪時T(n)的值，但是如果認(rèn)為T(n)足夠平滑，那么由n等于m的方冪時T(n)的值可以估計T(n)的增長速度。通常假定T(n)是單調(diào)上升的，從而當(dāng)mi≤n<mi+1時，T(mi)≤T(n)<T(mi+1)。

6二分搜索技術(shù)給定已按升序排好序的n個元素a[0:n-1]，現(xiàn)要在這n個元素中找出一特定元素x。分析：該問題的規(guī)?？s小到一定的程度就可以容易地解決；該問題可以分解為若干個規(guī)模較小的相同問題;分解出的子問題的解可以合并為原問題的解；分解出的各個子問題是相互獨(dú)立的。分析：很顯然此問題分解出的子問題相互獨(dú)立，即在a[i]的前面或后面查找x是獨(dú)立的子問題，因此滿足分治法的第四個適用條件。7給定已按升序排好序的n個元素a[0:n-1]，現(xiàn)要在這n個元素中找出一特定元素x。據(jù)此容易設(shè)計出二分搜索算法：template<classType>intBinarySearch(Typea[],constType&x,intl,intr){while(r>=l){intm=(l+r)/2;if(x==a[m])returnm;if(x<a[m])r=m-1;elsel=m+1;}return-1;}算法復(fù)雜度分析：每執(zhí)行一次算法的while循環(huán)，待搜索數(shù)組的大小減少一半。因此，在最壞情況下，while循環(huán)被執(zhí)行了O(logn)次。循環(huán)體內(nèi)運(yùn)算需要O(1)時間，因此整個算法在最壞情況下的計算時間復(fù)雜性為O(logn)。8大整數(shù)的乘法分析算法的計算復(fù)雜性時，加和乘當(dāng)作基本運(yùn)算處理，即執(zhí)行一次加法和乘法運(yùn)算所需的計算時間當(dāng)作一個僅取決于計算機(jī)硬件處理速度的常數(shù)。有時我們要處理很大的整數(shù)，無法用硬件精確的表示時，若用浮點數(shù)表示，只能近似的表示。我們需要用軟件的方法來解決。9請設(shè)計一個有效的算法，可以進(jìn)行兩個n位大整數(shù)的乘法運(yùn)算小學(xué)的方法：O(n2)

效率太低分治法:X=Y=X=a2n/2+bY=c2n/2+d

XY=ac2n+(ad+bc)2n/2+bd

abcd10復(fù)雜度分析T(n)=O(n2)

沒有改進(jìn)XY=ac2n+(ad+bc)2n/2+bd

進(jìn)行4次n/2位整數(shù)的乘法（ac，ad，bcbd），以及3次不超過2n位的整數(shù)加法。此外，還要做2次移位。11為了降低時間復(fù)雜度，必須減少乘法的次數(shù)。XY=ac2n+((a-c)(b-d)+ac+bd)2n/2+bd進(jìn)行3次n/2位整數(shù)的乘法（ac，ad,（a-b)(b-d))，以及6次加、減法，和2次移位。復(fù)雜度分析T(n)=O(nlog3)=O(n1.59)

較大的改進(jìn)XY=ac2n+(ad+bc)2n/2+bd

12XY=ac2n+(ad+bc)2n/2+bd

還可以采用一種方案：XY=ac2n+((a+c)(b+d)-ac-bd)2n/2+bd細(xì)節(jié)問題：兩個XY的復(fù)雜度都是O(nlog3)，但考慮到a+c,b+d可能得到m+1位的結(jié)果，使問題的規(guī)模變大，故不選擇第2種方案。復(fù)雜度分析T(n)=O(nlog3)=O(n1.59)

較大的改進(jìn)13如果將大整數(shù)分成更多段，用更復(fù)雜的方式把它們組合起來，將有可能得到更優(yōu)的算法。最終的，這個思想導(dǎo)致了快速傅利葉變換(FastFourierTransform)的產(chǎn)生。該方法也可以看作是一個復(fù)雜的分治算法。小學(xué)的方法：O(n2)

效率太低分治法:O(n1.59)

較大的改進(jìn)更快的方法??14Strassen矩陣乘法A和B的乘積矩陣C中的元素C[i,j]定義為:

若依此定義來計算A和B的乘積矩陣C，則每計算C的一個元素C[i][j]，需要做n次乘法和n-1次加法。因此，算出矩陣C的個元素所需的計算時間為O(n3)15使用與上例類似的技術(shù)，將矩陣A，B和C中每一矩陣都分塊成4個大小相等的子矩陣。由此可將方程C=AB重寫為：由此可得：16如果n=2,則2個2階方陣的乘積可以直接計算出來，共需8次乘法和4次加法。當(dāng)子矩陣的階大于2時，為求2個子矩陣的積，可以繼續(xù)將子矩陣分塊，直到子矩陣的階降為2。這樣就產(chǎn)生了一個分治降階的遞歸算法。計算2個n階方陣的乘積轉(zhuǎn)化為計算8個n/2階方陣的乘積和4個n/2階方陣的加法。復(fù)雜度分析T(n)=O(n3)17為了降低時間復(fù)雜度，必須減少乘法的次數(shù)18復(fù)雜度分析T(n)=O(nlog7)=O(n2.81)

較大的改進(jìn)計算7次n/2階方陣乘積和18次n/2階方陣的加減法。19Strassen矩陣乘法傳統(tǒng)方法：O(n3)分治法:O(n2.81)更快的方法??Hopcroft和Kerr已經(jīng)證明(1971)，計算2個２×２矩陣的乘積，7次乘法是必要的。因此，要想進(jìn)一步改進(jìn)矩陣乘法的時間復(fù)雜性，就不能再基于計算2×2矩陣的7次乘法這樣的方法了?；蛟S應(yīng)當(dāng)研究３×３或５×５矩陣的更好算法。在Strassen之后又有許多算法改進(jìn)了矩陣乘法的計算時間復(fù)雜性。目前最好的計算時間上界是O(n2.376)是否能找到O(n2)的算法？20棋盤覆蓋在一個2k×2k

個方格組成的棋盤中，恰有一個方格與其它方格不同，稱該方格為一特殊方格，且稱該棋盤為一特殊棋盤。在棋盤覆蓋問題中，要用圖示的4種不同形態(tài)的L型骨牌覆蓋給定的特殊棋盤上除特殊方格以外的所有方格，且任何2個L型骨牌不得重疊覆蓋。21特殊方格在棋盤上出現(xiàn)的位置有4k種情形，在k>=0時，有4k種不同的特殊棋盤。如圖：當(dāng)k=2時，有16個特殊棋盤。用圖示的4種不同形態(tài)的L型骨牌覆蓋給定的特殊棋盤上除特殊方格以外的所有方格，且任何2個L型骨牌不得重疊覆蓋。在一個2k×2k

個方格組成的棋盤中，L型骨牌個數(shù)恰為（4k-1）/322當(dāng)k>0時，將2k×2k棋盤分割為4個2k-1×2k-1

子棋盤(a)所示。特殊方格必位于4個較小子棋盤之一中，其余3個子棋盤中無特殊方格。為了將這3個無特殊方格的子棋盤轉(zhuǎn)化為特殊棋盤，可以用一個L型骨牌覆蓋這3個較小棋盤的會合處，如(b)所示，從而將原問題轉(zhuǎn)化為4個較小規(guī)模的棋盤覆蓋問題。遞歸地使用這種分割，直至棋盤簡化為棋盤1×1。

23voidchessBoard(inttr,inttc,intdr,intdc,intsize){if(size==1)return;intt=tile++,//L型骨牌號

s=size/2;//分割棋盤//覆蓋左上角子棋盤

if(dr<tr+s&&dc<tc+s)//特殊方格在此棋盤中

chessBoard(tr,tc,dr,dc,s);else{//此棋盤中無特殊方格//用t號L型骨牌覆蓋右下角

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{//此棋盤中無特殊方格//用t號L型骨牌覆蓋左下角

24

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{//用t號L型骨牌覆蓋右上角

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{//用t號L型骨牌覆蓋左上角

board[tr+s][tc+s]=t;//覆蓋其余方格

chessBoard(tr+s,tc+s,tr+s,tc+s,s);}}復(fù)雜度分析T(n)=O(4k)漸進(jìn)意義下的最優(yōu)算法25排序問題

在一般情況下，排序問題的輸入是n個數(shù)的一個序列，要設(shè)計一個有效的排序算法，產(chǎn)生輸入序列的一個重排，是序列從小到大的順序排列。算法的輸入通常是一個有n個元素的數(shù)組，當(dāng)然也可以用其它形式來表示輸入，如鏈表等。在實際中，待排序的對象往往不是單一的數(shù)而是一個記錄，我們是根據(jù)其中的一個關(guān)鍵字作為排序的依據(jù)。26合并排序基本思想：將待排序元素分成大小大致相同的2個子集合，分別對2個子集合進(jìn)行排序，最終將排好序的子集合合并成為所要求的排好序的集合。voidMergeSort(Typea[],intleft,intright){if(left<right){//至少有2個元素

inti=(left+right)/2;//取中點

mergeSort(a,left,i);mergeSort(a,i+1,right);merge(a,b,left,i,right);//合并到數(shù)組bcopy(a,b,left,right);//復(fù)制回數(shù)組a}}27算法mergeSort的遞歸過程可以消去。初始序列[49][38][65][97][76][13][27][3849][6597][1376][27]第一步第二步[38496597][132776]第三步[13273849657697]28復(fù)雜度分析T(n)=O(nlogn)漸進(jìn)意義下的最優(yōu)算法最壞時間復(fù)雜度：O(nlogn)平均時間復(fù)雜度：O(nlogn)輔助空間：O(n)29快速排序在快速排序中，記錄的比較和交換是從兩端向中間進(jìn)行的，關(guān)鍵字較大的記錄一次就能交換到后面單元，關(guān)鍵字較小的記錄一次就能交換到前面單元，記錄每次移動的距離較大，因而總的比較和移動次數(shù)較少。template<classType>voidQuickSort(Typea[],intp,intr){if(p<r){intq=Partition(a,p,r);QuickSort(a,p,q-1);//對左半段排序

QuickSort(a,q+1,r);//對右半段排序}}30template<classType>intPartition(Typea[],intp,intr){inti=p,j=r+1;Typex=a[p];//將<x的元素交換到左邊區(qū)域//將>x的元素交換到右邊區(qū)域

while(true){while(a[++i]<x);while(a[--j]>x);if(i>=j)break;Swap(a[i],a[j]);}a[p]=a[j];