數(shù)據(jù)結(jié)構(gòu)與算法-第十章Algorithmdesigntechniques武漢理工大學(xué)

1、信息工程學(xué)院信息工程學(xué)院School of Information Engineering2Ch10 Ch10 算法設(shè)計技術(shù)算法設(shè)計技術(shù)(Algorithm Design Techniques)10.1 窮舉法（Exhaustive Algorithm）10.2 遞推法與迭代法（ Recurrence and Iterative Algorithm ）10.3 遞歸（ Recursive Algorithm ）10.4 逐步求精（ Stepwise Refinement ）10.5 分治法（ Divide and ConquerDivide and Conquer ）10.6 貪心法（ Gre

2、edy AlgorithmGreedy Algorithm ）10.7 回溯法（ Backtracking AlgorithmBacktracking Algorithm ）10.8 動態(tài)規(guī)劃法（ Dynamic ProgrammingDynamic Programming ）10.9 分支界限法（ Branch and Bound AlgorithmBranch and Bound Algorithm ）Summary 310.1 窮舉法（Exhaustive Algorithm） 窮舉法窮舉法( (枚舉法枚舉法/ /試探法試探法) )基本思想是：基本思想是： 分別列舉出各種可能解，測試（試

3、探）其是否滿足條件分別列舉出各種可能解，測試（試探）其是否滿足條件（是否是欲求的解），若是，則輸出之。（是否是欲求的解），若是，則輸出之。 特點是算法簡單，但是運算量大。當問題的規(guī)模變大，執(zhí)行的的速度變慢。410.1 窮舉法（窮舉法（Exhaustive Algorithm） 例例1解不定方程。不定方程（組）是指獨立方程個數(shù)少于變量個數(shù)而導(dǎo)致方程有多解。 如，2x+3y=20是一個不定方程（設(shè)x, y為正整數(shù)）。解這個方程，就是求出所有的解。 不定方程一般都有限定條件，我們這里考慮正整數(shù)解的情況。解這個方程，一個簡單的做法是，讓x和y分別遍取0到20內(nèi)的正整數(shù)，并代入方程計算，若值為20，則表

4、示找到一組解。具體的程序片斷如下。 for (i=0; i=20; i+) for (j=0; j=20; j+) if (2*i + 3*j = 20 ) coutni,j; 510.2 遞推法與迭代法 （Recurrence and Iterative Algorithm） 遞推遞推法與法與迭代迭代法是兩種風(fēng)格類似的方法，它們都法是兩種風(fēng)格類似的方法，它們都是是基于分步遞增基于分步遞增方式進行求解。方式進行求解。6（1）遞推法）遞推法（Recurrence Algorithm） 遞推法遞推法是針對這樣一類問題：問題的解決可以分為若干步驟，每個步驟都產(chǎn)生一個子解（部分結(jié)果），每個子解都是由前

5、面若干子解生成。把這種由前面的子解得出后面的子解的規(guī)則稱為遞推關(guān)系。例如例如，對于Fibonacci數(shù)列：1 1 2 3 5 8 13 21 34 設(shè)f(n)表示數(shù)列中第n項，則有：f(1) = 1f(2) = 1f(k) = f(k-1) + f(k-2)7遞推法實現(xiàn)Fibonacci數(shù)列int Fibonacci(int n) int f1, f2, f3; int k; f1 = 1 ; f2 = 1 ; if ( n=1 ) return 1; if ( n=2 ) return 1; for (k=3; kprecision | x0-xprecision); /當最近兩個近似解的差

6、的絕對值小于給定精度時結(jié)束 return x; 1210.3.1 10.3.1 什么是遞歸什么是遞歸（1 1）遞歸的定義）遞歸的定義在定義一個過程或函數(shù)時出現(xiàn)調(diào)用本過程或本函數(shù)的成在定義一個過程或函數(shù)時出現(xiàn)調(diào)用本過程或本函數(shù)的成分分, ,稱之為稱之為遞歸遞歸。 若調(diào)用自身若調(diào)用自身, ,稱之為稱之為直接遞歸直接遞歸。 若過程或函數(shù)若過程或函數(shù)p p調(diào)用過程或函數(shù)調(diào)用過程或函數(shù)q,q,而而q q又調(diào)用又調(diào)用p,p,稱之為稱之為間接遞歸間接遞歸。 如果一個遞歸過程或遞歸函數(shù)中遞歸調(diào)用語句是最后如果一個遞歸過程或遞歸函數(shù)中遞歸調(diào)用語句是最后一條執(zhí)行語句一條執(zhí)行語句, ,則稱這種遞歸調(diào)用為則稱這種遞歸

