CH分治實(shí)用教學(xué)課件

1、知識要點(diǎn) 遞歸的概念和典型的遞歸問題 階乘、Fibonacci數(shù)列、hanoi塔等問題 分治法的基本思想 分治法的典型例子 二分搜索、矩陣乘法、歸并排序、快速排序 大整數(shù)的乘法、最接近點(diǎn)對問題第1頁/共83頁第1頁，共83頁。2.1 遞歸的概念第2頁/共83頁第2頁，共83頁。遞歸(recursion)什么是遞歸？程序調(diào)用自身的編程技巧稱為遞歸基本思路將一個大型的復(fù)雜問題轉(zhuǎn)化為一些與原問題相似的規(guī)模較小的問題來求解第3頁/共83頁第3頁，共83頁。遞歸(recursive)如果函數(shù)調(diào)用它本身，那么此函數(shù)就是遞歸的例如n!的定義就是遞歸的：n! = n (n 1)!考察下面的函數(shù)：int fac

2、t(int n) if (n = 1) /初值，1！=1 return 1; else return n * fact(n - 1);為了解遞歸的工作原理，我們來跟蹤 fact(4) 的執(zhí)行遞歸終止條件遞歸表達(dá)式第4頁/共83頁第4頁，共83頁。調(diào)用函數(shù)時系統(tǒng)的工作在調(diào)用函數(shù)時系統(tǒng)需要完成3件事：將所有實(shí)參（指針），返回地址傳遞給被調(diào)用的函數(shù)為被調(diào)用函數(shù)的局部變量分配存儲區(qū)將控制轉(zhuǎn)移到被調(diào)用函數(shù)的入口從被調(diào)用函數(shù)返回時系統(tǒng)也要做3件事：保存被調(diào)用算法的計算結(jié)果（返回值）釋放分配給被調(diào)用算法的存儲空間依照被調(diào)算法保存的返回地址將控制轉(zhuǎn)移回到調(diào)用算法第5頁/共83頁第5頁，共83頁。遞歸過程與遞歸

3、工作棧遞歸過程執(zhí)行時需多次調(diào)用自身。多個(相同)函數(shù)嵌套調(diào)用，信息傳遞和控制轉(zhuǎn)移通過棧實(shí)現(xiàn)每一次遞歸調(diào)用時，需要為過程中所使用的參數(shù)、局部變量等另外分配存儲空間層層向下遞歸，退出時次序正好相反每層遞歸調(diào)用需分配的空間形成遞歸工作記錄，用棧按照后進(jìn)先出規(guī)則管理這些信息第6頁/共83頁第6頁，共83頁。階乘的遞歸調(diào)用過程第7頁/共83頁第7頁，共83頁。int fact(int n) if (n =2，nN）問題定義是遞歸的!第12頁/共83頁第12頁，共83頁。遞歸定義式非遞歸定義式：斐波納契數(shù)列第13頁/共83頁第13頁，共83頁。斐波納契數(shù)列解法1：遞歸long fib1(int n) if

4、 (n = 1) return 1; else return fib1(n - 1) + fib1(n - 2); 第14頁/共83頁第14頁，共83頁。斐波那契數(shù)列的遞歸求解過程調(diào)用次數(shù) NumCall(k)=2k-1-1fibonacci(5)的遞歸求解過程：算法復(fù)雜度：O(2n)第15頁/共83頁第15頁，共83頁。斐波納契數(shù)列解法2：遞推long fib2(int n) long f1 = 1, f2 = 1, fu; for(int i = 2; i =2)F(n) 具有“無后效性”：只需“記住”前兩個狀態(tài)的結(jié)果即可第16頁/共83頁第16頁，共83頁。遞歸的應(yīng)用場景（2）問題采用的

5、數(shù)據(jù)結(jié)構(gòu)是遞歸的第17頁/共83頁第17頁，共83頁。二叉樹鏈?zhǔn)酱鎯Y(jié)構(gòu)：二叉鏈表typedef struct node Entrytype data; struct node *lchild, *rchild; BTNode, *BTPtr; lchild data rchild ABCDEFG在n個結(jié)點(diǎn)的二叉鏈表中，有n+1個空指針域 AB C D E F G有多少指針為空？遞歸算法示例2：數(shù)據(jù)結(jié)構(gòu)是遞歸的第18頁/共83頁第18頁，共83頁。void inorder ( BTPtr bt) if(bt != NULL) inorder ( bt-lchild ); printf (%ct

6、, bt-data); inorder ( bt-rchild ); return; 中序遍歷遞歸算法ACBD中序序列： BDACvoid postorder( BTPtr bt) if(bt != NULL) postorder( bt-lchild ); postorder( bt-rchild ); printf (%ct, bt-data); return; 后序遍歷遞歸算法后序序列： DBCA第19頁/共83頁第19頁，共83頁。遞歸的應(yīng)用場景（3）問題的求解過程是遞歸的第20頁/共83頁第20頁，共83頁。示例1：Hanoi Tower（漢諾塔）問題 問題描述：設(shè)有A、B、C3個塔

