第一篇：surf算法學習心得(二)源碼簡析

Surf算法學習心得(二)——源碼簡析

說明：作為初學者，我對于源代碼也只是簡單的分析，開始和(一)中一樣都叫做源碼分析，后來感覺自己分析的質(zhì)量不太好，還是都改為源碼簡析吧，結(jié)合起(一)及后面的心得來看估計效果會好點，呵呵。只是希望對于即將要學習Surf算法的人有一定的幫助就行！對于一些介紹得不對的地方，也希望各位大蝦能過指出，相互交流，共同進步！Surf算法源代碼分析surf算法源代碼分為兩種文件，學過C/C++的都知道，在此不多說。頭文件主要包括：imload.h、ipoint.h、image.h、fasthessian.h、surf.h、surflib.h，其中每個文件用于聲明一個特定的相應類，下面大體進行簡單介紹。ImLoad.h——聲明類ImLoad，主要封裝了對圖像的讀取和保存函數(shù)。Image *readImage(const char *filename);

//從圖像文件中讀取圖像void saveImage(const char *filename, Image* im);

//將圖像保存到文件中ipoint.h——聲明類Ipoint，主要定義關鍵點的相應屬性。Ipoint(){

//構造函數(shù)ivec = NULL;ori = 0.0;};~Ipoint(){

//析構函數(shù)if(ivec)delete [] ivec;};void allocIvec(const int si){

//內(nèi)存空間分配ivec = new double[si];};double x, y;

//特征點在圖像中的坐標double scale;

//檢測范圍double strength;

//特征點的強度double ori;

//特征點主方向int laplace;

//Laplacian相關的值double *ivec;

//特征點描述器(局部特征)image.h——聲明類Image，主要定義圖像的相關屬性。Image(const int w, const int h);

//帶參數(shù)的構造函數(shù)~Image();

//析構函數(shù)Image(double **pixels, int w, int h);

//根據(jù)已存在的像素數(shù)組構造圖像Image(Image *im, bool doubleImSize=false);

//構造積分圖像void setFrame(unsigned char *im);

//通過單一的幀到(預初始化)結(jié)構void setFrame(Image *im);Image *HalfImage();

//將圖片長寬個變?yōu)樵瓉淼?/2double getHessian(int *x);

//獲得特定點的Hessian檢測值int getTrace(int *x);

//獲得Hessian矩陣的跡(線性代數(shù)中學過跡)double **getPixels()const;

//獲得指向圖像像素的指針double getPix(const int x, const int y)const {

//獲得某一指定位置的像素值return _pixels[y][x];}double &getPix(const int x, const int y){

//重載getPix并返回引用return _pixels[y][x];}void setPix(const int x, const int y, const double val){ //設置指定位置的像素值_pixels[y][x] = val;}int getWidth();int getHeight();void setWidth(int wi);void setHeight(int hi);void allocPixels(int w, int h);

//為圖像像素分配二維內(nèi)存空間double *_buf;

//指向圖像實際緩沖區(qū)的指針double **_pixels;

//指向圖像像素二維數(shù)組的指針int _height, _width;int _orihi;

//原始圖像高度bool _ref;

//對圖像是否為引用的一種標志fasthessian.h——聲明類FastHessian，主要定義算法中的快速Hessian檢測子方法~FastHessian();//帶參數(shù)的構造方法FastHessian(Image *im, std::vector< Ipoint >& ip, double thres = 0.2, bool doub = false,short int initMasksize = 9, short int samplingStep = 2,short int octaves = 4);void setIimage(Image *iim);

//傳入積分圖像void getInterestPoints();

//檢測圖像的所有特征點//在特定位置創(chuàng)建新的點，并在一定范圍內(nèi)void makeIpoint(double x, double y, double scale, double strength=0);void allocateOctave();

//為Octave分配內(nèi)存空間//Fast non-maximum-suppressionvoid findMaximum(int *borders, int o, int octave);void interpFeature(int s, int row, int col, Image *map,int o, int octave, int movesRemain,int *borders);int fitQuadrat(int s, int r, int c, double &res);Image *_Iimage;Image **_scaleLevel;

