算法設(shè)計及分析總結(jié)

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

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

3、待運行結(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) 將x0的值保存于變量x1，然后計算g(x1),并將結(jié)果存于變量x0。（3）當(dāng)x0與x1的差的絕對值還小于指定的精度要求時，重復(fù)步驟（2

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

5、點有：（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ù)雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題，

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

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

9、法是一種在數(shù)學(xué)和計算機(jī)科學(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ī)劃算法的有效性依賴于問題本身所具有的兩個重要的性質(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)生的子問題并不總是新問題

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

11、efine NUM 100int n;/集裝箱的數(shù)量int c;/輪船的載重量int wNUM; /集裝箱的重量數(shù)組int xNUM; /當(dāng)前搜索的解向量int r;/剩余集裝箱的重量int cw;/當(dāng)前輪船的載重量int bestw; /當(dāng)前最優(yōu)載重量int bestxNUM; /當(dāng)前最優(yōu)解算法實現(xiàn)/形參表示搜索第t層結(jié)點void Backtrack(int t)/到達(dá)葉子結(jié)點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;/恢復(fù)狀態(tài)9、 分支限界算法分支限界算法是一種在表示問題解空間的樹上進(jìn)行系統(tǒng)搜索的方法。該方法使用了廣度優(yōu)先策略，同時采用最大收益（或最小損耗）策略來控制搜索的分支。分支限界法的基本思想是對包含具有約束條件的最優(yōu)化問題的所有可行解的解（數(shù)目有限）空間進(jìn)行搜索。該算法在具體執(zhí)行時，把全部可行的解空間不斷分割為越來越小的子集，并為每個子集內(nèi)的解計算一個下界或上界。在每次分支后，對所

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

14、益的解。提高分支限界算法的效率實現(xiàn)分支限界算法時，首先確定目標(biāo)值的上下界，邊搜索邊減掉搜索樹的某些分支，提高搜索效率。在搜索時，絕大部分需要用到剪枝?！凹糁Α笔撬阉魉惴ㄖ袃?yōu)化程序的一種基本方法，需要通過設(shè)計出合理的判斷方法，以決定某一分支的取舍。若我們把搜索的過程看成是對一棵樹的遍歷，那么剪枝就是將樹中的一些“死結(jié)點”，不能到達(dá)最優(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+wi;if (wt<=c) /檢查約束條件if (wt>bestw) bestw = wt;/加入活結(jié)點隊列if (i<n-1) Q.push(wt);/檢查右子樹/檢查上界條件if (Ew+r>bestw &am