第4章 分治法

1、第第4章章 分治法分治法 4.1 概概 述述 4.2 遞遞 歸歸4.3 排序問題中的分治法排序問題中的分治法4.4 組合問題中的分治法組合問題中的分治法4.5 幾何問題中的分治法幾何問題中的分治法4.6 實驗項目實驗項目最近對問題最近對問題 馬慧芳第1章 第1頁4.1 概概 述述 4.1.1 分治法的設(shè)計思想分治法的設(shè)計思想 4.1.2 分治法的求解過程分治法的求解過程 李志欣第1章 第2頁 將一個難以直接解決的大問題，劃分成一些規(guī)模較小的將一個難以直接解決的大問題，劃分成一些規(guī)模較小的子問題，以便各個擊破，分而治之。更一般地說，將要求解子問題，以便各個擊破，分而治之。更一般地說，將要求解的原

2、問題劃分成的原問題劃分成k個較小規(guī)模的子問題，對這個較小規(guī)模的子問題，對這k個子問題分別個子問題分別求解。如果子問題的規(guī)模仍然不夠小，則再將每個子問題劃求解。如果子問題的規(guī)模仍然不夠小，則再將每個子問題劃分為分為k個規(guī)模更小的子問題，如此分解下去，直到問題規(guī)模足個規(guī)模更小的子問題，如此分解下去，直到問題規(guī)模足夠小，很容易求出其解為止，再將子問題的解合并為一個更夠小，很容易求出其解為止，再將子問題的解合并為一個更大規(guī)模的問題的解，自底向上逐步求出原問題的解。大規(guī)模的問題的解，自底向上逐步求出原問題的解。 4.1.1 分治法的設(shè)計思想分治法的設(shè)計思想 李志欣第1章 第3頁2. 獨立子問題獨立子問題

3、：各子問題之間相互獨立，這涉及到分治法的：各子問題之間相互獨立，這涉及到分治法的效率，如果各子問題不是獨立的，則分治法需要重復(fù)地解公效率，如果各子問題不是獨立的，則分治法需要重復(fù)地解公共的子問題。共的子問題。 1. 平衡子問題平衡子問題：最好使子問題的規(guī)模大致相同。也就是將一：最好使子問題的規(guī)模大致相同。也就是將一個問題劃分成大小相等的個問題劃分成大小相等的k個子問題（通常個子問題（通常k2），這種使子），這種使子問題規(guī)模大致相等的做法是出自一種平衡（問題規(guī)模大致相等的做法是出自一種平衡（Balancing）子問）子問題的思想，它幾乎題的思想，它幾乎總是比子問題規(guī)模不等的做法要好。總是比子問題

4、規(guī)模不等的做法要好。啟發(fā)式規(guī)則： 李志欣第1章 第4頁 子問題子問題1的規(guī)模是的規(guī)模是n/2 子問題子問題1的解的解 子問題子問題2的解的解 子問題子問題2的規(guī)模是的規(guī)模是n/2 原問題的解原問題的解 原問題原問題的規(guī)模是的規(guī)模是n分治法的典型情況分治法的典型情況 李志欣第1章 第5頁4.1.2 分治法的求解過程分治法的求解過程 一般來說，分治法的求解過程由以下三個階段組成：一般來說，分治法的求解過程由以下三個階段組成： （1 1）劃分劃分：既然是分治，當(dāng)然需要把規(guī)模為：既然是分治，當(dāng)然需要把規(guī)模為n n的原問題劃的原問題劃分為分為k k個規(guī)模較小的子問題，并盡量使這個規(guī)模較小的子問題，并盡量

5、使這k k個子問題的規(guī)模個子問題的規(guī)模大致相同。大致相同。 （2 2）求解子問題求解子問題：各子問題的解法與原問題的解法通常：各子問題的解法與原問題的解法通常是相同的，可以用遞歸的方法求解各個子問題，有時遞歸是相同的，可以用遞歸的方法求解各個子問題，有時遞歸處理也可以用循環(huán)來實現(xiàn)。處理也可以用循環(huán)來實現(xiàn)。 （3 3）合并合并：把各個子問題的解合并起來，合并的代價因：把各個子問題的解合并起來，合并的代價因情況不同有很大差異，分治算法的有效性很大程度上依賴情況不同有很大差異，分治算法的有效性很大程度上依賴于合并的實現(xiàn)。于合并的實現(xiàn)。 李志欣第1章 第6頁 例：計算例：計算an，應(yīng)用分治技術(shù)得到如下

6、計算方法：，應(yīng)用分治技術(shù)得到如下計算方法： 34 32 32 81 31 31 9 31 31 9 3 3 3 3分解問題分解問題求解每個子問題求解每個子問題合并子問題的解合并子問題的解v 不是所有的分治法都比簡單的蠻力法更有效。不是所有的分治法都比簡單的蠻力法更有效。分析時間性能 = = =1122naanaannn如果如果如果如果 李志欣第1章 第7頁4.2 遞遞 歸歸 4.2.1 遞歸的定義遞歸的定義 4.2.2 遞歸函數(shù)的運行軌跡遞歸函數(shù)的運行軌跡4.2.3 遞歸函數(shù)的內(nèi)部執(zhí)行過程遞歸函數(shù)的內(nèi)部執(zhí)行過程 李志欣第1章 第8頁4.2.1 遞歸的定義遞歸的定義 遞歸（遞歸（Recursio