//Octavesint _vas[9];

//向量變量double _threshold;

//檢測特征點時的閾值bool _doubled;

//圖像是否放大std::vector< Ipoint >& _ipts;

//從外部傳進來的指向特征點向量的引用short int _initLobe;

//在某一方向第二次求導時的初始lobe值，默認為3short int _maxScales;

//Number scalesshort int _maxOctaves;

//Number octavesshort int _sampling;

//The sampling stepint _width;

//積分圖像的寬int _height;double _offset[3];

//二次擬合的結(jié)果surf.h——聲明surf，主要用于定義Surf中關鍵點相應的描述器Surf();Surf(Image *im, bool dbl=false, bool usurf=false,bool ext=false, int insi=4);~Surf();int getVectLength();

//獲得特征描述器向量的長度void setIpoint(Ipoint *ipt);

//為一個需要計算的描述器設置相應點void assignOrientation();

//定向分配重現(xiàn)void makeDescriptor();

//計算不變圖像特征void createVector(double scale，//創(chuàng)建向量double row, double col);void createUprightVector(double scale,double row, double col);void AddSample(int r, int c, double rpos，//向向量添加樣本double cpos, double rx, double cx, int step);void AddUprightSample(int r, int c, double rpos,double cpos, double rx, double cx, int step);void PlaceInIndex(double mag1, int ori1，//為向量中樣本設置索引值double mag2, int ori2, double rx, double cx);//!Normalise descriptor vector for illumination invariance for Lambertian surfacesvoid normalise();void createLookups();

//創(chuàng)建查找表surflib.h——聲明surf算法要用到的庫函數(shù)。//針對整個圖像定義關鍵點及其相應描述器（關鍵點附加的詳細信息（局部特征））//其中關鍵點信息保存在向量ipts當中inline void surfDetDes(Image *im, std::vector< Ipoint >& ipts,double thres = 4.0, bool doubleImageSize = false,int initLobe = 3, int samplingStep = 2, int octaves = 4,bool upright = false, bool extended = false, int indexSize = 4)//針對一個給定的特征點，計算相應的描述器（局部特征）inline void surfDes(Image *im, std::vector< Ipoint >& ipts,bool doubleImageSize = false,bool upright = false, bool extended = false, int indexSize = 4)編譯運行cmd下進入可執(zhí)行文件目錄，輸入可執(zhí)行文件名，得到如下提示：可以在相應的提示下進行運行，如：注意：輸入文件-i 參數(shù)后面的文件必須是PGM格式的圖像文件，可以自行網(wǎng)上下載，有個“人臉pgm圖片庫”可以拿來使用，輸出不限，如本程序中是output.txt運行完成后，打開文件output.txt可以看到文件中的如下數(shù)據(jù)：這只是一個簡單的示例，直接運行可執(zhí)行文件名出現(xiàn)的幫助里面還有很多選項，別的選項也就是與Surf算法源代碼中的那些參數(shù)對應的，大家應該都懂的，要學習的可以試一下，這樣就能更深入的了解Surf算法。另外源文件中有文件README的說明，里面有關于數(shù)據(jù)格式以及數(shù)據(jù)輸入輸出格式的說明，有興趣的朋友可以自行研究下

第二篇：算法學習心得

算法設計與分析學習心得

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

一、實驗內(nèi)容：

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

二、學習掌握：

基本程序描述：

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

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

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

貨郎擔的問題，我認為窮舉法相對比而言是比較初級的方法，費時耗力，適合在練習時選用，但是在實際問題中不建議采用。克魯斯卡爾或者普里姆算法求取最小生成樹的方法來解決貨郎擔的問題是更適合現(xiàn)實解決問題的。我認為程序可以用switch函數(shù)來將函數(shù)分成幾個部分更人性化，比如分為解決問題的的選項，輸出結(jié)果選項，退出程序選項等。再有就是費用矩陣的值可以從文件中讀取，而結(jié)果也可以直接放在指定文件中，這樣在實際應用中比較廣泛。

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

