遞歸與分治策略課件(PPT 38頁(yè)).ppt

1、第2章 遞歸與分治策略,學(xué)習(xí)要點(diǎn): 理解遞歸的概念。 掌握設(shè)計(jì)有效算法的分治策略。 通過(guò)下面的范例學(xué)習(xí)分治策略設(shè)計(jì)技巧。 （1）二分搜索技術(shù)； （2）大整數(shù)乘法； （3）棋盤覆蓋； （4）線性時(shí)間選擇；,將要求解的較大規(guī)模的問(wèn)題分割成k個(gè)更小規(guī)模的子問(wèn)題。,算法總體思想,n,T(n/2),T(n/2),T(n/2),T(n/2),T(n),=,對(duì)這k個(gè)子問(wèn)題分別求解。如果子問(wèn)題的規(guī)模仍然不夠小，則再劃分為k個(gè)子問(wèn)題，如此遞歸的進(jìn)行下去，直到問(wèn)題規(guī)模足夠小，很容易求出其解為止。,算法總體思想,對(duì)這k個(gè)子問(wèn)題分別求解。如果子問(wèn)題的規(guī)模仍然不夠小，則再劃分為k個(gè)子問(wèn)題，如此遞歸的進(jìn)行下去，直到問(wèn)題規(guī)

2、模足夠小，很容易求出其解為止。,n,T(n),=,將求出的小規(guī)模的問(wèn)題的解合并為一個(gè)更大規(guī)模的問(wèn)題的解，自底向上逐步求出原來(lái)問(wèn)題的解。,算法總體思想,將求出的小規(guī)模的問(wèn)題的解合并為一個(gè)更大規(guī)模的問(wèn)題的解，自底向上逐步求出原來(lái)問(wèn)題的解。,n,T(n),=,算法總體思想,將求出的小規(guī)模的問(wèn)題的解合并為一個(gè)更大規(guī)模的問(wèn)題的解，自底向上逐步求出原來(lái)問(wèn)題的解。,分治法的設(shè)計(jì)思想是，將一個(gè)難以直接解決的大問(wèn)題， 分割成一些規(guī)模較小的相同問(wèn)題，以便各個(gè)擊破， 分而治之。,具體步驟： 1、將源問(wèn)題分解為有限的若干個(gè)子問(wèn)題 2、解決子問(wèn)題 3、復(fù)合過(guò)程,2.1 遞歸的概念,直接或間接地調(diào)用自身的算法稱為遞歸算法

3、。用函數(shù)自身給出定義的函數(shù)稱為遞歸函數(shù)。 由分治法產(chǎn)生的子問(wèn)題往往是原問(wèn)題的較小模式，這就為使用遞歸技術(shù)提供了方便。在這種情況下，反復(fù)應(yīng)用分治手段，可以使子問(wèn)題與原問(wèn)題類型一致而其規(guī)模卻不斷縮小，最終使子問(wèn)題縮小到很容易直接求出其解。這自然導(dǎo)致遞歸過(guò)程的產(chǎn)生。 分治與遞歸像一對(duì)孿生兄弟，經(jīng)常同時(shí)應(yīng)用在算法設(shè)計(jì)之中，并由此產(chǎn)生許多高效算法。,下面來(lái)看幾個(gè)實(shí)例。,2.1 遞歸的概念,例1 階乘函數(shù) 階乘函數(shù)可遞歸地定義為：,邊界條件,遞歸方程,邊界條件與遞歸方程是遞歸函數(shù)的二個(gè)要素，遞歸函數(shù)只有具備了這兩個(gè)要素，才能在有限次計(jì)算后得出結(jié)果。,算法如下： int factorial(int n) i

