第4章 分治法.ppt

1、1,第4章 分治法,4.1 概 述,4.2 遞 歸,4.3 排序問題中的分治法,4.4 組合問題中的分治法,4.5 幾何問題中的分治法,4.6 實驗項目最近對問題,2,4.1 概 述,4.1.1 分治法的設(shè)計思想,4.1.2 分治法的求解過程,3,將一個難以直接解決的大問題，劃分成一些規(guī)模較小的子問題，以便各個擊破，分而治之。更一般地說，將要求解的原問題劃分成k個較小規(guī)模的子問題，對這k個子問題分別求解。如果子問題的規(guī)模仍然不夠小，則再將每個子問題劃分為k個規(guī)模更小的子問題，如此分解下去，直到問題規(guī)模足夠小，很容易求出其解為止，再將子問題的解合并為一個更大規(guī)模的問題的解，自底向上逐步求出原問題

2、的解。,4.1.1 分治法的設(shè)計思想,4,2. 獨立子問題：各子問題之間相互獨立，這涉及到分治法的效率，如果各子問題不是獨立的，則分治法需要重復(fù)地解公共的子問題。,1. 平衡子問題：最好使子問題的規(guī)模大致相同。也就是將一個問題劃分成大小相等的k個子問題（通常k2），這種使子問題規(guī)模大致相等的做法是出自一種平衡（Balancing）子問題的思想，它幾乎總是比子問題規(guī)模不等的做法要好。,啟發(fā)式規(guī)則：,5,分治法的典型情況,6,4.1.2 分治法的求解過程,一般來說，分治法的求解過程由以下三個階段組成： （1）劃分：既然是分治，當(dāng)然需要把規(guī)模為n的原問題劃分為k個規(guī)模較小的子問題，并盡量使這k個子問

3、題的規(guī)模大致相同。 （2）求解子問題：各子問題的解法與原問題的解法通常是相同的，可以用遞歸的方法求解各個子問題，有時遞歸處理也可以用循環(huán)來實現(xiàn)。 （3）合并：把各個子問題的解合并起來，合并的代價因情況不同有很大差異，分治算法的有效性很大程度上依賴于合并的實現(xiàn)。,7,例：計算an，應(yīng)用分治技術(shù)得到如下計算方法：,不是所有的分治法都比簡單的蠻力法更有效。,分析時 間性能,8,4.2 遞 歸,4.2.1 遞歸的定義,4.2.2 遞歸函數(shù)的運行軌跡,4.2.3 遞歸函數(shù)的內(nèi)部執(zhí)行過程,9,4.2.1 遞歸的定義,遞歸（Recursion）就是子程序（或函數(shù)）直接調(diào)用自己或通過一系列調(diào)用語句間接調(diào)用自己

4、，是一種描述問題和解決問題的基本方法。 遞歸有兩個基本要素： 邊界條件：確定遞歸到何時終止； 遞歸模式：大問題是如何分解為小問題的。,10,遞歸函數(shù)的經(jīng)典問題漢諾塔問題 在世界剛被創(chuàng)建的時候有一座鉆石寶塔（塔A），其上有64個金碟。所有碟子按從大到小的次序從塔底堆放至塔頂。緊挨著這座塔有另外兩個鉆石寶塔（塔B和塔C）。從世界創(chuàng)始之日起，婆羅門的牧師們就一直在試圖把塔A上的碟子移動到塔C上去，其間借助于塔B的幫助。每次只能移動一個碟子，任何時候都不能把一個碟子放在比它小的碟子上面。當(dāng)牧師們完成任務(wù)時，世界末日也就到了。,11,漢諾塔問題可以通過以下三個步驟實現(xiàn)： （1）將塔A上的n-1個碟子借助

