算法設計及分析總結

1、一個算法的優(yōu)劣可以用空間復雜性和時間復雜度來衡量。算法可以使用自然語言、偽代碼、流程圖等多種不同的方法來描述。計算機系統(tǒng)中的操作系統(tǒng)、語言編譯系統(tǒng)、數據庫管理系統(tǒng)以及各種各樣的計算機應用系統(tǒng)中的軟件，都必須使用具體的算法來實現。算法設計與分析是計算機科學與技術的一個核心問題。設計的算法要具有以下的特征才能有效的完成設計要求，算法的特征有：（1）有窮性。算法在執(zhí)行有限步后必須終止。（2）確定性。算法的每一個步驟必須有確切的定義。（3）輸入。一個算法有0個或多個輸入，作為算法開始執(zhí)行前的初始值，或初始狀態(tài)。（4）輸出。一個算法有一個或多個輸出，以反映對輸入數據加工后的結果。沒有輸出的算法是毫無意義

2、的。（5）可行性。在有限時間內完成計算過程。算法設計的整個過程，可以包含對問題需求的說明、數學模型的擬制、算法的詳細設計、算法的正確性驗證、算法的實現、算法分析、程序測試和文檔資料的編制。算法可大致分為基本算法、數據結構的算法、數論與 代數算法、計算幾何的算法、圖論的算法、動態(tài)規(guī)劃以及數值分析、加密算法、排序算法、檢索算法和并行算法。經典的算法主要有：1、 窮舉搜索法窮舉搜索法是對可能是解的眾多候選解按某種順序進行逐一枚舉和檢驗，bing從中找出那些符合要求的候選解作為問題的解。窮舉算法特點是算法簡單，但運行時所花費的時間量大。有些問題所列舉書來的情況數目會大得驚人，就是用高速計算機運行，其等

3、待運行結果的時間也將使人無法忍受。我們在用窮舉算法解決問題是，應盡可能將明顯不符合條件的情況排除在外，以盡快取得問題的解。2、 迭代算法迭代法是數值分析中通過從一個初始估計出發(fā)尋找一系列近似解來解決問題（一般是解方程或方程組）的過程，為實現這一過程所使用的方法統(tǒng)稱為迭代法。迭代法是用于求方程或方程組近似根的一種常用的算法設計方法。設方程為f(x)=0,用某種數學方法導出等價的形式x=g(x),然后按以下步驟執(zhí)行：（1）選一個方程的近似根，賦給變量x0。 (2) 將x0的值保存于變量x1，然后計算g(x1),并將結果存于變量x0。（3）當x0與x1的差的絕對值還小于指定的精度要求時，重復步驟（2

4、）的計算。若方程有根，并且用上述方法計算出來的近似根序列收斂，則按上述方法求得的x0就認為是方程的根。3、 遞推算法遞推算法是利用問題本身所具有的一種遞推關系求問題解的一種方法。它把問題分成若干步，找出相鄰幾步的關系，從而達到目的。4、 遞歸算法遞歸算法是一種直接或間接的調用自身的算法。能采用遞歸描述的算法通常有這樣的特征：為求解規(guī)模為n的問題，設法將它分解成規(guī)模較小的問題，然后從這些小問題的解方便地構造出大問題的解，并且這些規(guī)模較小的問題也能采用同樣的分解和綜合方法，分解成規(guī)模更小的問題，并從這些更小問題的解構造出規(guī)模較大問題的解。特別的，當規(guī)模n=0或1時，能直接得解。遞歸算法解決問題的特

5、點有：（1） 遞歸就是在過程或函數里調用自身（2） 在使用遞歸策略時，必須有一個明確的遞歸結束條件，稱為遞歸出口（3） 遞歸算法解題通常顯得很簡潔，但遞歸算法解題的運行效率較低（4） 在遞歸調用的過程中系統(tǒng)為每一層的返回點、局部變量等開辟堆棧來存儲。舉例如下：Fibonacci數列int fib50;/采用數組保存中間結果void fibonacci(int n)fib0 = 1;fib1 = 1;for (int i=2; i<=n; i+)fibi = fibi-1+fibi-2;5、 分治算法分治算法是把一個復雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題，