7、調(diào)用為尾遞歸尾遞歸。10.3 10.3 遞歸遞歸（Recursive Algorithm）13例例10.3.1 以下是求以下是求n!(n為正整數(shù)為正整數(shù))的遞歸函數(shù)。的遞歸函數(shù)。 int fun(int n) if (n=1) /*語句語句1*/ return 1;/*語句語句2*/ else /*語句語句3*/ return fun(n-1)*n;/*語句語句4*/ 在該函數(shù)在該函數(shù)fun(n)求解過程中求解過程中,直接調(diào)用直接調(diào)用fun(n-1)(語句語句4)自身自身,所以它是一個所以它是一個直接遞歸函數(shù)直接遞歸函數(shù)。 遞歸調(diào)用是最后一條語句遞歸調(diào)用是最后一條語句,所以它又屬于所以它又屬于

8、尾遞歸尾遞歸。14（2 2） 何時使用遞歸何時使用遞歸 在以下三種情況下在以下三種情況下,常常要用到遞歸的方法。常常要用到遞歸的方法。 （a） 定義是遞歸的定義是遞歸的 有許多數(shù)學(xué)公式、數(shù)列等的定義是遞歸的。有許多數(shù)學(xué)公式、數(shù)列等的定義是遞歸的。 例如例如,求求n!和和Fibonacci數(shù)列等。數(shù)列等。 這些問題的求解過程可以將其遞歸定義直接轉(zhuǎn)化這些問題的求解過程可以將其遞歸定義直接轉(zhuǎn)化為對應(yīng)的遞歸算法。為對應(yīng)的遞歸算法。 15（b）數(shù)據(jù)結(jié)構(gòu)是遞歸的）數(shù)據(jù)結(jié)構(gòu)是遞歸的 有些數(shù)據(jù)結(jié)構(gòu)是遞歸的。有些數(shù)據(jù)結(jié)構(gòu)是遞歸的。 例如例如,第第2章中介紹過的單鏈表就是一種遞歸數(shù)據(jù)結(jié)章中介紹過的單鏈表就是一種遞

9、歸數(shù)據(jù)結(jié)構(gòu)構(gòu),其結(jié)點類型定義如下：其結(jié)點類型定義如下： typedef struct LNode ElemType data; struct LNode *next; LinkList; 該定義中該定義中,結(jié)構(gòu)體結(jié)構(gòu)體LNode的定義中用到了它自身的定義中用到了它自身,即即指針域指針域next是一種指向自身類型的指針是一種指向自身類型的指針,所以它是一種所以它是一種遞歸數(shù)據(jù)結(jié)構(gòu)。遞歸數(shù)據(jù)結(jié)構(gòu)。 16 對于遞歸數(shù)據(jù)結(jié)構(gòu)對于遞歸數(shù)據(jù)結(jié)構(gòu),采用遞歸的方法編寫算法既方采用遞歸的方法編寫算法既方便又有效。便又有效。 例如例如,求一個不帶頭結(jié)點的單鏈表求一個不帶頭結(jié)點的單鏈表head的所有的所有data域

