《算法設(shè)計與分析遞歸與分治(第二章)課件.ppt》由會員分享，可在線閱讀，更多相關(guān)《算法設(shè)計與分析遞歸與分治(第二章)課件.ppt（75頁珍藏版）》請在匯文網(wǎng)上搜索。

1、27.07.2022,計算機(jī)算法設(shè)計與分析,1,第二章遞歸與分治,27.07.2022,計算機(jī)算法設(shè)計與分析,2,遞歸的思想,遞歸(Recursion)就是通過把復(fù)雜問題分解為較簡單的同一問題來求解。遞歸求解問題的方法通常有兩步：第一步是考慮最簡單的情況下該問題如何求解。第二步是考慮該問題的較復(fù)雜情況是如何由較簡單的所構(gòu)成的。由此得出該問題求解的方法。,27.07.2022,計算機(jī)算法設(shè)計與分析,3,Hanoi塔問題,Hanoi塔問題：有A、B、C三根柱子。A上有n個圓盤，自下而上由大到小地疊在一起。,現(xiàn)要將A上的全部圓盤移到B上，并要求：(1)每次只能移動一個圓盤；(2)任何時刻都不允許將較

2、大的圓盤壓在較小的圓盤上；(3)圓盤只能在A、B、C三個柱子間移動。,如何解決此問題呢？,27.07.2022,計算機(jī)算法設(shè)計與分析,4,Hanoi塔問題,讓我們先考慮最簡單的情況：1、若沒有盤子(n = 0)，自然不需要做任何事情。,2、若只有一個盤子，也很容易。直接把它移到B盤即可。,不妨設(shè)操作Move(X, Y)將X柱上的一個盤子(最頂上的)移到Y(jié)柱上。,27.07.2022,計算機(jī)算法設(shè)計與分析,5,Hanoi塔問題,讓我們先考慮最簡單的情況：1、若沒有盤子(n=0)，自然不需要做任何事情。,2、若只有一個盤子，也很容易。直接把它移到B盤即可。,不妨設(shè)操作Move(X, Y)將X柱上的

3、一個盤子(最頂上的)移到Y(jié)柱上。,即通過操作Move(A, B)即可實現(xiàn)。,27.07.2022,計算機(jī)算法設(shè)計與分析,6,Hanoi塔問題,現(xiàn)在來考慮復(fù)雜的情況，即n 1的情況。,怎樣將它變成A柱上只有一個盤子，即n = 1，呢？,顯然應(yīng)該先將A柱上的n 1個盤子，移到C柱上去。,27.07.2022,計算機(jī)算法設(shè)計與分析,7,Hanoi塔問題,于是我們有了解決n 1的的策略：,27.07.2022,計算機(jī)算法設(shè)計與分析,8,Hanoi塔問題,于是我們有了解決n 1的的策略：,(1)先將A上面n1個盤子移至C。,27.07.2022,計算機(jī)算法設(shè)計與分析,9,Hanoi塔問題,于是我們有了解

4、決n 1的的策略：,(1)先將A上面n1個盤子移至C。,(2)再將A上面的1個盤子移至B。,27.07.2022,計算機(jī)算法設(shè)計與分析,10,Hanoi塔問題,于是我們有了解決n 1的的策略：,(1)先將A上面n1個盤子移至C。,(2)再將A上面的1個盤子移至B。,(3)最后將C上面n1個盤子移至B。,27.07.2022,計算機(jī)算法設(shè)計與分析,11,Hanoi塔問題,我們用Fr、To和As分別表示源柱、目標(biāo)柱和輔助柱，解Hanoi塔可以描寫為這樣的遞歸過程：1、若n = 0，什么也不做；,最簡單的情況,2、若n 0，則用Hanoi的方法將Fr柱上的 n 1個盤子移到As柱上，用To柱做輔助柱

5、；將剩下的一個盤子從Fr移到To；用Hanoi的方法將As柱上的 n 1個盤子移到To柱上，用Fr柱做輔助柱。,27.07.2022,計算機(jī)算法設(shè)計與分析,12,Hanoi塔問題,若寫成java語言，解Hanoi塔可以描寫為這樣的遞歸過程：void Hanoi(int n, int Fr, int To, int As) if (n 0) Hanoi(n1, Fr, As, To); Move(Fr, To); Hanoi(n1, As, To, Fr)； ,當(dāng)n 0時，遞歸終止。,27.07.2022,計算機(jī)算法設(shè)計與分析,13,Hanoi塔問題,Hanoi(3, A, B, C), Han

