遞歸算法的優(yōu)缺點

1、遞歸算法的優(yōu)缺點：優(yōu)點：結(jié)構(gòu)清晰，可讀性強，而且容易用數(shù)學(xué)歸納法來證明算法的正確性，因此它為設(shè)計算法、調(diào)試程序帶來很大方便。缺點：遞歸算法的運行效率較低，無論是耗費的計算時間還是占用的存儲空間都比非遞歸算法要多。邊界條件與遞歸方程是遞歸函數(shù)的二個要素應(yīng)用分治法的兩個前提是問題的可分性和解的可歸并性以比較為基礎(chǔ)的排序算法的最壞倩況時間復(fù)雜性下界為0(n·log2n)?；厮莘ㄒ陨疃葍?yōu)先的方式搜索解空間樹T，而分支限界法則以廣度優(yōu)先或以最小耗費優(yōu)先的方式搜索解空間樹T。舍伍德算法設(shè)計的基本思想:設(shè)A是一個確定性算法，當(dāng)它的輸入實例為x時所需的計算時間記為tA(x)。設(shè)Xn是算法A的輸入規(guī)模

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

3、t;p<1。如果一個蒙特卡羅算法對于問題的任一實例得到正確解的概率不小于p，則稱該蒙特卡羅算法是p正確的，且稱p-1/2是該算法的優(yōu)勢。如果對于同一實例，蒙特卡羅算法不會給出2個不同的正確解答，則稱該蒙特卡羅算法是一致的。線性規(guī)劃基本定理：如果線性規(guī)劃問題有最優(yōu)解，則必有一基本可行最優(yōu)解。單純形算法的特點是：（1）只對約束條件的若干組合進行測試，測試的每一步都使目標(biāo)函數(shù)的值增加；（2）一般經(jīng)過不大于m或n次迭代就可求得最優(yōu)解。單純形算法的基本思想就是從一個基本可行解出發(fā)，進行一系列的基本可行解的變換。每次變換將一個非基本變量與一個基本變量互調(diào)位置，且保持當(dāng)前的線性規(guī)劃問題是一個與原問題完

4、全等價的標(biāo)準(zhǔn)線性規(guī)劃問題。圖靈機由以下幾部分組成：一條無限長的帶（有無窮個格子）、一個讀寫頭、一個有限狀態(tài)控制器以及一個程序。NPC形式化定義：定義1：語言L是NP完全的當(dāng)且僅當(dāng)（1） L【NP；（2）對于所有L【NP有L pL。 如果有一個語言L滿足上述性質(zhì)(2),但不一定滿足性質(zhì)（1），則稱該語言是NP難的。所有NP完全語言構(gòu)成的語言類稱為NP完全語言類，就是NPC。定理1 設(shè)L是NP完全的，則（1）LÎP當(dāng)且僅當(dāng)PNP；（2）若 L µp L1，且 L1Î NP，則L1是NP完全的。團問題: 任給圖G和整數(shù)k試判定圖G中是否存在具有k個頂點的團？ 1)團問題

5、ÎNP。顯然，驗證G的一個子圖是否成團只需多項式時間即可。 2)SATµ團問題。 任給表達式f構(gòu)造一個相應(yīng)的圖G如下：圖G的每個頂點對應(yīng)于f中的每個文字(多次出現(xiàn)的重復(fù)計算)。若G中兩個頂點其原對應(yīng)的文字不相互補且不出現(xiàn)于同一于句中，則將其連線。 設(shè)f有n個子句，則f可滿足當(dāng)且僅當(dāng)f對應(yīng)的圖G中有n個頂點的團。 這是因為：(a) 若f可滿足，即有某種賦值使得f取值為真，它等價于使得每個ci中都至少有一個文字為真，這n個文字(每個ci(1i<n)中一個)對應(yīng)的圖G中的n個頂點就構(gòu)成一個團。(b)若圖G中有一n個頂點的團，則取給出使得這n個頂點對應(yīng)的文字都為真的賦值，則f

6、的取值為真(這由圖G的定義易證)。顯見，上述構(gòu)造圖G的方法是多項式界的，因此SAT 團問題。由(a)、(b)有，團問題ÎNPC。證畢。單源最短路徑問題:void shortestpaths(v) MinHeap H1000; /定義最小堆MinHeapNode<type> E;E.i=v;E.length=0;Distv=0;/搜索問題界空間while(true) for(j=1;j<=n;j+)if(cE.ij<inf)&& (E.length+cE.ij<distj) distj=E.length+cE.ij; prevj=E.i;

