算法設(shè)計與分析學(xué)習(xí)總結(jié)匯編

1、學(xué)習(xí) 好資料學(xué)習(xí)-好資料算法分析與設(shè)計學(xué)習(xí)總結(jié)題目：算法分析與設(shè)計學(xué)習(xí)總結(jié)學(xué)院信息科學(xué)與工程學(xué)院專業(yè)2013級計算機應(yīng)用技術(shù)屆次學(xué)生姓名 學(xué) 號 2013110657二O三年一月十五日算法分析與設(shè)計學(xué)習(xí)總結(jié)本學(xué)期通過學(xué)習(xí)算法分析與設(shè)計課程，了解到： 算法是一系列解決問題的清晰指令，代表著用系統(tǒng)的方法描述解決問題的策略機制。 算法能夠?qū)σ欢ㄒ?guī)范的輸入， 在有限時間內(nèi)獲 得所要求的輸出。 如果一個算法有缺陷， 或不適合某個問題， 執(zhí)行這個算法將不會解決這個 問題。 不同的算法可能用不同的時間、 空間或效率來完成同樣的任務(wù)。 一個算法的優(yōu)劣可以 用空間復(fù)雜性和時間復(fù)雜度來衡量。 算法可以使用自然語言

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

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

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

5、指定的精度要求時，重復(fù)步驟（2）的計算。若方程有根，并且用上述方法計算出來的近似根序列收斂，則按上述方法求得的xo就認(rèn)為是方程的根。3、遞推算法遞推算法是利用問題本身所具有的一種遞推關(guān)系求問題解的一種方法。它把問題分成若干步，找出相鄰幾步的關(guān)系，從而達到目的。4、遞歸算法遞歸算法是一種直接或間接的調(diào)用自身的算法。能采用遞歸描述的算法通常有這樣的特征： 為求解規(guī)模為 n 的問題， 設(shè)法將它分解成規(guī) 模較小的問題， 然后從這些小問題的解方便地構(gòu)造出大問題的解， 并且這些規(guī)模較小的問題 也能采用同樣的分解和綜合方法， 分解成規(guī)模更小的問題， 并從這些更小問題的解構(gòu)造出規(guī)模較大問題的解。特別的，當(dāng)規(guī)模

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

7、更多的相同或相似的子問題， 再把子問題分成 更小的子問題，直到最后子問題可以簡單地直接求解，原問題的解即子問題解的合并。如果原問題可分割成 k 個子問題， 且這些子問題都可解， 并可利用這些子問題的解求出 原問題的解， 那么這種分治法就是可行的。 由分治法產(chǎn)生的子問題往往是原問題的較小模式， 這就為使用遞歸技術(shù)提供了方便。 在這種情況下， 反復(fù)應(yīng)用分治手段， 可以使子問題與原問題類型一致而其規(guī)模卻不斷縮小， 最終使子問題縮小到很容易直接求出其解。這自然導(dǎo)致遞歸過程的產(chǎn)生。 分治與遞歸像一對孿生兄弟， 多高效算法。分治策略的算法設(shè)計模式 Divide_and_Conquer ( P)if (|P

8、| v= n0 ) return adhoc(P);divide P into smaller substances P1， for (i = 1; i <= k; k + + )yi = Divide-and-Conquer ( Pi)Return merge (y1, y2, ，yk)經(jīng)常同時應(yīng)用在算法設(shè)計之中，并由此產(chǎn)生許P2， ， Pk；/遞歸解決 Pi/合并子問題6、貪心算法 貪心算法也稱貪婪算法。 它在對問題求解時， 總是做出在當(dāng)前看來是最好的選擇。 它不 從整體最優(yōu)上考慮，所得出的僅是在某種意義上的局部最優(yōu)解。貪心算法的基本思路如下：（1）建立數(shù)學(xué)模型來描述問題（2）把求解