10、域(假設(shè)為假設(shè)為int型型)之和的遞歸算法如下：之和的遞歸算法如下： int Sum(LinkList *head) if (head=NULL) return 0; else return(head-data+Sum(head-next); 17（c） 問題的求解方法是遞歸的問題的求解方法是遞歸的 有些問題的解法是遞歸的有些問題的解法是遞歸的, 典型的有典型的有Hanoi問題求解問題求解,該問題描述是：設(shè)有該問題描述是：設(shè)有3個個分別命名為分別命名為X,Y和和Z的塔座的塔座,在塔座在塔座X上有上有n個直徑各不個直徑各不相同相同,從小到大依次編號為從小到大依次編號為1,2,n的盤片的盤片,現(xiàn)要

11、求將現(xiàn)要求將X塔座上的塔座上的n個盤片移到塔座個盤片移到塔座Z上并仍按同樣順序疊放上并仍按同樣順序疊放,盤片移動時必須遵守以下規(guī)則：每次只能移動一個盤盤片移動時必須遵守以下規(guī)則：每次只能移動一個盤片；盤片可以插在片；盤片可以插在X,Y和和Z中任一塔座；任何時候都中任一塔座；任何時候都不能將一個較大的盤片放在較小的盤片上。設(shè)計遞歸不能將一個較大的盤片放在較小的盤片上。設(shè)計遞歸求解算法求解算法,并將其轉(zhuǎn)換為非遞歸算法。并將其轉(zhuǎn)換為非遞歸算法。 設(shè)設(shè)Hanoi(n,x,y,z)表示將表示將n個盤片從個盤片從x通過通過y移動到移動到z上上,遞歸分解的過程是：遞歸分解的過程是：18Hanoi(n,x,y

12、,z)Hanoi(n-1,x,z,y)；move(n,x,z):將第將第n個圓盤從個圓盤從x移到移到z；Hanoi(n-1,y,x,z)19（3 3） 遞歸模型遞歸模型 遞歸模型是遞歸算法的抽象遞歸模型是遞歸算法的抽象,它反映一個遞歸問題它反映一個遞歸問題的遞歸結(jié)構(gòu)的遞歸結(jié)構(gòu),例如例如,前面的遞歸算法對應(yīng)的遞歸模型如下：前面的遞歸算法對應(yīng)的遞歸模型如下： fun(1)=1 (1) fun(n)=n*fun(n-1) n1 (2) 式（式（1）給出了遞歸的終止條件）給出了遞歸的終止條件, 式（式（2）給出了）給出了fun(n)的值與的值與fun(n-1)的值之間的關(guān)系的值之間的關(guān)系 式（式（1）

13、稱為）稱為遞歸出口遞歸出口 式（式（2）稱為）稱為遞歸體遞歸體20 一般地一般地,一個遞歸模型是由遞歸出口和遞歸體兩部分一個遞歸模型是由遞歸出口和遞歸體兩部分組成組成,前者確定遞歸到何時結(jié)束前者確定遞歸到何時結(jié)束,后者確定遞歸求解時的后者確定遞歸求解時的遞推關(guān)系。遞推關(guān)系。遞歸出口的一般格式如下：遞歸出口的一般格式如下： f(s1)=m1 這里的這里的s1與與m1均為常量均為常量,有些遞歸問題可能有幾個遞有些遞歸問題可能有幾個遞歸出口。歸出口。遞歸體的一般格式如下：遞歸體的一般格式如下： f(sn+1)=g(f(si),f(si+1),f(sn),cj,cj+1,cm) (6.2) 其中其中,

14、n,i,j,m均為正整數(shù)。這里的均為正整數(shù)。這里的sn+1是一個遞歸是一個遞歸“大大問題問題”,si,si+1,sn為遞歸為遞歸“小問題小問題”,cj,cj+1,cm是若干是若干個可以直接個可以直接(用非遞歸方法用非遞歸方法)解決的問題解決的問題,g是一個非遞歸是一個非遞歸函數(shù)函數(shù),可以直接求值。可以直接求值。21 實際上實際上,遞歸思路是把一個不能或不好直接求解的遞歸思路是把一個不能或不好直接求解的“大問題大問題”轉(zhuǎn)化成一個或幾個轉(zhuǎn)化成一個或幾個“小問題小問題”來解決來解決,再把再把這些這些“小問題小問題”進一步分解成更小的進一步分解成更小的“小問題小問題”來解來解決決,如此分解如此分解,直

15、至每個直至每個“小問題小問題”都可以直接解決都可以直接解決(此此時分解到遞歸出口時分解到遞歸出口)。 遞歸分解不是隨意的分解遞歸分解不是隨意的分解,遞歸分解要保證遞歸分解要保證“大問題大問題”與與“小問題小問題”相似相似,即求解過程與環(huán)境都相似。即求解過程與環(huán)境都相似。 22為了討論方便為了討論方便,簡化上述遞歸模型為：簡化上述遞歸模型為： f(s1)=m1 f(sn)=g(f(sn-1),c)求求f(sn)的分解過程如下：的分解過程如下： f(sn) f(sn-1) f(s2) f(s1)23 一旦遇到遞歸出口一旦遇到遞歸出口,分解過程結(jié)束分解過程結(jié)束,開始求值過程開始求值過程,所所以分解過

16、程是以分解過程是“量變量變”過程過程,即原來的即原來的“大問題大問題”在慢在慢慢變小慢變小,但尚未解決但尚未解決,遇到遞歸出口后遇到遞歸出口后,便發(fā)生了便發(fā)生了“質(zhì)質(zhì)變變”,即原遞歸問題便轉(zhuǎn)化成直接問題。即原遞歸問題便轉(zhuǎn)化成直接問題。上面的求值過上面的求值過程如下：程如下： f(s1)=m1 f(s2)=g(f(s1),c1) f(s3)=g(f(s2),c2) f(sn)=g(f(sn-1),cn-1) 24 這樣這樣f(sn)便計算出來了。便計算出來了。 因此因此,遞歸的執(zhí)行過程由分解和求值兩部分構(gòu)成。遞歸的執(zhí)行過程由分解和求值兩部分構(gòu)成。 25 fun(5) d1:fun(4) d2:f

17、un(3) d3:fun(2) d4:fun(1) 返回 1 fun(2)=2 fun(3)=6 fun(4)=24 fun(5)=120 求解求解fun(5)的過程如下：的過程如下：2610.3.2 10.3.2 遞歸算法的設(shè)計遞歸算法的設(shè)計 遞歸的求解的過程均有這樣的特征：先將整個問題遞歸的求解的過程均有這樣的特征：先將整個問題劃分為若干個子問題劃分為若干個子問題,通過分別求解子問題通過分別求解子問題,最后獲得最后獲得整個問題的解。而這些子問題具有與原問題相同的求整個問題的解。而這些子問題具有與原問題相同的求解方法解方法,于是可以再將它們劃分成若干個子問題于是可以再將它們劃分成若干個子問題

18、,分別分別求解求解,如此反復(fù)進行如此反復(fù)進行,直到不能再劃分成子問題直到不能再劃分成子問題,或已經(jīng)或已經(jīng)可以求解為止。這種自上而下將問題分解、求解可以求解為止。這種自上而下將問題分解、求解,再自再自上而下引用、合并上而下引用、合并,求出最后解答的過程稱為遞歸求解求出最后解答的過程稱為遞歸求解過程。這是一種分而治之的算法設(shè)計方法。過程。這是一種分而治之的算法設(shè)計方法。 遞歸算法設(shè)計先要給出遞歸模型遞歸算法設(shè)計先要給出遞歸模型,再轉(zhuǎn)換成對應(yīng)的再轉(zhuǎn)換成對應(yīng)的C/C+語言函數(shù)。語言函數(shù)。27 遞歸設(shè)計的步驟如下：遞歸設(shè)計的步驟如下： (1)對原問題對原問題f(s)進行分析進行分析,假設(shè)出合理的假設(shè)出合

19、理的“較小問較小問題題”f(s)(與數(shù)學(xué)歸納法中假設(shè)與數(shù)學(xué)歸納法中假設(shè)n=k-1時等式成立相似時等式成立相似)； (2)假設(shè)假設(shè)f(s)是可解的是可解的,在此基礎(chǔ)上確定在此基礎(chǔ)上確定f(s)的解的解,即給出即給出f(s)與與f(s)之間的關(guān)系之間的關(guān)系(與數(shù)學(xué)歸納法中求證與數(shù)學(xué)歸納法中求證n=k時等式成時等式成立的過程相似立的過程相似)； (3)確定一個特定情況確定一個特定情況(如如f(1)或或f(0)的解的解,由此作為遞由此作為遞歸出口歸出口(與數(shù)學(xué)歸納法中求證與數(shù)學(xué)歸納法中求證n=1時等式成立相似時等式成立相似)。28 例如例如,采用遞歸算法求實數(shù)數(shù)組采用遞歸算法求實數(shù)數(shù)組A0.n-1中的

20、最小值。中的最小值。 假設(shè)假設(shè)f(A,i)函數(shù)求數(shù)組元素函數(shù)求數(shù)組元素A0Ai中的最小值。中的最小值。 當當i=0時時,有有f(A,i)=A0； 假設(shè)假設(shè)f(A,i-1)已求出已求出,則則f(A,i)=MIN(f(A,i-1),Ai),其中其中MIN()為求兩個值較小值函數(shù)。為求兩個值較小值函數(shù)。 因此得到如下遞歸模型：因此得到如下遞歸模型： A0 當當i=0時時 f(A,i)= MIN(f(A,i-1),Ai) 其他情況其他情況29由此得到如下遞歸求解算法：由此得到如下遞歸求解算法： float f(float A,int i) float m; if (i=0) return A0; el

21、se m=f(A,i-1); if (mAi) return Ai; else return m; 30例采用遞歸算法求解皇后問題：在例采用遞歸算法求解皇后問題：在nn的方的方格棋盤上，放置格棋盤上，放置n個皇后，要求每個皇后不同行、個皇后，要求每個皇后不同行、不同列、不同左右對角線。不同列、不同左右對角線。 （見教材）（見教材）3110.3.3 10.3.3 遞歸算法到非遞歸算法的轉(zhuǎn)換遞歸算法到非遞歸算法的轉(zhuǎn)換 遞歸算法有兩個基本特性：遞歸算法有兩個基本特性： 一是遞歸算法是一種分而治之的、把復(fù)雜問題分解為一是遞歸算法是一種分而治之的、把復(fù)雜問題分解為簡單問題的求解問題方法簡單問題的求解問題

22、方法,對求解某些復(fù)雜問題對求解某些復(fù)雜問題,遞歸算遞歸算法分析問題的方法是十分有效的；法分析問題的方法是十分有效的； 二是遞歸算法的時間效率通常比較差。二是遞歸算法的時間效率通常比較差。 因此因此,對求解某些問題時對求解某些問題時,我們希望用遞歸算法分析問我們希望用遞歸算法分析問題題,用非遞歸算法具體求解問題。用非遞歸算法具體求解問題。 這就需要把遞歸算法轉(zhuǎn)換為這就需要把遞歸算法轉(zhuǎn)換為非遞歸算法非遞歸算法。32把遞歸算法轉(zhuǎn)化為非遞歸算法有如下三種基本方法：把遞歸算法轉(zhuǎn)化為非遞歸算法有如下三種基本方法： (1)對于尾遞歸和單向遞歸的算法對于尾遞歸和單向遞歸的算法,可用循環(huán)結(jié)構(gòu)的算可用循環(huán)結(jié)構(gòu)的算

23、法替代。法替代。 (2)自己用棧模擬系統(tǒng)的運行時棧自己用棧模擬系統(tǒng)的運行時棧,通過分析只保存必通過分析只保存必須保存的信息須保存的信息,從而用非遞歸算法替代遞歸算法。從而用非遞歸算法替代遞歸算法。 (3)利用棧保存參數(shù)利用棧保存參數(shù),由于棧的后進先出特性吻合遞歸由于棧的后進先出特性吻合遞歸算法的執(zhí)行過程算法的執(zhí)行過程,因而可以用非遞歸算法替代遞歸算法。因而可以用非遞歸算法替代遞歸算法。 （見教材）（見教材） 3310.4 逐步求精（Stepwise Refinement）簡單地講，逐步求精方法，是一種逐步“劃分”的方法，即將問題的解決，先用幾個大/粗的模塊的組合表示。對這些模塊，先不考慮它們的

24、內(nèi)部實現(xiàn)，只規(guī)定其功能。然后再按類似方法繼續(xù)劃分這些模塊，直到它們都變?yōu)槌绦蛟O(shè)計語句。在這種劃分中，應(yīng)遵循下列規(guī)則：u保證模塊的粒度應(yīng)逐步變小保證模塊的粒度應(yīng)逐步變小。粒度越大/粗，“說明性”越強，越遠離程序設(shè)計語言，但越容易給出（設(shè)計）；u保證當前正確。保證當前正確。對每次劃分，若假定各模塊都可正確實現(xiàn)，則它們的當前組合（即劃分方式）是整個問題的正確實現(xiàn)；對逐步求精的描述，一般采用“偽碼”。所謂偽碼偽碼，是指不完全的程序代碼，它一般以程序設(shè)計語言(典型的是C/Pascal之類的結(jié)構(gòu)化程序設(shè)計語言)的流程控制語句（如while, for, if等）為主體，夾雜自然語言的描述。 34例 求矩陣的

25、鞍點考慮求矩陣鞍點的問題。所謂矩陣鞍點，是指滿足這樣條件的矩陣元素：它是所在行上的最小元素，同時是所在列上的最大元素。可以證明，一個矩陣可以有多個鞍點，但它們的值均相等。顯然，求鞍點的一個直接的方法是，檢查矩陣中每個元素是否為鞍點，用偽碼描述為（設(shè)矩陣名為a，有n行m列，元素下標從0起）：for (i=0; in; i+) for (j=0; jm; j+) 判斷aij是否為鞍點； if (aij 是鞍點) 輸出aij; 35例 求矩陣的鞍點(續(xù)1)這里，關(guān)鍵問題是判斷aij是否為鞍點，所以關(guān)鍵是細化模塊“判斷aij是否為鞍點”。解決該問題，先先檢查aij是否為i行上的最小者，若是，則則繼續(xù)檢

26、查其是否為j列上最大者，若是，則為鞍點。其他情況都不是鞍點。該過程的偽碼描述為：isSaddle = 0; 檢查aij是否為i行上最小者；if (是) 檢查aij是否為j列上最大者； if (是) isSaddle = 1;36例 求矩陣的鞍點（續(xù)2）這段程序結(jié)束后，isSaddle為非0時表示aij為鞍點，否則不是鞍點。在這里，有兩個模塊需要細化：a) 檢查aij是否為i行上最小者，這可以先找出i行上最小者的下標，然后與aij比較即可：kk=0;for (k=1; km; k+) if (aik aikk ) kk=k;if (aikk=aij) aij為i行上最小者；37例 求矩陣的鞍點（