6、直到最后子問題可以簡單地直接求解，原問題的解即子問題解的合并。如果原問題可分割成k個子問題，且這些子問題都可解，并可利用這些子問題的解求出原問題的解，那么這種分治法就是可行的。由分治法產生的子問題往往是原問題的較小模式，這就為使用遞歸技術提供了方便。在這種情況下，反復應用分治手段，可以使子問題與原問題類型一致而其規(guī)模卻不斷縮小，最終使子問題縮小到很容易直接求出其解。這自然導致遞歸過程的產生。分治與遞歸像一對孿生兄弟，經常同時應用在算法設計之中，并由此產生許多高效算法。分治策略的算法設計模式Divide_and_Conquer（P）if (|P|n0 ) return adhoc(P)；divi

7、de P into smaller substances P1，P2，Pk；for (i1; ik; k) yiDivide-and-Conquer（Pi） /遞歸解決PiReturn merge（y1，y2，yk） /合并子問題6、 貪心算法找零錢貪心算法也稱貪婪算法。它在對問題求解時，總是做出在當前看來是最好的選擇。它不從整體最優(yōu)上考慮，所得出的僅是在某種意義上的局部最優(yōu)解。貪心算法的基本思路如下：（1） 建立數學模型來描述問題（2） 把求解的問題分成若干個子問題（3） 對每一子問題求解，得到子問題的局部最優(yōu)解（4） 把子問題的局部最優(yōu)解合成原來問題的一個解貪心算法的一般流程:Greedy

