第一篇：作業(yè)：現(xiàn)代化優(yōu)算法學(xué)習(xí)心得

現(xiàn)代化優(yōu)算法學(xué)習(xí)心得

在科技高度發(fā)展的今天，計算機(jī)在人們之中的作用越來越突出。在這個學(xué)期里，我專門學(xué)習(xí)了現(xiàn)代優(yōu)化算法。現(xiàn)代優(yōu)化算法包括禁忌搜索（tabu search）、模擬退火simu-lated annclaing)、遺傳算法（genetic algorithms）、神經(jīng)網(wǎng)絡(luò)neural networks)、拉格朗日松弛等算法。這些算法涉及生物進(jìn)化、人工智能、數(shù)學(xué)和物理科學(xué)、神經(jīng)系統(tǒng)和統(tǒng)計力學(xué)等概念，都是以一定的直觀基礎(chǔ)而構(gòu)成的算法，我們稱之為啟發(fā)算法。啟發(fā)算法的興起于計算復(fù)雜性理論的形式有密切的聯(lián)系，當(dāng)人們不滿足常規(guī)算法求解復(fù)雜問題時，現(xiàn)代優(yōu)化算法開始體現(xiàn)其作用。我在這里就以禁忌搜索這種算法來談?wù)劕F(xiàn)代優(yōu)化算法在計算復(fù)雜性理論問題時所體現(xiàn)的優(yōu)越性。

禁忌搜索(rabu scarch)算法是局部鄰域搜運(yùn)算法的推廣，是人工智能在組合優(yōu)化算法中的一個成功應(yīng)用。Glover 在1986年首次提出這一概念，進(jìn)而形成一套完整算法，詳見文獻(xiàn)[2，3]。禁忌搜索算法的特點(diǎn)是采用了禁忌技術(shù)。所謂禁忌就是禁止重復(fù)前面的工作。為了回避局部鄰域搜索陷入局部最優(yōu)的主要不足，禁忌搜索算法用一個禁忌表記錄下已達(dá)到過的局部最優(yōu)點(diǎn)，在下一次搜索中，利用禁忌表中的信息不再或有選擇地搜索這些點(diǎn)，以此來跳出局部最優(yōu)點(diǎn)。禁忌搜索算法是一種人工智能的算法，因此，從以下方面來談?wù)劷伤阉魉惴ā?/p>

1、局部搜索

除特別強(qiáng)調(diào)外，我們都假設(shè)算法用以解決如下組合最優(yōu)化問題：其中)(X為目標(biāo)數(shù)，g（x）為約束方程，D為定義域。因?yàn)榻伤阉魉惴ㄖ杏玫骄植克阉魉惴?，我們首先介紹局部搜索算法。該算法可以簡單的表示為：局部搜索算法STEP1 選下一個初始可行解x0；記錄當(dāng)前最優(yōu)解xbest：= x0，令P=N（xbest）；STEP2當(dāng)P=Ф時，或滿足其他停止運(yùn)算準(zhǔn)則時，輸出計算結(jié)果，停止運(yùn)算；否則，從N（xbest）中選一集合S，得到S中的最優(yōu)解xbest；若xbest＜xbest，則xbest：=xnow，P：= N（xbest）；否則，P：=P-S；重復(fù)STEP2。在局部搜索算法中，STEP1的初始可行解選擇可以采用隨機(jī)的方法，也可用一些經(jīng)驗(yàn)的方法或是其他算法所得到的解。STEP2中的集合S選取可以大到是Nxbest）本身，也可以小到只有一個元素，如用隨機(jī)的方法在N（xbest）中選一點(diǎn)，從直觀可以看出，S選取得小將使每一步的計量減少，但可比較的范圍很?。籗選取大時每一步計算時間增加，比較的范圍自然增加，這兩種情況的應(yīng)用果依賴于實(shí)際問題。在STEP2中，其他停止準(zhǔn)則是除STEP2的P=Ф以外的其他準(zhǔn)則。這些準(zhǔn)則的給出往往取決于人們對算法的計算時間、計算結(jié)果的要求，通過下面的例子來理解局部搜索算法。例2．1 5個城市的對稱TSP數(shù)據(jù)如圖2.1 對應(yīng)的距離矩陣為

第二篇：算法學(xué)習(xí)心得

算法設(shè)計與分析學(xué)習(xí)心得

班級：物聯(lián)網(wǎng)1201 姓名：劉瀟 學(xué)號：1030612129

一、實(shí)驗(yàn)內(nèi)容：

這學(xué)期的算法與設(shè)計課，老師布置了這四個問題，分別是貨郎擔(dān)問題，動態(tài)生成二維數(shù)組，對話框下拉列表，排序問題。

二、學(xué)習(xí)掌握：

基本程序描述：

（1）貨郎擔(dān)問題：貨郎擔(dān)問題屬于易于描述但難于解決的著名難題之一，至今世界上還有不少人在研究它。貨郎擔(dān)問題要從圖g的所有周游路線中求取具有最小成本的周游路線，而由始點(diǎn)出發(fā)的周游路線一共有（n一1）！條，即等于除始結(jié)點(diǎn)外的n一1個結(jié)點(diǎn)的排列數(shù)，因此貨郎擔(dān)問題是一個排列問題。貨郎擔(dān)的程序?qū)崿F(xiàn)了利用窮舉法解決貨郎擔(dān)問題，可以在城市個數(shù)和各地費(fèi)用給定的情況下利用窮舉法逐一計算出每一條路線的費(fèi)用，并從中選出費(fèi)用最小的路線。從而求出問題的解

（2）費(fèi)用矩陣：費(fèi)用矩陣的主要內(nèi)容是動態(tài)生成二維數(shù)組。首先由鍵盤輸入自然數(shù)，費(fèi)用矩陣的元素由隨機(jī)數(shù)產(chǎn)生，并取整，把生成的矩陣存放在二維數(shù)組中，最后把矩陣內(nèi)容輸出到文件和屏幕上。它采用分支界限法，分支限界法的基本思想是對包含具有約束條件的最優(yōu)化問題的所有可行解的解（數(shù)目有限）空間進(jìn)行搜索。該算法在具體執(zhí)行時，把全部可行的解空間不斷分割為越來越小的子集，并為每個子集內(nèi)的解計算一個下界或上界。動態(tài)生成二維n*n的數(shù)組程序利用指針表示數(shù)組的行和列，并逐一分配空間，在輸入n的數(shù)值后，系統(tǒng)自動分配空間，生成n*n的數(shù)組，并產(chǎn)生隨機(jī)數(shù)填充數(shù)組，最后將結(jié)果輸入到指定文件中。

三.疑問與總結(jié)：

貨郎擔(dān)的問題，我認(rèn)為窮舉法相對比而言是比較初級的方法，費(fèi)時耗力，適合在練習(xí)時選用，但是在實(shí)際問題中不建議采用?？唆斔箍柣蛘咂绽锬匪惴ㄇ笕∽钚∩蓸涞姆椒▉斫鉀Q貨郎擔(dān)的問題是更適合現(xiàn)實(shí)解決問題的。我認(rèn)為程序可以用switch函數(shù)來將函數(shù)分成幾個部分更人性化，比如分為解決問題的的選項(xiàng)，輸出結(jié)果選項(xiàng)，退出程序選項(xiàng)等。再有就是費(fèi)用矩陣的值可以從文件中讀取，而結(jié)果也可以直接放在指定文件中，這樣在實(shí)際應(yīng)用中比較廣泛。

