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

1、信息工程學(xué)院信息工程學(xué)院School of Information Engineering2Ch10 Ch10 算法設(shè)計(jì)技術(shù)算法設(shè)計(jì)技術(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 動(dòng)態(tài)規(guī)劃法（ Dynamic ProgrammingDynamic Programming ）10.9 分支界限法（ Branch and Bound AlgorithmBranch and Bound Algorithm ）Summary 310.1 窮舉法（Exhaustive Algorithm） 窮舉法窮舉法( (枚舉法枚舉法/ /試探法試探法) )基本思想是：基本思想是： 分別列舉出各種可能解，測試（試

3、探）其是否滿足條件分別列舉出各種可能解，測試（試探）其是否滿足條件（是否是欲求的解），若是，則輸出之。（是否是欲求的解），若是，則輸出之。 特點(diǎn)是算法簡單，但是運(yùn)算量大。當(dāng)問題的規(guī)模變大，執(zhí)行的的速度變慢。410.1 窮舉法（窮舉法（Exhaustive Algorithm） 例例1解不定方程。不定方程（組）是指獨(dú)立方程個(gè)數(shù)少于變量個(gè)數(shù)而導(dǎo)致方程有多解。 如，2x+3y=20是一個(gè)不定方程（設(shè)x, y為正整數(shù)）。解這個(gè)方程，就是求出所有的解。 不定方程一般都有限定條件，我們這里考慮正整數(shù)解的情況。解這個(gè)方程，一個(gè)簡單的做法是，讓x和y分別遍取0到20內(nèi)的正整數(shù)，并代入方程計(jì)算，若值為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)格類似的方法，它們都是是基于分步遞增基于分步遞增方式進(jìn)行求解。方式進(jìn)行求解。6（1）遞推法）遞推法（Recurrence Algorithm） 遞推法遞推法是針對這樣一類問題：問題的解決可以分為若干步驟，每個(gè)步驟都產(chǎn)生一個(gè)子解（部分結(jié)果），每個(gè)子解都是由前

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

6、的絕對值小于給定精度時(shí)結(jié)束 return x; 1210.3.1 10.3.1 什么是遞歸什么是遞歸（1 1）遞歸的定義）遞歸的定義在定義一個(gè)過程或函數(shù)時(shí)出現(xiàn)調(diào)用本過程或本函數(shù)的成在定義一個(gè)過程或函數(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,稱之為稱之為間接遞歸間接遞歸。 如果一個(gè)遞歸過程或遞歸函數(shù)中遞歸調(diào)用語句是最后如果一個(gè)遞歸過程或遞歸函數(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)自身自身,所以它是一個(gè)所以它是一個(gè)直接遞歸函數(shù)直接遞歸函數(shù)。 遞歸調(diào)用是最后一條語句遞歸調(diào)用是最后一條語句,所以它又屬于所以它又屬于

8、尾遞歸尾遞歸。14（2 2） 何時(shí)使用遞歸何時(shí)使用遞歸 在以下三種情況下在以下三種情況下,常常要用到遞歸的方法。常常要用到遞歸的方法。 （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é)點(diǎn)類型定義如下：其結(jié)點(diǎn)類型定義如下： 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),采用遞歸的方法編寫算法既方采用遞歸的方法編寫算法既方便又有效。便又有效。 例如例如,求一個(gè)不帶頭結(jié)點(diǎn)的單鏈表求一個(gè)不帶頭結(jié)點(diǎn)的單鏈表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個(gè)個(gè)分別命名為分別命名為X,Y和和Z的塔座的塔座,在塔座在塔座X上有上有n個(gè)直徑各不個(gè)直徑各不相同相同,從小到大依次編號為從小到大依次編號為1,2,n的盤片的盤片,現(xiàn)要

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

