【正文】 整數(shù)規(guī)劃問題一種最常用的方法。典型應(yīng)用就是解決整數(shù)規(guī)劃問題。②評價(jià)算法性能的方法如平攤分析中的聚集法，會計(jì)法和勢能法。聚集法就是把指令分為幾類，計(jì)算每一類的消耗，再全部疊加起來。會計(jì)法就是計(jì)算某個指令時(shí)提前將另一個指令的消耗也算進(jìn)去，以后計(jì)算另一個指令時(shí)就不必再算了。勢能法計(jì)算每一步的勢的變化以及執(zhí)行這步指令的消耗，再將每一步消耗全部累計(jì)。這幾種方法都是平攤分析法，平攤分析的實(shí)質(zhì)就是總體考慮指令的消耗時(shí)間，盡管某些指令的消耗時(shí)間很大也可以忽略不計(jì)。上述三種方法難易程度差不多，每種方法都有屬于它的難點(diǎn)。如聚集法中如何將指令有效分類，會計(jì)法中用什么指令提前計(jì)算什么指令的消耗，勢能法中如何選取勢能。因此掌握這些方法原理還不夠，還要學(xué)會去應(yīng)用，在具體的問題中去判斷分析。三、重點(diǎn)學(xué)習(xí) 貪婪+其他算法：由于貪婪往往能大幅化簡狀態(tài)，利用問題的某些“單調(diào)性”，加上貪婪的思想，往往能是問題大幅簡化，從而結(jié)合其他算法解決問題經(jīng)典例題：田忌賽馬，利用貪婪來確定狀態(tài)。分而治之的思想在信息學(xué)競賽中是非常重要的，下面主要介紹一下分治的經(jīng)典應(yīng)用 1)二分查找思想很簡單，功能很強(qiáng)大，邊界要注意，負(fù)數(shù)要特判（noi2010 piano）在非負(fù)數(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）快速排序，歸并排序任何一本算法書上都會講的，這里就略過了，值得一提的是快排記得加上隨機(jī)化 k := a[random(rg(x)*ans = 0 重構(gòu)權(quán)，將f(i)g(i)*ans作為新權(quán)值，用相應(yīng)算法求出一個“最小值”，判斷是否=0，接著二分即可 5)樹的分治一般用來解決樹上的路徑或統(tǒng)計(jì)類問題，每次只考慮跟樹根有關(guān)的信息，然后遞歸分治處理樹的分治通常有基于點(diǎn)或基于邊的分治，基于點(diǎn)的難合，基于邊的復(fù)雜度太高，這里只介紹基于點(diǎn)的分治步驟：處理跟當(dāng)前樹根有關(guān)的信息，重新計(jì)算子樹大小，在子樹中選擇重心為根，遞歸到相應(yīng)子樹處理。因?yàn)槊看芜x了重心，所以遞歸總共logn層，每層o(n)的復(fù)雜度，總復(fù)雜度就是o(nlogn)6)二分搜索直接搜的復(fù)雜度是指數(shù)級的的話，一般是40左右的數(shù)據(jù)量，hash一半，搜一半，搜后面的時(shí)候利用之前的hash信息合并出原問題的解。而直接搜的復(fù)雜度達(dá)到階乘級的話n一般就不超過20了，做法一般差不多 經(jīng)典例題：poi02szy，noi2001方程的解數(shù)。作為信息學(xué)競賽中的所謂“萬能算法”，搜索可以說是計(jì)算機(jī)學(xué)科所具有的最大特點(diǎn)了，自然地，搜索算法的應(yīng)用自然也是非常之廣泛，除了專門的搜索題，搜索一般可以用來部分預(yù)處理，打表找規(guī)律，當(dāng)然還有騙分。搜索的一般步驟：確定狀態(tài)——選擇搜索方式（dfs、bfs）——確定產(chǎn)生式規(guī)則——開始搜索。搜索的常見優(yōu)化方式： 1)改變狀態(tài)表示這個需要根據(jù)題目而定，確定一個漂亮的狀態(tài)表示，可能就有希望轉(zhuǎn)向記憶化了，即使不行，搞出一個漂亮的狀態(tài)表示是解決一道麻煩題的最重要的一步，再者，調(diào)試起來也會容易許多。2）優(yōu)化搜索順序這個優(yōu)化在多數(shù)搜索中能起到摧枯拉朽的提速效果，通常我們選擇枝葉較少的兒子先擴(kuò)展，例如大名鼎鼎的dancing links，除了利用雙向十字鏈表去除冗余狀態(tài)，每次選擇可擴(kuò)展數(shù)最少的兒子擴(kuò)展同樣給它的神速創(chuàng)造了條件。3）可行性剪枝以及最優(yōu)性剪枝這是非常常用的剪枝思路之一，因題目而異，在迭代加深搜索中尤為重要 一般思路：考慮每次解最多變優(yōu)多少，從當(dāng)前的層數(shù)來看還有多少改進(jìn)空間，如果已經(jīng)不可能成為解或更新答案則可以剪枝了——a*及ida*算法：本質(zhì)就是給搜索加上一個滿足相容性的估價(jià)函數(shù)，然后用估價(jià)函數(shù)剪枝，理論上很牛b，實(shí)際上不常用，因?yàn)榭紙錾虾茈y想出滿足那么多條件的估價(jià)函數(shù)，但記得一些常見模型的估價(jià)函數(shù)還是有價(jià)值的。例如15 數(shù)碼的估價(jià)函數(shù)就可以選擇除了0之外每個元素到自己該到的位置的曼哈頓距離之和，因?yàn)槊看巫疃嗍挂粋€數(shù)距離減少1，所以這個估價(jià)函數(shù)是相容的，再例如求k短路的a*算法就是用個堆維護(hù) min{ f(s)+ g(s)}估價(jià)函數(shù)就是從匯點(diǎn)反搜的“反向最短路”的長度。四、總結(jié)在計(jì)算機(jī)軟件專業(yè)中，算法分析與設(shè)計(jì)是一門非常重要的課程，很多人為它如癡如醉。很多問題的解決，程序的編寫都要依賴它，在軟件還是面向過程的階段，就有程序=算法+數(shù)據(jù)結(jié)構(gòu)這個公式。算法的學(xué)習(xí)對于培養(yǎng)一個人的邏輯思維能力是有極大幫助的，它可以培養(yǎng)我們養(yǎng)成思考分析問題，解決問題的能力。作為it行業(yè)學(xué)生，學(xué)習(xí)算法無疑會增強(qiáng)自己的競爭力，修煉自己的“內(nèi)功”。經(jīng)過這門課的學(xué)習(xí)，我深刻的領(lǐng)悟到數(shù)學(xué)是一切算法分析與設(shè)計(jì)的基礎(chǔ)。這門課的很多時(shí)間多花在了數(shù)學(xué)公式定理的引入和證明上。雖然很枯燥，但是有必不可少。我們可以清晰的看到好多算法思路是從這些公式定理中得出來的，尤其是算法性能的分析更是與數(shù)學(xué)息息相關(guān)。其中有幾個定理令我印象深刻。①主定理本門課中它主要應(yīng)用在分治法性能分析上。例如：t(n)=a*t(n/b)+f(n)，它可以看作一個大問題分解為a個子問題，其中子問題的規(guī)模為b。而f(n)可看作這些子問題的組合時(shí)的消耗。這些可以利用主定理的相關(guān)結(jié)論進(jìn)行分析處理。當(dāng)f(n)量級高于時(shí)，我們可以設(shè)法降低子問題組合時(shí)的消耗來提高性能。反之我們可以降低的消耗，即可以擴(kuò)大問題的規(guī)?；蛘邷p小子問題的個數(shù)。因此主定理可以幫助我們清晰的分析出算法的性能以及如何進(jìn)行有效的改進(jìn)。②隨機(jī)算法中的許多定理的運(yùn)用在這門課中，我學(xué)到了以前從未遇見過的隨機(jī)算法，它給予我很大的啟示。隨機(jī)算法不隨機(jī)，它可通過多次的嘗試來降低它的錯誤率以至于可以忽略不計(jì)。這些都不是空穴來風(fēng)，它是建立在嚴(yán)格的定理的證明上。如素?cái)?shù)判定定理是個很明顯的例子。它運(yùn)用了包括費(fèi)馬小定理在內(nèi)的各種定理。將這些定理進(jìn)行有效的組合利用，才得出行之有效的素?cái)?shù)判定的定理。尤其是對尋找證據(jù)數(shù)算法的改進(jìn)的依據(jù)，也是建立在3個定理上。還有檢查字符串是否匹配也是運(yùn)用了許多定理：指紋的運(yùn)用，理論出錯率的計(jì)算，算法性能的評價(jià)也都是建立在數(shù)學(xué)定理的運(yùn)用上。篇五：遺傳算法學(xué)習(xí)心得基本概念遺傳算法(genetic algorithms, ga)是一類借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī)化搜索算法。它模擬自然選擇和自然遺傳過程中發(fā)生的繁殖、交叉和基因突變現(xiàn)象，在每次迭代中都保留一組候選解，并按某種指標(biāo)從解群中選取較優(yōu)的個體，利用遺傳算子(選擇、交叉和變異)對這些個體進(jìn)行組合，產(chǎn)生新一代的候選解群，重復(fù)此過程，直到滿足某種收斂指標(biāo)為止。ga的組成:（1）編碼（產(chǎn)生初始種群）（2）適應(yīng)度函數(shù)（3）遺傳算子（選擇、交叉、變異）（4）運(yùn)行參數(shù)編碼基因在一定能夠意義上包含了它所代表的問題的解?；虻木幋a方式有很多，這也取決于要解決的問題本身。常見的編碼方式有：（1）二進(jìn)制編碼，基因用0或1表示（常用于解決01背包問題）如：基因a：00100011010(代表一個個體的染色體)（2）互換編碼（用于解決排序問題，如旅行商問題和調(diào)度問題）如旅行商問題中，一串基因編碼用來表示遍歷的城市順序，如：234517986，表示九個城市中，先經(jīng)過城市2，再經(jīng)過城市3，依此類推。（3）樹形編碼（用于遺傳規(guī)劃中的演化編程或者表示）如,問題：給定了很多組輸入和輸出。請你為這些輸入輸出選擇一個函數(shù)，使得這個函數(shù)把每個輸入盡可能近地映射為輸出。編碼方法：基因就是樹形結(jié)構(gòu)中的一些函數(shù)。（4）值編碼（二進(jìn)制編碼不好用時(shí)，解決復(fù)雜的數(shù)值問題）在值編碼中，每個基因就是一串取值。這些取值可以是與問題有關(guān)任何值：整數(shù)，實(shí)數(shù)，字符或者其他一些更復(fù)雜的東西。適應(yīng)度函數(shù)遺傳算法對一個個體（解）的好壞用適應(yīng)度函數(shù)值來評價(jià)，適應(yīng)度函數(shù)值越大，解的質(zhì)量越好。適應(yīng)度函數(shù)是遺傳算法進(jìn)化過程的驅(qū)動力，也是進(jìn)行自然選擇的唯一標(biāo)準(zhǔn)，它的設(shè)計(jì)應(yīng)結(jié)合求解問題本身的要求而定。如tsp問題，遍歷各城市路徑之和越小越好，這樣可以用可能的最大路徑長度減去實(shí)際經(jīng)過的路徑長度，作為該問題的適應(yīng)度函數(shù)。遺傳算子——選擇遺傳算法使用選擇運(yùn)算來實(shí)現(xiàn)對群體中的個體進(jìn)行優(yōu)勝劣汰操作：適應(yīng)度高的個體被遺傳到下一代群體中的概率大；適應(yīng)度低的個體，被遺傳到下一代群體中的概率小。選擇操作的任務(wù)就是按某種方法從父代群體中選取一些個體，遺傳到下一代群體。sga（基本遺傳算法）中采用輪盤賭選擇方法。輪盤賭選擇又稱比例選擇算子，基本思想：各個個體被選中的概率與其適應(yīng)度函數(shù)值大小成正比。設(shè)群體大小為n，個體i 的適應(yīng)度為 fi，則個體i 被選中遺傳到下一代群體的概率為：遺傳算子——交叉所謂交叉運(yùn)算，是指對兩個相互配對的染色體依據(jù)交叉概率按某種方式相互交換其部分基因，從而形成兩個新的個體。交叉運(yùn)算在ga中起關(guān)鍵作用，是產(chǎn)生新個體的主要方法。（用于二進(jìn)制編碼）選擇一個交叉點(diǎn),子代在交叉點(diǎn)前面的基因從一個父代基因那里得到,后面的部分從另外一個父代基因那里得到。如：交叉前：00000|***00 11100|***01 交叉后：00000|***01 11100|***00 （用于二進(jìn)制編碼）選擇兩個交叉點(diǎn),子代基因在兩個交叉點(diǎn)間部分來自一個父代基因,：交叉前： 01 |0010| 11 11 |0111| 01 交叉后： 11 |0010| 01 01 |0111| 11 “ 與/或 ”交叉法（用于二進(jìn)制編碼）對父代按位與”邏輯運(yùn)算產(chǎn)生一子代a。按位”或”邏輯運(yùn)算產(chǎn)生另一子代b。：交叉前： 01001011 11011101 交叉后： 01001001 11011111 （用于互換編碼）選擇一個交叉點(diǎn)，子代的從初始位置出發(fā)的部分從一個基因復(fù)制，然后在另一個基因中掃描，如果某個位點(diǎn)在子代中沒有，就把它添加進(jìn)去。如：交叉前： 87213 | 09546 98356 | 71420 交叉后：87213 | 95640 98356 | 72104 （pmx）法（用于互換編碼）先隨機(jī)產(chǎn)生兩個交叉點(diǎn)，定義這兩點(diǎn)間的區(qū)域?yàn)槠ヅ鋮^(qū)域，并用交換兩個父代的匹配區(qū)域。父代a：872 | 130 | 9546 父代b：983 | 567 | 1420 變?yōu)椋?temp a: 872 | 567 | 9546 temp b: 983 | 130 | 1420 對于 temp a、temp ｂ中匹配區(qū)域以外出現(xiàn)的數(shù)碼重復(fù)，要依據(jù)匹配區(qū)域內(nèi)的位置逐一進(jìn)行替換。匹配關(guān)系：1５ ３６ ７０ 子代ａ：802 | 567 | 9143 子代ｂ：986 | 130 | 5427 (ox)（用于互換編碼）從父代ａ隨機(jī)選一個編碼子串，放到子代ａ的對應(yīng)位置；子代ａ空余的位置從父代ｂ中按ｂ的順序選?。ㄅc己有編碼不重復(fù)）。同理可得子代ｂ。父代a: 872 | 139 | 0546 父代b: 983 | 567 | 1420 交叉后：子代a: 856 | 139 | 7420 子代b: 821 | 567 | 3904 （cx）法（用于互換編碼）cx同ox交叉都是從一個親代中取一些城市，而其它城市來自另外一個親代，但是二者不同之處在于：ox中來自第一個親代的編碼子串是隨機(jī)產(chǎn)生的，而cx卻不是，它是根據(jù)兩個雙親相應(yīng)位置的編碼而確定的。父代ａ：1 2 3 4 5 6 7 8 9 | | | | | 父代ａ：5 4 6 9 2 3 7 8 1 可得循環(huán)基因：152491 用循環(huán)的基因構(gòu)成子代ａ，順序與父代ａ一樣 1 2 4 5 9 用父代ｂ剩余的基因填滿子代ａ： 1 2 6 4 5 3 7 8 9 子代ｂ的編碼同理。（循環(huán)基因 519425）遺傳算子——變異 變異是指依據(jù)變異概率將個體編碼串中的某些基因值用其它基因值來替換，從而形成一個新的個體。ga中的變異運(yùn)算是產(chǎn)生新個體的輔助方法，它決定了ga的局部搜索能力，同時(shí)保持種群的多樣性。交叉運(yùn)算和變異運(yùn)算的相互配合，共同完成對搜索空間的全局搜索和局部搜索。注：變異概率pm不能太小，這樣降低全局搜索能力；也不能太大，pm ，這時(shí)ga退化為隨機(jī)搜索。