動態(tài)生成二維數(shù)組的程序我認(rèn)為如果按照規(guī)范性，我的方法是中規(guī)中矩的，畢竟再向下延伸，生成三維的數(shù)組，需要三層的指針來實(shí)現(xiàn)。但是就程序的簡化程度和計算機(jī)處理時間來說，我認(rèn)為這樣雙層指針的算法有些太占用內(nèi)存，畢竟要給行和列各分配n個空間。我通過與同學(xué)的交流，我發(fā)現(xiàn)可以用1位數(shù)組來實(shí)現(xiàn)二維的n*n的數(shù)組。首先分配n*n的空間，然后通過循環(huán)在一行的數(shù)據(jù)達(dá)到n時自動換行。這樣程序得到了一定的簡化，并且減少了一定的內(nèi)存使用。我認(rèn)為這種方法是比較貼合實(shí)際的。

四.心得體會

在計算機(jī)軟件專業(yè)中，算法分析與設(shè)計是一門非常重要的課程，很多人為它如癡如醉。很多問題的解決，程序的編寫都要依賴它，在軟件還是面向過程的階段，就有程序=算法+數(shù)據(jù)結(jié)構(gòu)這個公式。算法的學(xué)習(xí)對于培養(yǎng)一個人的邏輯思維能力是有極大幫助的，它可以培養(yǎng)我們養(yǎng)成思考分析問題，解決問題的能力。

如果一個算法有缺陷，或不適合某個問題，執(zhí)行這個算法將不會解決這個問題。不同的算法可能用不同的時間、空間或效率來完成同樣的任務(wù)。一個算法的優(yōu)劣可以用空間復(fù)雜性和時間復(fù)雜度來衡量。算法可以使用自然語言、偽代碼、流程圖等多種不同的方法來描述。計算機(jī)系統(tǒng)中的操作系統(tǒng)、語言編譯系統(tǒng)、數(shù)據(jù)庫管理系統(tǒng)以及各種各樣的計算機(jī)應(yīng)用系統(tǒng)中的軟件，都必須使用具體的算法來實(shí)現(xiàn)。算法設(shè)計與分析是計算機(jī)科學(xué)與技術(shù)的一個核心問題。因此，學(xué)習(xí)算法無疑會增強(qiáng)自己的競爭力，提高自己的修為，為自己增彩。篇二：算法個人心得

算法學(xué)習(xí)心得: 算法這個詞是在我在大學(xué)第一次c語言課上聽到的，當(dāng)時老師講的是程序=算法+數(shù)據(jù)結(jié)構(gòu)，算法是一個程序的靈魂。當(dāng)時我什么也不懂，不知道什么叫數(shù)據(jù)結(jié)構(gòu)，什么叫算法，它們是干什么的我也不明白。然而經(jīng)歷了大學(xué)四年的學(xué)習(xí)，現(xiàn)在的我對算法有了一個較為清晰的認(rèn)識，對于它的作用也有了深刻的體會。

所謂算法簡單來說就是指解題方案的準(zhǔn)確而完整的描述，是一系列解決問題的清晰指令，也就是說算法告訴計算機(jī)怎么做，以此來解決問題。同一個問題存在多種算法來解決它，但是這些算法存在著優(yōu)劣之分，好的算法速度快，效率高，占用空間小，差的算法不僅復(fù)雜難懂，而且效率低，對機(jī)器要求還高，當(dāng)然，有時候算法之間存在一種互補(bǔ)關(guān)系，有些算法效率高，節(jié)省時間，但浪費(fèi)空間，另外一些算法可能速度上慢些，但是空間比較節(jié)約，這時候我們就應(yīng)該根據(jù)實(shí)際要求，和具體情況來采取相應(yīng)的算法來解決問題。

這學(xué)期算法課上我們主要講了七部分內(nèi)容.第一章主要講的是算法的基本概念，算法時間復(fù)雜度分析，算法的漸近時間復(fù)雜度等內(nèi)容。因?yàn)樗惴ㄖg的比較就是通過時間復(fù)雜度和空間復(fù)雜度來來比較的，第一章的主要目的就是讓我們學(xué)會去分析一個算法的復(fù)雜度，以后就可以通過對復(fù)雜度的分析來評價算法的好壞。

第二章講的是分治法，任何一個可以用計算機(jī)求解的問題所需的計算時間都與其規(guī)模有關(guān)。問題的規(guī)模越小，越容易直接求解，解題所需的計算時間也越少，分治法的設(shè)計思想就是，將一個難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個擊破，分而治之。在這一章中我們講到了尋找第k個元素，矩陣相乘，尋找最近點(diǎn)對等幾個使用分治法的經(jīng)典例子，最后還將講到了傅里葉變換的問題。以前我們學(xué)到的歸并排序，二分搜索其實(shí)也是基于分治法思想的。能采用分治法來解決的問題通常有如下幾個特征： 1)該問題的規(guī)?？s小到一定的程度就可以容易地解決 2)該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有最優(yōu)子

結(jié)構(gòu)性質(zhì)。

3)利用該問題分解出的子問題的解可以合并為該問題的解； 4)該問題所分解出的各個子問題是相互獨(dú)立的，即子問題之間不包含公

共的子子問題。

在用分治法解決實(shí)際問題時，我們疑問究竟各個子問題的規(guī)模應(yīng)該怎樣才為適當(dāng)？從大量實(shí)踐中發(fā)現(xiàn)，在用分治法設(shè)計算法時，最好使子問題的規(guī)模大致相同。換句話說，將一個問題分成大小相等的k個子問題的處理方法是行之有效的，這就是一種平衡的思想。

第三章主要講動態(tài)規(guī)劃問題。這一章的內(nèi)容我覺得是算法設(shè)計思想中最難，也最有趣的這部分。什么叫動態(tài)規(guī)劃，動態(tài)規(guī)劃的思想是什么？動態(tài)規(guī)劃采用自頂向下的方式分析問題，自底向上的方式遞推求值，將待求解的問題分解成若干個子問題，先求解子問題，并把子問題的解存儲起來以便以后用來計算所需要求的解。簡言之，動態(tài)規(guī)劃的基本思想就是把全局的問題化為局部的問題，為了全局最優(yōu)必須局部最優(yōu)。“多階段決策問題是根據(jù)問題本身的特點(diǎn)，將其求解的過程劃分為若干個相互獨(dú)立又相互聯(lián)系的階段，在每一個階段都需要做出決策，并且在一個階段的決策確定以后再轉(zhuǎn)移到下一個階段，在每一階段選取其最優(yōu)決策，從而實(shí)現(xiàn)整個過程總體決策最優(yōu)的目的”（引用）。還記得期末考試中的最后一道關(guān)于任意給定一個數(shù)，從所給的牌中用最少的牌組成這個數(shù)，這個問題其實(shí)就可以用動態(tài)規(guī)劃來解決。本科期間，在算法課上老師在動態(tài)規(guī)劃這一章不布置的一個作業(yè)跟這個題目類似，當(dāng)時的題目是找錢問題，問題是這樣描述的：有n種不同面值的硬幣，各硬幣面值存于數(shù)組t[1:n]，現(xiàn)用這些面值的錢來找錢，編程計算找錢m的最少硬幣數(shù)及各個面值。分析如下：假設(shè)對于i = 1...n-1，所需最少的硬幣數(shù)count(i)已知，那么對于n，所需的硬幣數(shù)為min(count(i)+ count(n-i)), i=1...n-1;于是一個直觀的方法是用遞歸計算。

