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

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

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

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

4、全等價(jià)的標(biāo)準(zhǔn)線性規(guī)劃問題。圖靈機(jī)由以下幾部分組成：一條無限長的帶（有無窮個(gè)格子）、一個(gè)讀寫頭、一個(gè)有限狀態(tài)控制器以及一個(gè)程序。NPC形式化定義：定義1：語言L是NP完全的當(dāng)且僅當(dāng)（1） L【NP；（2）對于所有L【NP有L pL。 如果有一個(gè)語言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完全的。團(tuán)問題: 任給圖G和整數(shù)k試判定圖G中是否存在具有k個(gè)頂點(diǎn)的團(tuán)？ 1)團(tuán)問題

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

6、的取值為真(這由圖G的定義易證)。顯見，上述構(gòu)造圖G的方法是多項(xiàng)式界的，因此SAT 團(tuán)問題。由(a)、(b)有，團(tuán)問題Î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é)點(diǎn)優(yōu)先隊(duì)列 MinHeapNode <type> N;N.i=j; N.length=distj; H.Insert(N); /取下一個(gè)擴(kuò)展結(jié)點(diǎn) try H.DeleteMin(E); /優(yōu)先隊(duì)列為空 catch (OutOfBounds) break;(1)數(shù)值隨機(jī)化算法: ß求解數(shù)值問題,得到近似解(2)Monte Carlo算法:ß 問題準(zhǔn)確性,但卻無法確定解正確性(3)Las Vegas算法:ß獲得正確解,但存在找不到解的可能性(4)Sherwood算法:ß保證能獲得正確解旅行售貨員問題:(優(yōu)先隊(duì)列式分支限界法) Type

8、Travding (int v) MinHeapNode H(1000)； Type MinoutN+1； /計(jì)算 Minouti=頂點(diǎn) i的最小出邊費(fèi)用 Type Minsurn=0；/最小出邊費(fèi)用和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é)點(diǎn)if（E.s<n-1） /當(dāng)前擴(kuò)展結(jié)點(diǎn)是葉結(jié)點(diǎn)的父結(jié)點(diǎn) if（aE.xn-2E.xn-1!=NoEdge aE.xn-21!=NoEdge&&（E.cc+aE.xn-2E.xn-1+aE.xn-11<bestc | bestc=NoEdge） /費(fèi)用更小的回路 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) ； /舍棄擴(kuò)展結(jié)點(diǎn) else /產(chǎn)生當(dāng)前擴(kuò)展結(jié)點(diǎn)的兒子結(jié)點(diǎn) for（ iE.s+1；in；i+ if（aE.xE.sE.xi!=NoEdge） /可行兒子結(jié)點(diǎn) 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é)點(diǎn)擴(kuò)展DeleteMin(H,E)； /取下一擴(kuò)展結(jié)點(diǎn) if (堆已空) break； /堆已空 if（bestc=NoEdge）return( NoEdge)； /無回路/將最優(yōu)解復(fù)制到vl：nfor（i=0；in；i+) vi+ 1=E.xi；while (true) /釋放最小堆中所有結(jié)點(diǎn) delete(H, E. x)； DeleteMin(H,E)； /取下一擴(kuò)展結(jié)點(diǎn) 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; 所以在最壞的情況下，整個(gè)算法的計(jì)算時(shí)間復(fù)雜性為O(n!)回溯算法解0-1背包問題(

13、解空間：子集樹):template<class Typew, class Typep>Typep Knap<Typew, Typep>:Bound(int i)/ 計(jì)算上界 Typew cleft = c - cw; / 剩余容量 Typep b = cp; / 以物品單位重量價(jià)值遞減序裝入物品 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)的時(shí)間，在最壞的情況下有O(2n)個(gè)右兒子結(jié)點(diǎn)需要計(jì)算上界函數(shù)，所以0-1背包問題的回溯算法Backtrack()所需要的時(shí)間是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;回溯法總的時(shí)間耗費(fèi)是O(mn *n)回溯算法解最大團(tuán)問題（解空間：子集樹）：void Cliq

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

17、 bestn) / 進(jìn)入右子樹 xi = 0; Backtrack(i+1);解最大團(tuán)問題的回溯算法Backtrack所需的計(jì)算時(shí)間為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個(gè)向量。解符號三角形問題的回溯算法Backtrack所需的計(jì)算時(shí)間為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;算法所需的計(jì)算時(shí)間為 O(nlogn)算法是指解決問題的一種方法或一個(gè)過程。算法是若干指令的有窮序列，滿足性質(zhì)：(1)輸入 (2)輸出 (3)確定性 (4)有限性：問題的計(jì)算時(shí)間下界為W(f(n)，則計(jì)算時(shí)間復(fù)雜性為O(f(n)的算法是最優(yōu)

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

20、求解的判定問題的集合。對于NP類，相當(dāng)于要求驗(yàn)證模塊在多項(xiàng)式時(shí)間內(nèi)完成對應(yīng)NDTM，有非確定性算法。1. 算法的分類：1）(數(shù)值算法 ) 2） 非數(shù)值算法2. 算法的描述：1）自然語言描述 2）(流程圖描述) 3）程序語言描述3. 算法的分析標(biāo)準(zhǔn)：1） 時(shí)空觀念 2 ）(發(fā)展觀念) 3） 設(shè)計(jì)觀點(diǎn) 4） 交流的觀點(diǎn)設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法的步驟。(1)找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。(2)遞歸地定義最優(yōu)值。(3)以自底向上的方式計(jì)算出最優(yōu)值。(4)根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。動(dòng)態(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; 因此算法的計(jì)算時(shí)間上界為O(n3)。算法所占用的空間顯然為O(n2)。1. 簡述算法的五

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

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

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

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

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