四.心得體會

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

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

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

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

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

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

結(jié)構性質(zhì)。

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

共的子子問題。

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

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

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

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

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

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

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

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

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

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

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

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

題目：算法分析與設計學習總結(jié)

學 院 信息科學與工程學院

專 業(yè) 屆 次

學生姓名 學 號

二○一三年一月十五日

算法分析與設計學習總結(jié)

本學期通過學習算法分析與設計課程，了解到：算法是一系列解決問題的清晰指令，代表著用系統(tǒng)的方法描述解決問題的策略機制。算法能夠?qū)σ欢ㄒ?guī)范的輸入，在有限時間內(nèi)獲得所要求的輸出。如果一個算法有缺陷，或不適合某個問題，執(zhí)行這個算法將不會解決這個問題。不同的算法可能用不同的時間、空間或效率來完成同樣的任務。一個算法的優(yōu)劣可以用空間復雜性和時間復雜度來衡量。算法可以使用自然語言、偽代碼、流程圖等多種不同的方法來描述。計算機系統(tǒng)中的操作系統(tǒng)、語言編譯系統(tǒng)、數(shù)據(jù)庫管理系統(tǒng)以及各種各樣的計算機應用系統(tǒng)中的軟件，都必須使用具體的算法來實現(xiàn)。算法設計與分析是計算機科學與技術的一個核心問題。

設計的算法要具有以下的特征才能有效的完成設計要求，算法的特征有：（1）有窮性。算法在執(zhí)行有限步后必須終止。（2）確定性。算法的每一個步驟必須有確切的定義。（3）輸入。一個算法有0個或多個輸入，作為算法開始執(zhí)行前的初始值，或初始狀態(tài)。（4）輸出。一個算法有一個或多個輸出，以反映對輸入數(shù)據(jù)加工后的結(jié)果。沒有輸出的算法是毫無意義的。（5）可行性。在有限時間內(nèi)完成計算過程。

算法設計的整個過程，可以包含對問題需求的說明、數(shù)學模型的擬制、算法的詳細設計、算法的正確性驗證、算法的實現(xiàn)、算法分析、程序測試和文檔資料的編制。算法可大致分為基本算法、數(shù)據(jù)結(jié)構的算法、數(shù)論與 代數(shù)算法、計算幾何的算法、圖論的算法、動態(tài)規(guī)劃以及數(shù)值分析、加密算法、排序算法、檢索算法和并行算法。經(jīng)典的算法主要有：

1、窮舉搜索法

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

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

2、迭代算法

迭代法是數(shù)值分析中通過從一個初始估計出發(fā)尋找一系列近似解來解決問題（一般是解方程或方程組）的過程，為實現(xiàn)這一過程所使用的方法統(tǒng)稱為迭代法。迭代法是用于求方程或方程組近似根的一種常用的算法設計方法。設方程為f(x)=0,用某種數(shù)學方法導出等價的形式x=g(x),然后按以下步驟執(zhí)行：

（1）選一個方程的近似根，賦給變量x0。(2)將x0的值保存于變量x1，然后計算g(x1),并將結(jié)果存于變量x0。（3）當x0與x1的差的絕對值還小于指定的精度要求時，重復步驟（2）的計算。若方程有根，并且用上述方法計算出來的近似根序列收斂，則按上述方法求得的x0就認為是方程的根。

3、遞推算法

遞推算法是利用問題本身所具有的一種遞推關系求問題解的一種方法。它把問題分成若干步，找出相鄰幾步的關系，從而達到目的。

4、遞歸算法

遞歸算法是一種直接或間接的調(diào)用自身的算法。

能采用遞歸描述的算法通常有這樣的特征：為求解規(guī)模為n的問題，設法將它分解成規(guī)模較小的問題，然后從這些小問題的解方便地構造出大問題的解，并且這些規(guī)模較小的問題也能采用同樣的分解和綜合方法，分解成規(guī)模更小的問題，并從這些更小問題的解構造出規(guī)

