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

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

2、作系統(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é)果。沒有輸出的算法是毫無意義的。（5）可行性。在有限時間內(nèi)完成計算過程。算法設(shè)計的整個過程，可以包含對問題需求的說明、數(shù)學(xué)模型的擬制、算法的詳細(xì)設(shè)計、算法的正確

3、性驗證、算法的實現(xiàn)、算法分析、程序測試和文檔資料的編制。算法可大致分為基本算法、數(shù)據(jù)結(jié)構(gòu)的算法、數(shù)論與代數(shù)算法、計算幾何的算法、圖論的算法、動態(tài)規(guī)劃以及數(shù)值分析、加密算法、排序算法、檢索算法和并行算法。經(jīng)典的算法主要有：1、窮舉搜索法窮舉搜索法是對可能是解的眾多候選解按某種順序進(jìn)行逐一枚舉和檢驗，bing從中找出那些符合要求的候選解作為問題的解。窮舉算法特點是算法簡單，但運(yùn)行時所花費(fèi)的時間量大。有些問題所列舉書來的情況數(shù)目會大得驚人，就是用高速計算機(jī)運(yùn)行，其等待運(yùn)行結(jié)果的時間也將使人無法忍受。我們在用窮舉算法解決問題是，應(yīng)盡可能將明顯不符合條件的情況排除在外，以盡快取得問題的解。2、迭代算法（

4、迭代法是數(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）的計算。若方程有根，并且用上述方法計算出來的近似根序列收斂，則按上述方法求得的x0就認(rèn)為是方程的根。3、遞推算法遞推算法是利用問題本身所具有

5、的一種遞推關(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時，能直接得解。遞歸算法解決問題的特點有：（1）遞歸就是在過程或函數(shù)里調(diào)用自身（2）在使用遞歸策略時，必須有一個明確的遞歸結(jié)束條件，稱為遞歸出口（3）遞歸算法解題通常顯得很簡潔，但遞

6、歸算法解題的運(yùn)行效率較低（4）在遞歸調(diào)用的過程中系統(tǒng)為每一層的返回點、局部變量等開辟堆棧來存儲。舉例如下：fibonacci數(shù)列intfib50;/采用數(shù)組保存中間結(jié)果voidfibonacci(intn)fib0=1;fib1=1;for(inti=2;in)/更新最優(yōu)解if(cwbestw)for(inti=1;i=n;i+)bestxi=xi;bestw=cw;return;/更新剩余集裝箱的重量r-=wt;/搜索左子樹if(cw+wtbestw)xt=0;backtrack(t+1);r+=wt;/恢復(fù)狀態(tài)9、分支限界算法分支限界算法是一種在表示問題解空間的樹上進(jìn)行系統(tǒng)搜索的方法。該方

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

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

9、不能到達(dá)最優(yōu)解的枝條“剪”掉，以減少搜索的時間。裝載問題裝載問題分支限界算法的數(shù)據(jù)結(jié)構(gòu)#definenum100intn;/集裝箱的數(shù)量intc;/輪船的載重量intwnum;/集裝箱的重量數(shù)組算法實現(xiàn)intmaxloading()queueq;q.push(-1);inti=0;intew=0;intbestw=0;intr=0;for(intj=1;jn;j+)r+=wj;/搜索子空間樹while(true)/檢查左子樹intwt=ew+wi;if(wtbestw)bestw=wt;/加入活結(jié)點隊列if(ibestw&in-1)q.push(ew);/從隊列中取出活結(jié)點ew=q.front();q.pop();if(ew=-1)/判斷同層的尾部if(q.empty()returnbestw;/同層結(jié)點尾部標(biāo)志q.push(-1);/從隊列中取出活結(jié)點ew=q.front();q.pop();i+;r-=wi;returnbestw;在計算機(jī)軟件專業(yè)中，算法分析與設(shè)計是一門非常重要的課程，很多人為它如癡如醉。很多問題的解決，程序的編寫都要依賴它，在軟件還是面向過程的階段，就有程序=算法+數(shù)據(jù)結(jié)構(gòu)這個公式。算法的學(xué)習(xí)對于培養(yǎng)一個人的邏輯思維能力