7、nRecursion）就是子程序（或函數(shù)）直）就是子程序（或函數(shù)）直接調(diào)用自己或通過一系列調(diào)用語句間接調(diào)用自己，接調(diào)用自己或通過一系列調(diào)用語句間接調(diào)用自己，是一種描述問題和解決問題的基本方法。是一種描述問題和解決問題的基本方法。遞歸有兩個基本要素：遞歸有兩個基本要素： 邊界條件邊界條件：確定遞歸到何時終止；：確定遞歸到何時終止； 遞歸模式遞歸模式：大問題是如何分解為小問題的。：大問題是如何分解為小問題的。 李志欣第1章 第9頁n階乘函數(shù)遞歸的定義為階乘函數(shù)遞歸的定義為int Fac(int n)if(n=1) return 1;else return n*Fac(n-1);第1章 第10頁 李

8、志欣 = = =11nn(n-1)!n1n!如果如果如果如果遞歸模式遞歸模式邊界條件邊界條件nFibonacci數(shù)列數(shù)列int Fib(int n)if(n = = =10,1nF(n-1)+F(n-2)n1F(n)如果如果如果如果1111515()()225nnnAckerman函數(shù)（雙遞歸函數(shù)）函數(shù)（雙遞歸函數(shù)）當(dāng)一個函數(shù)以及它的一個變量是由函數(shù)自身定義當(dāng)一個函數(shù)以及它的一個變量是由函數(shù)自身定義時，稱這個函數(shù)是雙遞歸函數(shù)。時，稱這個函數(shù)是雙遞歸函數(shù)。Ackerman函數(shù)函數(shù)A(n,m)有兩個獨立的整變量有兩個獨立的整變量m=0，n=0。其定。其定義如下：義如下：第1章 第12頁 李志欣(1

9、,0)2(0,)10( ,0)22( ,)( (1,),1),1AAmmA nnnA n mA A nm mn m=遞歸函數(shù)的經(jīng)典問題遞歸函數(shù)的經(jīng)典問題漢諾塔問題漢諾塔問題在世界剛被創(chuàng)建的時候有一座鉆石寶塔（塔在世界剛被創(chuàng)建的時候有一座鉆石寶塔（塔A），），其上有其上有64個金碟。所有碟子按從大到小的次序從個金碟。所有碟子按從大到小的次序從塔底堆放至塔頂。緊挨著這座塔有另外兩個鉆石塔底堆放至塔頂。緊挨著這座塔有另外兩個鉆石寶塔（塔寶塔（塔B和塔和塔C）。從世界創(chuàng)始之日起，婆羅）。從世界創(chuàng)始之日起，婆羅門的牧師們就一直在試圖把塔門的牧師們就一直在試圖把塔A上的碟子移動到上的碟子移動到塔塔C上去，

10、其間借助于塔上去，其間借助于塔B的幫助。每次只能移的幫助。每次只能移動一個碟子，任何時候都不能把一個碟子放在比動一個碟子，任何時候都不能把一個碟子放在比它小的碟子上面。當(dāng)牧師們完成任務(wù)時，世界末它小的碟子上面。當(dāng)牧師們完成任務(wù)時，世界末日也就到了。日也就到了。 李志欣13漢諾塔問題可以通過以下三個步驟實現(xiàn)：漢諾塔問題可以通過以下三個步驟實現(xiàn)：（1）將塔）將塔A上的上的n-1個碟子借助塔個碟子借助塔C先移到塔先移到塔B上。上。（2）把塔）把塔A上剩下的一個碟子移到塔上剩下的一個碟子移到塔C上。上。（3）將）將n-1個碟子從塔個碟子從塔B借助塔借助塔A移到塔移到塔C上。上。 顯然，這是一個遞歸求解

11、的過程顯然，這是一個遞歸求解的過程 李志欣第1章 第14頁 李志欣第1章 第15頁算法4.2漢諾塔算法 1 void Hanoi( (int n, char A, char B, char C) ) /第一列為語句行號第一列為語句行號 2 3 if ( (n=1) ) Move( (A, C) ); /Move是一個抽象操作，表示將碟子從是一個抽象操作，表示將碟子從A移到移到C上上 4 else 5 Hanoi( (n- -1, A, C, B) ); 6 Move( (A, C) ); 7 Hanoi( (n- -1, B, A, C) ); 8 9 李志欣164.2.2 遞歸函數(shù)的運行軌跡

12、遞歸函數(shù)的運行軌跡 在遞歸函數(shù)中，調(diào)用函數(shù)和被調(diào)用函數(shù)是同一在遞歸函數(shù)中，調(diào)用函數(shù)和被調(diào)用函數(shù)是同一個函數(shù)，需要注意的是遞歸函數(shù)的調(diào)用層次，如果個函數(shù)，需要注意的是遞歸函數(shù)的調(diào)用層次，如果把調(diào)用遞歸函數(shù)的主函數(shù)稱為第把調(diào)用遞歸函數(shù)的主函數(shù)稱為第0 0層，進入函數(shù)后，層，進入函數(shù)后，首次遞歸調(diào)用自身稱為第首次遞歸調(diào)用自身稱為第1層調(diào)用；從第層調(diào)用；從第i層遞歸調(diào)層遞歸調(diào)用自身稱為第用自身稱為第i+1層。反之，退出第層。反之，退出第i+1層調(diào)用應(yīng)該層調(diào)用應(yīng)該返回第返回第i層。采用圖示方法描述遞歸函數(shù)的運行軌層。采用圖示方法描述遞歸函數(shù)的運行軌跡，從中可較直觀地了解到各調(diào)用層次及其執(zhí)行情跡，從中可較

13、直觀地了解到各調(diào)用層次及其執(zhí)行情況。況。 李志欣第1章 第17頁Hanio(3,A,B,C)Hanio(2,A,C,B)Hanio(1,A,B,C)Move (A,C)Move (A,B)Hanio(1,C,A,B)Hanio(1,A,B,C)Hanio(2,A,C,B)Move (C,B)Hanio(1,C,A,B)Move (A,C)Hanio(2,B,A,C)Hanio(1,B,C,A)Move (B,C)Hanio(1,A,B,C)Hanio(1,B,C,A)Move (A,C)Hanio(2,B,A,C)Move (B,A)Hanio(1,A,B,C)結(jié)束結(jié)束 李志欣184.2.3

14、遞歸函數(shù)的內(nèi)部執(zhí)行過程遞歸函數(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í)行遞歸調(diào)用之前，把遞歸函數(shù)的值參和局部變量的當(dāng)前值以及調(diào)用后的返回地址壓棧；（3）每次遞歸調(diào)用結(jié)束后，將棧頂元素出棧，使相應(yīng)的值參和局部變量恢復(fù)為調(diào)用前的值，然后轉(zhuǎn)向返回地址指定的位置繼續(xù)執(zhí)行。 李志欣19漢諾塔算法漢諾塔算法在執(zhí)行過程中，工作棧的變化下圖所示，在執(zhí)行過程中，工作棧

15、的變化下圖所示，其中棧元素的結(jié)構(gòu)為（返回地址，其中棧元素的結(jié)構(gòu)為（返回地址，n值，值，A值，值，B值，值，C值），返回地址對應(yīng)算法中語句的行號。值），返回地址對應(yīng)算法中語句的行號。 0, 3, A, B, C5, 2, A, C, B0, 3, A, B, C5, 1, A, B, C5, 2, A, C, B0, 3, A, B, C5, 2, A, C, B0, 3, A, B, C7, 1, C, A, B5, 2, A, C, B0, 3, A, B, C5, 2, A, C, B0, 3, A, B, C0, 3, A, B, C7, 2, B, A, C0, 3, A, B, C5

16、, 1, B, C, A7, 2, B, A, C0, 3, A, B, C7, 2, B, A, C0, 3, A, B, C7, 1, A, B, C7, 2, B, A, C0, 3, A, B, C7, 2, B, A, C0, 3, A, B, C0, 3, A, B, C 李志欣20 遞歸算法結(jié)構(gòu)清晰，可讀性強，而且容易用遞歸算法結(jié)構(gòu)清晰，可讀性強，而且容易用數(shù)學(xué)歸納法來證明算法的正確性，因此，它為設(shè)數(shù)學(xué)歸納法來證明算法的正確性，因此，它為設(shè)計算法和調(diào)試程序帶來很大方便，是算法設(shè)計中計算法和調(diào)試程序帶來很大方便，是算法設(shè)計中的一種強有力的工具。但是，因為遞歸算法是一的一種強有力的工

17、具。但是，因為遞歸算法是一種自身調(diào)用自身的算法，隨著遞歸深度的增加，種自身調(diào)用自身的算法，隨著遞歸深度的增加，工作棧所需要的空間增大，遞歸調(diào)用時的輔助操工作棧所需要的空間增大，遞歸調(diào)用時的輔助操作增多，因此，遞歸算法的運行效率較低。作增多，因此，遞歸算法的運行效率較低。 李志欣21遞歸算法到非遞歸算法的轉(zhuǎn)換遞歸算法到非遞歸算法的轉(zhuǎn)換n遞歸算法的兩個基本特征：遞歸算法的兩個基本特征：(1)分而治之；分而治之；(2)效效率低。將遞歸算法轉(zhuǎn)換為非遞歸算法主要有兩率低。將遞歸算法轉(zhuǎn)換為非遞歸算法主要有兩種方法：種方法：n1.用循環(huán)結(jié)構(gòu)消除遞歸（沒有通用的轉(zhuǎn)換方法用循環(huán)結(jié)構(gòu)消除遞歸（沒有通用的轉(zhuǎn)換方法）

18、q階乘問題階乘問題int fun(int n) int f=1,i;for(i=2;i=n;i+) f=f*n;return f; 李志欣第1章 第22頁qFibonacci數(shù)列數(shù)列int Fib(int n) int i,f1,f2,f3;if(n=1|n=2) return n;f1=1; f2=2;for(i=3;i-1)/棧不空是循環(huán)棧不空是循環(huán)if(stacktop.tag =1)if(stacktop.n=1) stacktop.tag = 0;else 李志欣第1章 第25頁a=stacktop.x; b=stacktop.y;c=stacktop.z; num=stacktop

19、.n;top-; /退棧退棧hanoi(n,x,y,z)top+;/將將hanoi(n-1,y,x,z)進棧進棧stacktop.n=num-1;stacktop.x=b; stacktop.y=a;stacktop.z=c; stacktop.tag=1;top+;/將將move(n,x,z)進棧進棧stacktop.n=num;stacktop.x=a; stacktop.z=c; stacktop.tag=0;第1章 第26頁 李志欣top+; /將將hanoi(n-1,x,z,y)進棧進棧stacktop.n=num-1;stacktop.x=a; stacktop.y=c;stack

20、top.z=b; stacktop.tag=1;else if()printf(“t將第將第%d個盤片從個盤片從%c移動到移動到%cn”, stacktop.n, stacktop.x, stacktop.z);top-;/while/hanoi第1章 第27頁 李志欣4.3 排序問題中的分治法排序問題中的分治法4.3.1 4.3.1 歸并排序歸并排序4.3.2 4.3.2 快速排序快速排序 李志欣284.3.1 歸并排序歸并排序 二路歸并排序的分治策略是：二路歸并排序的分治策略是：（1）劃分劃分：將待排序序列：將待排序序列r1, r2, , rn劃分為兩個劃分為兩個長度相等的子序列長度相等的

21、子序列r1, , rn/2和和rn/21, , rn；（2）求解子問題求解子問題：分別對這兩個子序列進行排：分別對這兩個子序列進行排序，得到兩個有序子序列；序，得到兩個有序子序列；（3）合并合并：將這兩個有序子序列合并成一個有：將這兩個有序子序列合并成一個有序序列。序序列。 李志欣第1章 第29頁 r1 rn/2 rn/21 rn 劃分劃分r1 rn/2 rn/21 rn 遞歸處理遞歸處理r1rn/2rn/21 =1)2(211)(nnnTnnT 李志欣第1章 第32頁算法算法4.4合并有序子序列合并有序子序列 void Merge( (int r , int r1 , int s, int

22、m, int t) ) i=s; j=m+1; k=s; while ( (i=m & j=t) ) if ( (ri=rj) ) r1k+=ri+; /取取ri和和rj中較小者放入中較小者放入r1k else r1k+=rj+; if ( (i=m) ) while ( (i=m) ) /若第一個子序列沒處理完，則進行收尾處理若第一個子序列沒處理完，則進行收尾處理 r1k+=ri+; else while ( (j=t) ) /若第二個子序列沒處理完，則進行收尾處理若第二個子序列沒處理完，則進行收尾處理 r1k+=rj+; 李志欣第1章 第33頁4.3.2 快速排序快速排序 （2）求

23、解子問題求解子問題：分別對劃分后的每一個子序列：分別對劃分后的每一個子序列遞歸處理；遞歸處理；（3）合并合并：由于對子序列：由于對子序列r1 ri-1和和ri+1 rn的排序的排序是就地進行的，所以合并不需要執(zhí)行任何操作。是就地進行的，所以合并不需要執(zhí)行任何操作?？焖倥判虻姆种尾呗允牵嚎焖倥判虻姆种尾呗允牵海?）劃分劃分：選定一個記錄作為軸值，以軸值為基準(zhǔn)：選定一個記錄作為軸值，以軸值為基準(zhǔn)將整個序列劃分為兩個子序列將整個序列劃分為兩個子序列r1 ri- -1和和ri+1 rn，前一個子序列中記錄的值均小于或等于軸值，后一前一個子序列中記錄的值均小于或等于軸值，后一個子序列中記錄的值均大于或等

24、于軸值；個子序列中記錄的值均大于或等于軸值； 李志欣第1章 第34頁 r1 ri- -1 ri ri+1 rn 均均ri 軸值軸值 均均ri 位于最終位置位于最終位置 v歸并排序按照記錄在序列中的位置對序列進行劃分，歸并排序按照記錄在序列中的位置對序列進行劃分，v快速排序按照記錄的值對序列進行劃分。快速排序按照記錄的值對序列進行劃分。 李志欣第1章 第35頁以第一個記錄作為軸值，對待排序序列進行劃分的過程為：以第一個記錄作為軸值，對待排序序列進行劃分的過程為：（1）初始化初始化：取第一個記錄作為基準(zhǔn)，設(shè)置兩個參數(shù)：取第一個記錄作為基準(zhǔn)，設(shè)置兩個參數(shù)i，j分分別用來指示將要與基準(zhǔn)記錄進行比較的左

25、側(cè)記錄位置和右側(cè)別用來指示將要與基準(zhǔn)記錄進行比較的左側(cè)記錄位置和右側(cè)記錄位置，也就是本次劃分的區(qū)間；記錄位置，也就是本次劃分的區(qū)間；（2）右側(cè)掃描過程右側(cè)掃描過程：將基準(zhǔn)記錄與：將基準(zhǔn)記錄與j指向的記錄進行比較，指向的記錄進行比較，如果如果j指向記錄的關(guān)鍵碼大，則指向記錄的關(guān)鍵碼大，則j前移一個記錄位置。重復(fù)右前移一個記錄位置。重復(fù)右側(cè)掃描過程，直到右側(cè)的記錄?。捶葱颍魝?cè)掃描過程，直到右側(cè)的記錄?。捶葱颍鬷j，則將，則將基準(zhǔn)記錄與基準(zhǔn)記錄與j指向的記錄進行交換；指向的記錄進行交換；（3）左側(cè)掃描過程左側(cè)掃描過程：將基準(zhǔn)記錄與：將基準(zhǔn)記錄與i指向的記錄進行比較，指向的記錄進行比較，如