5、塔C先移到塔B上。 （2）把塔A上剩下的一個碟子移到塔C上。 （3）將n-1個碟子從塔B借助塔A移到塔C上。 顯然，這是一個遞歸求解的過程,12,13,14,4.2.2 遞歸函數(shù)的運行軌跡,在遞歸函數(shù)中，調(diào)用函數(shù)和被調(diào)用函數(shù)是同一個函數(shù)，需要注意的是遞歸函數(shù)的調(diào)用層次，如果把調(diào)用遞歸函數(shù)的主函數(shù)稱為第0層，進入函數(shù)后，首次遞歸調(diào)用自身稱為第1層調(diào)用；從第i層遞歸調(diào)用自身稱為第i+1層。反之，退出第i+1層調(diào)用應(yīng)該返回第i層。采用圖示方法描述遞歸函數(shù)的運行軌跡，從中可較直觀地了解到各調(diào)用層次及其執(zhí)行情況。,15,Hanio(3,A,B,C),Hanio(2,A,C,B),Hanio(1,A,B,

6、C),Move (A,C),Move (A,B),Hanio(1,C,A,B),Move (C,B),Move (A,C),Hanio(2,B,A,C),Hanio(1,B,C,A),Move (B,C),Hanio(1,A,B,C),Move (A,C),Move (B,A),16,4.2.3 遞歸函數(shù)的內(nèi)部執(zhí)行過程,一個遞歸函數(shù)的調(diào)用過程類似于多個函數(shù)的嵌套調(diào)用，只不過調(diào)用函數(shù)和被調(diào)用函數(shù)是同一個函數(shù)。為了保證遞歸函數(shù)的正確執(zhí)行，系統(tǒng)需設(shè)立一個工作棧。具體地說，遞歸調(diào)用的內(nèi)部執(zhí)行過程如下： （1）運行開始時，首先為遞歸調(diào)用建立一個工作棧，其結(jié)構(gòu)包括值參、局部變量和返回地址； （2）每次執(zhí)行

7、遞歸調(diào)用之前，把遞歸函數(shù)的值參和局部變量的當(dāng)前值以及調(diào)用后的返回地址壓棧； （3）每次遞歸調(diào)用結(jié)束后，將棧頂元素出棧，使相應(yīng)的值參和局部變量恢復(fù)為調(diào)用前的值，然后轉(zhuǎn)向返回地址指定的位置繼續(xù)執(zhí)行。,17,漢諾塔算法在執(zhí)行過程中，工作棧的變化下圖所示，其中棧元素的結(jié)構(gòu)為（返回地址，n值，A值，B值，C值），返回地址對應(yīng)算法中語句的行號。,18,遞歸算法結(jié)構(gòu)清晰，可讀性強，而且容易用數(shù)學(xué)歸納法來證明算法的正確性，因此，它為設(shè)計算法和調(diào)試程序帶來很大方便，是算法設(shè)計中的一種強有力的工具。但是，因為遞歸算法是一種自身調(diào)用自身的算法，隨著遞歸深度的增加，工作棧所需要的空間增大，遞歸調(diào)用時的輔助操作增多，因

8、此，遞歸算法的運行效率較低。,19,4.3 排序問題中的分治法,4.3.1 歸并排序,4.3.2 快速排序,20,4.3.1 歸并排序,二路歸并排序的分治策略是： （1）劃分：將待排序序列r1, r2, , rn劃分為兩個長度相等的子序列r1, , rn/2和rn/21, , rn； （2）求解子問題：分別對這兩個子序列進行排序，得到兩個有序子序列； （3）合并：將這兩個有序子序列合并成一個有序序列。,21,22,23,二路歸并排序的合并步的時間復(fù)雜性為O(n)，所以，二路歸并排序算法存在如下遞推式：,根據(jù)1.2.4節(jié)的主定理，二路歸并排序的時間代價是O(nlog2n)。 二路歸并排序在合并過