9、的問題分成若干個子問題（3）對每一子問題求解，得到子問題的局部最優(yōu)解（4） 把子問題的局部最優(yōu)解合成原來問題的一個解 貪心算法的一般流程 :Greedy(A)/初始解集合為空集/集合 S 沒有構(gòu)成問題的一個解/在候選集合 A 中做貪心選擇/判斷集合 S 中加入 x 后的解是否可行S= ;while (not solution(S)x = select(A);if feasible(S, x)S = S+x;A = A-x;return S;( 1)候選集合 A ：問題的最終解均取自于候選集合A。(2) 解集合S:解集合S不斷擴展，直到構(gòu)成滿足問題的完整解。(3) 解決函數(shù)solution :檢

10、查解集合 S是否構(gòu)成問題的完整解。(4) 選擇函數(shù)select：貪心策略，這是貪心算法的關(guān)鍵。(5) 可行函數(shù)feasible：解集合擴展后是否滿足約束條件。7、動態(tài)規(guī)劃算法 動態(tài)規(guī)劃算法是一種在數(shù)學(xué)和計算機科學(xué)中用于求解包含重疊子問題的最優(yōu)化問題的方法。 其基本思想是， 將原問題分解為相似的子問題， 在求解的過程中通過子問題的解求出 原問題的解。動態(tài)規(guī)劃算法的步驟(1) 找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征；(2) 遞歸地定義最優(yōu)值(寫出動態(tài)規(guī)劃方程)；(3) 以自底向上的方式計算出最優(yōu)值；(4) 根據(jù)算法最優(yōu)值時得到的信息，構(gòu)造一個最優(yōu)值。動態(tài)規(guī)劃算法的有效性依賴于問題本身所具有的兩個重要的

11、性質(zhì)：最優(yōu)子結(jié)構(gòu)性質(zhì)和子問題重疊性質(zhì)。(1) 最優(yōu)子結(jié)構(gòu)：當(dāng)問題的最優(yōu)解包含了其子問題的最優(yōu)解時，稱該問題具有最優(yōu)子結(jié)構(gòu) 性質(zhì)。(2) 重疊子問題：在用遞歸算法自頂向下解問題時，每次產(chǎn)生的子問題并不總是新問題， 有些子問題被反復(fù)計算多次。8、回溯算法回溯法是一種選優(yōu)搜索法，按選優(yōu)條件向前搜索， 以達到目標(biāo)。當(dāng)探索到某一步時，發(fā) 現(xiàn)原先的選擇并不優(yōu)或達不到目標(biāo)， 就回退一步重新選擇， 這種走不通就退回再走的技術(shù)成 為回溯法，滿足回溯條件的某個狀態(tài)的點稱為“回溯點” 。迷宮問題算法所采用的就是回溯 算法?；厮菟惴ń鉀Q問題的過程是先選擇某一可能的線索進行試探，每一步試探都有多種方 式，將每一方式都一

12、一試探，如有問題就返回糾正，反復(fù)進行這種試探在反復(fù)糾正，直到得 出全部符合條件的答案或是問題無解為止。 由于回溯方法的本質(zhì)是深度優(yōu)先的方法在解的空 間樹中搜索，就要從堆棧中找到回溯的前一個位置繼續(xù)試探。裝載問題回溯算法數(shù)據(jù)結(jié)構(gòu)#define NUM 100int n;int c;int wNUM;int xNUM;int r;int cw;int bestw;int bestxNUM;/集裝箱的數(shù)量/輪船的載重量/集裝箱的重量數(shù)組 /當(dāng)前搜索的解向量 /剩余集裝箱的重量 /當(dāng)前輪船的載重量 /當(dāng)前最優(yōu)載重量/當(dāng)前最優(yōu)解算法實現(xiàn)/形參表示搜索第 t 層結(jié)點 void Backtrack(int

13、t)/到達葉子結(jié)點 if(t>n)/更新最優(yōu)解 if(cw>bestw) for(int i=1; i<=n; i+)bestxi = xi; bestw = cw; return; /更新剩余集裝箱的重量r -= wt;/搜索左子樹 if(cw+wt<=c)xt = 1; cw += wt; Backtrack(t+1); cw -= wt;/搜索右子樹 if(cw+r>bestw)xt=0; Backtrack(t+1);r += wt;/ 恢復(fù)狀態(tài)該方法使用了廣度9、分支限界算法 分支限界算法是一種在表示問題解空間的樹上進行系統(tǒng)搜索的方法。 優(yōu)先策略，同時采

14、用最大收益(或最小損耗)策略來控制搜索的分支。 分支限界法的基本思想是對包含具有約束條件的最優(yōu)化問題的所有可行解的解 (數(shù)目有 限)空間進行搜索。 該算法在具體執(zhí)行時， 把全部可行的解空間不斷分割為越來越小的子集， 并為每個子集內(nèi)的解計算一個下界或上界。 在每次分支后， 對所有界限超出已知可行解的那 些子集不再做進一步分支， 解的許多子集可不予考慮， 從而縮小了搜索的范圍。 這一過程一 直進行到找出可行解的值不大于任何子集的界限為止。這種算法一般可以求得最優(yōu)解。分支結(jié)點的選擇 從活結(jié)點表中選擇下一個活結(jié)點作為新的擴展結(jié)點， 分支限界算法通?？梢苑譃閮煞N形 式：1、 FIFO ( First I

15、n First Out )分支限界算法 按照先進先出( FIFO )原則選擇下一個活結(jié)點作為擴展結(jié)點，即從活結(jié)點表中取出結(jié) 點的順序與加入結(jié)點的順序相同。2、 最小耗費或最大收益分支限界算法 在這種情況下，每個結(jié)點都有一個耗費或收益。 根據(jù)問題的需要， 可能是要查找一個具有最小耗費的解， 或者是查找一個具有最大收益 的解。提高分支限界算法的效率 實現(xiàn)分支限界算法時， 首先確定目標(biāo)值的上下界， 邊搜索邊減掉搜索樹的某些分支， 提 高搜索效率。在搜索時， 絕大部分需要用到剪枝。 “剪枝 ”是搜索算法中優(yōu)化程序的一種基本方法， 需 要通過設(shè)計出合理的判斷方法，以決定某一分支的取舍。若我們把搜索的過程

16、看成是對一棵樹的遍歷，那么剪枝就是將樹中的一些“死結(jié)點 ”， 不能到達最優(yōu)解的枝條 “剪 ”掉，以減少搜索的時間。裝載問題裝載問題分支限界算法的數(shù)據(jù)結(jié)構(gòu)#define NUM 100int n;/集裝箱的數(shù)量int c;/輪船的載重量int wNUM;/集裝箱的重量數(shù)組算法實現(xiàn)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+w

17、i;if (wt<=c)/ 檢查約束條件if (wt>bestw) bestw = wt; /加入活結(jié)點隊列 if (i<n-1) Q.push(wt);/檢查右子樹/檢查上界條件if (Ew+r>bestw && i<n-1)Q.push(Ew);/從隊列中取出活結(jié)點Ew = Q.front();Q.pop();if (Ew=-1)/判斷同層的尾部if (Q.empty() return bestw; /同層結(jié)點尾部標(biāo)志 Q.push(-1);/從隊列中取出活結(jié)點Ew = Q.front();Q.pop(); i+;r -= wi;return bestw;在計算機軟件專