第2章遞歸與分治策略ppt課件

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

2、2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4) 將求出的小規(guī)模的問(wèn)題的解合并為一個(gè)更大規(guī)模的問(wèn)題的解，自底向上逐漸求出原來(lái)問(wèn)題的解。算法總體思想將求出的小規(guī)模的問(wèn)題的解合并為一個(gè)更大規(guī)模的問(wèn)題的解，自底向上逐漸求出原來(lái)問(wèn)題的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T

3、(n/4)T(n/4)算法總體思想將求出的小規(guī)模的問(wèn)題的解合并為一個(gè)更大規(guī)模的問(wèn)題的解，自底向上逐漸求出原來(lái)問(wèn)題的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4) 分治法的設(shè)計(jì)思想是，將一個(gè)難以直接處理的大問(wèn)題，分割成一些規(guī)模較小的一樣問(wèn)題，以便各個(gè)擊破，分而治之。詳細(xì)步驟：1、將源問(wèn)題分解為有限的假設(shè)干個(gè)子問(wèn)題2、處理子問(wèn)題3、復(fù)合過(guò)程2.1 遞歸的概念直接或間接地調(diào)用本身的算法稱(chēng)為遞歸算法。用函數(shù)本身給出定義

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

5、urn n*factorial(n-1);2.1 遞歸的概念例2 Fibonacci數(shù)列無(wú)窮數(shù)列1，1，2，3，5，8，13，21，34，55，稱(chēng)為Fibonacci數(shù)列。它可以遞歸地定義為：邊境條件遞歸方程第n個(gè)Fibonacci數(shù)可遞歸地計(jì)算如下：int fibonacci(int n) if (n 1時(shí)，perm(R)由(r1)perm(R1)，(r2)perm(R2)，(rn)perm(Rn)構(gòu)成。 void Perm (Type list, int k, int m) if (k=m) for ( int i=0; i=m; i+) coutlisti; cout endl; els

6、e for ( int i=k; im1;正整數(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 遞歸的概念例5 整數(shù)劃分問(wèn)題前面的幾個(gè)例子中，問(wèn)題本身都具有比較明顯的遞歸關(guān)系，因此容易用遞歸函數(shù)直接求解。在本例中，假設(shè)設(shè)p(n)為正整數(shù)n的劃分?jǐn)?shù)，那么難以找到遞歸關(guān)系，因此思索添加一個(gè)自變量：將最大加數(shù)n1不大于m的劃分個(gè)數(shù)記作q(n,m)?？梢越(n,m)的如下遞歸關(guān)系。2.1 遞歸的概念例5 整數(shù)劃分問(wèn)題前面的幾個(gè)例子中，問(wèn)題本身都具有比較明顯的遞歸關(guān)系，因

7、此容易用遞歸函數(shù)直接求解。在本例中，假設(shè)設(shè)p(n)為正整數(shù)n的劃分?jǐn)?shù)，那么難以找到遞歸關(guān)系，因此思索添加一個(gè)自變量：將最大加數(shù)n1不大于m的劃分個(gè)數(shù)記作q(n,m)?？梢越(n,m)的如下遞歸關(guān)系。正整數(shù)n的劃分?jǐn)?shù)p(n)=q(n,n)。 Int q(int n,int m) if(n1)|(m1) return 0; if(n=1)|(m=1) return 1; if(n 0) hanoi(n-1, a, c, b); move(a,b); hanoi(n-1, c, b, a); 遞歸小結(jié)優(yōu)點(diǎn)：構(gòu)造明晰，可讀性強(qiáng)，而且容易用數(shù)學(xué)歸納法來(lái)證明算法的正確性，因此它為設(shè)計(jì)算法、調(diào)試程序帶來(lái)

8、很大方便。缺陷：遞歸算法的運(yùn)轉(zhuǎn)效率較低，無(wú)論是耗費(fèi)的計(jì)算時(shí)間還是占用的存儲(chǔ)空間都比非遞歸算法要多。處理方法：在遞歸算法中消除遞歸調(diào)用，使其轉(zhuǎn)化為非遞歸算法。1、采用一個(gè)用戶(hù)定義的棧來(lái)模擬系統(tǒng)的遞歸調(diào)用任務(wù)棧。該方法通用性強(qiáng)，但本質(zhì)上還是遞歸，只不過(guò)人工做了本來(lái)由編譯器做的事情，優(yōu)化效果不明顯。2、用遞推來(lái)實(shí)現(xiàn)遞歸函數(shù)。3、經(jīng)過(guò)變換能將一些遞歸轉(zhuǎn)化為尾遞歸，從而迭代求出結(jié)果。 后兩種方法在時(shí)空復(fù)雜度上均有較大改善，但其適用范圍有限。遞歸小結(jié)分治法的適用條件分治法所能處理的問(wèn)題普通具有以下幾個(gè)特征：該問(wèn)題的規(guī)模減少到一定的程度就可以容易地處理；該問(wèn)題可以分解為假設(shè)干個(gè)規(guī)模較小的一樣問(wèn)題，即該問(wèn)題具