9、程中需要與原始記錄序列同樣數(shù)量的存儲空間，因此其空間復(fù)雜性為O(n)。,24,25,4.3.2 快速排序,（2）求解子問題：分別對劃分后的每一個子序列遞歸處理； （3）合并：由于對子序列r1 ri-1和ri+1 rn的排序是就地進行的，所以合并不需要執(zhí)行任何操作。,快速排序的分治策略是： （1）劃分：選定一個記錄作為軸值，以軸值為基準(zhǔn)將整個序列劃分為兩個子序列r1 ri-1和ri+1 rn，前一個子序列中記錄的值均小于或等于軸值，后一個子序列中記錄的值均大于或等于軸值；,26,歸并排序按照記錄在序列中的位置對序列進行劃分， 快速排序按照記錄的值對序列進行劃分。,27,以第一個記錄作為軸值，對待

10、排序序列進行劃分的過程為： （1）初始化：取第一個記錄作為基準(zhǔn)，設(shè)置兩個參數(shù)i，j分別用來指示將要與基準(zhǔn)記錄進行比較的左側(cè)記錄位置和右側(cè)記錄位置，也就是本次劃分的區(qū)間； （2）右側(cè)掃描過程：將基準(zhǔn)記錄與j指向的記錄進行比較，如果j指向記錄的關(guān)鍵碼大，則j前移一個記錄位置。重復(fù)右側(cè)掃描過程，直到右側(cè)的記錄小（即反序），若ij，則將基準(zhǔn)記錄與j指向的記錄進行交換； （3）左側(cè)掃描過程：將基準(zhǔn)記錄與i指向的記錄進行比較，如果i指向記錄的關(guān)鍵碼小，則i后移一個記錄位置。重復(fù)左側(cè)掃描過程，直到左側(cè)的記錄大（即反序），若ij，則將基準(zhǔn)記錄與i指向的記錄交換； （4）重復(fù)（2）（3）步，直到i與j指向同一位

11、置，即基準(zhǔn)記錄最終的位置。,28,一次劃分示例,29,30,以軸值為基準(zhǔn)將待排序序列劃分為兩個子序列后，對每一個子序列分別遞歸進行排序。,13,27,50,38,49,55,j,i,i,j,13,65,27,50,38,49,55,65,31,32,T(n)2 T(n/2)n 2(2T(n/4)n/2)n4T(n/4)2n 4(2T(n/8)n/4)2n8T(n/8)3n nT(1)nlog2nO(nlog2n) 因此，時間復(fù)雜度為O(nlog2n)。,在最好情況下，每次劃分對一個記錄定位后，該記錄的左側(cè)子序列與右側(cè)子序列的長度相同。在具有n個記錄的序列中，一次劃分需要對整個待劃分序列掃描一遍

12、，則所需時間為O(n)。設(shè)T(n)是對n個記錄的序列進行排序的時間，每次劃分后，正好把待劃分區(qū)間劃分為長度相等的兩個子序列，則有：,33,因此，時間復(fù)雜度為O(n2)。,在最壞情況下，待排序記錄序列正序或逆序，每次劃分只得到一個比上一次劃分少一個記錄的子序列（另一個子序列為空）。此時，必須經(jīng)過n-1次遞歸調(diào)用才能把所有記錄定位，而且第i趟劃分需要經(jīng)過n-i次關(guān)鍵碼的比較才能找到第i個記錄的基準(zhǔn)位置，因此，總的比較次數(shù)為：,34,在平均情況下，設(shè)基準(zhǔn)記錄的關(guān)鍵碼第k小（1kn），則有：,這是快速排序的平均時間性能，可以用歸納法證明，其數(shù)量級也為O(nlog2n)。,35,4.4 組合問題中的分治

13、法,4.4.1 最大子段和問題,4.4.2 棋盤覆蓋問題,4.4.3 循環(huán)賽日程安排問題,36,給定由n個整數(shù)組成的序列(a1, a2, , an)，最大子段和問題要求該序列形如 的最大值（1ijn），當(dāng)序列中所有整數(shù)均為負(fù)整數(shù)時，其最大子段和為0。例如，序列(-20, 11, -4, 13, -5, -2)的最大子段和為：,4.4.1 最大子段和問題,最大子段和問題的分治策略是： （1）劃分：按照平衡子問題的原則，將序列(a1, a2, , an)劃分成長度相同的兩個子序列(a1, , a )和(a 1, , an)，則會出現(xiàn)以下三種情況：,37, a1, , an的最大子段和a1, ,a