7、座在塔座A上有一疊共n個圓盤自上而下，由小到大地疊在一起自上而下依次編號為1,2,n問題：要求將塔座A上的圓盤全部移到塔座C上，仍按同樣順序疊置。在移動圓盤時遵守以下規(guī)則：每次只允許移動1個圓盤任何時刻都不允許將較大的圓盤壓在較小的圓盤之上在規(guī)則1和2的前提下，可將圓盤移至任何一塔座上第21頁/共83頁第21頁，共83頁。用遞歸技術(shù)求解漢諾塔問題 將3個盤子從A移至C，以B為輔助（7步完成）（1）1#A-C（2）2#A-B（3）1#C-B（4）3#A-C（5）1#B-A（6）2#B-C（7）1#A-C第22頁/共83頁第22頁，共83頁。用遞歸技術(shù)求解漢諾塔問題 將4個盤子從A移至C，以B為輔

8、助第23頁/共83頁第23頁，共83頁。漢諾塔問題的規(guī)模 一般的Hanoi塔玩具不超過8片 如果n=8，需移動255次如果n=10，需移動1023次如果n=15，需移動32767次如果n=20，需移動1048575次（超過一百萬次）如果n=64，需移動264-1次（超過一百萬次）如果每秒移動一塊圓盤，需5845.54億年按照宇宙大爆炸理論推測，宇宙的年齡也僅為137億年第24頁/共83頁第24頁，共83頁。用遞歸技術(shù)求解漢諾塔問題 算法設(shè)計思路 當(dāng)n=1時，問題可以直接求解，一步完成當(dāng)n1時，分三步完成：將n-1個較小盤子設(shè)法移動到輔助塔座構(gòu)造出一個比原問題規(guī)模小1的問題將最大的盤子從原塔座一

9、步移至目標(biāo)塔座將n-1個較小的盤子設(shè)法從輔助塔座移至目標(biāo)塔座仍然是比原問題規(guī)模小1的問題第25頁/共83頁第25頁，共83頁。漢諾塔問題的遞歸算法其中：hanoi(int n, int src, int tar, int aux) 表示將塔座src上的n個盤子移動到塔座tar，以塔座aux為輔助（auxiliary）void hanoi (int n, int src, int tar, int aux) if(n0) hanoi(n-1, src, aux, tar); move(src, tar); hanoi(n-1, aux, tar, src); 第26頁/共83頁第26頁，共83頁

10、。示例2：排列問題 設(shè)計一個遞歸算法：生成n個元素r1,r2,rn的全排列設(shè)R=r1,r2,rn是要進(jìn)行排列的n個元素，Ri=R-ri集合X中元素的全排列記為：perm(X)(ri)perm(X) ：在perm(X)的每個排列前加上前綴得到的排列R的全排列可歸納定義如下：當(dāng)n=1時，perm(R)=(r)，其中r是集合R中唯一的元素當(dāng)n1時，perm(R)的構(gòu)成情況如下：(r1)perm(R1)，(r2)perm(R2)， ， (rn)perm(Rn)第27頁/共83頁第27頁，共83頁。templatevoid Perm(Type list , int k, int m) /產(chǎn)生listk:

11、m的所有排列 if (k=m) /只剩下一個元素 for (int i=0; i=m; i+) cout listi; coutendl; else /還有多個元素待排列，遞歸產(chǎn)生排列 for(int i=k; i=m; i+) Swap(listk, listi); Perm(list, k+1, m); Swap(listk, listi); templateinline void Swap(Type &a, Type &b) Type temp=a; a=b; b=temp;第28頁/共83頁第28頁，共83頁。void perm(type R, int k, int m) if (k=

12、m) / 只剩下一個元素 for (int i=0; i=m; i+) cout Ri; coutendl; else / 還有多個元素待排列，遞歸產(chǎn)生排列 for(int i=k; i=m; i+) int tmp = Rk; Rk = Ri; Ri = tmp; perm(R, k+1, m); tmp = Rk; Rk = Ri; Ri = tmp; 排列問題：產(chǎn)生listk:m的所有排列第29頁/共83頁第29頁，共83頁。遞歸小結(jié)使用遞歸的注意事項(xiàng)原始問題可以分解為相似的子問題子問題的規(guī)模小于原始問題思考：只要問題變小就適合用遞歸么？遞歸函數(shù)必須有某些類型的終止條件遞歸的應(yīng)用問題的定

13、義是遞歸的，如階乘問題問題的求解過程是遞歸的，如漢諾塔問題 問題采用的數(shù)據(jù)結(jié)構(gòu)是遞歸的，如鏈表中搜索元素第30頁/共83頁第30頁，共83頁。遞歸小結(jié)遞歸算法的優(yōu)點(diǎn)結(jié)構(gòu)清晰，易于理解，而且容易用數(shù)學(xué)歸納法來證明算法的正確性，因此用遞歸技術(shù)來設(shè)計算法很方便。遞歸算法的缺點(diǎn)在執(zhí)行時要多次調(diào)用自身，運(yùn)行效率較低，無論是計算時間還是占用存儲空間都要比非遞歸算法要多。一些運(yùn)算步驟可能重復(fù)運(yùn)算，會進(jìn)一步降低效率。第31頁/共83頁第31頁，共83頁。2.2 分治法的思想第32頁/共83頁第32頁，共83頁。分治法的基本步驟經(jīng)驗(yàn)：實(shí)踐表明，在用分治法設(shè)計算法時，最好使子問題的規(guī)模大致相同，即：將一個問題分成

14、大小相等的k個子問題。這種使子問題規(guī)模大致相等的做法是出自一種平衡(balancing)子問題的思想，它幾乎總是比子問題規(guī)模不等的做法要好。divide-and-conquer(P) if ( | P | = n0) solve(P); / 解決小規(guī)模的問題 divide P into smaller subinstances P1,P2,.,Pk； / 分解 for ( i=1, ilchild) & (!pbt-rchild) return 1; dL = get_depth(pbt-lchild); dR = get_depth(pbt-rchild); / 二叉樹的深度為根結(jié)點(diǎn)左、右子

15、樹的深度值較大者加一 return 1 + (dL dR) ? dL : dR); DivideConquerCombine第35頁/共83頁第35頁，共83頁。分治法的適用條件分治法所能解決的問題一般具有以下四個特征：該問題的規(guī)模縮小到一定的程度就可以容易地解決因?yàn)閱栴}的計算復(fù)雜性一般是隨著問題規(guī)模的增加而增加，因此大部分問題滿足這個特征該問題可以分解為若干個規(guī)模較小的相同問題即：該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)這條特征是應(yīng)用分治法的前提，它也是大多數(shù)問題可以滿足的，此特征反映的就是遞歸算法的設(shè)計思想第36頁/共83頁第36頁，共83頁。分治法的適用條件分治法所能解決的問題一般具有以下四個特征：利用

16、子問題的解可以合并得到原始問題的解能否利用分治法完全取決于問題是否具有這條特征如果具備了前兩條特征，而不具備第三條特征，則可以考慮貪心算法或動態(tài)規(guī)劃該問題所分解出的各個子問題是相互獨(dú)立的即：子問題之間不包含公共的子問題這條特征涉及到分治法的效率，如果各子問題是不獨(dú)立的，則采用分治法需要重復(fù)地求解公共的子問題，此時雖然也可用分治法，但一般用動態(tài)規(guī)劃較好第37頁/共83頁第37頁，共83頁。分治法示例1：二分搜索技術(shù)給定：已按升序排好序的n個元素a0:n-1問題：在這n個元素中找出一特定元素x。分析1：該問題的規(guī)?？s小到一定的程度就可以容易地解決如果n=1，則通過一次比較就可以解決問題分析2：該問