4、f(n=0) return 1; return n*factorial(n-1); ,2.1 遞歸的概念,例2 Fibonacci數(shù)列 無(wú)窮數(shù)列1，1，2，3，5，8，13，21，34，55，稱為Fibonacci數(shù)列。它可以遞歸地定義為：,邊界條件,遞歸方程,第n個(gè)Fibonacci數(shù)可遞歸地計(jì)算如下： int fibonacci(int n) if (n = 1) return 1; return fibonacci(n-1)+fibonacci(n-2); ,2.1 遞歸的概念,例3 Ackerman函數(shù) 當(dāng)一個(gè)函數(shù)及它的一個(gè)變量是由函數(shù)自身定義時(shí)，稱這個(gè)函數(shù)是雙遞歸函數(shù)。 Ackerm

5、an函數(shù)A(n，m)定義如下：,2.1 遞歸的概念,例3 Ackerman函數(shù) 前2例中的函數(shù)都可以找到相應(yīng)的非遞歸方式定義：,本例中的Ackerman函數(shù)卻無(wú)法找到非遞歸的定義。,2.1 遞歸的概念,例3 Ackerman函數(shù) A(n，m)的自變量m的每一個(gè)值都定義了一個(gè)單變量函數(shù)： M=0時(shí)，A(n,0)=n+2 M=1時(shí)，A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2，和A(1,1)=2故A(n,1)=2*n M=2時(shí)，A(n,2)=A(A(n-1,2),1)=2A(n-1,2)，和A(1,2)=A(A(0,2),1)=A(1,1)=2，故A(n,2)= 2n 。 M=3

6、時(shí)，類似的可以推出 M=4時(shí)，A(n,4)的增長(zhǎng)速度非?？欤灾劣跊](méi)有適當(dāng)?shù)臄?shù)學(xué)式子來(lái)表示這一函數(shù)。,2.1 遞歸的概念,例4 排列問(wèn)題 設(shè)計(jì)一個(gè)遞歸算法生成n個(gè)元素r1,r2,rn的全排列。,設(shè)R=r1,r2,rn是要進(jìn)行排列的n個(gè)元素，Ri=R-ri。 集合X中元素的全排列記為perm(X)。 (ri)perm(X)表示在全排列perm(X)的每一個(gè)排列前加上前綴得到的排列。R的全排列可歸納定義如下：,當(dāng)n=1時(shí)，perm(R)=(r)，其中r是集合R中唯一的元素； 當(dāng)n1時(shí)，perm(R)由(r1)perm(R1)，(r2)perm(R2)，(rn)perm(Rn)構(gòu)成。,void Pe

7、rm (Type list, int k, int m) if (k=m) for ( int i=0; i=m; i+) coutlisti; cout endl; else for ( int i=k; i=m; i+) Swap ( listk, listi); Perm(list,k+1,m); Swap ( listk, listi); ,2.1 遞歸的概念,例5 整數(shù)劃分問(wèn)題 將正整數(shù)n表示成一系列正整數(shù)之和：n=n1+n2+nk， 其中n1n2nk1，k1。 正整數(shù)n的這種表示稱為正整數(shù)n的劃分。求正整數(shù)n的不 同劃分個(gè)數(shù)。,例如正整數(shù)6有如下11種不同的劃分： 6； 5+1；

8、4+2，4+1+1； 3+3，3+2+1，3+1+1+1； 2+2+2，2+2+1+1，2+1+1+1+1； 1+1+1+1+1+1。,(2) q(n,m)=q(n,n),mn; 最大加數(shù)n1實(shí)際上不能大于n。因此，q(1,m)=1。,(1) q(n,1)=1,n1; 當(dāng)最大加數(shù)n1不大于1時(shí)，任何正整數(shù)n只有一種劃分形式， 即,(4) q(n,m)=q(n,m-1)+q(n-m,m),nm1; 正整數(shù)n的最大加數(shù)n1不大于m的劃分由n1=m的劃分和 n1m-1 的劃分組成。,(3) q(n,n)=1+q(n,n-1); 正整數(shù)n的劃分由n1=n的劃分和n1n-1的劃分組成。,2.1 遞歸的概

