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

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

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

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

4、靈機(jī)由以下幾部分組成：一條無(wú)限長(zhǎng)的帶（有無(wú)窮個(gè)格子）、一個(gè)讀寫(xiě)頭、一個(gè)有限狀態(tài)把握器以及一個(gè)程序。NPC形式化定義：定義1：語(yǔ)言L是NP完全的當(dāng)且僅當(dāng)（1） L【NP；（2）對(duì)于全部L【NP有L pL。 假如有一個(gè)語(yǔ)言L滿足上述性質(zhì)(2),但不肯定滿足性質(zhì)（1），則稱(chēng)該語(yǔ)言是NP難的。全部NP完全語(yǔ)言構(gòu)成的語(yǔ)言類(lèi)稱(chēng)為NP完全語(yǔ)言類(lèi)，就是NPC。定理1 設(shè)L是NP完全的，則（1）LP當(dāng)且僅當(dāng)PNP；（2）若 L p L1，且 L1 NP，則L1是NP完全的。團(tuán)問(wèn)題: 任給圖G和整數(shù)k試判定圖G中是否存在具有k個(gè)頂點(diǎn)的團(tuán)？ 1)團(tuán)問(wèn)題NP。明顯，驗(yàn)證G的一個(gè)子圖是否成團(tuán)只需多項(xiàng)式時(shí)間即可。 2)S

5、AT團(tuán)問(wèn)題。 任給表達(dá)式f構(gòu)造一個(gè)相應(yīng)的圖G如下：圖G的每個(gè)頂點(diǎn)對(duì)應(yīng)于f中的每個(gè)文字(多次消滅的重復(fù)計(jì)算)。若G中兩個(gè)頂點(diǎn)其原對(duì)應(yīng)的文字不相互補(bǔ)且不消滅于同一于句中，則將其連線。 設(shè)f有n個(gè)子句，則f可滿足當(dāng)且僅當(dāng)f對(duì)應(yīng)的圖G中有n個(gè)頂點(diǎn)的團(tuán)。 這是由于：(a) 若f可滿足，即有某種賦值使得f取值為真，它等價(jià)于使得每個(gè)ci中都至少有一個(gè)文字為真，這n個(gè)文字(每個(gè)ci(1in)中一個(gè))對(duì)應(yīng)的圖G中的n個(gè)頂點(diǎn)就構(gòu)成一個(gè)團(tuán)。(b)若圖G中有一n個(gè)頂點(diǎn)的團(tuán)，則取給出訪得這n個(gè)頂點(diǎn)對(duì)應(yīng)的文字都為真的賦值，則f的取值為真(這由圖G的定義易證)。顯見(jiàn)，上述構(gòu)造圖G的方法是多項(xiàng)式界的，因此SAT 團(tuán)問(wèn)題。由(

6、a)、(b)有，團(tuán)問(wèn)題NPC。證畢。單源最短路徑問(wèn)題:void shortestpaths(v) MinHeap H1000; /定義最小堆MinHeapNode E;E.i=v;E.length=0;Distv=0;/搜尋問(wèn)題界空間while(true) for(j=1;j=n;j+)if(cE.ijinf)& (E.length+cE.ijdistj) distj=E.length+cE.ij; prevj=E.i; /加入活結(jié)點(diǎn)優(yōu)先隊(duì)列 MinHeapNode N;N.i=j; N.length=distj; H.Insert(N); /取下一個(gè)擴(kuò)展結(jié)點(diǎn) try H.DeleteMin(

7、E); /優(yōu)先隊(duì)列為空 catch (OutOfBounds) break;(1)數(shù)值隨機(jī)化算法: 求解數(shù)值問(wèn)題,得到近似解(2)Monte Carlo算法: 問(wèn)題精確性,但卻無(wú)法確定解正確性(3)Las Vegas算法:獲得正確解,但存在找不到解的可能性(4)Sherwood算法:保證能獲得正確解旅行售貨員問(wèn)題:(優(yōu)先隊(duì)列式分支限界法) Type 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=NoEd

8、ge； for（ j=1；jn；j+） if（aij!=NoEdge(aijMin | Min=NoEdge) Min=aij； if（Min=NoEdge） return(NoEdge)； /無(wú)回路 MinOuti= Min； MinSum+=Min； /初始化 MinHeapNode E； for（i= 0；i n；i+） E.xi= i+ 1； E.s=0； E.cc=0； E.rcost=MinSum； Bestc=NoEdge； while（E.sn-1) /非葉結(jié)點(diǎn)if（E.sn-1） /當(dāng)前擴(kuò)展結(jié)點(diǎn)是葉結(jié)點(diǎn)的父結(jié)點(diǎn) if（aE.xn-2E.xn-1!=NoEdge aE.xn-2