17、題可以分解為若干個規(guī)模較小的相同問題取中間元素amid對序列進(jìn)行劃分在amid前面或后面查找x，其方法都和在a中查找x一樣分析3：分解出的子問題的解可以合并為原問題的解分析4：分解出的各個子問題是相互獨(dú)立的在ai的前面或后面查找x是獨(dú)立的子問題第38頁/共83頁第38頁，共83頁。分治法示例1：二分搜索算法算法復(fù)雜度分析：每執(zhí)行一次算法的while循環(huán)， 待搜索數(shù)組的大小減少一半。因此，在最壞情況下，while循環(huán)被執(zhí)行了O(logn) 次。循環(huán)體內(nèi)運(yùn)算需要O(1) 時間，因此整個算法在最壞情況下的計算時間復(fù)雜性為O(logn) 。int BinarySearch(int a, int x,

18、int left, int right) while (right = left) int mid = (left+right)/2; if (x = am) return mid; if (x am) right = mid-1; else left = mid+1; return -1; 第39頁/共83頁第39頁，共83頁。分治法示例2：大整數(shù)的乘法問題：設(shè)計一個可以進(jìn)行兩個n位大整數(shù)乘法運(yùn)算的算法逐位相乘、錯位相加的傳統(tǒng)方法：O(n2) 效率太低分治法：將該問題分解為若干個規(guī)模較小的相同問題X = Y =X = a 2n/2 + b Y = c 2n/2 + d XY = ac 2n

19、+ (ad+bc) 2n/2 + bd 復(fù)雜度分析abcdT(n)=O(n2) 沒有改進(jìn)第40頁/共83頁第40頁，共83頁。分治法示例2：大整數(shù)的乘法思考：怎樣改進(jìn)？XY = ac 2n + (ad+bc) 2n/2 + bd為了降低時間復(fù)雜度，必須減少乘法的次數(shù)XY = ac 2n + (a-b)(d-c)+ac+bd) 2n/2 + bdXY = ac 2n + (a+b)(c+d)-ac-bd) 2n/2 + bd復(fù)雜度分析T(n)=O(nlog3) = O(n1.59) 較大地改進(jìn)細(xì)節(jié)問題：兩個XY的復(fù)雜度都是O(nlog3)，但考慮到a+c,b+d可能得到n/2+1位的結(jié)果，使問題

20、的規(guī)模變大，故不選擇第2種方案。第41頁/共83頁第41頁，共83頁。分治法示例3：Strassen矩陣乘法求矩陣乘積的傳統(tǒng)算法/ 以二維數(shù)組存儲矩陣元素，C為 A 和 B的乘積void multi(int A, int B, int C) for (int i=0; in; +i) for (int j=0; jn; +j) Ci,j = 0; for (int k=0; k0時，將2k2k棋盤分割為4個2k-12k-1 子棋盤特殊方格必位于4個較小的子棋盤其中之一其余3個子棋盤中無特殊方格為了將這3個無特殊方格的子棋盤轉(zhuǎn)化為特殊棋盤可以用一個L型骨牌覆蓋這3個較小棋盤的會合處從而將原問題轉(zhuǎn)

21、化為4個較小規(guī)模的棋盤覆蓋問題遞歸地使用這種分割，直至棋盤簡化為棋盤11第50頁/共83頁第50頁，共83頁。棋盤覆蓋問題第51頁/共83頁第51頁，共83頁。棋盤覆蓋問題第52頁/共83頁第52頁，共83頁。棋盤覆蓋問題第53頁/共83頁第53頁，共83頁。棋盤覆蓋問題第54頁/共83頁第54頁，共83頁。棋盤覆蓋問題復(fù)雜度分析T(n)=O(4k) 漸進(jìn)意義下的最優(yōu)算法第55頁/共83頁第55頁，共83頁。算法基本思想在數(shù)組中確定一個記錄（的關(guān)鍵字）作為“劃分元”將數(shù)組中關(guān)鍵字小于劃分元的記錄均移動至該記錄之前將數(shù)組中關(guān)鍵字大于劃分元的記錄均移動至該記錄之后由此：一趟排序之后，序列Rs.t將

22、分割成兩部分R s . i-1 和 R i+1 . t 且滿足：R s . i-1 R i R i+1.t 其中：R i 為選定的“劃分元”對各部分重復(fù)上述過程，直到每一部分僅剩一個記錄為止分治法示例5：快速排序（Quick Sort）第56頁/共83頁第56頁，共83頁。 首先對無序的記錄序列進(jìn)行一次劃分 之后分別對分割所得兩個子序列“遞歸”進(jìn)行快速排序根據(jù)選定的劃分元（36）進(jìn)行一次劃分對子序列1進(jìn)行快速排序?qū)ψ有蛄?進(jìn)行快速排序劃分元快速排序（Quick Sort）第57頁/共83頁第57頁，共83頁。 首先：設(shè) Rs=36 為劃分元，將其暫存到R0 比較 Rhigh 和劃分元的大小，要