8、(A)S= ;/初始解集合為空集while (not solution(S)/集合S沒有構成問題的一個解x = select(A);/在候選集合A中做貪心選擇if feasible(S, x)/判斷集合S中加入x后的解是否可行S = S+x;A = A-x;return S;（1）候選集合A：問題的最終解均取自于候選集合A。（2）解集合S：解集合S不斷擴展，直到構成滿足問題的完整解。（3）解決函數solution：檢查解集合S是否構成問題的完整解。（4）選擇函數select：貪心策略，這是貪心算法的關鍵。（5）可行函數feasible：解集合擴展后是否滿足約束條件。7、 動態(tài)規(guī)劃算法動態(tài)規(guī)劃算

9、法是一種在數學和計算機科學中用于求解包含重疊子問題的最優(yōu)化問題的方法。其基本思想是，將原問題分解為相似的子問題，在求解的過程中通過子問題的解求出原問題的解。動態(tài)規(guī)劃算法的步驟(1)找出最優(yōu)解的性質，并刻畫其結構特征；(2)遞歸地定義最優(yōu)值（寫出動態(tài)規(guī)劃方程）；(3)以自底向上的方式計算出最優(yōu)值；(4)根據算法最優(yōu)值時得到的信息，構造一個最優(yōu)值。動態(tài)規(guī)劃算法的有效性依賴于問題本身所具有的兩個重要的性質：最優(yōu)子結構性質和子問題重疊性質。(1)最優(yōu)子結構：當問題的最優(yōu)解包含了其子問題的最優(yōu)解時，稱該問題具有最優(yōu)子結構性質。(2)重疊子問題：在用遞歸算法自頂向下解問題時，每次產生的子問題并不總是新問題

10、，有些子問題被反復計算多次。8、 回溯算法回溯法是一種選優(yōu)搜索法，按選優(yōu)條件向前搜索，以達到目標。當探索到某一步時，發(fā)現原先的選擇并不優(yōu)或達不到目標，就回退一步重新選擇，這種走不通就退回再走的技術成為回溯法，滿足回溯條件的某個狀態(tài)的點稱為“回溯點”。迷宮問題算法所采用的就是回溯算法?；厮菟惴ń鉀Q問題的過程是先選擇某一可能的線索進行試探，每一步試探都有多種方式，將每一方式都一一試探，如有問題就返回糾正，反復進行這種試探在反復糾正，直到得出全部符合條件的答案或是問題無解為止。由于回溯方法的本質是深度優(yōu)先的方法在解的空間樹中搜索，就要從堆棧中找到回溯的前一個位置繼續(xù)試探。裝載問題回溯算法數據結構#d

11、efine NUM 100int n;/集裝箱的數量int c;/輪船的載重量int wNUM; /集裝箱的重量數組int xNUM; /當前搜索的解向量int r;/剩余集裝箱的重量int cw;/當前輪船的載重量int bestw; /當前最優(yōu)載重量int bestxNUM; /當前最優(yōu)解算法實現/形參表示搜索第t層結點void Backtrack(int t)/到達葉子結點if(t>n) /更新最優(yōu)解if(cw>bestw)for(int i=1; i<=n; i+) bestxi = xi;bestw = cw;return;/更新剩余集裝箱的重量r -= wt;/搜

12、索左子樹if(cw+wt<=c)xt = 1;cw += wt;Backtrack(t+1);cw -= wt;/搜索右子樹if(cw+r>bestw)xt=0;Backtrack(t+1);r += wt;/恢復狀態(tài)9、 分支限界算法分支限界算法是一種在表示問題解空間的樹上進行系統(tǒng)搜索的方法。該方法使用了廣度優(yōu)先策略，同時采用最大收益（或最小損耗）策略來控制搜索的分支。分支限界法的基本思想是對包含具有約束條件的最優(yōu)化問題的所有可行解的解（數目有限）空間進行搜索。該算法在具體執(zhí)行時，把全部可行的解空間不斷分割為越來越小的子集，并為每個子集內的解計算一個下界或上界。在每次分支后，對所

13、有界限超出已知可行解的那些子集不再做進一步分支，解的許多子集可不予考慮，從而縮小了搜索的范圍。這一過程一直進行到找出可行解的值不大于任何子集的界限為止。這種算法一般可以求得最優(yōu)解。分支結點的選擇從活結點表中選擇下一個活結點作為新的擴展結點，分支限界算法通?？梢苑譃閮煞N形式：1、 FIFO（First In First Out）分支限界算法按照先進先出（FIFO）原則選擇下一個活結點作為擴展結點，即從活結點表中取出結點的順序與加入結點的順序相同。2、 最小耗費或最大收益分支限界算法在這種情況下，每個結點都有一個耗費或收益。根據問題的需要，可能是要查找一個具有最小耗費的解，或者是查找一個具有最大收

14、益的解。提高分支限界算法的效率實現分支限界算法時，首先確定目標值的上下界，邊搜索邊減掉搜索樹的某些分支，提高搜索效率。在搜索時，絕大部分需要用到剪枝?！凹糁Α笔撬阉魉惴ㄖ袃?yōu)化程序的一種基本方法，需要通過設計出合理的判斷方法，以決定某一分支的取舍。若我們把搜索的過程看成是對一棵樹的遍歷，那么剪枝就是將樹中的一些“死結點”，不能到達最優(yōu)解的枝條“剪”掉，以減少搜索的時間。裝載問題裝載問題分支限界算法的數據結構#define NUM 100int n;/集裝箱的數量int c;/輪船的載重量int wNUM;/集裝箱的重量數組算法實現int MaxLoading()queue<int> Q;Q.push(-1);int i = 0;int Ew = 0;int bestw = 0;int r = 0;for(int j=1; j<n; j+)r += wj;/搜索子空間樹while (true)/檢查左子樹int wt = Ew+wi;if (wt<=c) /檢查約束條件if (wt>bestw) bestw = wt;/加入活結點隊列if (i<n-1) Q.push(wt);/檢查右子樹/檢查上界條件if (Ew+r>bestw &am