27、續(xù)3）b) 檢查aij是否為j列上最大者： kk=0; for (k=1; k akkj ) kk=k; if (akkj=aij) aij為j列上最大者； 3810.5 10.5 分治法分治法（Divide and ConquerDivide and Conquer） 分治是指“分而治之”（Divide and conquer），是把一個規(guī)模為n的問題分成兩個或多個較小的與原問題類型相同的子問題，通過對子問題的求解，并把子問題的解合并起來從而構(gòu)造出整個問題的解，即對問題分而治之。 如果子問題的規(guī)模仍然相當大，還不足以很容易地求得它的解，這時可以對此子問題重復(fù)地應(yīng)用分治策略。3910.5 10

28、.5 分治法分治法（Divide and ConquerDivide and Conquer） 分治法求解過程，分為3個階段： 劃分。規(guī)模為n的原問題劃分為k（k=1）規(guī)模較小子問題。 求解子問題。各子問題與原問題解法相同，可用遞歸方法求解各個子問題。子問題足夠小時，直接求解。 合并。把各個子問題的解合并起來。40 分治法的算法框架分治法的算法框架return_type d_and_c( objArray return_type d_and_c( objArray * * p , int i , int j ) p , int i , int j ) int temp ; int temp ;

29、 if ( simple (p,i,j) ) return solve (p,i,j) ; if ( simple (p,i,j) ) return solve (p,i,j) ; / /* *基值處理基值處理 * */ / temp = divide (p,i,j) ; / temp = divide (p,i,j) ; /* *分解問題分解問題 * */ / return ( combine ( d_and_c(p,i,temp-1),d_and_c(p,temp,j) ) ); return ( combine ( d_and_c(p,i,temp-1),d_and_c(p,temp,j

30、) ) ); / /* *遞歸調(diào)用與合并處理遞歸調(diào)用與合并處理 * */ / 10.5 10.5 分治法分治法（Divide and ConquerDivide and Conquer）4110.5 10.5 分治法分治法（Divide and ConquerDivide and Conquer） 二分法檢索就是我們所學(xué)過的應(yīng)用分治策略的典型的例子。 快速排序算法，歸并排序算法、漢諾塔問題等都可以用分治策略求解。 快速排序算法每趟把一個元素放入排完序后它所應(yīng)在的位置，這個位置把原表分成了兩個宏觀有序的子表； 歸并排序算法是把規(guī)模為的問題分成規(guī)模為n/2的兩個子問題； 而漢諾塔問題分原問題為兩個