23、求：Rhigh 劃分元 比較 Rlow 和劃分元的大小，要求：Rlow 劃分元 若條件不滿足，則交換元素，并在low-high之間進(jìn)行切換 一輪劃分后得到：（32,9,12,25,7）36（97,45,68,39）36R0eslowhigh323974536快速排序算法流程第58頁/共83頁第58頁，共83頁。時間復(fù)雜度最好情況 T(n)=O(n log2n) （每次總是選到中間值作劃分元）最壞情況 T(n)=O(n) （每次總是選到最小或最大元素作劃分元）快速排序算法的平均時間復(fù)雜度為：O(nlog2n)快速排序算法是不穩(wěn)定的例如待排序序列： 49 49 38 65快速排序結(jié)果為： 38 4

24、9 49 65 快速排序算法特點(diǎn)第59頁/共83頁第59頁，共83頁。算法性能與序列中關(guān)鍵字的排列順序和劃分元的選取有關(guān)當(dāng)初始序列按關(guān)鍵字有序（正序或逆序）時，快速排序蛻化為冒泡排序，此時算法性能最差 時間復(fù)雜度為O(n)可以用“三者取中”法來選取劃分元設(shè)：數(shù)組首記錄為rs、尾記錄為rt?。簉s、rt和r(s+t)/2三者的中間值為劃分元也可采用隨機(jī)選取劃分元的方式快速排序算法特點(diǎn)第60頁/共83頁第60頁，共83頁。元素選擇問題描述給定線性序集中n個元素和一個整數(shù)k（1kn）要求找出這n個元素中第k小的元素問題分析方法一：可以通過排序求解元素選擇問題： O(nlog2n)問題：元素選擇問題是

25、否可以在O(n)時間內(nèi)得到解決？可以采用分治算法：模仿快排對輸入數(shù)組進(jìn)行遞歸劃分 提示1：只對劃分出的子數(shù)組之一進(jìn)行遞歸處理 提示2：子數(shù)組的選擇與劃分元和k相關(guān)分治法示例6：線性時間選擇第61頁/共83頁第61頁，共83頁。int RandSelect(int A, int start, int end, int k) if (start =end) return Astart; int i=Partition(A, start, end); /劃分元位置 int n=i-start+1; / 左子數(shù)組Astart :i的元素個數(shù) if (k=n) return RandSelect (A,

26、 start, i, k); else return RandSelect(A, i+1, end, k-n);線性時間選擇但可以證明，算法運(yùn)行的平均時間為O(n)在最壞情況下，算法RandSelect需要O(n2)計算時間第62頁/共83頁第62頁，共83頁。算法改進(jìn)：是否可以在最壞情況下用O(n)時間就完成選擇？問題分析如果能在線性時間內(nèi)找到一個劃分基準(zhǔn)，使得劃分得到的兩個子數(shù)組的長度都至少為原數(shù)組長度的倍(01)那么就可以在最壞情況下用O(n)時間完成選擇任務(wù)。例如若=0.9：每次劃分得到的子數(shù)組的長度至少縮短1/10則最壞情況下算法的計算時間：T(n)T(0.9n)+O(n)由此可得：

27、T(n)=O(n)線性時間選擇第63頁/共83頁第63頁，共83頁。線性時間內(nèi)找到合理劃分基準(zhǔn)的步驟（select函數(shù)）將n個輸入元素劃分成 n/5 個組，每組5個元素則只可能有一個組不是5個元素用任意一種排序算法對每組中的元素排序然后取出每組的中位數(shù)，共 n/5 個元素遞歸調(diào)用select函數(shù)找出這 n/5 個元素的中位數(shù)如果 n/5 為偶數(shù)，則選擇2個中位數(shù)中較大的一個以這個選出的元素作為劃分基準(zhǔn)線性時間選擇第64頁/共83頁第64頁，共83頁。線性時間內(nèi)找到合理劃分基準(zhǔn)的步驟（select函數(shù)）線性時間選擇設(shè)所有元素互不相同。在這種情況下，找出的基準(zhǔn)x至少比3(n-5)/10個元素大，因

