(XXXX0518版第二講_分治策略-不可更改

1、1第2講分治與遞歸策略2.1 分治算法的基本思想2.2 遞歸概念 2.3 典型分治算法舉例12算法總體思想 將一個難以直接解決的規(guī)模較大的問題分解為若干個規(guī)模較小的子問題，并各個擊破，分而治之。n/16 n n/4 n/4 n/4 n/4n/16n/16n/16n/16n/16n/16n/16n/16n/16n/16n/16n/16n/16n/16n/1623 將求出的較小規(guī)模的問題解合并成一個較大規(guī)模的問題解，并自底向上地求出原問題的解。 最頂層問題a 為分解的子問題數(shù)量；n/b 為每個子問題的數(shù)據(jù)規(guī)模；f(n) 為合并子問題解所消耗的時間。342.1 分治算法的基本思想 分治算法的基本思想

2、是將一個規(guī)模為n的問題分解為a個規(guī)模較小的子問題，這些子問題互相獨立且與原問題相同。遞歸地解這些子問題，然后將各個子問題的解合并得到原問題的解。45分治算法所能解決問題一般具有以下幾個特征：縮小問題規(guī)?？梢越档徒鉀Q問題的難度；可以將子問題的解合并為原問題解；問題分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。56分治算法的算法框架divide-and-conquer(P) if ( | P | = n0) adhoc(P); /解決規(guī)模小的問題 /將問題P 分解為子問題P1,P2,.,Pa； for (i=1,i1是常數(shù)，f(n)是一個漸進函 數(shù)，描述劃分問題與合并解的時間復雜

3、性。 n/b可以是 ，也可以是 公式法上述方程描述了如下算法的運行時間：將一個規(guī)模為n的問題劃分為a個規(guī)模為n/b的子問題，其中a和b為正常數(shù)。分別遞歸地解決a個子問題，解每個子問題所需時間為T(n/b)。劃分原問題和合并子問題的解所需要的時間由f(n)決定1617定理：上述遞歸方程含有三種情形的漸進界：（1）對于某個常數(shù) 如果 則（2）如果 則 （3）對某個常數(shù) 如果 且對某個常數(shù) c 1時，perm(R)的全排列為：(r1)perm(R1)，(r2)perm(R2)，(rn)perm(Rn)方法1：固定位置找元素2627遞歸公式27282829將每個元素交換到固定位置上，并求解其余位置元素

4、的全排列。舉例，03共4個數(shù)值的全排列思路？2930假設: 要求Pm 、Pm+1 、 Pn的全排列:值得注意的是，將Pm和某個Pk交換，求出剩余元素的所有排列后，為 了避免重復，發(fā)生混亂，必須將Pm 和Pk交換回去，然后才能繼續(xù)Pm 和PK+1的交換。當問題規(guī)模降為求一個元素Pm的全排列時，問題就極為簡單，可作為 遞歸出口。3.然后依次考慮Pm+3，,Pn。2.然后考慮Pm+1，通過交換Pm和Pm+1，這樣我們仍然只要考慮求剩 余元素Pm+1 、Pm+2, Pn的所有排列即可。 1.需要先考慮Pm，如果能夠求出剩余元Pm+1 、Pm+2 、，Pn 的所有排列，我們只需將Pm放到每個排列的開頭。

5、30313132void perm(int r, int i, int n) / r存放R集合元素，r0rn / i,n 表示目前求解的全排列起始與終止位置 if （只有一個元素） /遞歸邊界條件 顯示當前排列； else 依次將i n 之間的每個元素交換 /遞歸到第i 個位置，并用同樣的方法 （遞歸）求解i+1n 之間的全排列 3233void perm(int r, int i, int n) if ( i = n ) / 只有一個數(shù)值 for (int j = 0; j = n; j+) / 輸出結果 coutrj; coutendl; else for (int j = i; j =

6、n; j+) swap(r, i, j); / 交換ri與rj perm(r, i + 1, n); / 計算i+1 n 全排列 swap(r, i, j); / 交換ri與rj 3334 將n放在p3位置上，并用p1.2和p4.n產生n-1個元素的全排列；方法2：固定元素找位置 元素放置位置：p1pn 直到將n放在pn位置上，并用p1.n-1產生n-1個 元素的全排列。 . 將n放在p1位置上，并用p2.n產生n-1個元素的全排列； 基本過程： 在n-1 個元素的全排列基礎上，將某個元素插入到每個位置上，進而得出n 個元素的全排列。 將n放在p2位置上，并用p1和p3.n產生n-1個元素的全

7、排列；3435321, 312, 231, 132, 213, 1233536void perm2(int p, int n) / n = NUM-1 / p1pn放置元素，初始為0， / n為當前參與排列的元素數(shù)量, 1,2,3, n if (參與排列的數(shù)據(jù)數(shù)量為0) 輸出結果 else 依次將n放在每個位置， 并采用同樣的方法求解另外n-1元素的全排列； 3637void perm2(int p, int n) if (n = 0) / 元素集合為空 for (int i = 1; i = NUM ; i+) / 輸出結果 coutpi; coutendl; else for (int i

8、 = 1; i = NUM; i+) if (pi = 0) pi = n; perm2(p, n-1); pi = 0; 初始：p1.n=0;perm(p,n);NUM為n+1例如：n = 3，NUM = 43738實現(xiàn)過程注意：在n放定一個位置pK，找到剩下n-1個元素的所有 排列后，在找n的下一個可放置位置時，即把n放到位置 Pk+1前，原來放n的位置pK一定要置0。否則，將有某 些元素找不到位置。 依次遞歸下去，直到數(shù)組沒有為0 的元素為止。我們初始化數(shù)組p1.n的值為0，對于元素n，可以依次把它 放到數(shù)組的p1,p2,.,pn位置，在n放定一個位置后pK 后，剩下的n-1個元素可以放

9、在那些值為0的數(shù)組元素p1.k-1 和pk+1.n上。3839遞歸小結遞歸算法的運行效率較低，無論是耗費的計算時間還是占用的存儲空間都比非遞歸算法要多。結構清晰，可讀性強，而且容易用數(shù)學歸納法來證明算法的正確性，因此它為設計算法、調試程序帶來很大方便。優(yōu)點：缺點：3940給定已按升序排列的n個元素a0:n-1，現(xiàn)要在這n個元素中找出一個特定元素x。分析：搜索范圍越小，越容易確定解；該問題可以分解為若干個規(guī)模較小的相同問題;分解出的子問題的解就是原問題的解；分解出的各個子問題是相互獨立的。2.3節(jié) 分治算法舉例1：二分搜索技術分析： 此問題分解出的子問題相互獨立，即在ai的前面或后面查找x是獨立

10、的子問題，因此滿足分治算法的基本條件。4041templat int binarySearch(T a, int x, int n) int left = 0;int right = n - 1;while (left amiddle) left = middle + 1;else right = middle - 1;return -1; / 未找到x算法復雜性分析：每執(zhí)行一次while循環(huán)，搜索范圍縮小一半。因此，在最壞情況下，while循環(huán)被執(zhí)行了O(lgn) 次。循環(huán)體內運算需要O(1) 時間，因此整個算法在最壞情況下的計算時間復雜性為O(lgn)41兩個n位二進制大整數(shù)乘法運算的基本

11、方法:(1)小學的方法：時間復雜性 效率太低42分治算法舉例2：大整數(shù)的乘法4243X = A 2n/2 + BY = C 2n/2 + D A B C DX = Y = (2)分治算法:注意：乘以2n表示向左位移n位，這個運算耗時復雜性分析XY = (A 2n/2 + B)(C 2n/2 + D) = AC 2n + (AD + BC) 2n/2 + BD乘法4次，加法3次，位移2次4344將公式：XY = AC 2n + (AD+BC) 2n/2 + BD變換為：XY = AC 2n + (A-B)(D-C)+AC+BD) 2n/2 + BD乘法：3次；加減法：6次；位移：2次4445fo

12、r ( int i = 0; i n; i+)for (int j = 0; j n; j+) Cij = 0;for (int k = 0; k 0時，將2k2k棋盤分割為4個2k-12k-1 子棋盤(a)所示。特殊方格必位于4個較小子棋盤之一中，其余3個子棋盤中無特殊方格。為了將這3個無特殊方格的子棋盤轉化為特殊棋盤，可以用一個L型骨牌覆蓋這3個較小棋盤的會合處，如(b)所示，從而將原問題轉化為4個較小規(guī)模的棋盤覆蓋問題。遞歸地使用這種分割，直至棋盤簡化為棋盤,即k=0,11。5354棋盤覆蓋分治算法偽語言if(size=0)return ;/ 覆蓋左上角子棋盤if ( 特殊方塊在左上角)

13、 覆蓋左上角;else 在右下角放一小方塊;覆蓋左上角;/ 覆蓋右上角子棋盤if ( 特殊方塊在右上角)覆蓋右上角;else 在左下角放一小方塊;覆蓋右上角;/ 覆蓋左下角子棋盤if ( 特殊方塊在左下角)覆蓋左下角;else 在右上角放一小方塊;覆蓋左下角;/ 覆蓋右下角子棋盤if ( 特殊方塊在右下角)覆蓋右下角;else 在左上角放一小方塊;覆蓋右下角;void chessBoard(int tr, int tc,int dr, int dc,int size) 5455void chessBoard(int tr, int tc, int dr, int dc, int size) i

14、f (size = 1) return;int t = tile+, / L型骨牌號s = size/2; / 分割棋盤/ 覆蓋左上角子棋盤if (dr tr + s & dc tc + s)/ 特殊方格在此棋盤中chessBoard(tr, tc, dr, dc, s);else / 此棋盤中無特殊方格/ 用t 號L型骨牌覆蓋右下角boardtr + s - 1tc + s - 1 = t;/ 覆蓋其余方格chessBoard(tr, tc, tr+s-1, tc+s-1, s);/ 覆蓋右上角子棋盤if (dr = tc + s)/ 特殊方格在此棋盤中chessBoard(tr, tc+s

15、, dr, dc, s);else / 此棋盤中無特殊方格/ 用t 號L型骨牌覆蓋左下角boardtr + s - 1tc + s = t;/ 覆蓋其余方格chessBoard(tr, tc+s, tr+s-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,

16、s);55565657void chessBoard(int boardNN,int tr,int tc,int dr,int dc,int size,int& tile) if (size = 1) return;int s = size/2;int t = tile+;/ 左上角if (dr tr + s & dc tc + s) chessBoard(board,tr,tc,dr,dc,s,tile);else boardtr+s-1tc+s-1 = t; chessBoard(board,tr,tc,tr+s-1,tc+s-1,s,tile); / 右上角if (dr = tc + s

17、) chessBoard(board,tr,tc+s,dr,dc,s,tile);else boardtr+s-1tc+s = t; chessBoard(board,tr,tc+s,tr+s-1,tc+s,s,tile); / 左下角if (dr = tr + s & dc = tr+s & dc = tc + s) chessBoard(board,tr+s,tc+s,dr,dc,s,tile);else boardtr+stc+s = t; chessBoard(board,tr+s,tc+s,tr+s,tc+s,s,tile); 57585859分治算法舉例5： 歸并排序void me

18、rgeSort(T a,int left, int right) if ( 含有2個以上元素) 計算中點位置；歸并排序前半部分； / 分解歸并排序后半部分； / 分解將兩個有序段合并到b； / 合并結果將b中的結果復制回a； 基本思想:將待排序元素分成大小大致相同的兩個子集合， 分別對兩個子集合進行排序，然后將兩個排好序的子集合 歸并成一個有序的集合。 5960template void mergeSort(T a,int left, int right) if (left right) mid = (left + right) / 2; / 計算中點mergeSort(a,left, mid

19、); / 歸并排序前后兩部分mergeSort(a,mid + 1, right);merge(a,b,left, mid, right); / 將兩個有序段合并到bcopy(a,b,left,right); / 將結果復制到數(shù)組a606161626263（2）成對處理輸入值，用其中較小者與當前最小值比較，用較大值與當前最大值比較，每對數(shù)據(jù)比較3次，共比較 次。分治算法舉例6：線性時間選擇在有n個元素的集合中找最小值或最大值需比較n-1次。如果利用錦標賽樹，其他元素需要比較 次。（1）分別找出最大值和最小值，比較次數(shù)為2（n-1）同時找到最大值和最小值方法：6364T randomizedSe

20、lect(T a, int p, int r, int k) 如果只有一個元素，將其返回；int i = 隨機將線性序列分解為兩部分(前小后大）；j = 計算前段元素個數(shù);if ( 第k個小的元素位于前段)采用同樣的方法在前段找第k 個小元素；else采用同樣的方法在后段找k-j 個小元素;pirja問題：給定線性序集中n個元素和一個整數(shù)k，1kn，要求找出這n個元素中第k小的元素。6465Template T randomizedSelect(T a, int p, int r, int k)if (p = r) return ap;int i = randomizedPartition(a

21、, p, r);j = i p + 1;if ( k = j) return randomizedSelect(a, p, i, k);else return randomizedSelect(a, i+1, r, k-j);pirja6566 一種選擇支點元素的方法是使用“中間的中間（median-of-median）”首先將數(shù)組a中的n 個元素分成n/r 組，r 為某一整常數(shù)，除了最后一組外，每組都有r個元素。然后通過在每組中對r 個元素進行排序來尋找每組中位于中間位置的元素。最后對所得到的n/r 個中間元素，遞歸使用選擇算法，求得”中間之中間”作為支點元素。規(guī)則：6667如果能在線性時間

22、內找到一個劃分基準，使得按這個基準所劃分出的2個子數(shù)組的長度都至多為原數(shù)組長度的倍(01是某個正常數(shù))，就可以在最壞情況下用O(n)時間完成選擇任務。在最壞情況下，算法randomizedSelect需要O(n2)計算時間。可以證明，算法randomizedSelect可以在O(n)時間內找出n個輸入元素中的第k小元素。例如，若=9/10，算法遞歸調用所產生的子數(shù)組的長度至少縮短1/10。所以，在最壞情況下，算法所需的計算時間T(n)滿足遞歸式T(n)T(9n/10)+O(n) 。由此可得T(n)=O(n)。6768P=8,17,4,11, 3,13,6,19,16,5,7,23,22Q=25

23、R=31,60,33,51,57,49,35,43,37,52,32,54,41,46,29按遞增順序，找出下面29個元素的第18個元素：8,31,60,33,17,4,51,57,49,35,11,43,37,3,13,52,6,19,25,32,54,16,5,41,7,23,22,46,29.舉例(1) 把前面25個元素分為5(=floor(29/5)組： (8,31,60,33,17),(4,51,57,49,35),(11,43,37,3,13),(52,6,19,25,32), (54,16,5,41,7).(2) 提取每一組的中值元素，構成集合31,49,13,25,16；(3)

24、 遞歸地使用算法求取該集合的中值，得到m=25；(4) 根據(jù)m=25, 把29個元素劃分為3個子數(shù)組：6869(7) 求取這3組元素的中值元素分別為：51,43,41， 這個集合的中值元素是43;例子（續(xù)）(5) 由于|P|=13,|Q|=1,k=18，所以放棄P,Q，使 k=18-13-1=4，對R遞歸地執(zhí)行本算法；(6) 將R劃分成3(floor(15/5)組： 31,60,33,51,57,49,35,43,37,52,32,54,41,46,29(8) 根據(jù)43將R劃分成3組： 31, 33, 35,37,32, 41, 29,43,60, 51,57, 49, 52,54, 4669

25、70(12) 因為k=4,而第一、第二個子數(shù)組的元素個數(shù)為3，所以33即為所求取的第18個小元素。例子（續(xù)）(9) 因為k=4，第一個子數(shù)組的元素個數(shù)大于k，所以放棄后面兩個子數(shù)組，以k=4對第一個子數(shù)組遞歸調用本算法；(10)將這個子數(shù)組分成5個元素的一組：31,33,35,37,32，取其中值元素為33；(11)根據(jù)33，把第一個子數(shù)組劃分成31,32,29,33,35,37,41;7071 找出這 個元素的中位數(shù)。如果 是偶數(shù)，就找它的2個中 位數(shù)中較大的一個。以這個元素作為劃分基準。 將n個輸入元素劃分成 個組，每組5個元素， 只可能有一個組不是5個元素。用任意一種排序算法，將每組中的

26、元素排好序，并取出每組的中位數(shù)，共 個。設所有元素不相同。在這種情況下，基準x至少比3 個元素大，因為在每一組中有2個元素小于本組的中位數(shù)，而 個中位數(shù)中又有 個小于基準x。同理，基準x也至少比3 個元素小。當n75時，3(n-5)/10n/4。所以按此基準劃分所得的2個子數(shù)組的長度都至少縮短1/4。7172T select (T a, int p, int r, int k) if (少于或等于5個數(shù)值) 直接排序;return ap+k-1;分組排序，并將中位數(shù)交換到前面;int x = 確定中位數(shù)的中位數(shù);int i = partition(p,r,x), j=計算前半?yún)^(qū)個數(shù);if (k

27、=j) return select(a, p , i , k);else return select(a, i+1, r, k-j);if (r-p5) bubbleSort(p,r);return ap+k-1;for ( int i = 0; i(r-p+1)/5; i+ ) int s=p+5*i,int t=s+4;bubbleSort(s,t);swap(a, p+i, s+2);int x = select(a, p, p+(r-p+1)/5-1, (r-p)/10);int i=partition(p,r,x);j=i-p+1;if (k=j) return select(a,

28、p , i , k);else return select(a, i+1, r, k-j);7273T(n/5)：在n/5個組中找中位數(shù)的中位數(shù)。T(3n/4)：劃分的子序列最多為3n/4。結論：在這里，將75作為遞歸界限條件，5作為分組大小，可以保證：n/5+3n/4=19n/20=n，01,這是關鍵。7374 給定平面上n個點的集合S，找其中的一對點，使得在n個點組成的所有點對中，該點對間的距離最小。 解決方法：將每個點與其余n-1個點的距離計算出來，最小距離者即為最接近點對。時間復雜性O(n2)。(1)一維情形:S中的n個點退化為x軸上的n個實數(shù)x1,x2,xn。最接近點對為其中相差最小

29、的2個實數(shù)。分治算法舉例7：最接近點對問題7475優(yōu)化最接近點對問題算法問題：無法應用于二維點對。解決方法：對所有點進行排序，需要O(nn)。再掃描一遍即可以得出最接近點對。證明得知，該問題的時間下界為(nn)7576優(yōu)化最接近點對問題算法假設用x軸上某個點m將S劃分為2個子集S1和S2，基于平 衡子問題的思想，用S中各點坐標的中位數(shù)來作分割點。遞歸地在S1和S2上找出其最接近點對p1,p2和q1,q2，并 設d=min|p1-p2|,|q1-q2|，S中的最接近點對或者是 p1,p2，或是q1,q2，或是某個p3,q3，其中p3S1且 q3S2。思考：能否在線性時間內找到p3,q3？7677

30、如果S的最接近點對是p3,q3，即|p3-q3|d，則p3和q3兩者 與m的距離不超過d，即p3(m-d,m，q3(m,m+d。由于在S1中，每個長度為d的半閉區(qū)間至多包含一個點（否則 必有兩點距離小于d），并且m是S1和S2的分割點，因此(m-d, m中至多包含S中的一個點。由圖可以看出，如果(m-d,m中 有S中的點，則此點就是S1中最大點。因此，用線性時間就能找到區(qū)間(m-d,m和(m,m+d中所有點， 即p3和q3。從而用線性時間就可以將S1的解和S2的解合并成 為S的解。7778一維點集S的最接近點對的算法double cpair1(S) /排序, (n n)n = |S|;if (

31、n2) return ;m=S中各點坐標的中位數(shù)；/線性時間構造S1和S2; /線性時間d1=cpair1(S1); /計算左側的最接近距離d2=cpair1(S2); /計算右側的最接近距離p=max(S1); / 左側最大值,線性時間q=min(S2); /右側最小值,線性時間d=min(d1,d2,q-p); /最接近距離,常量時間return d;7879(2) 二維情形選取一垂直線l，x=m來作為分割 直線。其中m為S中各點x坐標的中 位數(shù)。由此將S分割為S1和S2。遞歸地在S1和S2上找出其最小距 離d1和d2，并設d=mind1,d2，S 中的最接近點對或者是d，或者是 某個p,q，其中pP1且q