31、規(guī)模為n-1的子問題。 例子4210.5 10.5 分治法分治法（Divide and ConquerDivide and Conquer）討論 分治策略把問題分成若干個子問題，分成的子問題的數(shù)目一般不大。 如果每次分成的各子問題的規(guī)模相等或近乎相等的話，則分治策略的效率較高，否則效率就比較低。 例如：直接插入排序可以看作是把原問題分解成兩個子問題，一個是規(guī)模為的問題，另一個是規(guī)模為n-1的問題，算法的時間代價是O(n)級的。 而歸并排序把原問題分成了兩個大小為n/2的問題，算法的時間代價是O(nlog2n)級的。4310.6 10.6 貪心法貪心法（Greedy AlgorithmGreed

32、y Algorithm）貪心法貪心法(greedy)基本思想 根據(jù)題意，選取一種度量標準，然后將n個輸入數(shù)據(jù)排成這種標準所要求的順序，按這種順序一次輸入一個數(shù)據(jù)。每一次都要保證能獲得局部最優(yōu)解。若下一個數(shù)據(jù)與局部最優(yōu)解連在一起不再是可行解，就不把該數(shù)據(jù)添加到局部解中，直到把所有數(shù)據(jù)枚舉完，或者不能再添加為止。 這種能夠得到某種度量意義下的最優(yōu)解的分級處理方法貪心法。4410.6 10.6 貪心法貪心法（Greedy AlgorithmGreedy Algorithm） Dijkstra的最短路徑算法 求從源點到其它各結(jié)點的最短路徑 它總是從那些最短路徑還不知道的結(jié)點中挑選一個到源點最近的結(jié)點。