但是，遞歸過程中，每次計算count(i)，都會重復(fù)計算 count(1)....count(i-1);這樣時間復(fù)雜度就是o(n^2);我們可以從1開始記錄下每個錢數(shù)所需的硬幣枚數(shù)，避免重復(fù)計算，為了能夠輸出硬幣序列，我們還需要記錄下每次新加入的硬幣。下面給出用動態(tài)規(guī)劃解決此問題的遞推式：

參數(shù)說明： 當(dāng)只用面值為t[1],t[2],?t[n]來找出錢j時，所用的硬幣的最小個數(shù)記為c(i,j),則c(i,j)的遞推方程為：

運(yùn)用這個遞推式，我們可以從下往上記錄各個j所需要的應(yīng)兵書i，最后當(dāng)j=m時，所對應(yīng)的i就是我們要求的。第四章講的是集合算法，這一章的內(nèi)容是我第一次接觸，以前沒有學(xué)過。這一章主要講了平攤分析，union-find，finding the depth，以及2-3樹等內(nèi)容，平攤分析教會我們?nèi)绾螐恼w的角度去更精確的分析算法的時間復(fù)雜度，union-find sets是一種簡單的用途廣泛的集合，并查集是若干個不相交集合，能夠?qū)崿F(xiàn)較快的合并和判斷元素所在集合的操作，一般采取樹形結(jié)構(gòu)來存儲并查集，并利用一個rank數(shù)組來存儲集合的深度下界，在查找操作時進(jìn)行路徑壓縮使后續(xù)的查找操作加速，finding the depth 確定深度問題。為了既能求得各點(diǎn)在原先樹中的正確深度、又能使時間復(fù)雜度較小，需要使用具有路徑壓縮功能的find-depth指令，同時還需要采取一些輔助手段來保證深度計算的正確性。2-3樹具有以下幾個特點(diǎn)：

1、任一內(nèi)結(jié)點(diǎn)（非葉結(jié)點(diǎn)）均有2個或3個兒子。

2、從根到每片樹葉的路徑長度相等。

3、內(nèi)結(jié)點(diǎn)中只存放便于查找的信息，而葉結(jié)點(diǎn)中存放原始數(shù)據(jù)。

第五章主要講了隨機(jī)算法。在隨機(jī)算法中，我們不要求算法對所有可能的輸入均正確計算，只要求出現(xiàn)錯誤的可能性小到可以忽略的程度。另外我們也不要求對同一輸入算法每次執(zhí)行時給出相同的結(jié)果。我們所關(guān)心的是算法在執(zhí)行時，是否能夠產(chǎn)生真正隨機(jī)的結(jié)果。有不少問題，目前只有效率很差的確定性求解算法，但用隨機(jī)算法去求解，可以很快地獲得相當(dāng)可信的結(jié)果。隨機(jī)算法通常分為兩大類:las vegas算法、monte carlo算法。las vegas算法總是給出正確的結(jié)果，但在少數(shù)應(yīng)用中，可能出現(xiàn)求不出解的情況。此時需再次調(diào)用算法進(jìn)行計算，直到獲得解為止.mont carlo算法通常不能保證計算出的結(jié)果總是正確，一般只能斷定所給解的正確性不小于p（1/2＜p＜1）。通過反復(fù)執(zhí)行算法（即以增大算法的執(zhí)行時間為代價），能夠使發(fā)生錯誤的概率小到可以忽略的程度。第五章還講到素數(shù)測試，其中介紹了相關(guān)定理，重點(diǎn)講了miller-rabin算法。

第六章介紹了計算模型，這一章主要介紹了有關(guān)計算的一些本質(zhì)問題，random access machines(隨機(jī)存取機(jī)，簡稱ram)，存儲程序模型rasp（random access stored program），圖靈機(jī)（turning machine）以及各個計算模型之間的關(guān)系。

第七章介紹了np完全問題，主要包括近似算法（approximation algorithms），非確定性turing機(jī) ndtm，確定性turing機(jī) dtm，以及之間的區(qū)別，np完全經(jīng)典問題等內(nèi)容。

經(jīng)過一學(xué)期的算法學(xué)習(xí)，我對算法的了解進(jìn)一步加深，曾經(jīng)學(xué)習(xí)過的內(nèi)容得到進(jìn)一步鞏固，同時沒有接觸的內(nèi)容也讓我有了新的認(rèn)識。作為一名計算機(jī)專業(yè)的學(xué)生，算法是一門基礎(chǔ)學(xué)科，它里面包含的思想無處不在，學(xué)好算法分析，對于在自己的方向上獲得啟示，體會更深有著重大作用。所以，我們應(yīng)該培養(yǎng)對算法的興趣，將算法的運(yùn)用融入到生活當(dāng)中，比如找錢問題就是個很好的例子，通過具體的生活實(shí)例來讓算法變得更加有魅力，有吸引力,以此來激發(fā)對算法的興趣。篇三：算法設(shè)計與分析學(xué)習(xí)總結(jié) 算法分析與設(shè)計 學(xué)習(xí)總結(jié)

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

學(xué) 院 信息科學(xué)與工程學(xué)院

專 業(yè) 屆 次

學(xué)生姓名 學(xué) 號

二○一三年一月十五日

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

本學(xué)期通過學(xué)習(xí)算法分析與設(shè)計課程，了解到：算法是一系列解決問題的清晰指令，代表著用系統(tǒng)的方法描述解決問題的策略機(jī)制。算法能夠?qū)σ欢ㄒ?guī)范的輸入，在有限時間內(nèi)獲得所要求的輸出。如果一個算法有缺陷，或不適合某個問題，執(zhí)行這個算法將不會解決這個問題。不同的算法可能用不同的時間、空間或效率來完成同樣的任務(wù)。一個算法的優(yōu)劣可以用空間復(fù)雜性和時間復(fù)雜度來衡量。算法可以使用自然語言、偽代碼、流程圖等多種不同的方法來描述。計算機(jī)系統(tǒng)中的操作系統(tǒng)、語言編譯系統(tǒng)、數(shù)據(jù)庫管理系統(tǒng)以及各種各樣的計算機(jī)應(yīng)用系統(tǒng)中的軟件，都必須使用具體的算法來實(shí)現(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è)計、算法的正確性驗(yàn)證、算法的實(shí)現(xiàn)、算法分析、程序測試和文檔資料的編制。算法可大致分為基本算法、數(shù)據(jù)結(jié)構(gòu)的算法、數(shù)論與 代數(shù)算法、計算幾何的算法、圖論的算法、動態(tài)規(guī)劃以及數(shù)值分析、加密算法、排序算法、檢索算法和并行算法。經(jīng)典的算法主要有：

