1、遞歸算法的優缺點：1優點：結構清晰，可讀性強，而且容易用數學歸納法來證明算法的正確性，因此它為設計 算法、調試程序帶來很大方便。1缺點：遞歸算法的運行效率較低，無論是耗費的計算時間還是占用的存儲空間都比非遞歸 算法要多。邊界條件與遞歸方程是遞歸函數的二個要素應用分治法的兩個前提是問題的可分性和解的可歸并性tA(n)tA(x)/|Xn|X Xn以比較為基礎的排序算復雜0(n Iog2n)。t b ( x ) t a (n) s(n)回溯法以深度優先的方式搜索解空間樹T,而分支限界法則以廣度優先或以最小耗費優先的方式搜索解空間樹 T。舍伍德算法設計的基本思想：設A是一個確定性算法，當它的輸入實例為

2、x時所需的計算時間記為tA(x)。設Xn是算法A的輸入規模為n的實例的全體，則當問題的輸入規模為n時，算法A所需的平均時間為這顯然不能排除存在 x Xn使得B,使得對問題的輸入規模為n的每一個實例均有的可能性。希望獲得一個隨機化算法拉斯維加斯(Las Vegas )算法的基本思想：設p(x)是對輸入x調用拉斯維加斯算法獲得問題的一個解的概率。一個正確的拉斯維加斯算法應該對所有輸入 x均有p(x)>0 。設t(x)是算法obstinate找到具體實例x的一個解所需的平均時間,s(x)和e(x)分別是算法對于具體實例x求解成功或求解失敗所需的平均時間，則有：解此方程可得：蒙特卡羅(Monte

3、 Carlo) 算法的基本思想：設p是一個實數，且1/2<p<1。如果一個蒙特卡羅算法對于問題的任一實例得到正確解的概率不小于p，則稱該蒙特卡羅算法是 p正確的，且稱p-1/2是該算法的優勢。如果對于同一實例，蒙特卡羅算法不會給出2個不同的正確解答，則稱該蒙特卡羅算法是一致的。t(x) p(x)s(x) (1 p(x)(e(x) t(x)t ( x ) s ( x )1P ( X)e ( x )p ( x )線性規劃基本定理：如果線性規劃問題有最優解，則必有一基本可行最優解。單純形算法的特點是：(1 )只對約束條件的若干組合進行測試，測試的每一步都使目標函數的值增加；(2 )一般經

4、過不大于 m或n次迭代就可求得最優解。單純形算法的基本思想就是從一個基本可行解出發，進行一系列的基本可行解的變換。每次變換將一個非基本變量與一個基本變量互調位置，且保持當前的線性規劃問題是一個與原問題完全等價的標準線性規劃問題。圖靈機由以下幾部分組成：一條無限長的帶（有無窮個格子）、一個讀寫頭、一個有限狀態控制器以及一個程序。NPC形式化定義：定義1 :語言L是NP完全的當且僅當（1） L【NP ; （2 ）對于所有L'【NP有L'pL。 如果有一個語言L滿足上述性質（2）,但不一定滿足性質（1），則稱該語言是 NP難的。 所有NP完全語言構成的語言類稱為NP完全語言類，就是

5、NPC。定理1設L是NP完全的，則（1） L P當且僅當P= NP ; （2）若L p L1，且L1 NP，貝U L1是NP完全的。團問題：任給圖G和整數k.試判定圖G中是否存在具有k個頂點的團？1）團問題 NP。顯然，驗證 G的一個子圖是否成團只需多項式時間即可。2）SAT 團問題。任給表達式f .構造一個相應的圖 G如下： 圖G的每個頂點對應于f中的每個文字（多次出現的重復計算）。 若G中兩個頂點其原對應的文字不相互補且不出現于同一于句中，則將其連線。設f有n個子句，則f可滿足當且僅當f對應的圖G中有n個頂點的團。這是因為：(a) 若f可滿足，即有某種賦值使得f取值為真，它等價于使得每個c

6、i中都至少有一個文字為真，這n個文字(每個ci(1 v i<n)中一個)對應的圖G中的n個頂點就構成一個團。(b) 若圖G中有一 n個頂點的團，則取給出使得這n個頂點對應的文字都為真的賦值，則f的取值為真(這由圖G的定義易證)。X顯見，上述構造圖 G的方法是多項式界的，因此SAT團問題。由(a)、(b)有，團問題 NPC。證畢。單源最短路徑問題：void shortestpaths(v)MinHeap H1000;/定義最小堆Mi nHeap Node<type> E;E.i=v;E.le ngth=0;Distv=0;/搜索問題界空間while(true)for(j=1;j

7、<=n;j+)if(cE.i j<inf)&&(E.length+cE.ij<dist j)distj=E.le ngth+cE.i j;prevj=E.i;加入活結點優先隊列MinH eapNode <type> N;N.i=j;N.le ngth=distj;H.I nsert(N);/取下一個擴展結點try H.DeleteMi n( E); /優先隊列為空catch (OutOfBounds) break;(1) 數值隨機化算法：求解數值問題，得到近似解(2) Monte Carlo算法：問題準確性，但卻無法確定解正確性(3) Las Ve

8、gas算法：獲得正確解 但存在找不到解的可能性(4) Sherwood算法：保證能獲得正確解旅行售貨員問題:(優先隊列式分支限界法)Type Travd ing (int v) Min HeapNode H(1000)；TypeMin outN+1；/計算Minouti= 頂點i的最小出邊費用Type Minsurn=0 ； /最小出邊費用和 for (i=1;i v= n ； i+ ) Min=NoEdge ;for ( j=1 ; j<= n; j+ )if (aij!=NoEdge&&(ai j<Min|Mi n=NoEdge)Min=ai j;if(Min=

9、NoEdge)retur n(N oEdge);/無回路Mi nOuti=:Min;Mi nSum+=Min ;/初始化MinH eapNode E;for (i= 0 ; i < n ; i+ )E.x : i: = i+ 1 ;E.s=0 ;E.cc=0 ;E.rcost=Mi nSum ;Bestc=NoEdge ;while ( E.s< n-1) / 非葉結點if ( E.s<n-1 ) /當前擴展結點是葉結點的 父結點if ( aE.xn-2E.xn-1!=NoEdge& &aE.xn-21!=NoEdge&&( E.cc+aE.x

10、 n-2E.x n-1+aE.x n-11<bestc | bestc=NoEdge ) /費用更小的回路bestc=Ecc+aE.x n-2E.x n-1+aE.x n-11;E.c= bestc ;E.l cost=bestc ;E.s+ ;Insert (H,E); else delete(E.x) ； / 舍棄擴展結點else /產生當前擴展結點的兒子結點for ( i = E.s+1 ; i v n ; i+ =if (aE.xE.sE.xi!=NoEdge ) /可行兒子結點Type cc = E.cc+aE.xE.sE.xi;Typercost=E.rcost-Mi nOu

11、tE.xE.s;Type b=cc+rcost ;/ 下界if (b v bestc|bestc= NoEdge ) /子樹可能含最優解for (j= 0 ; j v n ;j+)N.xj=E.xj;N.xE.s+1=E.xi;N.xi=E.xE.s+1;N.cc=cc ;N.s= E.s+1;N.l cost=b ;N.rcost = rcost ;Insert ( H,N );delete(H,E.x);完成結點擴展DeleteMin(H,E) ; / 取下一擴展結點if (堆已空)break ;/堆已空if (bestc=NoEdge ) return( NoEdge)/無回路/將最優解

12、復制到vl : nfor (i=0 ; i v n ; i+)vi+ 1=E.xi;while (true) /釋放最小堆中所有結點delete(H, E. x);DeleteMin(H,E) ; / 取下一擴展結點if (堆已空)break ；/堆已空return(bestc) ;void Flowshop:Backtrack(i nt i)if (i > n) for (int j = 1; j <= n; j+)bestxj = xj;bestf = f;elsefor (int j = i; j <= n; j+) f1+=Mxj1;f2i=(f2i-1>f1)

13、?f2i-1:f1)+Mxj2;回溯算法解0-1背包問題(解空間：子集樹):template<class Typew, class Typep>Typep Kn ap<Typew, Typep>:Bo un d(i nti)/計算上界Typew cleft = c - cw; / 剩余容量回溯算法解批處理作業調度(解空間：排列 樹):f+=f2i;if (f < bestf) Swap(xi, x j);Backtrack(i+1);Swap(xi, x j);f1- =Mxj1;f- =f2i;所以在最壞的情況下，整個算法的計算時間復雜性為0(n!)Typep

14、b = cp;/以物品單位重量價值遞減序裝入物品while (i <= n && wi <= cleft) cleft -= wi;b += pi; cw+=wi ;cp+=pi;i+；backtrack(i+1);cw-=wi ;cp-=pi;/裝滿背包if ( boun d(i+1)>bestp )if (i <= n) b += pi/wi * cleft;backtrack(i+1); /xi=0return b;由于上界函數 Bound()需要0(n)的時間，void backtrack(i)在最壞的情況下有0(2n)個右兒子結點需 if( i

15、>n )要計算上界函數，所以0-1背包問題的回溯 bestp=cp;算法Backtrack()所需要的時間是0(n2n)。return; if(cw+wi<=c)/xi=1回溯算法解圖的m著色問題：void Color:Backtrack(i nt t)elsefor (in t i=1;i<=m;i+) if (t> n) xt=i;sum+;if (Ok(t) Backtrack(t+1);for (int i=1; i<=n; i+)cout << xi << ''cout << en dl;bool Co

16、lor:Ok(i nt k)/檢查顏色可用性for (int j=1;j<=n ;j+)if(akj=1) &&(xj=xk)return false;回溯算法解最大團問題(解空間：子集樹)void Clique:Backtrack(i nt i)/計算最大團if (i > n) / 到達葉結點for (int j = 1; j <= n; j+) bestxj=x j;best n = cn;return;/檢查頂點i與當前團的連接int OK = 1;for (int j = 1; j < i; j+)if (xj && aij =

17、0) / i與j不相連return true;回溯法總的時間耗費是O(mM *n)OK = 0; break;if (OK) / 進入左子樹xi = 1; cn+;Backtrack(i+1);xi = 0; cn-;if (cn + n - i > best n) /進入右子樹xi = 0;Backtrack(i+1);解最大團問題的回溯算法Backtrack所需的計算時間為O(n2n)。回溯法的基本思想是： 不斷用修改過的判定函數 Pi只（x1,x2,xi）（亦稱為限界函數）去測試 正在構造中的 n元組的部分向量（x1,x2，,xn）.看其是否可能導致最優解。如果判定 （x1 , x

18、2，xn）不可能導致最優解，那么就不再測試可能要測試的mi+1mi+2.mn 個向量。解符號三角形問題的回溯算法Backtrack所需的計算時間為 0(n2n)。貪心法解最優裝載問題：template<class Typevoid Loadi ng(i nt x.Type w. Type c, int n)int *t = new int n+1;Sort(w, t, n);for (i nt i = 1; i <= n; i+) xi = 0;for (int i = 1; i <= n && wti <= c; i+) xti = 1; c -= w

19、ti;算法所需的計算時間為O( nlogn)(1)輸算法是指解決問題的一種方法或一個過程。算法是若干指令的有窮序列，滿足性質：入 輸出 確定性(4)有限性：問題的計算時間下界為'十)，則計算時間復雜性為O(f(n)的算法是最優算法。1. 什么是動態規劃法：將問題分解成多級或許多子問題，然后順序求解子問題，前一個子 問題的解為后一個子問題的求解提供有用的信息。2. 什么是貪心法：從問題某一初始或推測值出發，一步步的攀登給定目標，盡可能快的去 逼近更好的解，當達到某一步不能繼續時終止。3什么是分支定界法：對有約束條件的最優化問題所有可行解定向、適當地進行搜索。將 可行解空間不斷地劃分為越來

20、越小的子集（分支），并為每一個子集的解計算一個上界和下界（定界）。5、什么是NP類問題：NP=L|L是一個能在多項式時間內被一臺NDTM圖靈機所接受的語言，其中NDTM是非確定性圖靈機。或者可說：NP是所有可在多項式時間內用不確定的算法求解的判定問題的集合。對于NP類，相當于要求驗證模塊在多項式時間內完成對應NDTM，有非確定性算法。1. 算法的分類：1）（數值算法）2）非數值算法2. 算法的描述：1）自然語言描述 2）（流程圖描述）3 ）程序語言描述3. 算法的分析標準：1）時空觀念2）（發展觀念）3）設計觀點4）交流的觀點 設計動態規劃算法的步驟。（1）找出最優解的性質，并刻劃其結構特征。

21、（2）遞歸地定義最優值。（3）以自底向上的方式計算出最優值。（4）根據計算最優值時得到的信息，構造最優解。動態規劃法求矩陣連乘問題：void MatrixChain（int *p，int n，int *m ，int *s）for (int i = 1; i <= n; i+) mii = 0;for (int r = 2; r <= n; r+)for (int i = 1; i <= n - r+1; i+) int j=i+r-1;mi j = mi+1j+ pi-1*pi*pj;si j = i;for (int k = i+1; k < j; k+) int t

22、 = mik + mk+1 j + pi-1*pk*pj;if (t < mij) mi j = t; si j = k;因此算法的計算時間上界為0(n3)。算法所占用的空間顯然為0(n2)。1簡述算法的五個重要的特征。：有窮性：一個算法必須保證執行有限步之后結束；確切性：算法的每一步驟必須有確切的定義；輸入：一個算法有0個或多個輸入，以刻畫運算對象的初始情況，所謂0個輸入是指算法本身定義了初始條件；輸出：一個算法有一個或多個輸出，以反映對輸入數據加工后的結果。沒有輸出的算法是毫無意義的；可行性：算法原則上能夠精確地運行，而且人們用筆和紙做有限次運算后即可完成。備注：算法可以沒有輸入。因

23、為有些算法中包含了輸入，如隨機產生輸入。2簡答貪心算法的基本元素：貪心選擇性質：所謂貪心選擇性質指所求問題的整體最優解可以通過一系列局部最優的選擇達到。最優子結構性質：當一個問題的最優解包含其子問題的最優解時，稱此問題具有最優子結構。3. 簡述動態規劃算法的基本思想和基本步驟以及動態規劃問題的特征。動態規劃的實質是分治思想和解決冗余，因此，動態規劃是一種將問題實例分解為更小的、相似的子問題，并存儲子問題的解而避免計算重復的子問題，以解決最優化問題的算法策略。按以下幾個步驟進行： 分析最優解的性質，并刻劃其結構特征。 遞歸地定義最優值。 以自底向上的方式或自頂向下的記憶化方法（備忘錄法）計算出最

24、優值。 根據計算最優值時得到的信息，構造一個最優解。動態規劃問題的特征：動態規劃算法的有效性依賴于問題本身所具有的兩個重要性質：最優子結構性質和子問題重疊性質。1、最優子結構：當問題的最優解包含了其子問題的最優解時，稱該問題具有最優子結構性質。2、重疊子問題：在用遞歸算法自頂向下解問題時，每次產生的子問題并不總是新問題，有些子問題被反復計算多次。動態規劃算法正是利用了這種子問題的重疊性質，對每一個子問題只解一次，而后將其解保存在一個表格中，在以后盡可能多地利用這些子問題的解。4簡述回溯算法的基本思想及解題步驟。回溯法的基本思想：確定了解空間的組織結構后，回溯法就從開始結點（根結點）出發，以深度

25、優先的方式搜索整個解空間。這個開始結點就成為一個活結點，同時也成為當前的擴展結點。在當前的擴展結點處， 搜索向縱深方向移至一個新結點。這個新結點就成為一個新的活結點，并成為當前擴展結點。如果在當前的擴展結點處不能再向縱深方向移動，則當前擴展結點就成為死結點。換句話說，這個結點不再是一個活結點。此時，應往回移動（回溯） 至最近的一個活結點處，并使這個活結點成為當前的擴展結點。回溯法即以這種工作方式遞歸地在解空間中搜索，直至找到所要求的解或解空間中已沒有活結點時為止。（9分）運用回溯法解題通常包含以下三個步驟：（1 ）針對所給問題，定義問題的解空間；（2分）（2） 確定易于搜索的解空間結構；（2分

26、）（3）以深度優先的方式搜索解空間，并且在搜索過程中用剪枝函數避免無效搜索。5. 簡述分治算法的基本思想及基本步驟。分治法的基本思想：對于一個輸入規模為n的問題，若該問題容易的解決，則直接解決，否則將其分解為k個規模較小的子問題， 這些子問題相互獨立且與原問題形式相同，遞歸求解這些子問題，然后將各個子問題的解合并，得到原問題的解。（9分）分治法在每一層遞歸上由以下三個步驟組成： 劃分：將原問題分解為若干規模較小、相互獨立、與原問題形式相同的子問題；（2分） 解決：若子問題規模較小，則直接解決；否則遞歸求解各個子問題。（2分） 合并：將各個子問題的解合并為原問題的解。（2分）6. 分支限界法的基本思想：分支限界法常以廣度優先或以最小耗費（最大效益）優先的方式搜索問題的解空間樹。問題的解空間樹是表示問題解空間的一棵有序樹，常見的有排列樹。在搜索問題的解空間樹時， 分支限界法與回溯法對當前擴展結點所使用的擴展方式不同。在分支限界法中，每一個活結點只有一次機會成為擴展結點。活結點一旦成為擴展結點，就一次性產生其所有兒子結點。在這些兒子結點中，那些導致不可行解或導致非最優解的兒子結點被舍棄，其余兒子結點被子加入活結點表中。此后，從活結點表中取下一結點成為當前擴展結點，并重復上述結點擴展過程。這個過程一直持續到找到所求的解