33、 另一采用貪心策略的算法是Kruskal的求最小生成樹算法。 Huffman樹的算法采用貪心法。45背包問題背包問題 給定n個物體和一個背包，已知物體i的重量為wi0，價值為pi，背包能容納物體的重量為M。要求確定一組分數(shù)xi(xi0,1)，能夠把物體i的xi部分放入背包，使得 最大，即將盡量多的價值裝入背包。 這是一個求最優(yōu)解的問題。在僅僅限制裝入背包的物品重量的前提下，為了使得裝入背包的物品得到盡量大的價值，應(yīng)該優(yōu)先放入按單位重量價值最大的物品?？梢杂秘澬姆ㄇ蠼?。貪心法是一個很直接的算法設(shè)計技術(shù)，可以很容易地用算法實現(xiàn)。10.6 10.6 貪心法貪心法（Greedy AlgorithmGr

34、eedy Algorithm）niiixp14610.6 10.6 貪心法貪心法（Greedy AlgorithmGreedy Algorithm）因為：p/w25/181.38，p/w24/151.6，p3/w315/101.5，p/wp/wp/w。所以首先把物品2全部放入背包，然后考慮物品3，最后如果還有余地考慮物品1。這樣得到的結(jié)果為（x，x2，x3）（0，1，1/2），例如：3，20， (p1,p2,p3)=(25,24,15), (w1,w2,w3)=(18,15,10)4710.6 10.6 貪心法貪心法（Greedy AlgorithmGreedy Algorithm） 解背包問