模較大問題的解。特別的，當規(guī)模n=0或1時，能直接得解。

遞歸算法解決問題的特點有：

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

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

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

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

儲。

舉例如下： 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、分治算法

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

如果原問題可分割成k個子問題，且這些子問題都可解，并可利用這些子問題的解求出原問題的解，那么這種分治法就是可行的。由分治法產(chǎn)生的子問題往往是原問題的較小模式，這就為使用遞歸技術提供了方便。在這種情況下，反復應用分治手段，可以使子問題與原問題類型一致而其規(guī)模卻不斷縮小，最終使子問題縮小到很容易直接求出其解。這自然導致遞歸過程的產(chǎn)生。分治與遞歸像一對孿生兄弟，經(jīng)常同時應用在算法設計之中，并由此產(chǎn)生許多高效算法。

分治策略的算法設計模式 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、貪心算法

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

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

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

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

貪心算法的一般流程: greedy(a){ s={ };//初始解集合為空集 while(not solution(s))//集合s沒有構成問題的一個解 { x = select(a);//在候選集合a中做貪心選擇 if feasible(s, x)//判斷集合s中加入x后的解是否可行 s = s+{x};a = a-{x};} return s;｝

（1）候選集合a：問題的最終解均取自于候選集合a。（2）解集合s：解集合s不斷擴展，直到構成滿足問題的完整解。

（3）解決函數(shù)solution：檢查解集合s是否構成問題的完整解。

（4）選擇函數(shù)select：貪心策略，這是貪心算法的關鍵。

（5）可行函數(shù)feasible：解集合擴展后是否滿足約束條件。

7、動態(tài)規(guī)劃算法

動態(tài)規(guī)劃算法是一種在數(shù)學和計算機科學中用于求解包含重疊子問題的最優(yōu)化問題的方法。其基本思想是，將原問題分解為相似的子問題，在求解的過程中通過子問題的解求出原問題的解。

動態(tài)規(guī)劃算法的步驟

(1)找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構特征；(2)遞歸地定義最優(yōu)值（寫出動態(tài)規(guī)劃方程）；(3)以自底向上的方式計算出最優(yōu)值；(4)根據(jù)算法最優(yōu)值時得到的信息，構造一個最優(yōu)值。

動態(tài)規(guī)劃算法的有效性依賴于問題本身所具有的兩個重要的性質(zhì)：最優(yōu)子結(jié)構性質(zhì)和子問題重疊性質(zhì)。(1)最優(yōu)子結(jié)構：當問題的最優(yōu)解包含了其子問題的最優(yōu)解時，稱該問題具有最優(yōu)子結(jié)構性質(zhì)。

(2)重疊子問題：在用遞歸算法自頂向下解問題時，每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復計算多次。

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

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

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

int bestx[num];//當前最優(yōu)解 算法實現(xiàn) //形參表示搜索第t層結(jié)點 void backtrack(int t){ //到達葉子結(jié)點 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];//恢復狀態(tài) }

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

指導教師

所在院（系）

班 級

學生姓名

學 號

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

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

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

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

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

二、算法的核心是思想

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

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

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

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

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

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

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

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

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

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

三、重點學習 1.貪婪算法

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

分而治之的思想在信息學競賽中是非常重要的，下面主要介紹一下分治的經(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)計類問題，每次只考慮跟樹根有關的信息，然后遞歸分治處理

樹的分治通常有基于點或基于邊的分治，基于點的難合，基于邊的復雜度太高，這里只介紹基于點的分治

步驟：處理跟當前樹根有關的信息，重新計算子樹大小，在子樹中選擇重心為根，遞歸到相應子樹處理。

因為每次選了重心，所以遞歸總共logn層，每層o(n)的復雜度，總復雜度就是o(nlogn)6)二分搜索

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

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