14、的最大子段和； a1, , an的最大子段和a 1, , an的最大子段和； a1, , an的最大子段和 ，且,（2）求解子問題：對于劃分階段的情況和可遞歸求解，情況需要分別計算 ，,，則s1+s2為情況的最大子段和。,（3）合并：比較在劃分階段的三種情況下的最大子段和，取三者之中的較大者為原問題的解。,38,39,40,s1=0; lefts=0; /以下對應(yīng)情況，先求解s1 for (i=center; i=left; i-) lefts+=ai; if (leftss1) s1=lefts; s2=0; rights=0; /再求解s2 for (j=center+1; js2) s2

15、=rights; sum=s1+s2; /計算情況的最大子段和 if (sumleftsum) sum=leftsum; /合并，在sum、leftsum和rightsum中取較大者 if (sumrightsum) sum=rightsum; return sum; ,41,分析算法4.7的時間性能，對應(yīng)劃分得到的情況和，需要分別遞歸求解，對應(yīng)情況，兩個并列for循環(huán)的時間復(fù)雜性是O(n)，所以，存在如下遞推式： 根據(jù)1.2.4節(jié)主定理，算法4.7的時間復(fù)雜性為O(nlog2n)。,42,4.4.2 棋盤覆蓋問題,在一個2k2k （k0）個方格組成的棋盤中，恰有一個方格與其他方格不同，稱該方

16、格為特殊方格。棋盤覆蓋問題要求用圖4.11（b）所示的4種不同形狀的L型骨牌覆蓋給定棋盤上除特殊方格以外的所有方格，且任何2個L型骨牌不得重疊覆蓋。,(a) k=2時的一種棋盤 (b) 4種不同形狀的L型骨牌,43,分治法求解棋盤覆蓋問題的技巧在于劃分棋盤，使劃分后的子棋盤的大小相同，并且每個子棋盤均包含一個特殊方格，從而將原問題分解為規(guī)模較小的棋盤覆蓋問題。 k0時，可將2k2k的棋盤劃分為4個2k-12k-1的子棋盤，這樣劃分后，由于原棋盤只有一個特殊方格，所以，這4個子棋盤中只有一個子棋盤包含該特殊方格，其余3個子棋盤中沒有特殊方格。為了將這3個沒有特殊方格的子棋盤轉(zhuǎn)化為特殊棋盤，以便采

17、用遞歸方法求解，可以用一個L型骨牌覆蓋這3個較小棋盤的會合處，從而將原問題轉(zhuǎn)化為4個較小規(guī)模的棋盤覆蓋問題。遞歸地使用這種劃分策略，直至將棋盤分割為11的子棋盤。,44,(a)棋盤分割 (b) 構(gòu)造相同子問題,45,下面討論棋盤覆蓋問題中數(shù)據(jù)結(jié)構(gòu)的設(shè)計。 （1）棋盤：可以用一個二維數(shù)組boardsizesize表示一個棋盤，其中，size=2k。為了在遞歸處理的過程中使用同一個棋盤，將數(shù)組board設(shè)為全局變量； （2）子棋盤：整個棋盤用二維數(shù)組boardsizesize表示，其中的子棋盤由棋盤左上角的下標(biāo)tr、tc和棋盤大小s表示； （3）特殊方格：用boarddrdc表示特殊方格，dr和d