1、窮舉搜索法

窮舉搜索法是對可能是解的眾多候選解按某種順序進(jìn)行逐一枚舉和檢驗(yàn)，bing從中找出那些符合要求的候選解作為問題的解。

窮舉算法特點(diǎn)是算法簡單，但運(yùn)行時所花費(fèi)的時間量大。有些問題所列舉書來的情況數(shù)目會大得驚人，就是用高速計算機(jī)運(yùn)行，其等待運(yùn)行結(jié)果的時間也將使人無法忍受。我們在用窮舉算法解決問題是，應(yīng)盡可能將明顯不符合條件的情況排除在外，以盡快取得問題的解。

2、迭代算法

迭代法是數(shù)值分析中通過從一個初始估計出發(fā)尋找一系列近似解來解決問題（一般是解方程或方程組）的過程，為實(shí)現(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、遞推算法

遞推算法是利用問題本身所具有的一種遞推關(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時，能直接得解。

遞歸算法解決問題的特點(diǎn)有：

（1）遞歸就是在過程或函數(shù)里調(diào)用自身

（2）在使用遞歸策略時，必須有一個明確的遞歸結(jié)束條件，稱為遞歸出口

（3）遞歸算法解題通常顯得很簡潔，但遞歸算法解題的運(yùn)行效率較低

（4）在遞歸調(diào)用的過程中系統(tǒng)為每一層的返回點(diǎn)、局部變量等開辟堆棧來存

儲。

舉例如下： fibonacci數(shù)列

int fib[50];//采用數(shù)組保存中間結(jié)果 void fibonacci(int n){ fib[0] = 1;fib[1] = 1;for(int i=2;i<=n;i++)fib[i] = fib[i-1]+fib[i-2];}

5、分治算法

分治算法是把一個復(fù)雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題，直到最后子問題可以簡單地直接求解，原問題的解即子問題解的合并。

如果原問題可分割成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)； divide p into smaller substances p1，p2，?，pk； for(i＝1;i＜＝k;k＋＋)yi＝divide-and-conquer（pi）//遞歸解決pi return merge（y1，y2，?，yk）//合并子問題 }

6、貪心算法

貪心算法也稱貪婪算法。它在對問題求解時，總是做出在當(dāng)前看來是最好的選擇。它不從整體最優(yōu)上考慮，所得出的僅是在某種意義上的局部最優(yōu)解。貪心算法的基本思路如下：（1）建立數(shù)學(xué)模型來描述問題

（2）把求解的問題分成若干個子問題

（3）對每一子問題求解，得到子問題的局部最優(yōu)解

（4）把子問題的局部最優(yōu)解合成原來問題的一個解

貪心算法的一般流程: greedy(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ī)劃算法是一種在數(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)生的子問題并不總是新問題，有些子問題被反復(fù)計算多次。

8、回溯算法 回溯法是一種選優(yōu)搜索法，按選優(yōu)條件向前搜索，以達(dá)到目標(biāo)。當(dāng)探索到某一步時，發(fā)現(xiàn)原先的選擇并不優(yōu)或達(dá)不到目標(biāo)，就回退一步重新選擇，這種走不通就退回再走的技術(shù)成為回溯法，滿足回溯條件的某個狀態(tài)的點(diǎn)稱為“回溯點(diǎn)”。迷宮問題算法所采用的就是回溯算法。

回溯算法解決問題的過程是先選擇某一可能的線索進(jìn)行試探，每一步試探都有多種方式，將每一方式都一一試探，如有問題就返回糾正，反復(fù)進(jìn)行這種試探在反復(fù)糾正，直到得出全部符合條件的答案或是問題無解為止。由于回溯方法的本質(zhì)是深度優(yōu)先的方法在解的空間樹中搜索，就要從堆棧中找到回溯的前一個位置繼續(xù)試探。

裝載問題回溯算法數(shù)據(jù)結(jié)構(gòu) #define num 100 int n;//集裝箱的數(shù)量 int c;//輪船的載重量 int w[num];//集裝箱的重量數(shù)組 int x[num];//當(dāng)前搜索的解向量 int r;//剩余集裝箱的重量 int cw;//當(dāng)前輪船的載重量 int bestw;//當(dāng)前最優(yōu)載重量

int bestx[num];//當(dāng)前最優(yōu)解 算法實(shí)現(xiàn) //形參表示搜索第t層結(jié)點(diǎn) void backtrack(int t){ //到達(dá)葉子結(jié)點(diǎn) if(t>n){ //更新最優(yōu)解 if(cw>bestw){ for(int i=1;i<=n;i++)bestx[i] = x[i];bestw = cw;} return;} //更新剩余集裝箱的重量 r-= w[t];//搜索左子樹

if(cw+w[t]<=c){ x[t] = 1;cw += w[t];backtrack(t+1);cw-= w[t];} //搜索右子樹

if(cw+r>bestw){ x[t]=0;backtrack(t+1);} r += w[t];//恢復(fù)狀態(tài) }

9、分支限界算法 分支限界算法是一種在表示問題解空間的樹上進(jìn)行系統(tǒng)搜索的方法。該方法使用了廣度篇四：算法設(shè)計與實(shí)現(xiàn)個人課程總結(jié) 算法課程總結(jié)

指導(dǎo)教師

所在院（系）

班 級

學(xué)生姓名

學(xué) 號

一、算法概述 1.什么是算法？

算法是解一確定類問題的任意一種特殊的方法。在計算機(jī)科學(xué)中，算法是使用計算機(jī)解一類問題的精確、有效方法的代名詞。算法是一組有窮的規(guī)則，它規(guī)定了解決某一特定類型問題的一系列運(yùn)算。

2.算法的五個重要特性：確定性、能行性、輸入、輸出、有窮性/有限性。1）確定性：算法每種運(yùn)算必須有確切定義，不能有二義性。2）能行性：算法中有待實(shí)現(xiàn)的運(yùn)算都是基本的運(yùn)算，原理上每種運(yùn)算都能由人用紙和筆在有限的時間內(nèi)完成。3）輸入：每個算法有0個或多個輸入。這些輸入是在算法開始之前給出的量，取自于特定的對象集合——定義域

4）輸出：一個算法產(chǎn)生一個或多個輸出，這些輸出是同輸入有某種特定關(guān)系的量。5）有窮性/有限性：一個算法總是在執(zhí)行了有窮步的運(yùn)算之后終止。3.計算過程：只滿足確定性、能行性、輸入、輸出四個特性但不一定能終止的一組規(guī)則。4.準(zhǔn)確理解算法和計算過程的區(qū)別：不能終止的計算過程：操作系統(tǒng)；算法是“可以終止的計算過程”；算法的時效性：只能把在相當(dāng)有窮步內(nèi)終止的算法投入到計算機(jī)上運(yùn)行。5.算法的語言主要有：自然語言，流程圖，盒圖，pad圖，偽代碼，計算機(jī)程序設(shè)計語言。

6.算法分類： 1)多項(xiàng)式時間算法：可用多項(xiàng)式（函數(shù)）對其計算時間限界的算法。常見的多項(xiàng)式限界函數(shù)有：ο(1)< ο(logn)< ο(n)< ο(nlogn)< ο(n2)< ο(n3)2）指數(shù)時間算法：計算時間用指數(shù)函數(shù)限界的算法。常見的指數(shù)時間限界函數(shù)：ο(2n)< ο(n！)< ο(nn)7.算法基本工具：循環(huán)與遞歸，算法與數(shù)據(jù)結(jié)構(gòu)，優(yōu)化算法的數(shù)學(xué)模型。8.主要算法：迭代算法，蠻力法，分治法，動態(tài)規(guī)劃法，貪婪算法，圖搜索基礎(chǔ)。