作為信息學競賽中的所謂“萬能算法”，搜索可以說是計算機學科所具有的最大特點了，自然地，搜索算法的應用自然也是非常之廣泛，除了專門的搜索題，搜索一般可以用來部分預處理，打表找規(guī)律，當然還有騙分。

搜索的一般步驟：確定狀態(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ù)搜索中能起到摧枯拉朽的提速效果，通常我們選擇枝葉較少的兒子先擴展，例如大名鼎鼎的dancing links，除了利用雙向十字鏈表去除冗余狀態(tài)，每次選擇可擴展數(shù)最少的兒子擴展同樣給它的神速創(chuàng)造了條件。3）可行性剪枝以及最優(yōu)性剪枝

這是非常常用的剪枝思路之一，因題目而異，在迭代加深搜索中尤為重要 一般思路：考慮每次解最多變優(yōu)多少，從當前的層數(shù)來看還有多少改進空間，如果已經(jīng)不可能成為解或更新答案則可以剪枝了

——a*及ida*算法：本質(zhì)就是給搜索加上一個滿足相容性的估價函數(shù)，然后用估價函數(shù)剪枝，理論上很牛b，實際上不常用，因為考場上很難想出滿足那么多條件的估價函數(shù)，但記得一些常見模型的估價函數(shù)還是有價值的。例如15 數(shù)碼的估價函數(shù)就可以選擇除了0之外每個元素到自己該到的位置的曼哈頓距離之和，因為每次最多使一個數(shù)距離減少1，所以這個估價函數(shù)是相容的，再例如求k短路的a*算法就是用個堆維護 min{ f(s)+ g(s)}估價函數(shù)就是從匯點反搜的“反向最短路”的長度。

四、總結(jié)

在計算機軟件專業(yè)中，算法分析與設計是一門非常重要的課程，很多人為它如癡如醉。很多問題的解決，程序的編寫都要依賴它，在軟件還是面向過程的階段，就有程序=算法+數(shù)據(jù)結(jié)構這個公式。算法的學習對于培養(yǎng)一個人的邏輯思維能力是有極大幫助的，它可以培養(yǎng)我們養(yǎng)成思考分析問題，解決問題的能力。作為it行業(yè)學生，學習算法無疑會增強自己的競爭力，修煉自己的“內(nèi)功”。

經(jīng)過這門課的學習，我深刻的領悟到數(shù)學是一切算法分析與設計的基礎。這門課的很多時間多花在了數(shù)學公式定理的引入和證明上。雖然很枯燥，但是有必不可少。我們可以清晰的看到好多算法思路是從這些公式定理中得出來的，尤其是算法性能的分析更是與數(shù)學息息相關。其中有幾個定理令我印象深刻。

①主定理

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

②隨機算法中的許多定理的運用

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

基本概念

遺傳算法(genetic algorithms, ga)是一類借鑒生物界自然選擇和自然遺傳機制的隨機化搜索算法。

它模擬自然選擇和自然遺傳過程中發(fā)生的繁殖、交叉和基因突變現(xiàn)象，在每次迭代中都保留一組候選解，并按某種指標從解群中選取較優(yōu)的個體，利用遺傳算子(選擇、交叉和變異)對這些個體進行組合，產(chǎn)生新一代的候選解群，重復此過程，直到滿足某種收斂指標為止。ga的組成:（1）編碼（產(chǎn)生初始種群）

（2）適應度函數(shù)

（3）遺傳算子（選擇、交叉、變異）

（4）運行參數(shù)

編碼

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

（1）二進制編碼，基因用0或1表示（常用于解決01背包問題）如：基因a：00100011010(代表一個個體的染色體)（2）互換編碼（用于解決排序問題，如旅行商問題和調(diào)度問題）

如旅行商問題中，一串基因編碼用來表示遍歷的城市順序，如：234517986，表示九個城市中，先經(jīng)過城市2，再經(jīng)過城市3，依此類推。

（3）樹形編碼（用于遺傳規(guī)劃中的演化編程或者表示）

如,問題：給定了很多組輸入和輸出。請你為這些輸入輸出選擇一個函數(shù)，使得這個函數(shù)把每個輸入盡可能近地映射為輸出。

