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

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

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

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

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

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

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

7、E); /優(yōu)先隊列為空 catch (OutOfBounds) break;(1)數值隨機化算法: 求解數值問題,得到近似解(2)Monte Carlo算法: 問題精確性,但卻無法確定解正確性(3)Las Vegas算法:獲得正確解,但存在找不到解的可能性(4)Sherwood算法:保證能獲得正確解旅行售貨員問題:(優(yōu)先隊列式分支限界法) Type Travding (int v) MinHeapNode H(1000)； Type MinoutN+1； /計算 Minouti=頂點 i的最小出邊費用 Type Minsurn=0；/最小出邊費用和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)； /無回路 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) /非葉結點if（E.sn-1） /當前擴展結點是葉結點的父結點 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; 所以在最壞的狀況下，整個算法的計算時間簡單性為O(n!)回溯算法解0-1背包問題(解空間：子集樹):templateTypep Knap:Bound(int

10、i)/ 計算上界 Typew cleft = c - cw; / 剩余容量 Typep b = cp; / 以物品單位重量價值遞減序裝入物品 while (i = n & wi = cleft) cleft -= wi; b += pi; i+; / 裝滿背包 if (i n ) bestp=cp; return; if(cw+wibestp ) backtrack(i+1); /xi=0由于上界函數Bound()需要O(n)的時間，在最壞的狀況下有O(2n)個右兒子結點需要計算上界函數，所以0-1背包問題的回溯算法Backtrack()所需要的時間是O(n2n)。回溯算法解圖的m著色問題: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) / 到達葉結點 for (int j = 1; j = n; j+) bestxj = xj; bestn = cn; return; / 檢查頂點 i 與當前團的連接 int OK = 1; for (int j =

12、 1; j bestn) / 進入右子樹 xi = 0; Backtrack(i+1);解最大團問題的回溯算法Backtrack所需的計算時間為O(n2n)。 回溯法的基本思想是：不斷用修改過的判定函數Pi只(x1,x2,xi)(亦稱為限界函數)去測試正在構造中的n元組的部分向量(x1,x2,xn)看其是否可能導致最優(yōu)解。假如判定(x1，x2，xn)不行能導致最優(yōu)解，那么就不再測試可能要測試的mi+1mi+2.mn個向量。解符號三角形問題的回溯算法Backtrack所需的計算時間為O(n2n)。 貪心法解最優(yōu)裝載問題：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;算法所需的計算時間為 O(nlogn)算法是指解決問題的一種方法或一個過程。算法是若干指令的有窮序列，滿足性質：(1)輸入 (2)輸出 (3)確定性 (4)有限性：問題的計算時間下界為W(f(n)，則計算時間簡單性為O(f(n)的算法是最優(yōu)算法。1. 什么是動態(tài)規(guī)劃法：將問題分解成多級或很多子問題，然后挨次求解子問題，

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

15、M，有非確定性算法。1. 算法的分類：1）(數值算法 ) 2） 非數值算法2. 算法的描述：1）自然語言描述 2）(流程圖描述) 3）程序語言描述3. 算法的分析標準：1） 時空觀念 2 ）(進展觀念) 3） 設計觀點 4） 溝通的觀點設計動態(tài)規(guī)劃算法的步驟。(1)找出最優(yōu)解的性質，并刻劃其結構特征。(2)遞歸地定義最優(yōu)值。(3)以自底向上的方式計算出最優(yōu)值。(4)依據計算最優(yōu)值時得到的信息，構造最優(yōu)解。動態(tài)規(guī)劃法求矩陣連乘問題：void MatrixChain(int *p，int n，int *m，int *s)for (int i = 1; i = n; i+) mii = 0; for (int r = 2;