二、算法的核心是思想

我們學(xué)習(xí)這門課不是僅僅掌握那幾個經(jīng)典算法例子，更重要的是為了學(xué)習(xí)蘊(yùn)含在其中的思想方法。為什么呢？舉個例子。有同學(xué)曾問我這樣一個問題：1000只瓶子裝滿水，但有一瓶有毒，且毒發(fā)期為1個星期?，F(xiàn)在用10只老鼠在一個星期內(nèi)判斷那只瓶子有毒，每只老鼠可以喝多個瓶子的水，每個瓶子可以只喝一點(diǎn)。問如何解決？其實(shí)一開始我也一頭霧水，但是他提醒我跟計算機(jī)領(lǐng)域相關(guān)，我就立馬有了思路，運(yùn)用二進(jìn)制。因?yàn)橛嬎銠C(jī)的最基本思想就是二進(jìn)制。所以說，我們不僅要學(xué)習(xí)算法，更得學(xué)習(xí)思想方法。

①算法最基本的設(shè)計方法包括分治法，動態(tài)規(guī)劃法，貪婪算法，周游法，回溯法，分支定界法。我們可利用分治法做快速排序，降低找n個元素中最大元和最小元的量級，降低n位二進(jìn)制x和y相乘的量級，做strassen矩陣乘法等等。它的思想就是規(guī)模很大的問題分解為規(guī)模較小的獨(dú)立的子問題，關(guān)鍵是子問題要與原問題同類，可以采取平衡法來提高性能。

動態(tài)規(guī)劃法是把大問題分解為子問題，但是子問題是重復(fù)的，后面的問題可

以利用前面解決過的問題的結(jié)果。如構(gòu)造最優(yōu)二叉查找樹，解決矩陣連乘時最小計算次數(shù)問題，尋找最長公共子序列等等。

貪婪算法就是局部最優(yōu)法，先使局部最優(yōu)，再依次構(gòu)造出更大的局部直至整體。如kruscal最小生成樹算法，求哈夫曼編碼問題。

周游法就是簡單理解就是采取一定的策略遍歷圖中所有的點(diǎn)，典型的應(yīng)用就是圖中的深度優(yōu)先搜索(dfs)和廣度優(yōu)先搜索(bfs)。

回溯法就是就是在滿足一定的條件后就往前走，當(dāng)走到某步時，發(fā)現(xiàn)不滿足條件就退回一步重新選擇新的路線。典型的應(yīng)用就是8皇后問題，平面點(diǎn)集的凸包問題和0-1背包問題。

分支定界法：它是解決整數(shù)規(guī)劃問題一種最常用的方法。典型應(yīng)用就是解決整數(shù)規(guī)劃問題。

②評價算法性能的方法如平攤分析中的聚集法，會計法和勢能法。聚集法就是把指令分為幾類，計算每一類的消耗，再全部疊加起來。會計法就是計算某個指令時提前將另一個指令的消耗也算進(jìn)去，以后計算另一個指令時就不必再算了。勢能法計算每一步的勢的變化以及執(zhí)行這步指令的消耗，再將每一步消耗全部累計。

這幾種方法都是平攤分析法，平攤分析的實(shí)質(zhì)就是總體考慮指令的消耗時間，盡管某些指令的消耗時間很大也可以忽略不計。上述三種方法難易程度差不多，每種方法都有屬于它的難點(diǎn)。如聚集法中如何將指令有效分類，會計法中用什么指令提前計算什么指令的消耗，勢能法中如何選取勢能。因此掌握這些方法原理還不夠，還要學(xué)會去應(yīng)用，在具體的問題中去判斷分析。

三、重點(diǎn)學(xué)習(xí) 1.貪婪算法

貪婪+其他算法：由于貪婪往往能大幅化簡狀態(tài)，利用問題的某些“單調(diào)性”，加上貪婪的思想，往往能是問題大幅簡化，從而結(jié)合其他算法解決問題經(jīng)典例題：田忌賽馬，利用貪婪來確定狀態(tài)。2.分治法

分而治之的思想在信息學(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)計類問題，每次只考慮跟樹根有關(guān)的信息，然后遞歸分治處理

樹的分治通常有基于點(diǎn)或基于邊的分治，基于點(diǎn)的難合，基于邊的復(fù)雜度太高，這里只介紹基于點(diǎn)的分治

步驟：處理跟當(dāng)前樹根有關(guān)的信息，重新計算子樹大小，在子樹中選擇重心為根，遞歸到相應(yīng)子樹處理。

因?yàn)槊看芜x了重心，所以遞歸總共logn層，每層o(n)的復(fù)雜度，總復(fù)雜度就是o(nlogn)6)二分搜索

直接搜的復(fù)雜度是指數(shù)級的的話，一般是40左右的數(shù)據(jù)量，hash一半，搜一半，搜后面的時候利用之前的hash信息合并出原問題的解。

而直接搜的復(fù)雜度達(dá)到階乘級的話n一般就不超過20了，做法一般差不多 經(jīng)典例題：poi02szy，noi2001方程的解數(shù)。3.搜索

作為信息學(xué)競賽中的所謂“萬能算法”，搜索可以說是計算機(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ì)就是給搜索加上一個滿足相容性的估價函數(shù)，然后用估價函數(shù)剪枝，理論上很牛b，實(shí)際上不常用，因?yàn)榭紙錾虾茈y想出滿足那么多條件的估價函數(shù)，但記得一些常見模型的估價函數(shù)還是有價值的。例如15 數(shù)碼的估價函數(shù)就可以選擇除了0之外每個元素到自己該到的位置的曼哈頓距離之和，因?yàn)槊看巫疃嗍挂粋€數(shù)距離減少1，所以這個估價函數(shù)是相容的，再例如求k短路的a*算法就是用個堆維護(hù) min{ f(s)+ g(s)}估價函數(shù)就是從匯點(diǎn)反搜的“反向最短路”的長度。

四、總結(jié)

在計算機(jī)軟件專業(yè)中，算法分析與設(shè)計是一門非常重要的課程，很多人為它如癡如醉。很多問題的解決，程序的編寫都要依賴它，在軟件還是面向過程的階段，就有程序=算法+數(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è)計的基礎(chǔ)。這門課的很多時間多花在了數(shù)學(xué)公式定理的引入和證明上。雖然很枯燥，但是有必不可少。我們可以清晰的看到好多算法思路是從這些公式定理中得出來的，尤其是算法性能的分析更是與數(shù)學(xué)息息相關(guān)。其中有幾個定理令我印象深刻。