7、/加入活結(jié)點優(yōu)先隊列 MinHeapNode <type> N;N.i=j; N.length=distj; H.Insert(N); /取下一個擴展結(jié)點 try H.DeleteMin(E); /優(yōu)先隊列為空 catch (OutOfBounds) break;(1)數(shù)值隨機化算法: ß求解數(shù)值問題,得到近似解(2)Monte Carlo算法:ß 問題準(zhǔn)確性,但卻無法確定解正確性(3)Las Vegas算法:ß獲得正確解,但存在找不到解的可能性(4)Sherwood算法:ß保證能獲得正確解旅行售貨員問題:(優(yōu)先隊列式分支限界法) Type

8、Travding (int v) MinHeapNode H(1000)； Type MinoutN+1； /計算 Minouti=頂點 i的最小出邊費用 Type Minsurn=0；/最小出邊費用和for（i=1;in；i+） Min=NoEdge； for（ j=1；jn；j+） if（aij!=NoEdge(aij<Min | Min=NoEdge) Min=aij； if（Min=NoEdge） return(NoEdge)； /無回路 MinOuti= Min； MinSum+=Min； /初始化 MinHeapNode E； for（i= 0；i n；i+） E.xi= i

9、+ 1； E.s=0； E.cc=0； E.rcost=MinSum； Bestc=NoEdge； while（E.sn-1) /非葉結(jié)點if（E.s<n-1） /當(dāng)前擴展結(jié)點是葉結(jié)點的父結(jié)點 if（aE.xn-2E.xn-1!=NoEdge aE.xn-21!=NoEdge&&（E.cc+aE.xn-2E.xn-1+aE.xn-11<bestc | bestc=NoEdge） /費用更小的回路 bestc=Ecc+aE.xn-2E.xn-1 +aE.xn-11； E.cbestc； E.lcost=bestc； E.s+； Insert（H,E）； else de

10、lete(E.x) ； /舍棄擴展結(jié)點 else /產(chǎn)生當(dāng)前擴展結(jié)點的兒子結(jié)點 for（ iE.s+1；in；i+ if（aE.xE.sE.xi!=NoEdge） /可行兒子結(jié)點 Type ccE.cc+aE.xE.sE.xi； Type rcost=E.rcost-MinOutE.xE.s； Type b=cc+rcost； /下界if（b bestc|bestc= NoEdge ) /子樹可能含最優(yōu)解 for（j= 0； j 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.lcost=b； N.rc

11、ostrcost； Insert（H,N）； delete(H,E.x)；/完成結(jié)點擴展DeleteMin(H,E)； /取下一擴展結(jié)點 if (堆已空) break； /堆已空 if（bestc=NoEdge）return( NoEdge)； /無回路/將最優(yōu)解復(fù)制到vl：nfor（i=0；in；i+) vi+ 1=E.xi；while (true) /釋放最小堆中所有結(jié)點 delete(H, E. x)； DeleteMin(H,E)； /取下一擴展結(jié)點 if (堆已空) break； /堆已空 return(bestc)；回溯算法解批處理作業(yè)調(diào)度(解空間：排列樹):void Flowsh

12、op:Backtrack(int i) if (i > n) for (int j = 1; j <= n; j+) bestxj = xj; bestf = f; else for (int j = i; j <= n; j+) f1+=Mxj1; f2i=(f2i-1>f1)?f2i-1:f1)+Mxj2; f+=f2i; if (f < bestf) Swap(xi, xj); Backtrack(i+1); Swap(xi, xj); f1- =Mxj1; f- =f2i; 所以在最壞的情況下，整個算法的計算時間復(fù)雜性為O(n!)回溯算法解0-1背包問題(

13、解空間：子集樹):template<class Typew, class Typep>Typep Knap<Typew, Typep>:Bound(int i)/ 計算上界 Typew cleft = c - cw; / 剩余容量 Typep b = cp; / 以物品單位重量價值遞減序裝入物品 while (i <= n && wi <= cleft) cleft -= wi; b += pi; i+; / 裝滿背包 if (i <= n) b += pi/wi * cleft; return b;void backtrack(i)

14、if( i>n ) bestp=cp; return; if(cw+wi<=c)/xi=1 cw+=wi ;cp+=pi; backtrack(i+1); cw-=wi ;cp-=pi; if ( bound(i+1)>bestp ) backtrack(i+1); /xi=0由于上界函數(shù)Bound()需要O(n)的時間，在最壞的情況下有O(2n)個右兒子結(jié)點需要計算上界函數(shù)，所以0-1背包問題的回溯算法Backtrack()所需要的時間是O(n2n)?；厮菟惴ń鈭D的m著色問題:void Color:Backtrack(int t) if (t>n) sum+; for