9、念,例5 整數(shù)劃分問(wèn)題 前面的幾個(gè)例子中，問(wèn)題本身都具有比較明顯的遞歸關(guān)系，因而容易用遞歸函數(shù)直接求解。 在本例中，如果設(shè)p(n)為正整數(shù)n的劃分?jǐn)?shù)，則難以找到遞歸關(guān)系，因此考慮增加一個(gè)自變量：將最大加數(shù)n1不大于m的劃分個(gè)數(shù)記作q(n,m)。可以建立q(n,m)的如下遞歸關(guān)系。,2.1 遞歸的概念,例5 整數(shù)劃分問(wèn)題 前面的幾個(gè)例子中，問(wèn)題本身都具有比較明顯的遞歸關(guān)系，因而容易用遞歸函數(shù)直接求解。 在本例中，如果設(shè)p(n)為正整數(shù)n的劃分?jǐn)?shù)，則難以找到遞歸關(guān)系，因此考慮增加一個(gè)自變量：將最大加數(shù)n1不大于m的劃分個(gè)數(shù)記作q(n,m)。可以建立q(n,m)的如下遞歸關(guān)系。,正整數(shù)n的劃分?jǐn)?shù)p(

10、n)=q(n,n)。,Int q(int n,int m) if(n1)|(m1) return 0; if(n=1)|(m=1) return 1; if(nm) return q(n, n); if(n=m) return q(n, m-1)+1; return q(n, m-1)+ q(n-m, m); ,2.1 遞歸的概念,例6 Hanoi塔問(wèn)題 設(shè)a,b,c是3個(gè)塔座。開(kāi)始時(shí)，在塔座a上有一疊共n個(gè)圓盤，這些圓盤自下而上，由大到小地疊在一起。各圓盤從小到大編號(hào)為1,2,n,現(xiàn)要求將塔座a上的這一疊圓盤移到塔座b上，并仍按同樣順序疊置。在移動(dòng)圓盤時(shí)應(yīng)遵守以下移動(dòng)規(guī)則： 規(guī)則1：每次只能

11、移動(dòng)1個(gè)圓盤； 規(guī)則2：任何時(shí)刻都不允許將較大的圓盤壓在較小的圓盤之上； 規(guī)則3：在滿足移動(dòng)規(guī)則1和2的前提下，可將圓盤移至a,b,c中任一塔座上。,在問(wèn)題規(guī)模較大時(shí)，較難找到一般的方法，因此我們嘗試用遞歸技術(shù)來(lái)解決這個(gè)問(wèn)題。,當(dāng)n=1時(shí)，問(wèn)題比較簡(jiǎn)單。此時(shí)，只要將編號(hào)為1的圓盤從塔座a直接移至塔座b上即可。 當(dāng)n1時(shí)，需要利用塔座c作為輔助塔座。此時(shí)若能設(shè)法將n-1個(gè)較小的圓盤依照移動(dòng)規(guī)則從塔座a移至塔座c，然后，將剩下的最大圓盤從塔座a移至塔座b，最后，再設(shè)法將n-1個(gè)較小的圓盤依照移動(dòng)規(guī)則從塔座c移至塔座b。 由此可見(jiàn)，n個(gè)圓盤的移動(dòng)問(wèn)題可分為2次n-1個(gè)圓盤的移動(dòng)問(wèn)題，這又可以遞歸地用

12、上述方法來(lái)做。由此可以設(shè)計(jì)出解Hanoi塔問(wèn)題的遞歸算法如下。,2.1 遞歸的概念,例6 Hanoi塔問(wèn)題,void hanoi(int n, int a, int b, int c) if (n 0) hanoi(n-1, a, c, b); move(a,b); hanoi(n-1, c, b, a); ,遞歸小結(jié),優(yōu)點(diǎn)：結(jié)構(gòu)清晰，可讀性強(qiáng)，而且容易用數(shù)學(xué)歸納法來(lái)證明算法的正確性，因此它為設(shè)計(jì)算法、調(diào)試程序帶來(lái)很大方便。,缺點(diǎn)：遞歸算法的運(yùn)行效率較低，無(wú)論是耗費(fèi)的計(jì)算時(shí)間還是占用的存儲(chǔ)空間都比非遞歸算法要多。,解決方法：在遞歸算法中消除遞歸調(diào)用，使其轉(zhuǎn)化為非遞歸算法。 1、采用一個(gè)用戶定義