①主定理

本門課中它主要應(yīng)用在分治法性能分析上。例如：t(n)=a*t(n/b)+f(n)，它可以看作一個大問題分解為a個子問題，其中子問題的規(guī)模為b。而f(n)可看作這些子問題的組合時的消耗。這些可以利用主定理的相關(guān)結(jié)論進(jìn)行分析處理。當(dāng)f(n)量級高于時，我們可以設(shè)法降低子問題組合時的消耗來提高性能。反之我們可以降低的消耗，即可以擴(kuò)大問題的規(guī)?；蛘邷p小子問題的個數(shù)。因此主定理可以幫助我們清晰的分析出算法的性能以及如何進(jìn)行有效的改進(jìn)。

②隨機(jī)算法中的許多定理的運(yùn)用

在這門課中，我學(xué)到了以前從未遇見過的隨機(jī)算法，它給予我很大的啟示。隨機(jī)算法不隨機(jī)，它可通過多次的嘗試來降低它的錯誤率以至于可以忽略不計。這些都不是空穴來風(fēng)，它是建立在嚴(yán)格的定理的證明上。如素數(shù)判定定理是個很明顯的例子。它運(yùn)用了包括費(fèi)馬小定理在內(nèi)的各種定理。將這些定理進(jìn)行有效的組合利用，才得出行之有效的素數(shù)判定的定理。尤其是對尋找證據(jù)數(shù)算法的改進(jìn)的依據(jù)，也是建立在3個定理上。還有檢查字符串是否匹配也是運(yùn)用了許多定理：指紋的運(yùn)用，理論出錯率的計算，算法性能的評價也都是建立在數(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ù)

編碼

基因在一定能夠意義上包含了它所代表的問題的解。基因的編碼方式有很多，這也取決于要解決的問題本身。常見的編碼方式有：

（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)制編碼不好用時，解決復(fù)雜的數(shù)值問題）在值編碼中，每個基因就是一串取值。這些取值可以是與問題有關(guān)任何值：整數(shù)，實(shí)數(shù)，字符或者其他一些更復(fù)雜的東西。

適應(yīng)度函數(shù)

遺傳算法對一個個體（解）的好壞用適應(yīng)度函數(shù)值來評價，適應(yīng)度函數(shù)值越大，解的質(zhì)量越好。適應(yīng)度函數(shù)是遺傳算法進(jìn)化過程的驅(qū)動力，也是進(jìn)行自然選擇的唯一標(biāo)準(zhǔn)，它的設(shè)計應(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)生新個體的主要方法。1.單交叉點(diǎn)法（用于二進(jìn)制編碼）

選擇一個交叉點(diǎn),子代在交叉點(diǎn)前面的基因從一個父代基因那里得到,后面的部分從另外一個父代基因那里得到。

如：交叉前：

00000|***00 11100|***01 交叉后：

00000|***01 11100|***00 2.雙交叉點(diǎn)法（用于二進(jìn)制編碼）

選擇兩個交叉點(diǎn),子代基因在兩個交叉點(diǎn)間部分來自一個父代基因,其余部分來自于另外一個父代基因.如：交叉前： 01 |0010| 11 11 |0111| 01 交叉后： 11 |0010| 01 01 |0111| 11 3.基于“ 與/或 ”交叉法（用于二進(jìn)制編碼）對父代按位與”邏輯運(yùn)算產(chǎn)生一子代a;按位”或”邏輯運(yùn)算產(chǎn)生另一子代b。該交叉策略在解背包問題中效果較好.如：交叉前： 01001011 11011101 交叉后： 01001001 11011111 4.單交叉點(diǎn)法（用于互換編碼）

選擇一個交叉點(diǎn)，子代的從初始位置出發(fā)的部分從一個基因復(fù)制，然后在另一個基因中掃描，如果某個位點(diǎn)在子代中沒有，就把它添加進(jìn)去。

如：交叉前： 87213 | 09546 98356 | 71420 交叉后：

87213 | 95640 98356 | 72104 5.部分匹配交叉（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 6.順序交叉法(ox)（用于互換編碼）

從父代ａ隨機(jī)選一個編碼子串，放到子代ａ的對應(yīng)位置；子代ａ空余的位置從父代ｂ中按ｂ的順序選?。ㄅc己有編碼不重復(fù)）。同理可得子代ｂ。父代a: 872 | 139 | 0546 父代b: 983 | 567 | 1420 交叉后：

子代a: 856 | 139 | 7420 子代b: 821 | 567 | 3904 7.循環(huán)交叉（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)基因：1->5->2->4->9->1 用循環(huán)的基因構(gòu)成子代ａ，順序與父代ａ一樣 1 2 4 5 9 用父代ｂ剩余的基因填滿子代ａ： 1 2 6 4 5 3 7 8 9 子代ｂ的編碼同理。（循環(huán)基因 5->1->9->4->2->5）

遺傳算子——變異 變異是指依據(jù)變異概率將個體編碼串中的某些基因值用其它基因值來替換，從而形成一個新的個體。ga中的變異運(yùn)算是產(chǎn)生新個體的輔助方法，它決定了ga的局部搜索能力，同時保持種群的多樣性。交叉運(yùn)算和變異運(yùn)算的相互配合，共同完成對搜索空間的全局搜索和局部搜索。

注：變異概率pm不能太小，這樣降低全局搜索能力；也不能太大，pm > 0.5，這時ga退化為隨機(jī)搜索。

第三篇：現(xiàn)代化網(wǎng)絡(luò)學(xué)習(xí)心得

現(xiàn)代化網(wǎng)絡(luò)學(xué)習(xí)心得

許麗晴

隨著信息化快速發(fā)展，作為一名幼兒園教師，必須具備良好的信息素養(yǎng)是終生學(xué)習(xí)、不斷完善自身的需要。應(yīng)具有現(xiàn)代化的教育思想、教學(xué)觀念，掌握現(xiàn)代化的教學(xué)方法和教學(xué)手段，熟練運(yùn)用信息工具對信息資源進(jìn)行有效的收集、加工、組織、運(yùn)用;這些素質(zhì)的養(yǎng)成就要求信息技術(shù)教師不斷地學(xué)習(xí)，才能滿足現(xiàn)代化教學(xué)的需要;信息素養(yǎng)成了終生學(xué)習(xí)的必備素質(zhì)之一，如果教師沒有良好的信息素養(yǎng)，就不能成為一名滿足現(xiàn)代教學(xué)需要的高素質(zhì)的數(shù)學(xué)教師。