18、c是該特殊方格在二維數(shù)組board中的下標(biāo); （4） L型骨牌：一個2k2k的棋盤中有一個特殊方格，所以，用到L型骨牌的個數(shù)為(4k-1)/3，將所有L型骨牌從1開始連續(xù)編號，用一個全局變量t表示。,46,47,48,/ 覆蓋右上角子棋盤 if (dr = tc + s) / 特殊方格在右上角子棋盤中 ChessBoard(tr, tc+s, dr, dc, s); /遞歸處理子棋盤 else / 用 t 號L型骨牌覆蓋左下角，再遞歸處理子棋盤 boardtr + s - 1tc + s = t; ChessBoard(tr, tc+s, tr+s-1, tc+s, s); / 覆蓋左下角子棋

19、盤 if (dr = tr + s ,49,設(shè)T(k)是覆蓋一個2k2k棋盤所需時間，從算法的劃分策略可知，T(k)滿足如下遞推式：,解此遞推式可得T(k)=O(4k)。由于覆蓋一個2k2k棋盤所需的骨牌個數(shù)為(4k-1)/3，所以，算法4.8是一個在漸進意義下的最優(yōu)算法。,50,4.4.3 循環(huán)賽日程安排問題,設(shè)有n=2k個選手要進行網(wǎng)球循環(huán)賽，要求設(shè)計一個滿足以下要求的比賽日程表： （1）每個選手必須與其他n-1個選手各賽一次； （2）每個選手一天只能賽一次。 按此要求，可將比賽日程表設(shè)計成一個 n 行n-1列的二維表，其中，第 i 行第 j 列表示和第 i 個選手在第 j 天比賽的選手。

20、,51,按照分治的策略，可將所有參賽的選手分為兩部分，n2k個選手的比賽日程表就可以通過為n/22k-1個選手設(shè)計的比賽日程表來決定。遞歸地執(zhí)行這種分割，直到只剩下2個選手時，比賽日程表的制定就變得很簡單：只要讓這2個選手進行比賽就可以了。,52,顯然，這個求解過程是自底向上的迭代過程，其中左上角和左下角分別為選手1至選手4以及選手5至選手8前3天的比賽日程，據(jù)此，將左上角部分的所有數(shù)字按其對應(yīng)位置抄到右下角，將左下角的所有數(shù)字按其對應(yīng)位置抄到右上角，這樣，就分別安排好了選手1至選手4以及選手5至選手8在后4天的比賽日程，如圖(c)所示。具有多個選手的情況可以依此類推。,(b) 2k(k=2)

21、個選手比賽 (c) 2k(k=3)個選手比賽,加4,加2,(a) 2k(k=1)個選手比賽,53,這種解法是把求解2k個選手比賽日程問題劃分成依次求解21、22、2k個選手的比賽日程問題，換言之，2k個選手的比賽日程是在2k-1個選手的比賽日程的基礎(chǔ)上通過迭代的方法求得的。在每次迭代中，將問題劃分為4部分： （1）左上角：左上角為2k-1個選手在前半程的比賽日程； （2）左下角：左下角為另2k-1個選手在前半程的比賽日程，由左上角加2k-1得到，例如22個選手比賽，左下角由左上角直接加2得到，23個選手比賽，左下角由左上角直接加4得到； （3）右上角：將左下角直接抄到右上角得到另2k-1個選手

22、在后半程的比賽日程； （4）右下角：將左上角直接抄到右下角得到2k-1個選手在后半程的比賽日程； 算法設(shè)計的關(guān)鍵在于尋找這4部分元素之間的對應(yīng)關(guān)系。,54,55,temp=n; n=n*2; /填左下角元素 for (i=temp+1; i=n; i+ ) for (j=1; j=temp; j+) aij=ai-tempj+temp; /左下角元素和左上角元素的對應(yīng)關(guān)系 /填右上角元素 for (i=1; i=temp; i+) for (j=temp+1; j=n; j+) aij=ai+temp(j+temp)% n; /填右下角元素 for (i=temp+1; i=n; i+) fo

23、r (j=temp+1; j=n; j+) aij=ai-tempj-temp; ,56,分析算法4.9的時間性能，迭代處理的循環(huán)體內(nèi)部有3個循環(huán)語句，每個循環(huán)語句都是一個嵌套的for循環(huán)，且他們的執(zhí)行次數(shù)相同，基本語句是最內(nèi)層循環(huán)體的賦值語句，即填寫比賽日程表中的元素?；菊Z句的執(zhí)行次數(shù)是： 所以，算法4.9的其時間復(fù)雜性為O(4k)。,57,4.5 幾何問題中的分治法,4.5.1 最近對問題,4.5.2 凸包問題,58,4.5.1 最近對問題,設(shè)p1=(x1, y1), p2=(x2, y2), , pn=(xn, yn)是平面上n個點構(gòu)成的集合S，最近對問題就是找出集合S中距離最近的點對

24、。 嚴(yán)格地講，最接近點對可能多于一對，簡單起見，只找出其中的一對作為問題的解。,59,用分治法解決最近對問題，很自然的想法就是將集合S分成兩個子集 S1和 S2，每個子集中有n/2個點。然后在每個子集中遞歸地求其最接近的點對，在求出每個子集的最接近點對后，在合并步中，如果集合 S 中最接近的兩個點都在子集 S1或 S2中，則問題很容易解決，如果這兩個點分別在 S1和 S2中，問題就比較復(fù)雜了。,60,為了使問題易于理解，先考慮一維的情形。 此時，S中的點退化為x軸上的n個點x1, x2, , xn。用x軸上的某個點m將S劃分為兩個集合S1和S2，并且S1和S2含有點的個數(shù)相同。遞歸地在S1和S

25、2上求出最接近點對 (p1, p2) 和(q1, q2)，如果集合S中的最接近點對都在子集S1或S2中，則d=min(p1, p2), (q1, q2)即為所求，如果集合S中的最接近點對分別在S1和S2中，則一定是(p3, q3)，其中，p3是子集S1中的最大值，q3是子集S2中的最小值。,61,按這種分治策略求解最近對問題的算法效率取決于劃分點m的選取，一個基本的要求是要遵循平衡子問題的原則。如果選取m=(maxS+minS)/2，則有可能因集合S中點分布的不均勻而造成子集S1和S2的不平衡，如果用S中各點坐標(biāo)的中位數(shù)（即S的中值）作為分割點，則會得到一個平衡的分割點m，使得子集S1和S2中

26、有個數(shù)大致相同的點。,62,下面考慮二維的情形，此時S中的點為平面上的點。 為了將平面上的點集S 分割為點的個數(shù)大致相同的兩個子集S1和S2，選取垂直線x=m來作為分割線，其中，m為S中各點x坐標(biāo)的中位數(shù)。由此將S分割為S1=pS | xpm和S2=qS | xqm。遞歸地在S1和S2上求解最近對問題，分別得到S1中的最近距離d1和S2中的最近距離d2，令d=min(d1, d2)，若S的最近對(p, q)之間的距離小于d，則p和q必分屬于S1和S2，不妨設(shè)pS1，qS2，則p和q距直線x=m的距離均小于d，所以，可以將求解限制在以x=m為中心、寬度為2d的垂直帶P1和P2中，垂直帶之外的任何點對之間的距離都一定大于d。,63,S1=pS | xpm,S2=qS | xqm,64,對于點pP1，需要考察P2中的各個點和點p之間的距離是否小于d，顯然，P2中這樣點的y軸坐標(biāo)一定位于區(qū)間y-d, y+d之間，而且，這樣的點不會超過6個。,65,應(yīng)用分治法求解含有n個點的最近對問題，其時間復(fù)雜性可由下面的遞推式表示： 合并子問題的解的時間f(n)O(1)，根據(jù)1.2.4節(jié)的主定理，可得T(n)=O(nlog2n)。,66,4.5.2 凸包問題,設(shè)p1=(x1, y1), p2=(x2, y2), , pn=(xn, yn