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

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

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

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

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

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

6、 n=0 或 1 時(shí)，能直接得解。 遞歸算法解決問(wèn)題的特點(diǎn)有：（1）遞歸就是在過(guò)程或函數(shù)里調(diào)用自身（2）在使用遞歸策略時(shí)，必須有一個(gè)明確的遞歸結(jié)束條件，稱為遞歸出口（3）遞歸算法解題通常顯得很簡(jiǎn)潔，但遞歸算法解題的運(yùn)行效率較低（4）在遞歸調(diào)用的過(guò)程中系統(tǒng)為每一層的返回點(diǎn)、局部變量等開(kāi)辟堆棧來(lái)存 儲(chǔ)。舉例如下：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、分治算法 分治算法是把一個(gè)復(fù)雜的問(wèn)題分成兩個(gè)或

7、更多的相同或相似的子問(wèn)題， 再把子問(wèn)題分成 更小的子問(wèn)題，直到最后子問(wèn)題可以簡(jiǎn)單地直接求解，原問(wèn)題的解即子問(wèn)題解的合并。如果原問(wèn)題可分割成 k 個(gè)子問(wèn)題， 且這些子問(wèn)題都可解， 并可利用這些子問(wèn)題的解求出 原問(wèn)題的解， 那么這種分治法就是可行的。 由分治法產(chǎn)生的子問(wèn)題往往是原問(wèn)題的較小模式， 這就為使用遞歸技術(shù)提供了方便。 在這種情況下， 反復(fù)應(yīng)用分治手段， 可以使子問(wèn)題與原問(wèn)題類型一致而其規(guī)模卻不斷縮小， 最終使子問(wèn)題縮小到很容易直接求出其解。這自然導(dǎo)致遞歸過(guò)程的產(chǎn)生。 分治與遞歸像一對(duì)孿生兄弟， 多高效算法。分治策略的算法設(shè)計(jì)模式 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)常同時(shí)應(yīng)用在算法設(shè)計(jì)之中，并由此產(chǎn)生許P2， ， Pk；/遞歸解決 Pi/合并子問(wèn)題6、貪心算法 貪心算法也稱貪婪算法。 它在對(duì)問(wèn)題求解時(shí)， 總是做出在當(dāng)前看來(lái)是最好的選擇。 它不 從整體最優(yōu)上考慮，所得出的僅是在某種意義上的局部最優(yōu)解。貪心算法的基本思路如下：（1）建立數(shù)學(xué)模型來(lái)描述問(wèn)題（2）把求解

9、的問(wèn)題分成若干個(gè)子問(wèn)題（3）對(duì)每一子問(wèn)題求解，得到子問(wèn)題的局部最優(yōu)解（4） 把子問(wèn)題的局部最優(yōu)解合成原來(lái)問(wèn)題的一個(gè)解 貪心算法的一般流程 :Greedy(A)/初始解集合為空集/集合 S 沒(méi)有構(gòu)成問(wèn)題的一個(gè)解/在候選集合 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 ：?jiǎn)栴}的最終解均取自于候選集合A。(2) 解集合S:解集合S不斷擴(kuò)展，直到構(gòu)成滿足問(wèn)題的完整解。(3) 解決函數(shù)solution :檢

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

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

12、一試探，如有問(wèn)題就返回糾正，反復(fù)進(jìn)行這種試探在反復(fù)糾正，直到得 出全部符合條件的答案或是問(wèn)題無(wú)解為止。 由于回溯方法的本質(zhì)是深度優(yōu)先的方法在解的空 間樹(shù)中搜索，就要從堆棧中找到回溯的前一個(gè)位置繼續(xù)試探。裝載問(wèn)題回溯算法數(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)解算法實(shí)現(xiàn)/形參表示搜索第 t 層結(jié)點(diǎn) void Backtrack(int

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

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

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

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

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