26、果如果i指向記錄的關(guān)鍵碼小，則指向記錄的關(guān)鍵碼小，則i后移一個記錄位置。重復(fù)左后移一個記錄位置。重復(fù)左側(cè)掃描過程，直到左側(cè)的記錄大（即反序），若側(cè)掃描過程，直到左側(cè)的記錄大（即反序），若ij，則將，則將基準(zhǔn)記錄與基準(zhǔn)記錄與i指向的記錄交換；指向的記錄交換；（4）重復(fù)重復(fù)（2）（）（3）步，直到）步，直到i與與j指向同一位置，即基準(zhǔn)記指向同一位置，即基準(zhǔn)記錄最終的位置。錄最終的位置。 李志欣36jijjjiiiijjj一次劃分示例一次劃分示例 李志欣37算法算法4.5一次劃分一次劃分 int Partition( (int r , int first, int end) ) i=first; j

27、=end; /初始化初始化 while ( (ij) ) while ( (ij & ri= rj) ) j-； /右側(cè)掃描右側(cè)掃描 if ( (ij) ) rirj; /將較小記錄交換到前面將較小記錄交換到前面 i+; while ( (ij & ri= rj) ) i+； /左側(cè)掃描左側(cè)掃描 if ( (ij) ) rjri; /將較大記錄交換到后面將較大記錄交換到后面 j-; retutn i; / i為軸值記錄的最終位置為軸值記錄的最終位置 李志欣38 以軸值為基準(zhǔn)將待排序序列劃分為兩個子序以軸值為基準(zhǔn)將待排序序列劃分為兩個子序列后，對每一個子序列分別遞歸進行排序。列后