9、1!=NoEdge&（E.cc+aE.xn-2E.xn-1+aE.xn-11 n) for (int j = 1; j = n; j+) bestxj = xj; bestf = f; else for (int j = i; j 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í)間簡(jiǎn)單性為O(n!)回溯算法解0-1背包問(wèn)題(解空間：子集樹(shù)):templateTypep Knap:Bound(int

10、i)/ 計(jì)算上界 Typew cleft = c - cw; / 剩余容量 Typep b = cp; / 以物品單位重量?jī)r(jià)值遞減序裝入物品 while (i = n & wi = cleft) cleft -= wi; b += pi; i+; / 裝滿背包 if (i n ) bestp=cp; return; if(cw+wibestp ) backtrack(i+1); /xi=0由于上界函數(shù)Bound()需要O(n)的時(shí)間，在最壞的狀況下有O(2n)個(gè)右兒子結(jié)點(diǎn)需要計(jì)算上界函數(shù)，所以0-1背包問(wèn)題的回溯算法Backtrack()所需要的時(shí)間是O(n2n)。回溯算法解圖的m著色問(wèn)題:v

11、oid Color:Backtrack(int t) if (tn) sum+; for (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) / 到達(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 =

12、 1; j bestn) / 進(jìn)入右子樹(shù) xi = 0; Backtrack(i+1);解最大團(tuán)問(wèn)題的回溯算法Backtrack所需的計(jì)算時(shí)間為O(n2n)。 回溯法的基本思想是：不斷用修改過(guò)的判定函數(shù)Pi只(x1,x2,xi)(亦稱(chēng)為限界函數(shù))去測(cè)試正在構(gòu)造中的n元組的部分向量(x1,x2,xn)看其是否可能導(dǎo)致最優(yōu)解。假如判定(x1，x2，xn)不行能導(dǎo)致最優(yōu)解，那么就不再測(cè)試可能要測(cè)試的mi+1mi+2.mn個(gè)向量。解符號(hào)三角形問(wèn)題的回溯算法Backtrack所需的計(jì)算時(shí)間為O(n2n)。 貪心法解最優(yōu)裝載問(wèn)題：templatevoid Loading(int x, Type w, Ty

13、pe 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)算法是指解決問(wèn)題的一種方法或一個(gè)過(guò)程。算法是若干指令的有窮序列，滿足性質(zhì)：(1)輸入 (2)輸出 (3)確定性 (4)有限性：?jiǎn)栴}的計(jì)算時(shí)間下界為W(f(n)，則計(jì)算時(shí)間簡(jiǎn)單性為O(f(n)的算法是最優(yōu)算法。1. 什么是動(dòng)態(tài)規(guī)劃法：將問(wèn)題分解成多級(jí)或很多子問(wèn)題，然后挨次求解子問(wèn)題，

14、前一個(gè)子問(wèn)題的解為后一個(gè)子問(wèn)題的求解供應(yīng)有用的信息。2. 什么是貪心法：從問(wèn)題某一初始或推想值動(dòng)身，一步步的攀登給定目標(biāo)，盡可能快的去靠近更好的解，當(dāng)達(dá)到某一步不能連續(xù)時(shí)終止。3. 什么是分支定界法：對(duì)有約束條件的最優(yōu)化問(wèn)題全部可行解定向、適當(dāng)?shù)剡M(jìn)行搜尋。將可行解空間不斷地劃分為越來(lái)越小的子集（分支），并為每一個(gè)子集的解計(jì)算一個(gè)上界和下界（定界）。5、什么是NP類(lèi)問(wèn)題：NP=L|L是一個(gè)能在多項(xiàng)式時(shí)間內(nèi)被一臺(tái)NDTM圖靈機(jī)所接受的語(yǔ)言，其中NDTM是非確定性圖靈機(jī)。或者可說(shuō)：NP是全部可在多項(xiàng)式時(shí)間內(nèi)用不確定的算法求解的判定問(wèn)題的集合。對(duì)于NP類(lèi)，相當(dāng)于要求驗(yàn)證模塊在多項(xiàng)式時(shí)間內(nèi)完成對(duì)應(yīng)NDT

15、M，有非確定性算法。1. 算法的分類(lèi)：1）(數(shù)值算法 ) 2） 非數(shù)值算法2. 算法的描述：1）自然語(yǔ)言描述 2）(流程圖描述) 3）程序語(yǔ)言描述3. 算法的分析標(biāo)準(zhǔn)：1） 時(shí)空觀念 2 ）(進(jìn)展觀念) 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ī)劃法求矩陣連乘問(wèn)題：void MatrixChain(int *p，int n，int *m，int *s)for (int i = 1; i = n; i+) mii = 0; for (int r = 2;