編碼方法：基因就是樹形結(jié)構中的一些函數(shù)。

（4）值編碼（二進制編碼不好用時，解決復雜的數(shù)值問題）在值編碼中，每個基因就是一串取值。這些取值可以是與問題有關任何值：整數(shù)，實數(shù)，字符或者其他一些更復雜的東西。

適應度函數(shù)

遺傳算法對一個個體（解）的好壞用適應度函數(shù)值來評價，適應度函數(shù)值越大，解的質(zhì)量越好。適應度函數(shù)是遺傳算法進化過程的驅(qū)動力，也是進行自然選擇的唯一標準，它的設計應結(jié)合求解問題本身的要求而定。

如tsp問題，遍歷各城市路徑之和越小越好，這樣可以用可能的最大路徑長度減去實際經(jīng)過的路徑長度，作為該問題的適應度函數(shù)。

遺傳算子——選擇

遺傳算法使用選擇運算來實現(xiàn)對群體中的個體進行優(yōu)勝劣汰操作：適應度高的個體被遺傳到下一代群體中的概率大；適應度低的個體，被遺傳到下一代群體中的概率小。選擇操作的任務就是按某種方法從父代群體中選取一些個體，遺傳到下一代群體。sga（基本遺傳算法）中采用輪盤賭選擇方法。

輪盤賭選擇又稱比例選擇算子，基本思想：各個個體被選中的概率與其適應度函數(shù)值大小成正比。設群體大小為n，個體i 的適應度為 fi，則個體i 被選中遺傳到下一代群體的概率為：

遺傳算子——交叉

所謂交叉運算，是指對兩個相互配對的染色體依據(jù)交叉概率按某種方式相互交換其部分基因，從而形成兩個新的個體。交叉運算在ga中起關鍵作用，是產(chǎn)生新個體的主要方法。1.單交叉點法（用于二進制編碼）

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

如：交叉前：

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

00000|***01 11100|***00 2.雙交叉點法（用于二進制編碼）

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

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

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

87213 | 95640 98356 | 72104 5.部分匹配交叉（pmx）法（用于互換編碼）

先隨機產(chǎn)生兩個交叉點，定義這兩點間的區(qū)域為匹配區(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ù)碼重復，要依據(jù)匹配區(qū)域內(nèi)的位置逐一進行替換。匹配關系：1<——>５ ３<——>６ ７<——>０ 子代ａ：802 | 567 | 9143 子代ｂ：986 | 130 | 5427 6.順序交叉法(ox)（用于互換編碼）

從父代ａ隨機選一個編碼子串，放到子代ａ的對應位置；子代ａ空余的位置從父代ｂ中按ｂ的順序選取（與己有編碼不重復）。同理可得子代ｂ。父代a: 872 | 139 | 0546 父代b: 983 | 567 | 1420 交叉后：

子代a: 856 | 139 | 7420 子代b: 821 | 567 | 3904 7.循環(huán)交叉（cx）法（用于互換編碼）cx同ox交叉都是從一個親代中取一些城市，而其它城市來自另外一個親代，但是二者不同之處在于：ox中來自第一個親代的編碼子串是隨機產(chǎn)生的，而cx卻不是，它是根據(jù)兩個雙親相應位置的編碼而確定的。

父代ａ：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)的基因構成子代ａ，順序與父代ａ一樣 1 2 4 5 9 用父代ｂ剩余的基因填滿子代ａ： 1 2 6 4 5 3 7 8 9 子代ｂ的編碼同理。（循環(huán)基因 5->1->9->4->2->5）

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

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

第三篇：算法設計與分析學習心得

算法設計與分析學習心得

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

一、實驗內(nèi)容：

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

二、學習掌握：

基本程序描述：

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

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