15、 (int i=1; i<=n; i+) cout << xi << ' ' cout << endl; else for (int i=1;i<=m;i+) xt=i; if (Ok(t) Backtrack(t+1); bool Color:Ok(int k)/ 檢查顏色可用性 for (int j=1;j<=n;j+) if (akj=1)&&(xj=xk) return false; return true;回溯法總的時間耗費是O(mn *n)回溯算法解最大團問題（解空間：子集樹）：void Cliq

16、ue:Backtrack(int i)/ 計算最大團 if (i > n) / 到達葉結(jié)點 for (int j = 1; j <= n; j+) bestxj = xj; bestn = cn; return; / 檢查頂點 i 與當(dāng)前團的連接 int OK = 1; for (int j = 1; j < i; j+) if (xj && aij = 0) / i與j不相連 OK = 0; break; if (OK) / 進入左子樹 xi = 1; cn+; Backtrack(i+1); xi = 0; cn-; if (cn + n - i >

17、 bestn) / 進入右子樹 xi = 0; Backtrack(i+1);解最大團問題的回溯算法Backtrack所需的計算時間為O(n2n)。 回溯法的基本思想是：不斷用修改過的判定函數(shù)Pi只(x1,x2,xi)(亦稱為限界函數(shù))去測試正在構(gòu)造中的n元組的部分向量(x1,x2,xn)看其是否可能導(dǎo)致最優(yōu)解。如果判定(x1，x2，xn)不可能導(dǎo)致最優(yōu)解，那么就不再測試可能要測試的mi+1mi+2.mn個向量。解符號三角形問題的回溯算法Backtrack所需的計算時間為O(n2n)。  貪心法解最優(yōu)裝載問題：template<class Type>void Loadin

18、g(int x, Type w, Type c, int n) int *t = new int n+1; Sort(w, t, n); for (int i = 1; i <= n; i+) xi = 0; for (int i = 1; i <= n && wti <= c; i+) xti = 1; c -= wti;算法所需的計算時間為 O(nlogn)算法是指解決問題的一種方法或一個過程。算法是若干指令的有窮序列，滿足性質(zhì)：(1)輸入 (2)輸出 (3)確定性 (4)有限性：問題的計算時間下界為W(f(n)，則計算時間復(fù)雜性為O(f(n)的算法是最優(yōu)

19、算法。1. 什么是動態(tài)規(guī)劃法：將問題分解成多級或許多子問題，然后順序求解子問題，前一個子問題的解為后一個子問題的求解提供有用的信息。2. 什么是貪心法：從問題某一初始或推測值出發(fā)，一步步的攀登給定目標(biāo)，盡可能快的去逼近更好的解，當(dāng)達到某一步不能繼續(xù)時終止。3. 什么是分支定界法：對有約束條件的最優(yōu)化問題所有可行解定向、適當(dāng)?shù)剡M行搜索。將可行解空間不斷地劃分為越來越小的子集（分支），并為每一個子集的解計算一個上界和下界（定界）。5、什么是NP類問題：NP=L|L是一個能在多項式時間內(nèi)被一臺NDTM圖靈機所接受的語言，其中NDTM是非確定性圖靈機?；蛘呖烧f：NP是所有可在多項式時間內(nèi)用不確定的算法

20、求解的判定問題的集合。對于NP類，相當(dāng)于要求驗證模塊在多項式時間內(nèi)完成對應(yīng)NDTM，有非確定性算法。1. 算法的分類：1）(數(shù)值算法 ) 2） 非數(shù)值算法2. 算法的描述：1）自然語言描述 2）(流程圖描述) 3）程序語言描述3. 算法的分析標(biāo)準(zhǔn)：1） 時空觀念 2 ）(發(fā)展觀念) 3） 設(shè)計觀點 4） 交流的觀點設(shè)計動態(tài)規(guī)劃算法的步驟。(1)找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。(2)遞歸地定義最優(yōu)值。(3)以自底向上的方式計算出最優(yōu)值。(4)根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解。動態(tài)規(guī)劃法求矩陣連乘問題：void MatrixChain(int *p，int n，int *m，int *s

21、)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; mij = mi+1j+ pi-1*pi*pj; sij = i; for (int k = i+1; k < j; k+) int t = mik + mk+1j + pi-1*pk*pj; if (t < mij) mij = t; sij = k; 因此算法的計算時間上界為O(n3)。算法所占用的空間顯然為O(n2)。1. 簡述算法的五

22、個重要的特征。：有窮性： 一個算法必須保證執(zhí)行有限步之后結(jié)束；確切性： 算法的每一步驟必須有確切的定義； 輸入：一個算法有0個或多個輸入，以刻畫運算對象的初始情況，所謂0個輸入是指算法本身定義了初始條件；輸出：一個算法有一個或多個輸出，以反映對輸入數(shù)據(jù)加工后的結(jié)果。沒有輸出的算法是毫無意義的；可行性： 算法原則上能夠精確地運行，而且人們用筆和紙做有限次運算后即可完成。備注： 算法可以沒有輸入。因為有些算法中包含了輸入，如隨機產(chǎn)生輸入。2. 簡答貪心算法的基本元素：貪心選擇性質(zhì)：所謂貪心選擇性質(zhì)指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇達到。最優(yōu)子結(jié)構(gòu)性質(zhì)：當(dāng)一個問題的最優(yōu)解包含其子問題

23、的最優(yōu)解時，稱此問題具有最優(yōu)子結(jié)構(gòu)。3.簡述動態(tài)規(guī)劃算法的基本思想和基本步驟以及動態(tài)規(guī)劃問題的特征。動態(tài)規(guī)劃的實質(zhì)是分治思想和解決冗余，因此，動態(tài)規(guī)劃是一種將問題實例分解為更小的、相似的子問題，并存儲子問題的解而避免計算重復(fù)的子問題，以解決最優(yōu)化問題的算法策略。按以下幾個步驟進行：分析最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。 遞歸地定義最優(yōu)值。 以自底向上的方式或自頂向下的記憶化方法（備忘錄法）計算出最優(yōu)值。 根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造一個最優(yōu)解。動態(tài)規(guī)劃問題的特征：動態(tài)規(guī)劃算法的有效性依賴于問題本身所具有的兩個重要性質(zhì)：最優(yōu)子結(jié)構(gòu)性質(zhì)和子問題重疊性質(zhì)。1、最優(yōu)子結(jié)構(gòu)：當(dāng)問題的最優(yōu)解包含了其子問

24、題的最優(yōu)解時，稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。2、重疊子問題：在用遞歸算法自頂向下解問題時，每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復(fù)計算多次。動態(tài)規(guī)劃算法正是利用了這種子問題的重疊性質(zhì)，對每一個子問題只解一次，而后將其解保存在一個表格中，在以后盡可能多地利用這些子問題的解。4. 簡述回溯算法的基本思想及解題步驟。回溯法的基本思想：確定了解空間的組織結(jié)構(gòu)后，回溯法就從開始結(jié)點（根結(jié)點）出發(fā)，以深度優(yōu)先的方式搜索整個解空間。這個開始結(jié)點就成為一個活結(jié)點，同時也成為當(dāng)前的擴展結(jié)點。在當(dāng)前的擴展結(jié)點處，搜索向縱深方向移至一個新結(jié)點。這個新結(jié)點就成為一個新的活結(jié)點，并成為當(dāng)前擴展結(jié)點。如果在當(dāng)前的擴

25、展結(jié)點處不能再向縱深方向移動，則當(dāng)前擴展結(jié)點就成為死結(jié)點。換句話說，這個結(jié)點不再是一個活結(jié)點。此時，應(yīng)往回移動（回溯）至最近的一個活結(jié)點處，并使這個活結(jié)點成為當(dāng)前的擴展結(jié)點?；厮莘匆赃@種工作方式遞歸地在解空間中搜索，直至找到所要求的解或解空間中已沒有活結(jié)點時為止。（9分）運用回溯法解題通常包含以下三個步驟：（1）針對所給問題，定義問題的解空間；（2分）（2）確定易于搜索的解空間結(jié)構(gòu)；（2分） （3）以深度優(yōu)先的方式搜索解空間，并且在搜索過程中用剪枝函數(shù)避免無效搜索。5.簡述分治算法的基本思想及基本步驟。分治法的基本思想：對于一個輸入規(guī)模為的問題，若該問題容易的解決，則直接解決，否則將其分解為

26、個規(guī)模較小的子問題，這些子問題相互獨立且與原問題形式相同，遞歸求解這些子問題，然后將各個子問題的解合并，得到原問題的解。（9分）分治法在每一層遞歸上由以下三個步驟組成：劃分：將原問題分解為若干規(guī)模較小、相互獨立、與原問題形式相同的子問題；（2分）解決：若子問題規(guī)模較小，則直接解決；否則遞歸求解各個子問題。（2分）合并：將各個子問題的解合并為原問題的解。（2分）6.分支限界法的基本思想：分支限界法常以廣度優(yōu)先或以最小耗費（最大效益）優(yōu)先的方式搜索問題的解空間樹。問題的解空間樹是表示問題解空間的一棵有序樹，常見的有排列樹。在搜索問題的解空間樹時，分支限界法與回溯法對當(dāng)前擴展結(jié)點所使用的擴展方式不同。在分支限界法中，每一個活結(jié)點只有一次機會成為擴展結(jié)點?；罱Y(jié)點一旦成為擴展結(jié)點，就一次性產(chǎn)生其所有兒子結(jié)點。在這些兒子結(jié)點中，那些導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點被舍棄，其余兒子結(jié)點被子加入活結(jié)點表中。此后，從活結(jié)點表中取下一結(jié)點成為當(dāng)前擴展結(jié)點，并重復(fù)上述結(jié)點擴展過程。這個過程一直