【正文】 結本學期通過學習算法分析與設計課程，了解到：算法是一系列解決問題的清晰指令，代表著用系統(tǒng)的方法描述解決問題的策略機制。一個算法的優(yōu)劣可以用空間復雜性和時間復雜度來衡量。設計的算法要具有以下的特征才能有效的完成設計要求，算法的特征有：（1）有窮性。（3）輸入。沒有輸出的算法是毫無意義的。算法可大致分為基本算法、數(shù)據(jù)結構的算法、數(shù)論與 代數(shù)算法、計算幾何的算法、圖論的算法、動態(tài)規(guī)劃以及數(shù)值分析、加密算法、排序算法、檢索算法和并行算法。我們在用窮舉算法解決問題是，應盡可能將明顯不符合條件的情況排除在外，以盡快取得問題的解。(2)將x0的值保存于變量x1，然后計算g(x1),并將結果存于變量x0。它把問題分成若干步，找出相鄰幾步的關系，從而達到目的。遞歸算法解決問題的特點有：（1）遞歸就是在過程或函數(shù)里調(diào)用自身（2）在使用遞歸策略時，必須有一個明確的遞歸結束條件，稱為遞歸出口（3）遞歸算法解題通常顯得很簡潔，但遞歸算法解題的運行效率較低（4）在遞歸調(diào)用的過程中系統(tǒng)為每一層的返回點、局部變量等開辟堆棧來存儲。for(int i=2。在這種情況下，反復應用分治手段，可以使子問題與原問題類型一致而其規(guī)模卻不斷縮小，最終使子問題縮小到很容易直接求出其解。i＜＝k。貪心算法的基本思路如下：（1）建立數(shù)學模型來描述問題（2）把求解的問題分成若干個子問題（3）對每一子問題求解，得到子問題的局部最優(yōu)解（4）把子問題的局部最優(yōu)解合成原來問題的一個解貪心算法的一般流程: greedy(a){ s={ }。} return s。（4）選擇函數(shù)select：貪心策略，這是貪心算法的關鍵。動態(tài)規(guī)劃算法的步驟(1)找出最優(yōu)解的性質，并刻畫其結構特征；(2)遞歸地定義最優(yōu)值（寫出動態(tài)規(guī)劃方程）；(3)以自底向上的方式計算出最優(yōu)值；(4)根據(jù)算法最優(yōu)值時得到的信息，構造一個最優(yōu)值?；厮菟惴?回溯法是一種選優(yōu)搜索法，按選優(yōu)條件向前搜索，以達到目標。由于回溯方法的本質是深度優(yōu)先的方法在解的空間樹中搜索，就要從堆棧中找到回溯的前一個位置繼續(xù)試探。//集裝箱的重量數(shù)組 int x[num]。//當前最優(yōu)載重量int bestx[num]。} r += w[t]。算法是一組有窮的規(guī)則，它規(guī)定了解決某一特定類型問題的一系列運算。3）輸入：每個算法有0個或多個輸入。：不能終止的計算過程：操作系統(tǒng)；算法是“可以終止的計算過程”；算法的時效性：只能把在相當有窮步內(nèi)終止的算法投入到計算機上運行。常見的指數(shù)時間限界函數(shù)：ο(2n) ο(n！) ο(nn)：循環(huán)與遞歸，算法與數(shù)據(jù)結構，優(yōu)化算法的數(shù)學模型。有同學曾問我這樣一個問題：1000只瓶子裝滿水，但有一瓶有毒，且毒發(fā)期為1個星期。所以說，我們不僅要學習算法，更得學習思想方法。動態(tài)規(guī)劃法是把大問題分解為子問題，但是子問題是重復的，后面的問題可以利用前面解決過的問題的結果。周游法就是簡單理解就是采取一定的策略遍歷圖中所有的點，典型的應用就是圖中的深度優(yōu)先搜索(dfs)和廣度優(yōu)先搜索(bfs)。典型應用就是解決整數(shù)規(guī)劃問題。勢能法計算每一步的勢的變化以及執(zhí)行這步指令的消耗，再將每一步消耗全部累計。因此掌握這些方法原理還不夠，還要學會去應用，在具體的問題中去判斷分析。而直接搜的復雜度達到階乘級的話n一般就不超過20了，做法一般差不多 經(jīng)典例題：poi02szy，noi2001方程的解數(shù)。2）優(yōu)化搜索順序這個優(yōu)化在多數(shù)搜索中能起到摧枯拉朽的提速效果，通常我們選擇枝葉較少的兒子先擴展，例如大名鼎鼎的dancing links，除了利用雙向十字鏈表去除冗余狀態(tài)，每次選擇可擴展數(shù)最少的兒子擴展同樣給它的神速創(chuàng)造了條件。很多問題的解決，程序的編寫都要依賴它，在軟件還是面向過程的階段，就有程序=算法+數(shù)據(jù)結構這個公式。這門課的很多時間多花在了數(shù)學公式定理的引入和證明上。①主定理本門課中它主要應用在分治法性能分析上。當f(n)量級高于時，我們可以設法降低子問題組合時的消耗來提高性能。隨機算法不隨機，它可通過多次的嘗試來降低它的錯誤率以至于可以忽略不計。將這些定理進行有效的組合利用，才得出行之有效的素數(shù)判定的定理。它模擬自然選擇和自然遺傳過程中發(fā)生的繁殖、交叉和基因突變現(xiàn)象，在每次迭代中都保留一組候選解，并按某種指標從解群中選取較優(yōu)的個體，利用遺傳算子(選擇、交叉和變異)對這些個體進行組合，產(chǎn)生新一代的候選解群，重復此過程，直到滿足某種收斂指標為止。（3）樹形編碼（用于遺傳規(guī)劃中的演化編程或者表示）如,問題：給定了很多組輸入和輸出。這些取值可以是與問題有關任何值：整數(shù)，實數(shù)，字符或者其他一些更復雜的東西。遺傳算子——選擇遺傳算法使用選擇運算來實現(xiàn)對群體中的個體進行優(yōu)勝劣汰操作：適應度高的個體被遺傳到下一代群體中的概率大；適應度低的個體，被遺傳到下一代群體中的概率小。設群體大小為n，個體i 的適應度為 fi，則個體i 被選中遺傳到下一代群體的概率為：遺傳算子——交叉所謂交叉運算，是指對兩個相互配對的染色體依據(jù)交叉概率按某種方式相互交換其部分基因，從而形成兩個新的個體。按位”或”邏輯運算產(chǎn)生另一子代b。匹配關系：1５ ３６ ７０ 子代ａ：802 | 567 | 9143 子代ｂ：986 | 130 | 5427 (ox)（用于互換編碼）從父代ａ隨機選一個編碼子串，放到子代ａ的對應位置；子代ａ空余的位置從父代ｂ中按ｂ的順序選?。ㄅc己有編碼不重復）。（循環(huán)基因 519425）遺傳算子——變異 變異是指依據(jù)變異概率將個體編碼串中的某些基因值用其它基因值來替換，從而形成一個新的個體。交叉運算和變異運算的相互配合，共同完成對搜索空間的全局搜索和局部搜索。父代a: 872 | 139 | 0546 父代b: 983 | 567 | 1420 交叉后：子代a: 856 | 139 | 7420 子代b: 821 | 567 | 3904 （cx）法（用于互換編碼）cx同ox交叉都是從一個親代中取一些城市，而其它城市來自另外一個親代，但是二者不同之處在于：ox中來自第一個親代的編碼子串是隨機產(chǎn)生的，而cx卻不是，它是根據(jù)兩個雙親相應位置的編碼而確定的。如：交叉前： 87213 | 09546 98356 | 71420 交叉后：87213 | 95640 98356 | 72104 （pmx）法（用于互換編碼）先隨機產(chǎn)生兩個交叉點，定義這兩點間的區(qū)域為匹配區(qū)域，并用交換兩個父代的匹配區(qū)域。（用于二進制編碼）選擇一個交叉點,子代在交叉點前面的基因從一個父代基因那里得到,后面的部分從另外一個父代基因那里得到。sga（基本遺傳算法）中采用輪盤賭選擇方法。適應度函數(shù)是遺傳算法進化過程的驅動力，也是進行自然選擇的唯一標準，它的設計應結合求解問題本身的要求而定。編碼方法：基因就是樹形結構中的一些函數(shù)?；虻木幋a方式有很多，這也取決于要解決的問題本身。還有檢查字符串是否匹配也是運用了許多定理：指紋的運用，理論出錯率的計算，算法性能的評價也都是建立在數(shù)學定理的運用上。如素數(shù)判定定理是個很明顯的例子。因此主定理可以幫助我們清晰的分析出算法的性能以及如何進行有效的改進。而f(n)可看作這些子問題的組合時的消耗。我們可以清晰的看到好多算法思路是從這些公式定理中得出來的，尤其是算法性能的分析更是與數(shù)學息息相關。作為it行業(yè)學生，學習算法無疑會增強自己的競爭力，修煉自己的“內(nèi)功”。例如15 數(shù)碼的估價函數(shù)就可以選擇除了0之外每個元素到自己該到的位置的曼哈頓距離之和，因為每次最多使一個數(shù)距離減少1，所以這個估價函數(shù)是相容的，再例如求k短路的a*算法就是用個堆維護 min{ f(s)+ g(s)}估價函數(shù)就是從匯點反搜的“反向最短路”的長度。搜索的一般步驟：確定狀態(tài)——選擇搜索方式（dfs、bfs）——確定產(chǎn)生式規(guī)則——開始搜索。分而治之的思想在信息學競賽中是非常重要的，下面主要介紹一下分治的經(jīng)典應用 1)二分查找思想很簡單，功能很強大，邊界要注意，負數(shù)要特判（noi2010 piano）在非負數(shù)范圍內(nèi)的二分一般寫法如果是l := mid1 或 +1則 mid :=(l + r + 1)div 2 2)快速冪a^b =(a^(b div 2))^2 + ord(odd(b))*a取模也適用 3）快速排序，歸并排序任何一本算法書上都會講的，這里就略過了，值得一提的是快排記得加上隨機化 k := a[random(rg(x)*ans = 0 重構權，將f(i)g(i)*ans作為新權值，用相應算法求出一個“最小值”，判斷是否=0，接著二分即可 5)樹的分治一般用來解決樹上的路徑或統(tǒng)計類問題，每次只考慮跟樹根有關的信息，然后遞歸分治處理樹的分治通常有基于點或基于邊的分治，基于點的難合，基于邊的復雜度太高，這里只介紹基于點的分治步驟：處理跟當前樹根有關的信息，重新計算子樹大小，在子樹中選擇重心為根，遞歸到相應子樹處理。上述三種方法難易程度差不多，每種方法都有屬于它的難點。聚集法就是把指令分為幾類，計算每一類的消耗，再全部疊加起來。典型的應用就是8皇后問題，平面點集的凸包問題和01背包問題。貪婪算法就是局部最優(yōu)法，先使局部最優(yōu)，再依次構造出更大的局部直至整體。我們可利用分治法做快速排序，降低找n個元素中最大元和最小元的量級，降低n位二進制x和y相乘的量級，做strassen矩陣乘法等等。問如何解決？其實一開始我也一頭霧水，但是他提醒我跟計算機領域相關，我就立馬有了思路，運用二進制。二、算法的核心是思想我們學習這門課不是僅僅掌握那幾個經(jīng)典算法例子，更重要的是為了學習蘊含在其中的思想方法。： 1)多項式時間算法：可用多項式（函數(shù)）對其計算時間限界的算法。5）有窮性/有限性：一個算法總是在執(zhí)行了有窮步的運算之后終止。1）確定性：算法每種運算必須有確切定義，不能有二義性。該方法使用了廣度篇四：算法設計與實現(xiàn)個人課程總結 算法課程總結指導教師所在院（系）班 級學生姓名學 號一、算法概述 ？算法是解一確定類問題的任意一種特殊的方法。iif(cw+w[t]if(cw+rbestw){ x[t]=0。//剩余集裝箱的重量 int cw。//集裝箱的數(shù)量 int c。迷宮問題算法所采用的就是回溯算法。(1)最優(yōu)子結構：當問題的最優(yōu)解包含了其子問題的最優(yōu)解時，稱該問題具有最優(yōu)子結構性質。動態(tài)規(guī)劃算法動態(tài)規(guī)劃算法是一種在數(shù)學和計算機科學中用于求解包含重疊子問題的最優(yōu)化問題的方法。（2）解集合s：解集合s不斷擴展，直到構成滿足問題的完整解。//在候選集合a中做貪心選擇 if feasible(s, x)//判斷集合s中加入x后的解是否可行 s = s+{x}。它在對問題求解時，總是做出在當前看來是最好的選擇。分治與遞歸像一對孿生兄弟，經(jīng)常同時應用在算法設計之中，并由此產(chǎn)生許多高效算法。如果原問題可分割成k個子問題，且這些子問題都可解，并可利用這些子問題的解求出原問題的解，那么這種分治法就是可行的。//采用數(shù)組保存中間結果 void fibonacci(int n){ fib[0] = 1。能采用遞歸描述的算法通常有這樣的特征：為求解規(guī)模為n的問題，設法將它分解成規(guī)模較小的問題，然后從這些小問題的解方便地構造出大問題的解，并且這些規(guī)模較小的問題也能采用同樣的分解和綜合方法，分解成規(guī)模更小的問題，并從這些更小問題的解構造出規(guī)模較大問題的解。若方程有根，并且用上述方法計算出來的近似根序列收斂，則按上述方法求得的x0就認為是方程的根。迭代法是用于求方程或方程組近似根的一種常用的算法設計方法。窮舉算法特點是算法簡單，但運行時所花費的時間量大。在有限時間內(nèi)完成計算過程。（4）輸出。（2）確定性。計算機系統(tǒng)中的操作系統(tǒng)、語言編譯系統(tǒng)、數(shù)據(jù)庫管理系統(tǒng)以及各種各樣的計算機應用系統(tǒng)中的軟件，都必須使用具體的算法來實現(xiàn)。如果一個算法有缺陷，或不適合某個問題，執(zhí)行這個算法將不會解決這個問題。作為一名計算機專業(yè)