28、，對每一個子序列分別遞歸進行排序。jiij 李志欣39算法4.6快速排序 void QuickSort(int r , int first, int end) if (first0) sum=aleft; else sum=0; else center=(left+right)/2; /劃分劃分 leftsum=MaxSum(a, left, center); /對應(yīng)情況，遞歸求解對應(yīng)情況，遞歸求解 rightsum=MaxSum(a, center+1, right); /對應(yīng)情況，遞歸求解對應(yīng)情況，遞歸求解 李志欣48 s1=0; lefts=0; /以下對應(yīng)情況，先求解以下對應(yīng)情況，先求

29、解s1 for (i=center; i=left; i-) lefts+=ai; if (leftss1) s1=lefts; s2=0; rights=0; /再求解再求解s2 for (j=center+1; js2) s2=rights; sum=s1+s2; /計算情況的最大子段和計算情況的最大子段和 if (sumleftsum) sum=leftsum; /合并，在合并，在sum、leftsum和和rightsum中取較大者中取較大者 if (sum=1)2(211)(nnnTnnT 李志欣504.4.2 棋盤覆蓋問題棋盤覆蓋問題 在一個在一個2k2k （k0）個方格組成的棋盤中

30、，）個方格組成的棋盤中，恰有一個方格與其他方格不同，稱該方格為特殊恰有一個方格與其他方格不同，稱該方格為特殊方格。棋盤覆蓋問題要求用圖方格。棋盤覆蓋問題要求用圖4.11（b）所示的）所示的4種不同形狀的種不同形狀的L型骨牌覆蓋給定棋盤上除特殊方型骨牌覆蓋給定棋盤上除特殊方格以外的所有方格，且任何格以外的所有方格，且任何2個個L型骨牌不得重疊型骨牌不得重疊覆蓋。覆蓋。(a) k=2時的一種棋盤時的一種棋盤 (b) 4種不同形狀的種不同形狀的L型骨牌型骨牌 李志欣51 分治法求解棋盤覆蓋問題的技巧在于劃分棋盤，使劃分治法求解棋盤覆蓋問題的技巧在于劃分棋盤，使劃分后的子棋盤的大小相同，并且每個子棋盤

31、均包含一個特分后的子棋盤的大小相同，并且每個子棋盤均包含一個特殊方格，從而將原問題分解為規(guī)模較小的棋盤覆蓋問題。殊方格，從而將原問題分解為規(guī)模較小的棋盤覆蓋問題。 k0時，可將時，可將2k2k的棋盤劃分為的棋盤劃分為4個個2k-12k-1的子棋盤，的子棋盤，這樣劃分后，由于原棋盤只有一個特殊方格，所以，這這樣劃分后，由于原棋盤只有一個特殊方格，所以，這4個個子棋盤中只有一個子棋盤包含該特殊方格，其余子棋盤中只有一個子棋盤包含該特殊方格，其余3個子棋盤個子棋盤中沒有特殊方格。為了將這中沒有特殊方格。為了將這3個沒有特殊方格的子棋盤轉(zhuǎn)化個沒有特殊方格的子棋盤轉(zhuǎn)化為特殊棋盤，以便采用遞歸方法求解，可

32、以用一個為特殊棋盤，以便采用遞歸方法求解，可以用一個L型骨牌型骨牌覆蓋這覆蓋這3個較小棋盤的會合處，從而將原問題轉(zhuǎn)化為個較小棋盤的會合處，從而將原問題轉(zhuǎn)化為4個較個較小規(guī)模的棋盤覆蓋問題。遞歸地使用這種劃分策略，直至小規(guī)模的棋盤覆蓋問題。遞歸地使用這種劃分策略，直至將棋盤分割為將棋盤分割為11的子棋盤。的子棋盤。 李志欣522k-12k-12k-12k-12k-12k-12k-12k-1(a)棋盤分割棋盤分割 (b) 構(gòu)造相同子問題構(gòu)造相同子問題 李志欣第1章 第53頁下面討論棋盤覆蓋問題中數(shù)據(jù)結(jié)構(gòu)的設(shè)計。下面討論棋盤覆蓋問題中數(shù)據(jù)結(jié)構(gòu)的設(shè)計。（1）棋盤：可以用一個二維數(shù)組）棋盤：可以用一個二

33、維數(shù)組boardsizesize表示一個表示一個棋盤，其中，棋盤，其中，size=2k。為了在遞歸處理的過程中使用同一個。為了在遞歸處理的過程中使用同一個棋盤，將數(shù)組棋盤，將數(shù)組board設(shè)為全局變量；設(shè)為全局變量；（2）子棋盤：整個棋盤用二維數(shù)組）子棋盤：整個棋盤用二維數(shù)組boardsizesize表示，表示，其中的子棋盤由棋盤左上角的下標(biāo)其中的子棋盤由棋盤左上角的下標(biāo)tr、tc和棋盤大小和棋盤大小s表示；表示； （3）特殊方格：用）特殊方格：用boarddrdc表示特殊方格，表示特殊方格，dr和和dc是該特殊方格在二維數(shù)組是該特殊方格在二維數(shù)組board中的下標(biāo)中的下標(biāo); （4） L型骨牌

34、：一個型骨牌：一個2k2k的棋盤中有一個特殊方格，所的棋盤中有一個特殊方格，所以，用到以，用到L型骨牌的個數(shù)為型骨牌的個數(shù)為(4k-1)/3，將所有，將所有L型骨牌從型骨牌從1開始開始連續(xù)編號，用一個全局變量連續(xù)編號，用一個全局變量t表示。表示。 李志欣54dcdrtrtcsize棋盤覆蓋問題中的數(shù)據(jù)結(jié)構(gòu)棋盤覆蓋問題中的數(shù)據(jù)結(jié)構(gòu) 李志欣第1章 第55頁算法算法4.8棋盤覆蓋棋盤覆蓋void ChessBoard(int tr, int tc, int dr, int dc, int size)/ tr和和tc是棋盤左上角的下標(biāo)，是棋盤左上角的下標(biāo)，dr和和dc是特殊方格的下標(biāo)，是特殊方格的下標(biāo)

35、，/ size是棋盤的大小，是棋盤的大小，t已初始化為已初始化為0 if (size = = 1) return; /棋盤只有一個方格且是特殊方格棋盤只有一個方格且是特殊方格 t+; / L型骨牌號型骨牌號 s = size/2; / 劃分棋盤劃分棋盤 / 覆蓋左上角子棋盤覆蓋左上角子棋盤 if (dr tr + s & dc tc + s) / 特殊方格在左上角子棋盤中特殊方格在左上角子棋盤中 ChessBoard(tr, tc, dr, dc, s); /遞歸處理子棋盤遞歸處理子棋盤 else / 用用 t 號號L型骨牌覆蓋右下角，再遞歸處理子棋盤型骨牌覆蓋右下角，再遞歸處理子棋盤

36、 boardtr + s - - 1tc + s - - 1 = t; ChessBoard(tr, tc, tr+s- -1, tc+s- -1, s); 李志欣56 / 覆蓋右上角子棋盤覆蓋右上角子棋盤 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-

37、1, tc+s, s); / 覆蓋左下角子棋盤覆蓋左下角子棋盤 if (dr = tr + s & dc = tr + s & dc = tc + s) / 特殊方格在右下角子棋盤中特殊方格在右下角子棋盤中 ChessBoard(tr+s, tc+s, dr, dc, s); /遞歸處理子棋盤遞歸處理子棋盤 else / 用用 t 號號L型骨牌覆蓋左上角，再遞歸處理子棋盤型骨牌覆蓋左上角，再遞歸處理子棋盤 boardtr + stc + s = t; ChessBoard(tr+s, tc+s, tr+s, tc+s, s); 李志欣第1章 第57頁 設(shè)設(shè)T( (k) )是覆蓋