28、為在每一組中有2個元素小于本組的中位數(shù)，而n/5個中位數(shù)中又有(n-5)/10個小于基準(zhǔn)x。同理，基準(zhǔn)x也至少比3(n-5)/10個元素小當(dāng)n30時，3(n-5)/10n/4所以按此基準(zhǔn)劃分所得的2個子數(shù)組的長度都至少縮短1/4第65頁/共83頁第65頁，共83頁。int Select(int a, int start, int end, int k) if (end-start30) 用某個簡單排序算法對數(shù)組astart:end排序; return astart+k-1; for ( int i = 0; i=(end-start-4)/5; i+ ) 將astart+5*i至astart+

29、5*i+4的第3小元素與astart+i交換位置; /找中位數(shù)的中位數(shù)，end-start-4即n-5 int x = Select(a, start, start+(end-start-4)/5, (end-start-4)/10); int i = Partition(a, start, end, x); / 劃分元位置 int n = i-start+1; / 劃分元左邊的數(shù)組長度 if (k=n) return Select(a, start, i, k); / 在左邊尋找第k大元素 else return Select(a, i+1, end, k-n); / 在右邊尋找第k-j大元

30、素線性時間選擇第66頁/共83頁第66頁，共83頁。算法復(fù)雜度分析當(dāng)n30時，算法所用的計算時間不超過一個常數(shù)C1分組求中位數(shù)的for循環(huán)執(zhí)行時間為O(n)以中位數(shù)x為基準(zhǔn)對數(shù)組進(jìn)行劃分，需要O(n)時間設(shè)：對n個元素的數(shù)組調(diào)用select需要T(n)時間則找出中位數(shù)的中位數(shù)x，至多需要T(n/5)時間已證明劃分得到的子數(shù)組長度不超過3n/4無論對哪個子數(shù)組調(diào)用select至多需T(3n/4)時間線性時間選擇第67頁/共83頁第67頁，共83頁。算法復(fù)雜度分析：T(n)=O(n)線性時間選擇算法分析分組大小固定為5，以30作為是否遞歸調(diào)用的分界點(diǎn)這兩點(diǎn)保證了T(n)的遞歸式中2個自變量之和n/

31、5+3n/4=19n/20=n，01這是使T(n)=O(n)的關(guān)鍵之處當(dāng)然，除了5和30之外，還有其他選擇第68頁/共83頁第68頁，共83頁。計算機(jī)應(yīng)用中經(jīng)常采用點(diǎn)、圓等簡單的幾何對象表示物理實(shí)體，常需要了解其鄰域中其他幾何對象的信息例如：在空中交通控制中，若將飛機(jī)作為空間中的一個點(diǎn)來處理，則具有最大碰撞危險的兩架飛機(jī)，就是這個空間中距離最接近的一對點(diǎn)這類問題是計算幾何學(xué)中研究的基本問題之一我們著重考慮平面上的最接近點(diǎn)對問題最接近點(diǎn)對問題：給定平面上的n個點(diǎn)，找出其中的一對點(diǎn)，使得在n個點(diǎn)組成的所有點(diǎn)對中，該點(diǎn)對的距離最小分治法示例7：最接近點(diǎn)對問題第69頁/共83頁第69頁，共83頁。直觀

32、解法將每一個點(diǎn)與其他n-1個點(diǎn)的距離算出，找出最小距離時間復(fù)雜度：分治法分解：將n個點(diǎn)的集合分成大小近似相等的兩個子集求解：遞歸地求解兩個子集內(nèi)部的最接近點(diǎn)對合并（關(guān)鍵問題）：從子空間內(nèi)部最接近點(diǎn)對，和兩個子空間之間的最接近點(diǎn)對中，選擇最接近點(diǎn)對求解最接近點(diǎn)對問題T(n)=n(n-1)/2+n=O(n2)第70頁/共83頁第70頁，共83頁。分治法求解最接近點(diǎn)對問題首先考慮一維的情況此時，S中的n個點(diǎn)退化為x軸上的n個實(shí)數(shù) x1, x2, , xn最接近點(diǎn)對即為這n個實(shí)數(shù)中相差最小的2個實(shí)數(shù)思考：排序可以在O(nlogn)時間解決問題分治法假設(shè)我們用x軸上某個點(diǎn)m將S劃分為2個子集S1和S2基