（3）Mfc：在下拉列表框中添加內(nèi)容程序，在下拉列表對應的函數(shù)中利用addstring添加需要的內(nèi)容。首先定義下拉列表框為ccombox型，并定義其屬性名，利用addstring函數(shù)可以任意添加需要的內(nèi)容。a排序問題:快速排序的運行時間與劃分是否對稱有關，其最壞情況發(fā)生在劃分過程中產(chǎn)生的兩個區(qū)域分別包含n-1個元素和1個元素的時候。其算法的時間復雜度為O(n 2),在最好的情況下每次劃分的基準恰好為中值，可得其算法時間復雜度為O(n㏒n)。算法的實現(xiàn)和理解和代碼實現(xiàn)完全是兩回事，想要完全掌握一種算法，需要動手實踐，用代碼實現(xiàn)，才能理解透徹，真正掌握。b對話框下拉列表：這個項目簡單易懂，輕松實現(xiàn)。三.疑問與總結(jié)：

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

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

四.心得體會

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

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

第四篇：學習心得二

愛能創(chuàng)造新的奇跡

愛可以創(chuàng)造新的生命，愛能創(chuàng)造新的奇跡！前不久看到一部電視劇上的一個哲學教授說的一個故事：1976年唐山大地震，有一對年輕的夫婦面對房屋倒塌，一塊重達千余斤的水泥樓板壓下時，他們?yōu)榱松砼缘男『?，兩雙手竟勇敢地撐起水泥板，直到援救人員的趕到，當救援人員把小孩抱走時，他們再也支持不住，樓板轟然壓下；這個教授還說到有一個母親上街買菜回來遇一鄰居拉家常，住在六樓上的小女兒見媽媽回來，不小心從窗口掉下，其母親見狀，百米沖刺用雙手接住了女兒，女兒得救了，然而母親卻再也沒有醒來。事后有人做過測算，這個母親的跑步速度竟超過消防隊員！為什么？母愛、父愛的偉大！也有人說一個足球運動員那臨射門的一腳，力量可達千斤！哪里來得這么大勁呢？我想，是不是足球運動員那對足球的摯愛，愛的力量！因此我說，愛可以創(chuàng)造生命，愛能創(chuàng)造奇跡！愛能創(chuàng)造教育的輝煌！

剛剛來校上課的第一個星期，我就遇到了一件非常尷尬的事情。學校為了班級的轉(zhuǎn)接，安排了一次周練，其中有一部分學生做的很不理想，當時，我找到這些小孩，講的第一句話就是：看看你們的試卷，好好反思一下為什么會做成這樣？本來我是想給這些學生一個下馬威，并借此樹立自己的威信的，但是，出乎意料的是，立刻就有一個小孩頂撞我，當時我是非常生氣的，但是，事后我當再靜下來好好思考的時候，我覺得自己當時的處理方式確實是很不妥的，于是，事后我又與這位學生進行了一次單獨的交流，這次我變換了一種態(tài)度，我嘗試以朋友的身份與之談話，幫助他尋找學習中的弱點，鼓勵他要克服困難，不斷進步，結(jié)果，這位學生很欣然地接受了我的意見。通過這件事，我認識到要樹立自己的威信，方法其實可以很多，在教育中，暴風驟雨往往不如和風細雨來的有效。經(jīng)過一段時間的摸索，我發(fā)現(xiàn)師生之間的關系應該是一種平等的、友好的朋友關系。