38、一個是覆蓋一個2k2k棋盤所需時間，從算棋盤所需時間，從算法的劃分策略可知，法的劃分策略可知，T( (k) )滿足如下遞推式：滿足如下遞推式： =00) 1 () 1(4) 1 ()(kkOkTOkT 解此遞推式可得解此遞推式可得T( (k) )=O( (4k) )。由于覆蓋一個。由于覆蓋一個2k2k棋盤所需的骨牌個數(shù)為棋盤所需的骨牌個數(shù)為(4k- -1)/ /3，所以，算，所以，算法法4.8是一個在漸進意義下的最優(yōu)算法。是一個在漸進意義下的最優(yōu)算法。 李志欣584.4.3 循環(huán)賽日程安排問題循環(huán)賽日程安排問題 設(shè)有設(shè)有n=2k個選手要進行網(wǎng)球循環(huán)賽，要求設(shè)個選手要進行網(wǎng)球循環(huán)賽，要求設(shè)計一個

39、滿足以下要求的比賽日程表：計一個滿足以下要求的比賽日程表：（1）每個選手必須與其他）每個選手必須與其他n- -1個選手各賽一次；個選手各賽一次；（2）每個選手一天只能賽一次。）每個選手一天只能賽一次。 按此要求，可將比賽日程表設(shè)計成一個按此要求，可將比賽日程表設(shè)計成一個 n 行行n- -1列的二維表，其中，第列的二維表，其中，第 i 行第行第 j 列表示和第列表示和第 i 個選手在第個選手在第 j 天比賽的選手。天比賽的選手。 李志欣第1章 第59頁 按照分治的策略，可將所有參賽的選手分為兩按照分治的策略，可將所有參賽的選手分為兩部分，部分，n2k個選手的比賽日程表就可以通過為個選手的比賽日程

40、表就可以通過為n/22k-1個選手設(shè)計的比賽日程表來決定。遞歸個選手設(shè)計的比賽日程表來決定。遞歸地執(zhí)行這種分割，直到只剩下地執(zhí)行這種分割，直到只剩下2個選手時，比賽個選手時，比賽日程表的制定就變得很簡單：只要讓這日程表的制定就變得很簡單：只要讓這2個選手個選手進行比賽就可以了。進行比賽就可以了。 李志欣第1章 第60頁 顯然，這個求解過程是自底向上的迭代過程，其中左上角顯然，這個求解過程是自底向上的迭代過程，其中左上角和左下角分別為選手和左下角分別為選手1至選手至選手4以及選手以及選手5至選手至選手8前前3天的比賽天的比賽日程，據(jù)此，將左上角部分的所有數(shù)字按其對應(yīng)位置抄到右下日程，據(jù)此，將左上

41、角部分的所有數(shù)字按其對應(yīng)位置抄到右下角，將左下角的所有數(shù)字按其對應(yīng)位置抄到右上角，這樣，就角，將左下角的所有數(shù)字按其對應(yīng)位置抄到右上角，這樣，就分別安排好了選手分別安排好了選手1至選手至選手4以及選手以及選手5至選手至選手8在后在后4天的比賽天的比賽日程，如圖日程，如圖(c)所示。具有多個選手的情況可以依此類推。所示。具有多個選手的情況可以依此類推。 (b) 2k(k=2)個選手比賽個選手比賽 (c) 2k(k=3)個選手比賽個選手比賽加加4加加2(a) 2k(k=1)個選手比賽個選手比賽12211 22 13 44 33 44 31 22 11 2 3 42 1 4 33 4 1 24 3

42、2 15 6 7 86 5 8 77 8 5 68 7 6 55 6 7 86 5 8 77 8 5 68 7 6 51 2 3 42 1 4 33 4 1 24 3 2 1 李志欣61 這種解法是把求解這種解法是把求解2k個選手比賽日程問題劃分成依次求解個選手比賽日程問題劃分成依次求解21、22、2k個選手的比賽日程問題，換言之，個選手的比賽日程問題，換言之，2k個選手的個選手的比賽日程是在比賽日程是在2k-1個選手的比賽日程的基礎(chǔ)上通過迭代的方法個選手的比賽日程的基礎(chǔ)上通過迭代的方法求得的。在每次迭代中，將問題劃分為求得的。在每次迭代中，將問題劃分為4部分：部分：（1）左上角：左上角為）左

43、上角：左上角為2k-1個選手在前半程的比賽日程；個選手在前半程的比賽日程；（2）左下角：左下角為另）左下角：左下角為另2k-1個選手在前半程的比賽日程，個選手在前半程的比賽日程，由左上角加由左上角加2k-1得到，例如得到，例如22個選手比賽，左下角由左上角直個選手比賽，左下角由左上角直接加接加2得到，得到，23個選手比賽，左下角由左上角直接加個選手比賽，左下角由左上角直接加4得到；得到；（3）右上角：將左下角直接抄到右上角得到另）右上角：將左下角直接抄到右上角得到另2k-1個選手在個選手在后半程的比賽日程；后半程的比賽日程；（4）右下角：將左上角直接抄到右下角得到）右下角：將左上角直接抄到右下

44、角得到2k-1個選手在后個選手在后半程的比賽日程；半程的比賽日程； 算法設(shè)計的關(guān)鍵在于尋找這算法設(shè)計的關(guān)鍵在于尋找這4部分元素之間的對應(yīng)關(guān)系。部分元素之間的對應(yīng)關(guān)系。 李志欣62算法算法4.9循環(huán)賽日程表循環(huán)賽日程表 void GameTable(int k, int a ) / n=2k( (k1) )個選手參加比賽，個選手參加比賽， /二維數(shù)組二維數(shù)組a表示日程安排，數(shù)組下標(biāo)從表示日程安排，數(shù)組下標(biāo)從1開始開始 n=2; /k=0，2個選手比賽日程可直接求得個選手比賽日程可直接求得 /求解求解2個選手比賽日程，得到左上角元素個選手比賽日程，得到左上角元素 a11=1; a12=2; a21

45、=2; a22=1; for (t=1; tk; t+) /迭代處理，依次處理迭代處理，依次處理22, , 2k個選手比賽日程個選手比賽日程 李志欣63 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)系左下角元素和左上角元素的對應(yīng)關(guān)系 /填右上角元素填右上角元素 for (i=1; i=temp; i+) for (j=temp+1; j=n; j+) aij=ai+temp(j+temp)% n; /填右下角元素填右下