6、oi(2, A, C, B); Move(A, B); Hanoi(2, C, B, A),Hanoi(1, A, B, C);Move(A, C);Hanoi(1, B, C, A),Move(A, B);,Move(B, C);,Hanoi(1, C, A, B);Move(C, B);Hanoi(1, A, B, C),Move(C, A);,Move(A, B);,Move(A, C);,Move(A, B);,Move(C, B);,27.07.2022,計算機(jī)算法設(shè)計與分析,14,Hanoi塔問題的時間復(fù)雜性,不難證明Hanoi塔問題的時間復(fù)雜性為O(2n)。證明：對n歸納證明移動

7、次數(shù)move(n) = 2n 1。歸納基礎(chǔ)：當(dāng)n = 1， move(1) = 1 = 21 1。歸納假設(shè)：當(dāng)n k， move(n) = 2n 1。歸納步驟：當(dāng)n = k + 1，移動次數(shù)為move(k+1) = 2(move(k) + 1 = 2(2k 1) + 1 = 2k+1 1 由歸納法可知對任意的n有move(n) = 2n 1。,27.07.2022,計算機(jī)算法設(shè)計與分析,15,遞歸元,遞歸思想是將對較大規(guī)模的對象的操作歸結(jié)為對較小規(guī)模的對象實施同樣的操作。這種規(guī)模的變化體現(xiàn)在遞歸的參數(shù)表中的一類(一個或幾個)變元上，這類變元被稱之為遞歸元。在遞歸定義中遞歸元的變化應(yīng)導(dǎo)致遞歸計算

8、終止，即逐步變化為最簡單規(guī)模的計算。在遞歸算法的設(shè)計中遞歸元是非常重要的。,27.07.2022,計算機(jī)算法設(shè)計與分析,16,常見的遞歸形式,除基本的遞歸形式外，其它常見的遞歸形式有四種，它們是：,多變元遞歸；多步遞歸；嵌套遞歸；聯(lián)立遞歸,27.07.2022,計算機(jī)算法設(shè)計與分析,17,多變元遞歸,多變元遞歸就是遞歸元多于一個的遞歸。例如，求最大公約數(shù)的輾轉(zhuǎn)相除法：,其中x和y都是遞歸元。,最簡單的情況有兩種,27.07.2022,計算機(jī)算法設(shè)計與分析,18,多步遞歸,若遞歸函數(shù)f(x, y)，其中y是遞歸元，不僅與f(x, y1)有關(guān)，而且與f(x, y2)，乃至f(x, 0)有關(guān)，則稱為

9、多步遞歸。例如Fibonacci函數(shù)：,Fibonacci函數(shù)是一個兩步的遞歸函數(shù)。,27.07.2022,計算機(jī)算法設(shè)計與分析,19,嵌套遞歸,所謂嵌套遞歸是指遞歸調(diào)用中又含有遞歸調(diào)用，又稱為多重遞歸。例如Ackermann函數(shù)：,Ackermann函數(shù)是一個雙重的遞歸函數(shù)。同時它也是個二元遞歸。,27.07.2022,計算機(jī)算法設(shè)計與分析,20,聯(lián)立遞歸,聯(lián)立遞歸是同時定義幾個函數(shù)，它們彼此相互調(diào)用，從而形成遞歸，又稱間接遞歸。例如Hilbert圖案，下面為H1，H2和H3：,27.07.2022,計算機(jī)算法設(shè)計與分析,21,Hilbert圖案,將Hi記為Ai，將Hi旋轉(zhuǎn)90, 180和2

10、70后的圖形分別記為Bi，Ci和Di，其中一、二級曲線如下所示：,A1,B1,C1,D1,A2,D1,A1,A1,B1,B2,C1,B1,B1,A1,C2,B1,C1,C1,D1,D2,A1,D1,D1,C1,27.07.2022,計算機(jī)算法設(shè)計與分析,22,Hilbert圖案,于是得出這些子曲線逐級間的關(guān)系如下：,其中，箭頭表示曲線移動的方向，,于是便可寫出畫這些曲線的遞歸子程序。,可將0級的Hilbert曲線視為一個點。,27.07.2022,計算機(jī)算法設(shè)計與分析,23,Hilbert圖案,A(i) if (i 0) D(i 1); x = x h; ploting(x, y) ; A(i

11、 1); y = y h; ploting(x, y) ; A(i 1); x = x + h; ploting(x, y) ; B(i 1); /*ploting(x, y)是從畫筆現(xiàn)行坐標(biāo)到坐標(biāo)(x, y)畫條直線。,類似地可以寫出畫B、C和D的曲線的子程序。,畫Hilbert曲線的程序在調(diào)用A之前還應(yīng)有一些初始化的工作，如計算h，移動畫筆至起點等。,27.07.2022,計算機(jī)算法設(shè)計與分析,24,遞歸方法小結(jié),遞歸方法是將復(fù)雜問題分解為較為簡單的子問題的組合，且子問題與原問題相似。遞歸算法中必有一個或幾個最簡情況的計算(非遞歸分支)，若缺少或者不完備將造成遞歸不終止。遞歸算法中遞歸元必

12、須隨遞歸的進(jìn)程變化到最簡情況，保證導(dǎo)致非遞歸分支的計算。遞歸算法具有層次性，低層的解組合成高層的解。各層間最好通過參數(shù)傳遞來交流信息，如使用全局量，則要注意全局量的及時修訂。,27.07.2022,計算機(jī)算法設(shè)計與分析,25,遞歸復(fù)雜性的一般形式,一般的，遞歸復(fù)雜性可描述為遞歸方程：,其中，a是子問題個數(shù)， 表示遞減方式， b是遞減步長， D(n)是合成子問題的開銷。,顯然影響f(n)的因素有：遞減方式、子問題個數(shù)a ，步長b、以及合成開銷D(n) 。我們先來看看遞減方式這個因素。,27.07.2022,計算機(jī)算法設(shè)計與分析,26,遞歸復(fù)雜性的一般形式,一般的，遞歸復(fù)雜性可描述為遞歸方程：,其

13、中，a是子問題個數(shù)， 表示遞減方式， b是遞減步長， D(n)是合成子問題的開銷。,通常，遞歸元的遞減方式有兩種：,1、除法，即n / b，的形式；2、減法，即n b，的形式。,分治法,遞推法,27.07.2022,計算機(jī)算法設(shè)計與分析,27,分治法的時間復(fù)雜性,分析分治法，即用除法遞減，的遞歸方程的一般情形，可得其時間復(fù)雜性函數(shù)為：,合并開銷函數(shù)D(n)是k階的 。,影響復(fù)雜性的主要因素：當(dāng)a D(b)時是子問題個數(shù)，當(dāng)a D(b)時是合并開銷函數(shù)。,27.07.2022,計算機(jī)算法設(shè)計與分析,28,分治法的基本思想,將一個規(guī)模為n的問題分解為a個規(guī)模較小的子問題，這些子問題互相獨立并且與原

14、問題相同。遞歸地求解這些子問題問題。然后將各個子問題的解合并在一起，從而得到原問題的解。影響其時間復(fù)雜性的因素是子問題的個數(shù)和合并開銷函數(shù)，其中較大者起主要作用。,27.07.2022,計算機(jī)算法設(shè)計與分析,29,分治法的一般模式,Divide-and-Conquer(P) if (|P|=n0) return Adhoc(P); /若P的規(guī)模不超過閾值n0可直接求解并結(jié)束遞歸/ divide P into smaller subinstants P1, ., Pa; for (i =1; i = a; i+) /逐個求子問題解yi/ yi = Divide-and-Conquer(Pi);

15、return Merge(y1, , ya); /返回P的解/Merge(y1, , ya)將子問題解合成P的解/,27.07.2022,計算機(jī)算法設(shè)計與分析,30,最接近點對問題,給定平面上n個點，在n個點組成的所有點對中，找出其中相互距離的最小一對點。此問題的簡單解法是，算出每個點與其它n1 個點之間距離，再找出其中距離最小的一對點。這樣做的時間復(fù)雜性為O(n2)。用分治法構(gòu)造一個復(fù)雜性為O(nlogn)的算法。為此我們先考慮一維的情況：,27.07.2022,計算機(jī)算法設(shè)計與分析,31,一維最接近點對,設(shè)集合S為x軸上n個點，求S中最接近點對。假設(shè)用x軸上某個點m劃分S為S1和S2，使得

16、S1=xS | xm，S2=xS | xm。,遞歸地在S1和S2中找出其最接近點對p1, p2和q1, q2，并設(shè)d = min| p2 p1 |, |q2 q1|。,27.07.2022,計算機(jī)算法設(shè)計與分析,32,一維最接近點對,設(shè)集合S為x軸上n個點，求S中最接近點對。假設(shè)用x軸上某個點m劃分S為S1和S2，使得S1=xS | xm，S2=xS | xm。,易知，S中最接近點對是p1, p2或q1, q2，或 p3, q3，這里p3=maxS1，q3 =minS2。,27.07.2022,計算機(jī)算法設(shè)計與分析,33,一維最接近點對算法,float Cpair1(S) n = |S|; if (n m/ d1 = Cpair1(S1); /求S1的最接近點對/ d2 = Cpair1(S2); /求S2的最接近點對/ p=maxS1; q=minS2; d=mind1, d2, qp; return(d);,最簡單情況是S中有0個或1個點。注意這時取其最接近點對距離為。,27.07.2022,計算機(jī)算法設(shè)計與分析,34,一維最接近點對算法復(fù)雜性,如果對S的分割不平衡的話，最壞情況是