通過聆聽本次網(wǎng)絡(luò)提升的學(xué)習(xí)，使我充認(rèn)識到作為老師，要掌握信息操作的基本能力和獲取信息的能力，除此之外還應(yīng)具備信息收集處理以及表達(dá)的能力和綜合運(yùn)用能力。深刻的認(rèn)識到教育信息的重要性，明白什么是教育信息化發(fā)的發(fā)展情況，真正理解了信息化教學(xué)環(huán)境在教育教學(xué)中的作用，掌握常用的教學(xué)模式和軟件的基本應(yīng)用。在線培訓(xùn)為我們提供了一個合作交流的平臺，一個增強(qiáng)自信的平臺。通過看專家視頻講座及各種電子教育技術(shù)的展示與操作，我獲益很大。要想成為新型的幼兒教師，要不斷地學(xué)習(xí)、不斷的、地提高，才能適應(yīng)當(dāng)今教育發(fā)展的需要。此次培訓(xùn)改變了我對信息技術(shù)的片面理解，拓寬了個人的知識面，讓我對信息技術(shù)有了一個全新的認(rèn)識和理解?，F(xiàn)代信息技術(shù)以圖、文、聲、像于一體，及多樣性、新穎性、直觀性、靈活性于一身，使靜止的圖文說話，復(fù)雜的內(nèi)容變簡單，抽象的思維更可及，知識的內(nèi)容更明朗。使教學(xué)形象生動，方便快捷，實(shí)用有效。

在今后的教育教學(xué)過程中，我一定扎實(shí)工作，努力學(xué)習(xí)，把用所學(xué)到的教育技術(shù)知識更好地應(yīng)用到現(xiàn)代化的教育教學(xué)中，扎實(shí)做好基本功，學(xué)習(xí)各種關(guān)于信息技術(shù)的專業(yè)知識，并將新的信息技術(shù)應(yīng)用的課堂教育之中，持之以恒，不懈的努力優(yōu)化自我的專業(yè)技能，更好的適應(yīng)現(xiàn)代化教學(xué)的發(fā)展需求。

第四篇：教育現(xiàn)代化學(xué)習(xí)心得（最終版）

教育現(xiàn)代化學(xué)習(xí)心得

隨著科學(xué)技術(shù)的發(fā)展，特別是計算機(jī)技術(shù)的推廣和普及，使得多所學(xué)校能夠通過教育網(wǎng)進(jìn)行交流，互相探討，互相學(xué)習(xí)，本人深受感觸，通過對網(wǎng)上教育的學(xué)習(xí)，知道了多媒體技術(shù)在課堂教學(xué)中得到了廣泛的應(yīng)用，對教師教學(xué)質(zhì)量的提高以及個人素質(zhì)的提高都有很大的幫助。

下面我就自己通過學(xué)習(xí)計算機(jī)多媒體技術(shù)和課件制作方面的有關(guān)情況談以下幾點(diǎn)體會。

一、小學(xué)教師特別是青年教師要善于學(xué)習(xí)、樂于學(xué)習(xí)信息技術(shù)。

運(yùn)用信息技術(shù)對我教學(xué)工作起到重要的作用。信息技術(shù)可以將我用語言難以表達(dá)清楚的問題直觀、形象地展現(xiàn)給學(xué)生。有助于教學(xué)重點(diǎn)和難點(diǎn)的突破；教學(xué)過程中把豐富多彩的視頻、動畫、圖片等資料展示給學(xué)生，可以引起學(xué)生的學(xué)習(xí)興趣；通過某些問題的設(shè)置，可以培養(yǎng)學(xué)生對教學(xué)過程的參與意識，加深其對問題的認(rèn)識和理解程度；選擇合適的媒體進(jìn)行教學(xué)，可以增大我課容量，節(jié)約時間。

單純靠粉筆、黑板等教學(xué)工具來進(jìn)行教學(xué)的傳統(tǒng)教學(xué)模式顯然是跟不上現(xiàn)代化教學(xué)的要求的掌握一定的計算機(jī)多媒體技術(shù)，如果沒有現(xiàn)代化信息技術(shù)，就沒有現(xiàn)在高質(zhì)量的教學(xué)。

二、我是如何學(xué)習(xí)信息技術(shù)和課件制作的1、培養(yǎng)興趣，循序漸進(jìn)

以前我對信息技術(shù)和課件制作幾乎是一竅不通?？墒钱?dāng)我看到有的老師把信息技術(shù)引進(jìn)課堂教學(xué)時，我就覺得課件制作作為一門技術(shù)對教學(xué)的作用是非常大的，我必須掌握這門技術(shù)，才能適應(yīng)現(xiàn)代化的教育。

人們常說“興趣是最好的老師”，培養(yǎng)了興趣我就開始下功夫?qū)W習(xí)計算機(jī)的使用和課件制作。通過學(xué)習(xí)我知道了好多以前根本沒有接觸過的東西，比如制圖軟件photoshop等，還有各種課件制作軟件，如powerpoint、flash等。在學(xué)習(xí)的過程中我發(fā)現(xiàn)我們常用的課件制作軟件有好多相通之處，學(xué)好了其中的某一個，其他的自己動手、多進(jìn)行嘗試也會慢慢掌握。

2、善于研究，多問問題

學(xué)習(xí)的過程就是一個不斷遇到問題和不斷解決問題的過程。在學(xué)習(xí)和使用各種軟件制作課件的時候，我遇到了很多的問題，遇到問題首先我就自己先琢磨，每個軟件的功能都很多，我們學(xué)會的可能只是這些功能中的一部分，有好多功能需要靠自己嘗試、研究和琢磨。當(dāng)然也有好多問題自己解決不了，我就虛心請教別的老師。我相信，只要我們樂于嘗試，善于思考問題、詢問問題，難題是沒有解決不了的。工作在教學(xué)第一線的老師們在教學(xué)過程中可能都有這種感覺，我們覺得很簡單的東西有的學(xué)生還要問，我們認(rèn)為簡單的東西學(xué)生們說不定覺得挺難，所以我們鼓勵學(xué)生多提問問題。課件制作也是同樣的道理，我們初學(xué)者覺得不好解決的問題在別人看來也許是簡單的，所以在學(xué)習(xí)課件制作的過程中多問問題是必要的。

3、親自動手，樂于嘗試

哲學(xué)上講實(shí)踐是認(rèn)識的動力和來源，也是檢驗(yàn)認(rèn)識正確與否的唯一標(biāo)準(zhǔn)，把這一觀點(diǎn)應(yīng)用到課件制作上就是要親自動手制作課件。也許我們在某一方面的創(chuàng)意是非常好的，可不親自動手，這方面的創(chuàng)意就實(shí)現(xiàn)不了。我們可以先從簡單的做起，由簡單到復(fù)雜，根據(jù)自己的實(shí)際水平動手制作幾個完整的課件，只有這樣，自己的水平才會不斷提高。

三，課件制作過程中應(yīng)注意的幾個問題

1、選擇合適的媒體

現(xiàn)在開發(fā)的課件制作軟件有好多，每一種軟件都有它的優(yōu)勢，當(dāng)然也可能在某些方面存在不足，我們在制作課件之前，應(yīng)該通盤考慮所要講授的課程的特點(diǎn)，需要處理的內(nèi)容，然后根據(jù)不同的軟件的優(yōu)點(diǎn)來選擇使用什么平臺。

2、簡潔實(shí)用是課件制作的重要原則