35、題的貪心算法的實現(xiàn)：其中參數(shù)數(shù)組其中參數(shù)數(shù)組p和和w中中,按按pi/wi的降序分別存放物體的價格和重量；的降序分別存放物體的價格和重量；m是背包能放的物體總重量，是背包能放的物體總重量，n是物體件數(shù)。是物體件數(shù)。x存放解向量。存放解向量。float knapSack(float* p, float* w, float * x ,float m, int n) int i=0; float s=0; while(in & pim) m -= wi; s += pi; xi = 1; i+; if ( i0 ) s += pi*m/wi; xi = m/wi; i+; for ( ; in

36、 ; i+ ) xi=0; return (s);48 進一步討論進一步討論 貪心算法各個階段的局部最優(yōu)選擇，一經(jīng)確定就固定地作為解序列的一部分。N步的選擇就可得到一個較好的次優(yōu)解（有可能是最優(yōu)解，但是最優(yōu)解一般是需經(jīng)全排列所有測試才能得到）。 貪心法在各個階段，選擇那些在某些意義下是局部最優(yōu)的方案，期望各階段的局部最優(yōu)的選擇帶來整體也最優(yōu)。但是，貪心法不是每次都能成功地產(chǎn)生出一個整體最優(yōu)解。 對某些問題，只有通過系統(tǒng)的、徹底的搜索才能得到最優(yōu)解，從而使我們求得最優(yōu)解的代價甚高。但是只要求得一個與最優(yōu)解相差不多的次優(yōu)解就滿足要求時，選用貪心法可以幫助我們很快地得到這樣的解。 10.6 10.6

37、 貪心法貪心法（Greedy AlgorithmGreedy Algorithm）4910.7 10.7 回溯法回溯法（Backtracking AlgorithmBacktracking Algorithm） 有一類問題，要求找到一個滿足某些條件的最優(yōu)解。對于解決這樣的問題，可以通過使用徹底的搜索方法來解決。然而，徹底的搜索，要進行大量的比較，大量的舍棄，要以大量的運算時間為代價，有時甚至大到連計算機也承受不了的程度。 因此，用“窮舉”的方法來解決這些問題往往是不實際的。 回溯法（backtracking）為我們解決這類問題提供了一個好的方法。求助于回溯技巧，常?？梢源蟠蟮販p少實際的搜索數(shù)目