46、角元素 for (i=temp+1; i=n; i+) for (j=temp+1; j=n; j+) aij=ai-tempj-temp; 李志欣第1章 第64頁 分析算法分析算法4.9的時間性能，迭代處理的循環(huán)體內(nèi)部有的時間性能，迭代處理的循環(huán)體內(nèi)部有3個循環(huán)語句，每個循環(huán)語句都是一個嵌套的個循環(huán)語句，每個循環(huán)語句都是一個嵌套的for循環(huán)，且他循環(huán)，且他們的執(zhí)行次數(shù)相同，基本語句是最內(nèi)層循環(huán)體的賦值語句，們的執(zhí)行次數(shù)相同，基本語句是最內(nèi)層循環(huán)體的賦值語句，即填寫比賽日程表中的元素。基本語句的執(zhí)行次數(shù)是：即填寫比賽日程表中的元素?；菊Z句的執(zhí)行次數(shù)是：所以，算法所以，算法4.9的其時間復(fù)雜性

47、為的其時間復(fù)雜性為O(4k)。=11212111)4(4313)(ktijktktttOnT 李志欣654.5 幾何問題中的分治法幾何問題中的分治法4.5.1 最近對問題最近對問題 4.5.2 凸包問題凸包問題 李志欣664.5.1 最近對問題最近對問題 設(shè)設(shè)p1=(x1, y1), p2=(x2, y2), , pn=(xn, yn)是平面是平面上上n個點構(gòu)成的集合個點構(gòu)成的集合S，最近對問題就是找出集合，最近對問題就是找出集合S中距離最近的點對。中距離最近的點對。 嚴(yán)格地講，最接近點對可能多于一對，簡單嚴(yán)格地講，最接近點對可能多于一對，簡單起見，只找出其中的一對作為問題的解。起見，只找出其

48、中的一對作為問題的解。 李志欣第1章 第67頁 用分治法解決最近對問題，很自然的想法就用分治法解決最近對問題，很自然的想法就是將集合是將集合S分成兩個子集分成兩個子集 S1和和 S2，每個子集中，每個子集中有有n/2個點。然后在每個子集中遞歸地求其最接近個點。然后在每個子集中遞歸地求其最接近的點對，在求出每個子集的最接近點對后，在合的點對，在求出每個子集的最接近點對后，在合并步中，如果集合并步中，如果集合 S 中最接近的兩個點都在子集中最接近的兩個點都在子集 S1或或 S2中，則問題很容易解決，如果這兩個點中，則問題很容易解決，如果這兩個點分別在分別在 S1和和 S2中，問題就比較復(fù)雜了。中，

49、問題就比較復(fù)雜了。 李志欣第1章 第68頁為了使問題易于理解，先考慮為了使問題易于理解，先考慮一維一維的情形。的情形。此時，此時，S中的點退化為中的點退化為x軸上的軸上的n個點個點x1, x2, , xn。用。用x軸上軸上的某個點的某個點m將將S劃分為兩個集合劃分為兩個集合S1和和S2，并且，并且S1和和S2含有點含有點的個數(shù)相同。遞歸地在的個數(shù)相同。遞歸地在S1和和S2上求出最接近點對上求出最接近點對 (p1, p2) 和和(q1, q2)，如果集合，如果集合S中的最接近點對都在子集中的最接近點對都在子集S1或或S2中，則中，則d=min(p1, p2), (q1, q2)即為所求，如果集合

50、即為所求，如果集合S中的最接近點中的最接近點對分別在對分別在S1和和S2中，則一定是中，則一定是(p3, q3)，其中，其中，p3是子集是子集S1中中的最大值，的最大值，q3是子集是子集S2中的最小值。中的最小值。S1S2p2p1p3q3q1q2m 李志欣69 按這種分治策略求解最近對問題的算法按這種分治策略求解最近對問題的算法效率取決于劃分點效率取決于劃分點m的選取，一個基本的要求的選取，一個基本的要求是要遵循平衡子問題的原則。如果選取是要遵循平衡子問題的原則。如果選取m=(maxS+minS)/2，則有可能因集合，則有可能因集合S中中點分布的不均勻而造成子集點分布的不均勻而造成子集S1和和

51、S2的不平衡，的不平衡，如果用如果用S中各點坐標(biāo)的中位數(shù)（即中各點坐標(biāo)的中位數(shù)（即S的中值）的中值）作為分割點，則會得到一個平衡的分割點作為分割點，則會得到一個平衡的分割點m，使得子集使得子集S1和和S2中有個數(shù)大致相同的點。中有個數(shù)大致相同的點。 李志欣第1章 第70頁下面考慮下面考慮二維二維的情形，此時的情形，此時S中的點為平面上的點。中的點為平面上的點。為了將平面上的點集為了將平面上的點集S 分割為點的個數(shù)大致相同的兩個子集分割為點的個數(shù)大致相同的兩個子集S1和和S2，選取垂直線，選取垂直線x=m來作為分割線，其中，來作為分割線，其中，m為為S中各點中各點x坐標(biāo)的中位數(shù)。由此將坐標(biāo)的中位

52、數(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è)，不妨設(shè)pS1，qS2，則，則p和和q距直線距直線x=m的距離均的距離均小于小于d，所以，可以將求解限制在以，所以，可以將求解限制在以x=m為中心、寬度為為中心、寬度為2d的垂直帶的垂直帶P1和和P2中，垂直帶之外的任何點

53、對之間的距離都中，垂直帶之外的任何點對之間的距離都一定大于一定大于d。 李志欣71x=mddd2d1S1S2pq 最近對問題的分治思想最近對問題的分治思想P1P2S1=pS | xpmS2=qS | xqm 李志欣72x=mddp(a) 包含點包含點q的的d2d的矩形區(qū)域的矩形區(qū)域 (b) 最壞情況下需要檢查的最壞情況下需要檢查的6個點個點P1P22dx=mddpP1P22d 對于點對于點pP1，需要考察，需要考察P2中的各個點和點中的各個點和點p之間的距之間的距離是否小于離是否小于d，顯然，顯然，P2中這樣點的中這樣點的y軸坐標(biāo)一定位于區(qū)間軸坐標(biāo)一定位于區(qū)間y- -d, y+d之間，而且，這樣的點不會超過之間，而且，這樣的點不會超過6個。個。 李志欣73 應(yīng)用分治法求解含有應(yīng)用分治法求解含有n個點的最近對問題，其個點的最近對問題，其時間復(fù)雜性可由下面的遞推式表示：時間復(fù)雜性可由下面的遞推式表示： 合并子問題的解的時間合并子問題的解的時間f( (n) )O( (1) )，根據(jù)，根