數(shù)據(jù)結(jié)構(gòu)與算法第十章Algorithmdesigntechniques

1、Ch10 算法設(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 Conquer ）10.6 貪心法（ Greedy Algorithm ）10.7 回溯法（ Backtracking Algorithm ）10.8 動態(tài)規(guī)劃法（ Dynamic Progra

2、mming ）10.9 分支界限法（ Branch and Bound Algorithm ）Summary 10.1 窮舉法（Exhaustive Algorithm） 窮舉法(枚舉法/試探法)基本思想是： 分別列舉出各種可能解，測試（試探）其是否滿足條件（是否是欲求的解），若是，則輸出之。 特點是算法簡單，但是運算量大。當(dāng)問題的規(guī)模變大，執(zhí)行的的速度變慢。10.1 窮舉法（Exhaustive Algorithm） 例1解不定方程。不定方程（組）是指獨立方程個數(shù)少于變量個數(shù)而導(dǎo)致方程有多解。 如，2x+3y=20是一個不定方程（設(shè)x, y為正整數(shù)）。解這個方程，就是求出所有的解。 不定方程

3、一般都有限定條件，我們這里考慮正整數(shù)解的情況。解這個方程，一個簡單的做法是，讓x和y分別遍取0到20內(nèi)的正整數(shù)，并代入方程計算，若值為20，則表示找到一組解。具體的程序片斷如下。 for (i=0; i=20; i+) for (j=0; j=20; j+) if (2*i + 3*j = 20 ) coutni,j; 10.2 遞推法與迭代法 （Recurrence and Iterative Algorithm） 遞推法與迭代法是兩種風(fēng)格類似的方法，它們都是基于分步遞增方式進(jìn)行求解。（1）遞推法（Recurrence Algorithm） 遞推法是針對這樣一類問題：問題的解決可以分為若干步

4、驟，每個步驟都產(chǎn)生一個子解（部分結(jié)果），每個子解都是由前面若干子解生成。把這種由前面的子解得出后面的子解的規(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)遞推法實現(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

5、-xprecision); /當(dāng)最近兩個近似解的差的絕對值小于給定精度時結(jié)束 return x; 10.3.1 什么是遞歸（1）遞歸的定義在定義一個過程或函數(shù)時出現(xiàn)調(diào)用本過程或本函數(shù)的成分,稱之為遞歸。 若調(diào)用自身,稱之為直接遞歸。 若過程或函數(shù)p調(diào)用過程或函數(shù)q,而q又調(diào)用p,稱之為間接遞歸。 如果一個遞歸過程或遞歸函數(shù)中遞歸調(diào)用語句是最后一條執(zhí)行語句,則稱這種遞歸調(diào)用為尾遞歸。10.3 遞歸（Recursive Algorithm）例10.3.1 以下是求n!(n為正整數(shù))的遞歸函數(shù)。 int fun(int n) if (n=1) /*語句1*/ return 1;/*語句2*/ els

6、e /*語句3*/ return fun(n-1)*n;/*語句4*/ 在該函數(shù)fun(n)求解過程中,直接調(diào)用fun(n-1)(語句4)自身,所以它是一個直接遞歸函數(shù)。 遞歸調(diào)用是最后一條語句,所以它又屬于尾遞歸。（2） 何時使用遞歸 在以下三種情況下,常常要用到遞歸的方法。 （a） 定義是遞歸的 有許多數(shù)學(xué)公式、數(shù)列等的定義是遞歸的。 例如,求n!和Fibonacci數(shù)列等。 這些問題的求解過程可以將其遞歸定義直接轉(zhuǎn)化為對應(yīng)的遞歸算法。 （b）數(shù)據(jù)結(jié)構(gòu)是遞歸的 有些數(shù)據(jù)結(jié)構(gòu)是遞歸的。 例如,第2章中介紹過的單鏈表就是一種遞歸數(shù)據(jù)結(jié)構(gòu),其結(jié)點類型定義如下： typedef struct LN

7、ode ElemType data; struct LNode *next; LinkList; 該定義中,結(jié)構(gòu)體LNode的定義中用到了它自身,即指針域next是一種指向自身類型的指針,所以它是一種遞歸數(shù)據(jù)結(jié)構(gòu)。 對于遞歸數(shù)據(jù)結(jié)構(gòu),采用遞歸的方法編寫算法既方便又有效。 例如,求一個不帶頭結(jié)點的單鏈表head的所有data域(假設(shè)為int型)之和的遞歸算法如下： int Sum(LinkList *head) if (head=NULL) return 0; else return(head-data+Sum(head-next); （c） 問題的求解方法是遞歸的 有些問題的解法是遞歸的, 典

8、型的有Hanoi問題求解,該問題描述是：設(shè)有3個分別命名為X,Y和Z的塔座,在塔座X上有n個直徑各不相同,從小到大依次編號為1,2,n的盤片,現(xiàn)要求將X塔座上的n個盤片移到塔座Z上并仍按同樣順序疊放,盤片移動時必須遵守以下規(guī)則：每次只能移動一個盤片；盤片可以插在X,Y和Z中任一塔座；任何時候都不能將一個較大的盤片放在較小的盤片上。設(shè)計遞歸求解算法,并將其轉(zhuǎn)換為非遞歸算法。 設(shè)Hanoi(n,x,y,z)表示將n個盤片從x通過y移動到z上,遞歸分解的過程是：Hanoi(n,x,y,z)Hanoi(n-1,x,z,y)；move(n,x,z):將第n個圓盤從x移到z；Hanoi(n-1,y,x,z

9、)（3） 遞歸模型 遞歸模型是遞歸算法的抽象,它反映一個遞歸問題的遞歸結(jié)構(gòu),例如,前面的遞歸算法對應(yīng)的遞歸模型如下： fun(1)=1 (1) fun(n)=n*fun(n-1) n1 (2) 式（1）給出了遞歸的終止條件, 式（2）給出了fun(n)的值與fun(n-1)的值之間的關(guān)系 式（1）稱為遞歸出口 式（2）稱為遞歸體 一般地,一個遞歸模型是由遞歸出口和遞歸體兩部分組成,前者確定遞歸到何時結(jié)束,后者確定遞歸求解時的遞推關(guān)系。遞歸出口的一般格式如下： f(s1)=m1 這里的s1與m1均為常量,有些遞歸問題可能有幾個遞歸出口。遞歸體的一般格式如下： f(sn+1)=g(f(si),f(

10、si+1),f(sn),cj,cj+1,cm) (6.2) 其中,n,i,j,m均為正整數(shù)。這里的sn+1是一個遞歸“大問題”,si,si+1,sn為遞歸“小問題”,cj,cj+1,cm是若干個可以直接(用非遞歸方法)解決的問題,g是一個非遞歸函數(shù),可以直接求值。 實際上,遞歸思路是把一個不能或不好直接求解的“大問題”轉(zhuǎn)化成一個或幾個“小問題”來解決,再把這些“小問題”進(jìn)一步分解成更小的“小問題”來解決,如此分解,直至每個“小問題”都可以直接解決(此時分解到遞歸出口)。 遞歸分解不是隨意的分解,遞歸分解要保證“大問題”與“小問題”相似,即求解過程與環(huán)境都相似。 為了討論方便,簡化上述遞歸模型為

11、： f(s1)=m1 f(sn)=g(f(sn-1),c)求f(sn)的分解過程如下： f(sn) f(sn-1) f(s2) f(s1) 一旦遇到遞歸出口,分解過程結(jié)束,開始求值過程,所以分解過程是“量變”過程,即原來的“大問題”在慢慢變小,但尚未解決,遇到遞歸出口后,便發(fā)生了“質(zhì)變”,即原遞歸問題便轉(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) 這樣f(sn)便計算出來了。 因此,遞歸的執(zhí)行過程由分解和求值兩部分構(gòu)成。 求解fun(5)的過程如下：10.3.2 遞歸算

12、法的設(shè)計 遞歸的求解的過程均有這樣的特征：先將整個問題劃分為若干個子問題,通過分別求解子問題,最后獲得整個問題的解。而這些子問題具有與原問題相同的求解方法,于是可以再將它們劃分成若干個子問題,分別求解,如此反復(fù)進(jìn)行,直到不能再劃分成子問題,或已經(jīng)可以求解為止。這種自上而下將問題分解、求解,再自上而下引用、合并,求出最后解答的過程稱為遞歸求解過程。這是一種分而治之的算法設(shè)計方法。 遞歸算法設(shè)計先要給出遞歸模型,再轉(zhuǎn)換成對應(yīng)的C/C+語言函數(shù)。 遞歸設(shè)計的步驟如下： (1)對原問題f(s)進(jìn)行分析,假設(shè)出合理的“較小問題”f(s)(與數(shù)學(xué)歸納法中假設(shè)n=k-1時等式成立相似)； (2)假設(shè)f(s)

13、是可解的,在此基礎(chǔ)上確定f(s)的解,即給出f(s)與f(s)之間的關(guān)系(與數(shù)學(xué)歸納法中求證n=k時等式成立的過程相似)； (3)確定一個特定情況(如f(1)或f(0)的解,由此作為遞歸出口(與數(shù)學(xué)歸納法中求證n=1時等式成立相似)。 例如,采用遞歸算法求實數(shù)數(shù)組A0.n-1中的最小值。 假設(shè)f(A,i)函數(shù)求數(shù)組元素A0Ai中的最小值。 當(dāng)i=0時,有f(A,i)=A0； 假設(shè)f(A,i-1)已求出,則f(A,i)=MIN(f(A,i-1),Ai),其中MIN()為求兩個值較小值函數(shù)。 因此得到如下遞歸模型： A0 當(dāng)i=0時 f(A,i)= MIN(f(A,i-1),Ai) 其他情況由此得

14、到如下遞歸求解算法： float f(float A,int i) float m; if (i=0) return A0; else m=f(A,i-1); if (mAi) return Ai; else return m; 例采用遞歸算法求解皇后問題：在nn的方格棋盤上，放置n個皇后，要求每個皇后不同行、不同列、不同左右對角線。 （見教材）10.3.3 遞歸算法到非遞歸算法的轉(zhuǎn)換 遞歸算法有兩個基本特性： 一是遞歸算法是一種分而治之的、把復(fù)雜問題分解為簡單問題的求解問題方法,對求解某些復(fù)雜問題,遞歸算法分析問題的方法是十分有效的； 二是遞歸算法的時間效率通常比較差。 因此,對求解某些問題

15、時,我們希望用遞歸算法分析問題,用非遞歸算法具體求解問題。 這就需要把遞歸算法轉(zhuǎn)換為非遞歸算法。把遞歸算法轉(zhuǎn)化為非遞歸算法有如下三種基本方法： (1)對于尾遞歸和單向遞歸的算法,可用循環(huán)結(jié)構(gòu)的算法替代。 (2)自己用棧模擬系統(tǒng)的運行時棧,通過分析只保存必須保存的信息,從而用非遞歸算法替代遞歸算法。 (3)利用棧保存參數(shù),由于棧的后進(jìn)先出特性吻合遞歸算法的執(zhí)行過程,因而可以用非遞歸算法替代遞歸算法。 （見教材） 10.4 逐步求精（Stepwise Refinement）簡單地講，逐步求精方法，是一種逐步“劃分”的方法，即將問題的解決，先用幾個大/粗的模塊的組合表示。對這些模塊，先不考慮它們的內(nèi)

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

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

18、該過程的偽碼描述為：isSaddle = 0; 檢查aij是否為i行上最小者；if (是) 檢查aij是否為j列上最大者； if (是) isSaddle = 1;例 求矩陣的鞍點（續(xù)2）這段程序結(jié)束后，isSaddle為非0時表示aij為鞍點，否則不是鞍點。在這里，有兩個模塊需要細(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行上最小者；例 求矩陣的鞍點（續(xù)3）b) 檢查aij是否為j列上最大者： kk=0; for (k

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

20、。求解子問題。各子問題與原問題解法相同，可用遞歸方法求解各個子問題。子問題足夠小時，直接求解。合并。把各個子問題的解合并起來。分治法的算法框架return_type d_and_c( objArray * p , int i , int j ) int temp ; if ( simple (p,i,j) ) return solve (p,i,j) ; /*基值處理 */ temp = divide (p,i,j) ; /*分解問題 */ return ( combine ( d_and_c(p,i,temp-1),d_and_c(p,temp,j) ) ); /*遞歸調(diào)用與合并處理 */1

21、0.5 分治法（Divide and Conquer）10.5 分治法（Divide and Conquer）二分法檢索就是我們所學(xué)過的應(yīng)用分治策略的典型的例子?？焖倥判蛩惴?，歸并排序算法、漢諾塔問題等都可以用分治策略求解。 快速排序算法每趟把一個元素放入排完序后它所應(yīng)在的位置，這個位置把原表分成了兩個宏觀有序的子表；歸并排序算法是把規(guī)模為的問題分成規(guī)模為n/2的兩個子問題；而漢諾塔問題分原問題為兩個規(guī)模為n-1的子問題。 例子10.5 分治法（Divide and Conquer）討論分治策略把問題分成若干個子問題，分成的子問題的數(shù)目一般不大。如果每次分成的各子問題的規(guī)模相等或近乎相等的話，

22、則分治策略的效率較高，否則效率就比較低。例如：直接插入排序可以看作是把原問題分解成兩個子問題，一個是規(guī)模為的問題，另一個是規(guī)模為n-1的問題，算法的時間代價是O(n)級的。而歸并排序把原問題分成了兩個大小為n/2的問題，算法的時間代價是O(nlog2n)級的。10.6 貪心法（Greedy Algorithm）貪心法(greedy)基本思想根據(jù)題意，選取一種度量標(biāo)準(zhǔn)，然后將n個輸入數(shù)據(jù)排成這種標(biāo)準(zhǔn)所要求的順序，按這種順序一次輸入一個數(shù)據(jù)。每一次都要保證能獲得局部最優(yōu)解。若下一個數(shù)據(jù)與局部最優(yōu)解連在一起不再是可行解，就不把該數(shù)據(jù)添加到局部解中，直到把所有數(shù)據(jù)枚舉完，或者不能再添加為止。這種能夠得

23、到某種度量意義下的最優(yōu)解的分級處理方法貪心法。10.6 貪心法（Greedy Algorithm）Dijkstra的最短路徑算法 求從源點到其它各結(jié)點的最短路徑 它總是從那些最短路徑還不知道的結(jié)點中挑選一個到源點最近的結(jié)點。另一采用貪心策略的算法是Kruskal的求最小生成樹算法。Huffman樹的算法采用貪心法。背包問題 給定n個物體和一個背包，已知物體i的重量為wi0，價值為pi，背包能容納物體的重量為M。要求確定一組分?jǐn)?shù)xi(xi0,1)，能夠把物體i的xi部分放入背包，使得 最大，即將盡量多的價值裝入背包。 這是一個求最優(yōu)解的問題。在僅僅限制裝入背包的物品重量的前提下，為了使得裝入背包

24、的物品得到盡量大的價值，應(yīng)該優(yōu)先放入按單位重量價值最大的物品?？梢杂秘澬姆ㄇ蠼狻Ｘ澬姆ㄊ且粋€很直接的算法設(shè)計技術(shù)，可以很容易地用算法實現(xiàn)。10.6 貪心法（Greedy Algorithm）10.6 貪心法（Greedy Algorithm）因為：p/w25/18，p/w24/15，p3/w315/10，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)10.6 貪心法（Greedy Algo

25、rithm）解背包問題的貪心算法的實現(xiàn)：其中參數(shù)數(shù)組p和w中,按pi/wi的降序分別存放物體的價格和重量；m是背包能放的物體總重量，n是物體件數(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+ ) xi=0; return (s); 進(jìn)一步討論 貪心算法各個階段的局部最

26、優(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 貪心法（Greedy Algorithm）10.7 回溯法（Backtracking Algorithm） 有

27、一類問題，要求找到一個滿足某些條件的最優(yōu)解。對于解決這樣的問題，可以通過使用徹底的搜索方法來解決。然而，徹底的搜索，要進(jìn)行大量的比較，大量的舍棄，要以大量的運算時間為代價，有時甚至大到連計算機也承受不了的程度。 因此，用“窮舉”的方法來解決這些問題往往是不實際的。 回溯法（backtracking）為我們解決這類問題提供了一個好的方法。求助于回溯技巧，常?？梢源蟠蟮販p少實際的搜索數(shù)目?；厮莘ɑ舅枷耄喝粼诋?dāng)前位置探測到一條通路則繼續(xù)向前，若在當(dāng)前位置探測不到一條通路則回溯至前一位置繼續(xù)探測尚未探測的方向，直到找到一條通路或探測出無通路存在為止。典型回溯算法舉例 （1）求解迷宮問題 （2）深度優(yōu)

28、先對圖的遍歷 回溯算法與棧 由于回溯方法的本質(zhì)是用深度優(yōu)先的方法在解的空間樹中搜索。所以在算法中都需要建立一個棧，用來保存搜索的路徑。一旦產(chǎn)生的部分解系列不合要求，就要從棧中找到回溯的前一個位置，繼續(xù)試探。10.7 回溯法（Backtracking Algorithm）10.7 回溯法（Backtracking Algorithm）一般回溯方法的程序結(jié)構(gòu)：void backtrack (void) 準(zhǔn)備初值； do while (范圍未超界并且工作未完成) 分析條件；/* 保證滿足條件才往下去 */if (成功) 路徑進(jìn)棧； 由第一選擇開始進(jìn)入下一層；/* 縱向走 */ else 本層更換選擇； /* 橫向走 */ if (