在我原來所教的一（17）班中，有一個小孩被視為是神經(jīng)病，班主任在我接班之前就跟我講，不要去管他。剛開始我沒有在意他，但是通過幾次作業(yè)，發(fā)現(xiàn)有些同學做的不好，于是我想找他們談談，當時正在上晚自習，我叫到解進（當時還不認識他）時，他沒有任何反應，坐在位置上一動不動，我以為他不在，或者沒有聽到，又讓其他學生帶信叫他出來，他仍舊不動，我又去叫了他一次，他還是沒有任何反應，其他同學都朝他笑，他自己也在笑，但是就是一動不動，當時我是非常惱火，因為這將使我在學生心目中的威信全無，于是我找到他嚴肅的要他當面認錯，后來他態(tài)度還較好，主動地向我道歉，我也沒有再說什么。但事后，我冷靜地想了想，也許這個小孩他心理上是有一些障礙，也許在他認為這很好玩，也許他只是想跟我開個玩笑而已吧。于是，我又一次找他交談，經(jīng)過一番談話，我發(fā)現(xiàn)其實這個小孩并非神經(jīng)病，他跟同齡的小孩相比顯得早熟，且把周圍的一切看的太透，可以說在他的心目中，周圍的一切事物，總是陰暗的一面比較多，周圍的人總是很虛偽，所以他不愿意與別人交流，他看不慣周圍的一切。針對這一現(xiàn)象，我與他進行了一些交談，并鼓勵他要好好學習、適應環(huán)境，而不能苛求環(huán)境來適應自己等等，雖然談話時間不長，但是，我的態(tài)度很誠懇，這樣，我很輕松地贏得了學生對我的信任，正所謂“親其師，信其道”。從那以后，這位學生上課特別認真，而且每次見到我總是老遠就打招呼“尹老師，您好”，雖然這只是一個簡單的招呼，但它飽涵了一個學生對老師的一份敬意和愛戴。

發(fā)生在我們身邊的故事還有很多，通過這些活生生的教學案例，我深刻的感受到：教育是心靈的藝術。如果我們承認教育的對象是活生生的人，那么教育過程便絕不僅僅是一種技巧的施展，而應該充滿人情味；教育的每一個環(huán)節(jié)都應該充滿著對人的理解、尊重和感染，應該體現(xiàn)出民主與平等的現(xiàn)代意識。雖然就學科知識、專業(yè)能力、認識水平來說，教師遠在學生之上，但就人格而言，師生之間是天然平等的；教師和學生不但是在人格上、感情上平等的朋友，而且也是在求知道路上共同探索前進的平等的志同道合者。每一個優(yōu)秀的教師都有其與眾不同的一面，但我相信所有優(yōu)秀的教師都有一個共同的特點：那就是充滿了愛心，愛他們的事業(yè)，愛他們的學生

第五篇：專題二學習心得

堅持“四個服從”，以堅毅如鐵的信念詮釋對黨的絕對忠誠學習心得 黨的十八屆六中全會通過的《關于新形勢下黨內(nèi)政治生活的若干準則》，對堅決維護黨中央權威提出一系列明確要求，強調(diào)必須堅持黨員個人服從黨的組織，少數(shù)服從多數(shù)，下級組織服從上級組織，全黨各個組織和全體黨員服從黨的全國代表大會和中央委員會，其意義十分重大?！八膫€服從”既反映了民主又體現(xiàn)了集中，是貫徹落實民主集中制的有效途徑，是黨內(nèi)生活秩序的總概括，是正確處理黨內(nèi)各種關系的基本準則。堅持“四個服從”使我們黨的集中統(tǒng)一領導更加有力，確保了各項決策的有效執(zhí)行。這是我們黨經(jīng)過長期革命斗爭形成的優(yōu)良傳統(tǒng)，一定要長久堅持下去。政治意識、大局意識、核心意識、看齊意識，是相互聯(lián)系的有機整體，與《中國共產(chǎn)黨章程》規(guī)定的“四個服從”一脈相承。黨員個人服從黨的組織，少數(shù)服從多數(shù)，下級組織服從上級組織，全黨各個組織和全體黨員服從黨的全國代表大會和中央委員會，這“四個服從”是黨的民主集中制的基本原則之一，也是黨的紀律建設的核心內(nèi)容。黨的各個組織和全體黨員，只有切實增強“四個意識”，自覺堅持和維護“四個服從”，才能使全黨產(chǎn)生無比的向心力、凝聚力和戰(zhàn)斗力，從而團結(jié)帶領人民協(xié)調(diào)推進全面建成小康社會、全面深化改革、全面依法治國、全面從嚴治黨戰(zhàn)略布局，實現(xiàn)兩個百年奮斗目標和中華民族偉大復興的中國夢。