不少老師在制作課件時往往將自己的課件做得特別“好看”，在課件中加入大量的小動畫和艷麗的圖片以及很刺激的聲音，我認(rèn)為這樣不僅起不到應(yīng)有的效果，反而可能會沖淡主題，這些與課堂無直接關(guān)系的東西會過多的吸引學(xué)生的注意力。信息技術(shù)畢竟是一種輔助手段，它是用來輔助我們的教學(xué)的。一個好的課件關(guān)鍵在于它的實(shí)用性，應(yīng)該說只要是有助于突破重點(diǎn)難點(diǎn)、有助于引起學(xué)生的深刻思考、有助于加深學(xué)生對問題的認(rèn)識的課件就是好課件。

另外，我認(rèn)為不要試圖每堂課都通過信息技術(shù)來處理，這樣既沒有必要，也不現(xiàn)實(shí)，制作一個好的課件往往需要較長的時間。信息技術(shù)的應(yīng)用不是對傳統(tǒng)教學(xué)的否定，而是對傳統(tǒng)教學(xué)的有利補(bǔ)充，提高學(xué)生學(xué)習(xí)效率的關(guān)鍵還是在課堂，我們在制作課件時應(yīng)充分認(rèn)識到這一點(diǎn)。

我相信，只要我們對信息技術(shù)有了正確的認(rèn)識，加上我們的正確使用，信息技術(shù)必將在我們的教學(xué)過程中發(fā)揮其應(yīng)有的作用。

第五篇：短作業(yè)優(yōu)先調(diào)度算法

《操作系統(tǒng)》課程實(shí)驗(yàn)報告

姓名：陳凱

學(xué)號：541413430202

地點(diǎn)：四教樓301

指導(dǎo)老師：張旭

專業(yè)班級：嵌入式軟件14-02

實(shí)驗(yàn)名稱：短作業(yè)優(yōu)先調(diào)度算法

一、實(shí)驗(yàn)?zāi)康模?/p>

測試數(shù)據(jù)可以隨即輸入或從文件中讀入。必須要考慮到作業(yè)的到達(dá)時間

最終能夠計算每一個作業(yè)的周轉(zhuǎn)時間。

二、實(shí)驗(yàn)內(nèi)容：

模擬實(shí)現(xiàn)短作業(yè)調(diào)度算法，具體如下：

設(shè)置作業(yè)體：作業(yè)名，作業(yè)的到達(dá)時間，服務(wù)時間，作業(yè)間的鏈接指針 進(jìn)程初始化：由用戶輸入作業(yè)名、作業(yè)的到達(dá)時間和服務(wù)時間進(jìn)行初始化。顯示函數(shù)：

1、顯示當(dāng)前調(diào)度的是哪個作業(yè)，后備隊列中有哪些作業(yè)

2、最終顯示每個作業(yè)的作業(yè)名、到達(dá)時間、服務(wù)時間、完成時間和周轉(zhuǎn)時間

排序函數(shù)：對就已到達(dá)的作業(yè)按照服務(wù)時間進(jìn)行排序。注意考慮到達(dá)時間 調(diào)度函數(shù)：每次從已到達(dá)的作業(yè)隊列隊首調(diào)度優(yōu)一個作業(yè)執(zhí)行。刪除函數(shù)：作業(yè)結(jié)束后撤銷。

三、實(shí)驗(yàn)代碼

#include structsjf //定義進(jìn)程的結(jié)構(gòu)體 {

char name[10];//進(jìn)程名

floatarrivetime;//到達(dá)時間

floatservicetime;//服務(wù)時間

floatstarttime;

//開始時間

floatfinishtime;//完成時間 floatzztime;//周轉(zhuǎn)時間 floatdqzztime;

//帶權(quán)周轉(zhuǎn)時間 };

sjf b[100];

//定義短作業(yè)優(yōu)先算法進(jìn)程的最大數(shù)量 voidSinput(sjf *p,int N)

//輸入函數(shù) { int i;

printf(“輸入進(jìn)程的名稱、到達(dá)時間、服務(wù)時間:n”);for(i=0;i<=N-1;i++){

printf(“輸入第%d進(jìn)程的名稱、到達(dá)時間、服務(wù)時間:”,i+1);scanf(“%s%f%f”,&p[i].name,&p[i].arrivetime,&p[i].servicetime);} }

//輸出函數(shù) voidSPrint(sjf *p,floatarrivetime,floatservicetime,floatstarttime,floatfinishtime,floatzztime,floatdqzztime,int N){ int k;

printf(“n執(zhí)行順序:n”);printf(“%s”,p[0].name);

for(k=1;k

{

printf(“-%s”,p[k].name);}

printf(“n進(jìn)程名tarrivetservicetstarttfinishtzztdqzzn”);

for(k=0;k<=N-1;k++)

{

printf(“%st%-.2ft%-.2ft%-.2ft%-.2ft%-.2ft%-.2ftnn”,p[k].name,p[k].arrivetime,p[k].servicetime,p[k].starttime,p[k].finishtime,p[k].zztime,p[k].dqzztime);

} }

voidSsort(sjf *p,int N)

//按短作業(yè)優(yōu)先算法排序 {

for(int i=1;i<=N-1;i++)for(int j=1;j<=i;j++)

if(p[i].servicetime

sjf temp;temp=p[i];

p[i]=p[j];

p[j]=temp;} }

//運(yùn)行結(jié)果 voidSdeal(sjf *p, float arrivetime,floatservicetime,floatstarttime,floatfinishtime,float&zztime,float&dqzztime,int N){

int k;

for(k=0;k<=N-1;k++)

{

if(k==0){

p[k].starttime=p[k].arrivetime;

p[k].finishtime=p[k].arrivetime+p[k].servicetime;

} else {

p[k].starttime=p[k-1].finishtime;//開始時間=前一個進(jìn)程的完成時間

p[k].finishtime=p[k-1].finishtime+p[k].servicetime;

//結(jié)束時間=前一個進(jìn)程的完成時間+現(xiàn)在進(jìn)程的服務(wù)時間 }

}

for(k=0;k<=N-1;k++){

p[k].zztime=p[k].finishtime-p[k].arrivetime;

//周轉(zhuǎn)時間=完成時間-到達(dá)時間

p[k].dqzztime=p[k].zztime/p[k].servicetime;

//帶權(quán)周轉(zhuǎn)時間=周轉(zhuǎn)時間/服務(wù)時間 } }

void SJF(sjf *p,int N){

float arrivetime=0,servicetime=0,starttime=0,finishtime=0,zztime=0,dqzztime=0;

Ssort(p,N);

Sdeal(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N);

SPrint(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N);}

void main()//主函數(shù) { int M;printf(“------------短作業(yè)優(yōu)先調(diào)度算法-----------n”);printf(“輸入作業(yè)數(shù):”);scanf(“%d”,&M);

Sinput(b,M);SJF(b,M);}

四、實(shí)驗(yàn)結(jié)果

五、實(shí)驗(yàn)總結(jié)

通過本次實(shí)驗(yàn)讓我學(xué)到了很多關(guān)于作業(yè)與作業(yè)調(diào)度的知識，今后我會好好努力學(xué)習(xí)。