38、?；厮莘ɑ舅枷耄喝粼诋斍拔恢锰綔y到一條通路則繼續(xù)向前，若在當前位置探測不到一條通路則回溯至前一位置繼續(xù)探測尚未探測的方向，直到找到一條通路或探測出無通路存在為止。50典型回溯算法舉例典型回溯算法舉例 （1）求解迷宮問題 （2）深度優(yōu)先對圖的遍歷 回溯算法與?；厮菟惴ㄅc棧 由于回溯方法的本質(zhì)是用深度優(yōu)先的方法在解的空間樹中搜索。所以在算法中都需要建立一個棧，用來保存搜索的路徑。一旦產(chǎn)生的部分解系列不合要求，就要從棧中找到回溯的前一個位置，繼續(xù)試探。10.7 10.7 回溯法回溯法（Backtracking AlgorithmBacktracking Algorithm）5110.7 10.7

39、回溯法回溯法（Backtracking AlgorithmBacktracking Algorithm）一般回溯方法的程序結(jié)構(gòu)：void backtrack (void) 準備初值； do while (范圍未超界并且工作未完成) 分析條件；/* 保證滿足條件才往下去 */if (成功) 路徑進棧； 由第一選擇開始進入下一層；/* 縱向走 */ else 本層更換選擇； /* 橫向走 */ if ( 工作未完成 ) 彈出堆棧； 原來的上一層更換為下一選擇；/* 回溯到上層橫向*/ while ( 全部工作未完成 ) ；輸出結(jié)果；5210.8 10.8 動態(tài)規(guī)劃法動態(tài)規(guī)劃法（Dynamic Pr

40、ogrammingDynamic Programming） 1951年，美國數(shù)學(xué)家R.Bellman等人根據(jù)一類多階段問題的特點，把多階段決策問題變換為一系列相互聯(lián)系的單階段問題，然后逐個加以解決。 同時提出解決這類問題的“最優(yōu)化原理”，從而創(chuàng)建了最優(yōu)化問題的一種新的算法設(shè)計方法動態(tài)規(guī)劃法。 能采用動態(tài)規(guī)劃法求解問題需要滿足以下條件： 問題的狀態(tài)必須滿足最優(yōu)化原理。 問題中的狀態(tài)必須滿足無后效性（下一時刻的狀態(tài)只與當前狀態(tài)有關(guān)，而與當前狀態(tài)之前的狀態(tài)無關(guān)）。5310.8 10.8 動態(tài)規(guī)劃法動態(tài)規(guī)劃法（Dynamic ProgrammingDynamic Programming） 與貪心法比較

41、 動態(tài)規(guī)劃法是將一系列的子問題的解確定后填入表中，從而導(dǎo)出原問題的解； 而貪心算法是進行了一系列的挑選，確定一個較好的解。 相同點：二者都作出一系列的確定； 區(qū)別（1）動態(tài)規(guī)劃法先求子問題的解，然后通過求解子問題構(gòu)造原問題的解；而貪心法是直接地解原問題。54 與貪心法比較 區(qū)別（2）動態(tài)規(guī)劃法一般產(chǎn)生多個子問題的解，每個子問題的解都是局部最優(yōu)的，局部最優(yōu)解構(gòu)造的整體解不一定是最優(yōu)的。動態(tài)規(guī)劃法通過對若干局部最優(yōu)解的比較，去掉了次優(yōu)解。從而產(chǎn)生了更高一層次的局部最優(yōu)解，保持了每個新產(chǎn)生的解都是該層次的局部最優(yōu)解。相當于對較低層次的局部最優(yōu)解進行貪心的選擇而得到高一級的局部最優(yōu)解，因而最終產(chǎn)生一個最高層次的局部最優(yōu)解，它就是原問題所求的整體的最優(yōu)解。 而貪心法是每階段只作一個挑選，各階段的解一經(jīng)選出就固定不變了，后階段的局部最優(yōu)是基于前階段的挑選，所以往往只能求出次優(yōu)解。10.8 10.8 動態(tài)規(guī)劃法動態(tài)規(guī)劃法（Dynamic ProgrammingDynamic Programming）55 與分治法比較 共同點：把一個大問題分解為若干較小的子問題，通過求解子問題而得到原問題的解。 不同點： 分治法每次分解的子問題數(shù)目比較少，子問題之間界限清楚，處理的過程通常是自頂向下進行； 動態(tài)規(guī)劃法分解的子問題可能比較多