13、的棧來(lái)模擬系統(tǒng)的遞歸調(diào)用工作棧。該方法通用性強(qiáng)，但本質(zhì)上還是遞歸，只不過(guò)人工做了本來(lái)由編譯器做的事情，優(yōu)化效果不明顯。 2、用遞推來(lái)實(shí)現(xiàn)遞歸函數(shù)。 3、通過(guò)變換能將一些遞歸轉(zhuǎn)化為尾遞歸，從而迭代求出結(jié)果。 后兩種方法在時(shí)空復(fù)雜度上均有較大改善，但其適用范圍有限。,遞歸小結(jié),分治法的適用條件,分治法所能解決的問(wèn)題一般具有以下幾個(gè)特征： 該問(wèn)題的規(guī)?？s小到一定的程度就可以容易地解決； 該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題，即該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì) 利用該問(wèn)題分解出的子問(wèn)題的解可以合并為該問(wèn)題的解； 該問(wèn)題所分解出的各個(gè)子問(wèn)題是相互獨(dú)立的，即子問(wèn)題之間不包含公共的子問(wèn)題。,因?yàn)閱?wèn)題的計(jì)算復(fù)雜性

14、一般是隨著問(wèn)題規(guī)模的增加而增加，因此大部分問(wèn)題滿足這個(gè)特征。,這條特征是應(yīng)用分治法的前提，它也是大多數(shù)問(wèn)題可以滿足的，此特征反映了遞歸思想的應(yīng)用,能否利用分治法完全取決于問(wèn)題是否具有這條特征，如果具備了前兩條特征，而不具備第三條特征，則可以考慮貪心算法或動(dòng)態(tài)規(guī)劃。,這條特征涉及到分治法的效率，如果各子問(wèn)題是不獨(dú)立的，則分治法要做許多不必要的工作，重復(fù)地解公共的子問(wèn)題，此時(shí)雖然也可用分治法，但一般用動(dòng)態(tài)規(guī)劃較好。,divide-and-conquer(P) if ( | P | = n0) adhoc(P); /解決小規(guī)模的問(wèn)題 divide P into smaller subinstance

15、s P1,P2,.,Pk；/分解問(wèn)題 for (i=1,i=k,i+) yi=divide-and-conquer(Pi); /遞歸的解各子問(wèn)題 return merge(y1,.,yk); /將各子問(wèn)題的解合并為原問(wèn)題的解 ,分治法的基本步驟,人們從大量實(shí)踐中發(fā)現(xiàn)，在用分治法設(shè)計(jì)算法時(shí)，最好使子問(wèn)題的規(guī)模大致相同。即將一個(gè)問(wèn)題分成大小相等的k個(gè)子問(wèn)題的處理方法是行之有效的。這種使子問(wèn)題規(guī)模大致相等的做法是出自一種平衡(balancing)子問(wèn)題的思想，它幾乎總是比子問(wèn)題規(guī)模不等的做法要好。,分治法的復(fù)雜性分析,一個(gè)分治法將規(guī)模為n的問(wèn)題分成k個(gè)規(guī)模為nm的子問(wèn)題去解。設(shè)分解閥值n0=1，且a