33、于平衡子問題的思想，用S中各點(diǎn)坐標(biāo)的中位數(shù)來作分割點(diǎn)遞歸地在S1和S2上找出其最接近點(diǎn)對p1,p2和q1,q2設(shè)d=min|p1-p2|,|q1-q2|，則S中的最接近點(diǎn)對或者是p1,p2，或者是q1,q2，或者是某個p3,q3，其中p3S1且q3S2缺點(diǎn)：難以推廣到高維第71頁/共83頁第71頁，共83頁。分治法求解最接近點(diǎn)對問題如果S的最接近點(diǎn)對是p3,q3，即|p3-q3|d則p3和q3兩者與m的距離不超過d即：p3(m-d, m，q3(m, m+d問題分析 在S1中每個長度為d的半閉區(qū)間至多包含一個點(diǎn) 由于m是S1和S2的分割點(diǎn)，因此(m-d,m中至多包含S中的一個點(diǎn)如果(m-d,m中

34、有S中的點(diǎn)，則此點(diǎn)就是S1中最大點(diǎn)（S2同理）因此用線性時間可找到(m-d, m和(m, m+d中所有點(diǎn)（即p3和q3）所以，用線性時間就可以將S1的解和S2的解合并成為S的解思考：影響算法性能的主要因素是什么？分割點(diǎn)m的選取應(yīng)使得劃分出的子集盡可能平衡第72頁/共83頁第72頁，共83頁。int cpair(int S, int n) int d, d1, d2; if(n m d1 = cpair(S1); d2 = cpair(S2); p = max(S1); q = min(S2); d = min(d1, d2, q-p); return d;求一維點(diǎn)集S的最接近點(diǎn)對的算法復(fù)雜度分

35、析：T(n)=O(nlogn)第73頁/共83頁第73頁，共83頁。分治法求解最接近點(diǎn)對問題考慮二維的情況選取二維平面的一條垂直線L：x=m 作為分割線其中m為S中各點(diǎn)x坐標(biāo)的中位數(shù)，由此將S分割為S1和S2遞歸地在S1和S2上找出其最小距離d1和d2設(shè)：d=mind1,d2，S中的最接近點(diǎn)對間的距離或者是d，或者是某個點(diǎn)對p,q之間的距離，其中pS1且qS2如果用符號P1和P2分別表示直線 L 的左右兩邊寬為d的區(qū)域則必有pP1且qP2pq第74頁/共83頁第74頁，共83頁。分治法求解最接近點(diǎn)對問題問題分析考慮P1中任意一點(diǎn)p它若與P2中的點(diǎn)q構(gòu)成最接近點(diǎn)對的候選者則必有：distance

36、(p，q)dP2中滿足條件的點(diǎn)一定落在矩形R中矩形R的大小為：d2d由d的定義可知：P2中任何2個點(diǎn)（qiS）的距離都不小于d由此可以推出矩形R中最多只有6個S中的點(diǎn)（證明見下頁）因此，在分治法的合并步驟中最多只需要檢查6n/2=3n個候選者第75頁/共83頁第75頁，共83頁。分治法求解最接近點(diǎn)對問題證明：合并時最多只需檢查6n/2=3n個候選者將矩形R長為2d的邊3等分，將長為d的邊2等分由此導(dǎo)出6個(d/2)(2d/3)的小矩形，如圖若矩形R中有多于6個S中的點(diǎn)，由鴿籠原理易知至少有一個小矩形中有2個以上S中的點(diǎn)設(shè)u，v是位于同一小矩形中的2個點(diǎn)，則即：distance(u,v)d，這與d的意義相矛盾，命題得證。第76頁/共83頁第76頁，共83頁。分治法求解最接近點(diǎn)對問題問題：如何確定需要檢查的6個點(diǎn)？可以將p和P2中所有S2的點(diǎn)投影到垂直線l上由于能與p點(diǎn)一起構(gòu)成最接近點(diǎn)對候選者的S2中的點(diǎn)一定在矩形R中，所以它們在直線 L 上的投影點(diǎn)距 p 在 L 上投影