12、,z)Hanoi(n-1,x,z,y)；move(n,x,z):將第將第n個(gè)圓盤從個(gè)圓盤從x移到移到z；Hanoi(n-1,y,x,z)19（3 3） 遞歸模型遞歸模型 遞歸模型是遞歸算法的抽象遞歸模型是遞歸算法的抽象,它反映一個(gè)遞歸問題它反映一個(gè)遞歸問題的遞歸結(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 一般地一般地,一個(gè)遞歸模型是由遞歸出口和遞歸體兩部分一個(gè)遞歸模型是由遞歸出口和遞歸體兩部分組成組成,前者確定遞歸到何時(shí)結(jié)束前者確定遞歸到何時(shí)結(jié)束,后者確定遞歸求解時(shí)的后者確定遞歸求解時(shí)的遞推關(guān)系。遞推關(guān)系。遞歸出口的一般格式如下：遞歸出口的一般格式如下： f(s1)=m1 這里的這里的s1與與m1均為常量均為常量,有些遞歸問題可能有幾個(gè)遞有些遞歸問題可能有幾個(gè)遞歸出口。歸出口。遞歸體的一般格式如下：遞歸體的一般格式如下： 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是一個(gè)遞歸是一個(gè)遞歸“大大問題問題”,si,si+1,sn為遞歸為遞歸“小問題小問題”,cj,cj+1,cm是若干是若干個(gè)可以直接個(gè)可以直接(用非遞歸方法用非遞歸方法)解決的問題解決的問題,g是一個(gè)非遞歸是一個(gè)非遞歸函數(shù)函數(shù),可以直接求值?？梢灾苯忧笾?。21 實(shí)際上實(shí)際上,遞歸思路是把一個(gè)不能或不好直接求解的遞歸思路是把一個(gè)不能或不好直接求解的“大問題大問題”轉(zhuǎn)化成一個(gè)或幾個(gè)轉(zhuǎn)化成一個(gè)或幾個(gè)“小問題小問題”來解決來解決,再把再把這些這些“小問題小問題”進(jìn)一步分解成更小的進(jìn)一步分解成更小的“小問題小問題”來解來解決決,如此分解如此分解,直

15、至每個(gè)直至每個(gè)“小問題小問題”都可以直接解決都可以直接解決(此此時(shí)分解到遞歸出口時(shí)分解到遞歸出口)。 遞歸分解不是隨意的分解遞歸分解不是隨意的分解,遞歸分解要保證遞歸分解要保證“大問題大問題”與與“小問題小問題”相似相似,即求解過程與環(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)便計(jì)算出來了。便計(jì)算出來了。 因此因此,遞歸的執(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è)計(jì)遞歸算法的設(shè)計(jì) 遞歸的求解的過程均有這樣的特征：先將整個(gè)問題遞歸的求解的過程均有這樣的特征：先將整個(gè)問題劃分為若干個(gè)子問題劃分為若干個(gè)子問題,通過分別求解子問題通過分別求解子問題,最后獲得最后獲得整個(gè)問題的解。而這些子問題具有與原問題相同的求整個(gè)問題的解。而這些子問題具有與原問題相同的求解方法解方法,于是可以再將它們劃分成若干個(gè)子問題于是可以再將它們劃分成若干個(gè)子問題

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

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

20、最小值。中的最小值。 假設(shè)假設(shè)f(A,i)函數(shù)求數(shù)組元素函數(shù)求數(shù)組元素A0Ai中的最小值。中的最小值。 當(dāng)當(dāng)i=0時(shí)時(shí),有有f(A,i)=A0； 假設(shè)假設(shè)f(A,i-1)已求出已求出,則則f(A,i)=MIN(f(A,i-1),Ai),其中其中MIN()為求兩個(gè)值較小值函數(shù)。為求兩個(gè)值較小值函數(shù)。 因此得到如下遞歸模型：因此得到如下遞歸模型： A0 當(dāng)當(dāng)i=0時(shí)時(shí) 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個(gè)皇后，要求每個(gè)皇后不同行、個(gè)皇后，要求每個(gè)皇后不同行、不同列、不同左右對角線。不同列、不同左右對角線。 （見教材）（見教材）3110.3.3 10.3.3 遞歸算法到非遞歸算法的轉(zhuǎn)換遞歸算法到非遞歸算法的轉(zhuǎn)換 遞歸算法有兩個(gè)基本特性：遞歸算法有兩個(gè)基本特性： 一是遞歸算法是一種分而治之的、把復(fù)雜問題分解為一是遞歸算法是一種分而治之的、把復(fù)雜問題分解為簡單問題的求解問題方法簡單問題的求解問題

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

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

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

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

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

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），是把一個(gè)規(guī)模為n的問題分成兩個(gè)或多個(gè)較小的與原問題類型相同的子問題，通過對子問題的求解，并把子問題的解合并起來從而構(gòu)造出整個(gè)問題的解，即對問題分而治之。 如果子問題的規(guī)模仍然相當(dāng)大，還不足以很容易地求得它的解，這時(shí)可以對此子問題重復(fù)地應(yīng)用分治策略。3910.5 10

28、.5 分治法分治法（Divide and ConquerDivide and Conquer） 分治法求解過程，分為3個(gè)階段： 劃分。規(guī)模為n的原問題劃分為k（k=1）規(guī)模較小子問題。 求解子問題。各子問題與原問題解法相同，可用遞歸方法求解各個(gè)子問題。子問題足夠小時(shí)，直接求解。 合并。把各個(gè)子問題的解合并起來。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)用分治策略的典型的例子。 快速排序算法，歸并排序算法、漢諾塔問題等都可以用分治策略求解。 快速排序算法每趟把一個(gè)元素放入排完序后它所應(yīng)在的位置，這個(gè)位置把原表分成了兩個(gè)宏觀有序的子表； 歸并排序算法是把規(guī)模為的問題分成規(guī)模為n/2的兩個(gè)子問題； 而漢諾塔問題分原問題為兩個(gè)

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

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

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

34、eedy Algorithm）niiixp14610.6 10.6 貪心法貪心法（Greedy AlgorithmGreedy Algorithm）因?yàn)椋簆/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、題的貪心算法的實(shí)現(xiàn)：其中參數(shù)數(shù)組其中參數(shù)數(shù)組p和和w中中,按按pi/wi的降序分別存放物體的價(jià)格和重量；的降序分別存放物體的價(jià)格和重量；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 ; i

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

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

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

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

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

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