16、dhoc解規(guī)模為1的問(wèn)題耗費(fèi)1個(gè)單位時(shí)間。再設(shè)將原問(wèn)題分解為k個(gè)子問(wèn)題以及用merge將k個(gè)子問(wèn)題的解合并為原問(wèn)題的解需用f(n)個(gè)單位時(shí)間。用T(n)表示該分治法解規(guī)模為|P|=n的問(wèn)題所需的計(jì)算時(shí)間，則有：,通過(guò)迭代法求得方程的解：,注意：遞歸方程及其解只給出n等于m的方冪時(shí)T(n)的值，但是如果認(rèn)為T(n)足夠平滑，那么由n等于m的方冪時(shí)T(n)的值可以估計(jì)T(n)的增長(zhǎng)速度。通常假定T(n)是單調(diào)上升的，從而當(dāng)minmi+1時(shí)，T(mi)T(n)T(mi+1)。,分析：如果n=1即只有一個(gè)元素，則只要比較這個(gè)元素和x就可以確定x是否在表中。因此這個(gè)問(wèn)題滿足分治法的第一個(gè)適用條件,分析：

17、比較x和a的中間元素amid，若x=amid，則x在L中的位置就是mid；如果xai，同理我們只要在amid的后面查找x即可。無(wú)論是在前面還是后面查找x，其方法都和在a中查找x一樣，只不過(guò)是查找的規(guī)?？s小了。這就說(shuō)明了此問(wèn)題滿足分治法的第二個(gè)和第三個(gè)適用條件。,分析：很顯然此問(wèn)題分解出的子問(wèn)題相互獨(dú)立，即在ai的前面或后面查找x是獨(dú)立的子問(wèn)題，因此滿足分治法的第四個(gè)適用條件。,二分搜索技術(shù),給定已按升序排好序的n個(gè)元素a0:n-1，現(xiàn)要在這n個(gè)元素中找出一特定元素x。 分析：,該問(wèn)題的規(guī)?？s小到一定的程度就可以容易地解決； 該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題; 分解出的子問(wèn)題的解可以合并

18、為原問(wèn)題的解； 分解出的各個(gè)子問(wèn)題是相互獨(dú)立的。,二分搜索技術(shù),給定已按升序排好序的n個(gè)元素a0:n-1，現(xiàn)要在這n個(gè)元素中找出一特定元素x。,據(jù)此容易設(shè)計(jì)出二分搜索算法： template int BinarySearch(Type a, const Type,算法復(fù)雜度分析： 每執(zhí)行一次算法的while循環(huán)， 待搜索數(shù)組的大小減少一半。因此，在最壞情況下，while循環(huán)被執(zhí)行了O(logn) 次。循環(huán)體內(nèi)運(yùn)算需要O(1) 時(shí)間，因此整個(gè)算法在最壞情況下的計(jì)算時(shí)間復(fù)雜性為O(logn) 。,大整數(shù)的乘法,請(qǐng)?jiān)O(shè)計(jì)一個(gè)有效的算法，可以進(jìn)行兩個(gè)n位大整數(shù)的乘法運(yùn)算,小學(xué)的方法：O(n2) 效率太低

19、 分治法:,X = Y = X = a 2n/2 + b Y = c 2n/2 + d XY = ac 2n + (ad+bc) 2n/2 + bd,a,b,c,d,復(fù)雜度分析 T(n)=O(n2) 沒(méi)有改進(jìn),大整數(shù)的乘法,請(qǐng)?jiān)O(shè)計(jì)一個(gè)有效的算法，可以進(jìn)行兩個(gè)n位大整數(shù)的乘法運(yùn)算,小學(xué)的方法：O(n2) 效率太低 分治法:,XY = ac 2n + (ad+bc) 2n/2 + bd 為了降低時(shí)間復(fù)雜度，必須減少乘法的次數(shù)。 XY = ac 2n + (a-b)(d-c)+ac+bd) 2n/2 + bd XY = ac 2n + (a+b)(c+d)-ac-bd) 2n/2 + bd,復(fù)雜度分