9、有最優(yōu)子構(gòu)造性質(zhì)利用該問(wèn)題分解出的子問(wèn)題的解可以合并為該問(wèn)題的解；該問(wèn)題所分解出的各個(gè)子問(wèn)題是相互獨(dú)立的，即子問(wèn)題之間不包含公共的子問(wèn)題。 由于問(wèn)題的計(jì)算復(fù)雜性普通是隨著問(wèn)題規(guī)模的添加而添加，因此大部分問(wèn)題滿足這個(gè)特征。這條特征是運(yùn)用分治法的前提，它也是大多數(shù)問(wèn)題可以滿足的，此特征反映了遞歸思想的運(yùn)用能否利用分治法完全取決于問(wèn)題能否具有這條特征，假設(shè)具備了前兩條特征，而不具備第三條特征，那么可以思索貪婪算法或動(dòng)態(tài)規(guī)劃。這條特征涉及到分治法的效率，假設(shè)各子問(wèn)題是不獨(dú)立的，那么分治法要做許多不用要的任務(wù)，反復(fù)地解公共的子問(wèn)題，此時(shí)雖然也可用分治法，但普通用動(dòng)態(tài)規(guī)劃較好。divide-and-con

10、quer(P) if ( | P | = n0) adhoc(P); /處理小規(guī)模的問(wèn)題 divide P into smaller subinstances 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)

11、題的思想，它幾乎總是比子問(wèn)題規(guī)模不等的做法要好。分治法的復(fù)雜性分析一個(gè)分治法將規(guī)模為n的問(wèn)題分成k個(gè)規(guī)模為nm的子問(wèn)題去解。設(shè)分解閥值n0=1，且adhoc解規(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í)間，那么有：經(jīng)過(guò)迭代法求得方程的解：留意：遞歸方程及其解只給出n等于m的方冪時(shí)T(n)的值，但是假設(shè)以為T(mén)(n)足夠平滑，那么由n等于m的方冪時(shí)T(n)的值可以估計(jì)T(n)的增長(zhǎng)速度。通常假定T(n)是單調(diào)上升的，從而當(dāng)minmi+1時(shí)，T(mi)T(

12、n)T(mi+1)。 分析：假設(shè)n=1即只需一個(gè)元素，那么只需比較這個(gè)元素和x就可以確定x能否在表中。因此這個(gè)問(wèn)題滿足分治法的第一個(gè)適用條件分析：比較x和a的中間元素amid，假設(shè)x=amid，那么x在L中的位置就是mid；假設(shè)xai，同理我們只需在amid的后面查找x即可。無(wú)論是在前面還是后面查找x，其方法都和在a中查找x一樣，只不過(guò)是查找的規(guī)模減少了。這就闡明了此問(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è)元素中

13、找出一特定元素x。分析：該問(wèn)題的規(guī)模減少到一定的程度就可以容易地處理；該問(wèn)題可以分解為假設(shè)干個(gè)規(guī)模較小的一樣問(wèn)題;分解出的子問(wèn)題的解可以合并為原問(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& x, int l, int r) int m = (l+r)/2; if(x = am) return m;if(amx) return D(a,x,l,m-1);if(am0時(shí)，將2k2k棋盤(pán)分割為4

14、個(gè)2k-12k-1 子棋盤(pán)(a)所示。特殊方格必位于4個(gè)較小子棋盤(pán)之一中，其他3個(gè)子棋盤(pán)中無(wú)特殊方格。為了將這3個(gè)無(wú)特殊方格的子棋盤(pán)轉(zhuǎn)化為特殊棋盤(pán)，可以用一個(gè)L型骨牌覆蓋這3個(gè)較小棋盤(pán)的會(huì)合處，如 (b)所示，從而將原問(wèn)題轉(zhuǎn)化為4個(gè)較小規(guī)模的棋盤(pán)覆蓋問(wèn)題。遞歸地運(yùn)用這種分割，直至棋盤(pán)簡(jiǎn)化為棋盤(pán)11。 棋盤(pán)覆蓋void chessBoard(int tr, int tc, int dr, int dc, int size) if (size = 1) return; int t = tile+, / L型骨牌號(hào) s = size/2; / 分割棋盤(pán) / 覆蓋左上角子棋盤(pán) if (dr tr +

15、s & dc tc + s) / 特殊方格在此棋盤(pán)中 chessBoard(tr, tc, dr, dc, s); else / 此棋盤(pán)中無(wú)特殊方格 / 用 t 號(hào)L型骨牌覆蓋右下角 boardtr + s - 1tc + s - 1 = t; / 覆蓋其他方格 chessBoard(tr, tc, tr+s-1, tc+s-1, s); / 覆蓋右上角子棋盤(pán) if (dr = tc + s) / 特殊方格在此棋盤(pán)中 chessBoard(tr, tc+s, dr, dc, s); else / 此棋盤(pán)中無(wú)特殊方格 / 用 t 號(hào)L型骨牌覆蓋左下角 boardtr + s - 1tc + s

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

17、kn，要求找出這n個(gè)元素中第k小的元素templateType 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è)輸

18、入元素中的第k小元素。線性時(shí)間選擇假設(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ù)。例如，假設(shè)=9/10，算法遞歸調(diào)用所產(chǎn)生的子數(shù)組的長(zhǎng)度至少縮短1/10。所以，在最壞情況下，算法所需的計(jì)算時(shí)間T(n)滿足遞歸式T(n)T(9n/10)+O(n) 。由此可得T(n)=O(n)。將n個(gè)輸入元素劃分成n/5個(gè)組，每組5個(gè)元素，只能夠有一個(gè)組不是5個(gè)元素。用恣意一種排序算法，將每組中的元素排好序，并取出每組的中位數(shù)，共n/5個(gè)。遞歸調(diào)用select來(lái)找出這n/5個(gè)元素的中位數(shù)。假設(shè)n/5是偶數(shù)，就找它的2個(gè)中位數(shù)中較大的一個(gè)。以這個(gè)元素作為劃分基準(zhǔn)。線性時(shí)間選擇設(shè)一切元素互不一樣。在這種