分治算法詳解課件

分治1將要求解的較大規(guī)模的問題分割成k個(gè)更小規(guī)模的子問題。算法總體思想nT(n/m)T(n/m)T(n/m)T(n/m)T(n)=

對(duì)這k個(gè)子問題分別求解。如果子問題的規(guī)模仍然不夠小，則再劃分為k個(gè)子問題，如此遞歸的進(jìn)行下去，直到問題規(guī)模足夠小，很容易求出其解為止。2算法總體思想對(duì)這k個(gè)子問題分別求解。如果子問題的規(guī)模仍然不夠小，則再劃分為k個(gè)子問題，如此遞歸的進(jìn)行下去，直到問題規(guī)模足夠小，很容易求出其解為止。nT(n)=n/mT(n/m2)T(n/m2)T(n/m2)T(n/m2)n/mT(n/m2)T(n/m2)T(n/m2)T(n/m2)n/mT(n/m2)T(n/m2)T(n/m2)T(n/m2)n/mT(n/m2)T(n/m2)T(n/m2)T(n/m2)

將求出的小規(guī)模的問題的解合并為一個(gè)更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。3算法總體思想將求出的小規(guī)模的問題的解合并為一個(gè)更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。nT(n)=n/mT(n/m2)T(n/m2)T(n/m2)T(n/m2)n/mT(n/m2)T(n/m2)T(n/m2)T(n/m2)n/mT(n/m2)T(n/m2)T(n/m2)T(n/m2)n/mT(n/m2)T(n/m2)T(n/m2)T(n/m2)4算法總體思想將求出的小規(guī)模的問題的解合并為一個(gè)更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)

分治法的設(shè)計(jì)思想是，將一個(gè)難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個(gè)擊破，分而治之。

5分治法的適用條件分治法所能解決的問題一般具有以下幾個(gè)特征：該問題的規(guī)模縮小到一定的程度就可以容易地解決；該問題可以分解為若干個(gè)規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)利用該問題分解出的子問題的解可以合并為該問題的解；該問題所分解出的各個(gè)子問題是相互獨(dú)立的，即子問題之間不包含公共的子問題。因?yàn)閱栴}的計(jì)算復(fù)雜性一般是隨著問題規(guī)模的增加而增加，因此大部分問題滿足這個(gè)特征。這條特征是應(yīng)用分治法的前提，它也是大多數(shù)問題可以滿足的，此特征反映了遞歸思想的應(yīng)用能否利用分治法完全取決于問題是否具有這條特征，如果具備了前兩條特征，而不具備第三條特征，則可以考慮貪心算法或動(dòng)態(tài)規(guī)劃。這條特征涉及到分治法的效率，如果各子問題是不獨(dú)立的，則分治法要做許多不必要的工作，重復(fù)地解公共的子問題，此時(shí)雖然也可用分治法，但一般用動(dòng)態(tài)規(guī)劃較好。6divide-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);//將各子問題的解合并為原問題的解

}分治法的基本步驟人們從大量實(shí)踐中發(fā)現(xiàn)，在用分治法設(shè)計(jì)算法時(shí)，最好使子問題的規(guī)模大致相同。即將一個(gè)問題分成大小相等的k個(gè)子問題的處理方法是行之有效的。這種使子問題規(guī)模大致相等的做法是出自一種平衡(balancing)子問題的思想，它幾乎總是比子問題規(guī)模不等的做法要好。7分析：如果n=1即只有一個(gè)元素，則只要比較這個(gè)元素和x就可以確定x是否在表中。因此這個(gè)問題滿足分治法的第一個(gè)適用條件分析：比較x和a的中間元素a[mid]，若x=a[mid]，則x在L中的位置就是mid；如果x<a[mid]，由于a是遞增排序的，因此假如x在a中的話，x必然排在a[mid]的前面，所以我們只要在a[mid]的前面查找x即可；如果x>a[i]，同理我們只要在a[mid]的后面查找x即可。無論是在前面還是后面查找x，其方法都和在a中查找x一樣，只不過是查找的規(guī)?？s小了。這就說明了此問題滿足分治法的第二個(gè)和第三個(gè)適用條件。