20、析 T(n)=O(nlog3) =O(n1.59)較大的改進(jìn),細(xì)節(jié)問(wèn)題：兩個(gè)XY的復(fù)雜度都是O(nlog3)，但考慮到a+c,b+d可能得到m+1位的結(jié)果，使問(wèn)題的規(guī)模變大，故不選擇第2種方案。,大整數(shù)的乘法,請(qǐng)?jiān)O(shè)計(jì)一個(gè)有效的算法，可以進(jìn)行兩個(gè)n位大整數(shù)的乘法運(yùn)算,小學(xué)的方法：O(n2) 效率太低 分治法: O(n1.59) 較大的改進(jìn) 更快的方法?,如果將大整數(shù)分成更多段，用更復(fù)雜的方式把它們組合起來(lái)，將有可能得到更優(yōu)的算法。,棋盤覆蓋,在一個(gè)2k2k 個(gè)方格組成的棋盤中，恰有一個(gè)方格與其它方格不同，稱該方格為一特殊方格，且稱該棋盤為一特殊棋盤。在棋盤覆蓋問(wèn)題中，要用圖示的4種不同形態(tài)的L型

21、骨牌覆蓋給定的特殊棋盤上除特殊方格以外的所有方格，且任何2個(gè)L型骨牌不得重疊覆蓋。,棋盤覆蓋,當(dāng)k0時(shí)，將2k2k棋盤分割為4個(gè)2k-12k-1 子棋盤(a)所示。 特殊方格必位于4個(gè)較小子棋盤之一中，其余3個(gè)子棋盤中無(wú)特殊方格。為了將這3個(gè)無(wú)特殊方格的子棋盤轉(zhuǎn)化為特殊棋盤，可以用一個(gè)L型骨牌覆蓋這3個(gè)較小棋盤的會(huì)合處，如 (b)所示，從而將原問(wèn)題轉(zhuǎn)化為4個(gè)較小規(guī)模的棋盤覆蓋問(wèn)題。遞歸地使用這種分割，直至棋盤簡(jiǎn)化為棋盤11。,棋盤覆蓋,void chessBoard(int tr, int tc, int dr, int dc, int size) if (size = 1) return;

22、int t = tile+, / L型骨牌號(hào) s = size/2; / 分割棋盤 / 覆蓋左上角子棋盤 if (dr = tc + s) / 特殊方格在此棋盤中 chessBoard(tr, tc+s, dr, dc, s); else / 此棋盤中無(wú)特殊方格 / 用 t 號(hào)L型骨牌覆蓋左下角,boardtr + s - 1tc + s = t; / 覆蓋其余方格 chessBoard(tr, tc+s, tr+s-1, tc+s, s); / 覆蓋左下角子棋盤 if (dr = tr + s ,復(fù)雜度分析 T(n)=O(4k) 漸進(jìn)意義下的最優(yōu)算法,線性時(shí)間選擇,給定線性序集中n個(gè)元素和一

23、個(gè)整數(shù)k，1kn，要求找出這n個(gè)元素中第k小的元素,template Type RandomizedSelect(Type a,int p,int r,int k) if (p=r) return ap; int i=RandomizedPartition(a,p,r), j=i-p+1; if (k=j) return RandomizedSelect(a,p,i,k); else return RandomizedSelect(a,i+1,r,k-j); ,在最壞情況下，算法randomizedSelect需要O(n2)計(jì)算時(shí)間 但可以證明，算法randomizedSelect可以在O(n)平均時(shí)間內(nèi)找出n個(gè)輸入元素中的第k小元素。,線性時(shí)間選擇,如果能在線性時(shí)間內(nèi)找到一個(gè)劃分基準(zhǔn)，使得按這個(gè)基準(zhǔn)所劃分出的2個(gè)子數(shù)組的長(zhǎng)度都至少為原數(shù)組長(zhǎng)度的倍(01是某個(gè)正常數(shù))，那么就可以在最壞情況下用O(n)時(shí)間完成選擇任務(wù)。,例如，若=9/10，算法遞歸調(diào)用所產(chǎn)生的子數(shù)組的長(zhǎng)度至少縮短1/10。所以，在最壞情況下，算法所需的計(jì)算時(shí)間T(n)滿足遞歸式T(n)T(9n/10)+O(