分析：很顯然此問題分解出的子問題相互獨(dú)立，即在a[i]的前面或后面查找x是獨(dú)立的子問題，因此滿足分治法的第四個(gè)適用條件。二分搜索技術(shù)給定已按升序排好序的n個(gè)元素a[0:n-1]，現(xiàn)要在這n個(gè)元素中找出一特定元素x。分析：該問題的規(guī)?？s小到一定的程度就可以容易地解決；該問題可以分解為若干個(gè)規(guī)模較小的相同問題;分解出的子問題的解可以合并為原問題的解；分解出的各個(gè)子問題是相互獨(dú)立的。8二分搜索技術(shù)給定已按升序排好序的n個(gè)元素a[0:n-1]，現(xiàn)要在這n個(gè)元素中找出一特定元素x。據(jù)此容易設(shè)計(jì)出二分搜索算法：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)時(shí)間，因此整個(gè)算法在最壞情況下的計(jì)算時(shí)間復(fù)雜性為O(logn)。9分治法求數(shù)組最大值給定n個(gè)元素a[0:n-1]，現(xiàn)要在這n個(gè)元素中找出最大值x。思路：將數(shù)組一分為二求前半部分的最大值位置，求后半部分最大值位置（分的過程）求前后兩部分最大值位置。（合的過程）10合并排序基本思想：將待排序元素分成大小大致相同的2個(gè)子集合，分別對(duì)2個(gè)子集合進(jìn)行排序，最終將排好序的子集合合并成為所要求的排好序的集合。voidMergeSort(Typea[],intleft,intright){

if(left<right){//至少有2個(gè)元素

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

mergeSort(a,left,i);

mergeSort(a,i+1,right);

merge(a,b,left,i,right);//合并到數(shù)組b

copy(a,b,left,right);//復(fù)制回?cái)?shù)組a}}復(fù)雜度分析T(n)=O(nlogn)漸進(jìn)意義下的最優(yōu)算法11合并排序算法mergeSort的遞歸過程可以消去。初始序列[49][38][65][97][76][13][27][3849][6597][1376][27]第一步第二步[38496597][132776]第三步[13273849657697]12合并排序最壞時(shí)間復(fù)雜度：O(nlogn)平均時(shí)間復(fù)雜度：O(nlogn)輔助空間：O(n)13棋盤覆蓋在一個(gè)2k×2k個(gè)方格組成的棋盤中，恰有一個(gè)方格與其它方格不同，稱該方格為一特殊方格，且稱該棋盤為一特殊棋盤。在棋盤覆蓋問題中，要用圖示的4種不同形態(tài)的L型骨牌覆蓋給定的特殊棋盤上除特殊方格以外的所有方格，且任何2個(gè)L型骨牌不得重疊覆蓋。14棋盤覆蓋當(dāng)k>0時(shí)，將2k×2k棋盤分割為4個(gè)2k-1×2k-1子棋盤(a)所示。特殊方格必位于4個(gè)較小子棋盤之一中，其余3個(gè)子棋盤中無特殊方格。為了將這3個(gè)無特殊方格的子棋盤轉(zhuǎn)化為特殊棋盤，可以用一個(gè)L型骨牌覆蓋這3個(gè)較小棋盤的會(huì)合處，如(b)所示，從而將原問題轉(zhuǎn)化為4個(gè)較小規(guī)模的棋盤覆蓋問題。遞歸地使用這種分割，直至棋盤簡(jiǎn)化為棋盤1×1。

15棋盤的識(shí)別

首先，子棋盤的規(guī)模是一個(gè)必要的信息，有了這個(gè)信息，只要知道左上角的方格在原棋盤中的行、列號(hào)就可以標(biāo)識(shí)這個(gè)子棋盤了；其次子棋盤中殘缺方格或“偽”殘缺方格直接用它們?cè)谠灞P中的行、列號(hào)標(biāo)識(shí)。①tr表示棋盤左上角方格的行號(hào)；②tc表示棋盤左上角方格的列號(hào)③dr表示特殊方格所在的行號(hào)④dc表示特殊方格所在的列號(hào)，⑤size表示方形棋盤行數(shù)或列數(shù)。16棋盤數(shù)據(jù)結(jié)構(gòu)用二維數(shù)組Board[][]來模擬棋盤，Board[1][1]是棋盤的左上角方格。title表示L型骨牌的編號(hào)，其初始值為0。覆蓋殘缺棋盤所需要的三格板數(shù)目為：(size*size-1)/3。將這些三格板編號(hào)為1到(size*size-1)/3，則將覆蓋殘缺棋盤的三格板編號(hào)存儲(chǔ)在數(shù)組Board的對(duì)應(yīng)位置，這樣輸出數(shù)組內(nèi)容就是問題的解。如果是一個(gè)4×4的棋盤，特殊方格為(2,1)，那么程序的輸出為對(duì)于如圖8-6(a)所示的棋盤，其結(jié)果為8-6(b)所示的棋盤。其中特殊方格為0，相同數(shù)字的為同一骨牌。17棋盤覆蓋voidchessBoard(inttr,inttc,intdr,intdc,intsize){

if(size==1)return;intt=tile++,//L型骨牌號(hào)

s=size/2;//分割棋盤

//覆蓋左上角子棋盤

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

chessBoard(tr,tc,dr,dc,s);

else{//此棋盤中無特殊方格

//用t號(hào)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號(hào)L型骨牌覆蓋左下角

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號(hào)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號(hào)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)算法18循環(huán)賽日程表設(shè)計(jì)一個(gè)滿足以下要求的比賽日程表：(1)每個(gè)選手必須與其他n-1個(gè)選手各賽一次；(2)每個(gè)選手一天只能賽一次；(3)循環(huán)賽一共進(jìn)行n-1天。按分治策略，將所有的選手分為兩半，n個(gè)選手的比賽日程表就可以通過為n/2個(gè)選手設(shè)計(jì)的比賽日程表來決定。遞歸地用對(duì)選手進(jìn)行分割，直到只剩下2個(gè)選手時(shí)，比賽日程表的制定就變得很簡(jiǎn)單。這時(shí)只要讓這2個(gè)選手進(jìn)行比賽就可以了。123456782143658734127856432187655678123465872143785634128765432119本題方法有很多，遞歸是其中一種比較容易理解的方法。圖8所示是k=3時(shí)的一個(gè)可行解，它是4塊拼起來的。左上角是k=2時(shí)的一組解，左下角是左上角每個(gè)數(shù)加4得到，而右上角、右下角分別由左下角、左上角復(fù)制得到的。123456782143658734127856432187655678123465872143785634128765432120#include<iostream>usingnamespacestd;in