【文章內(nèi)容簡(jiǎn)介】 第六章分支限界法分支限界法的基本思想：分支界限法類(lèi)似與回溯法，也是在問(wèn)題解空間中搜索問(wèn)題解的一種算法。分支界限法與回溯法思想對(duì)比：求解目標(biāo)：回溯法的求解目標(biāo)是找出解空間樹(shù)中滿(mǎn)足約束條件的所有解，而分支限界法的求解目標(biāo)則是找出滿(mǎn)足約束條件的一個(gè)解，或是在滿(mǎn)足約束條件的解中找出在某種意義下的最優(yōu)解。搜索方式的不同：回溯法以深度優(yōu)先的方式搜索解空間樹(shù)，而分支限界法則以廣度優(yōu)先或以最小耗費(fèi)優(yōu)先的方式搜索解空間樹(shù)。在分支限界法中，每一個(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(kuò)展結(jié)點(diǎn)?；罱Y(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn)，就一次性產(chǎn)生其所有兒子結(jié)點(diǎn)。在這些兒子結(jié)點(diǎn)中，導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點(diǎn)被舍棄，其余兒子結(jié)點(diǎn)被加入活結(jié)點(diǎn)表中。此后，從活結(jié)點(diǎn)表中取下一結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，并重復(fù)上述結(jié)點(diǎn)擴(kuò)展過(guò)程。這個(gè)過(guò)程一直持續(xù)到找到所需的解或活結(jié)點(diǎn)表為空時(shí)為止。常見(jiàn)的兩種分支界限法：隊(duì)列式(FIFO)分支限界法：按照隊(duì)列先進(jìn)先出（FIFO）原則選取下一個(gè)節(jié)點(diǎn)為擴(kuò)展節(jié)點(diǎn)。優(yōu)先隊(duì)列式分支限界法：按照優(yōu)先隊(duì)列中規(guī)定的優(yōu)先級(jí)選取優(yōu)先級(jí)最高的節(jié)點(diǎn)成為當(dāng)前擴(kuò)展節(jié)點(diǎn)。最大堆：最大效益優(yōu)先最小堆：最小耗費(fèi)優(yōu)先第五篇：算法學(xué)習(xí)心得算法設(shè)計(jì)與分析學(xué)習(xí)心得班級(jí)：物聯(lián)網(wǎng)1201 姓名：劉瀟 學(xué)號(hào)：1030612129一、實(shí)驗(yàn)內(nèi)容：這學(xué)期的算法與設(shè)計(jì)課，老師布置了這四個(gè)問(wèn)題，分別是貨郎擔(dān)問(wèn)題，動(dòng)態(tài)生成二維數(shù)組，對(duì)話(huà)框下拉列表，排序問(wèn)題。二、學(xué)習(xí)掌握：基本程序描述：（1）貨郎擔(dān)問(wèn)題：貨郎擔(dān)問(wèn)題屬于易于描述但難于解決的著名難題之一，至今世界上還有不少人在研究它。貨郎擔(dān)問(wèn)題要從圖g的所有周游路線(xiàn)中求取具有最小成本的周游路線(xiàn)，而由始點(diǎn)出發(fā)的周游路線(xiàn)一共有（n一1）！條，即等于除始結(jié)點(diǎn)外的n一1個(gè)結(jié)點(diǎn)的排列數(shù)，因此貨郎擔(dān)問(wèn)題是一個(gè)排列問(wèn)題。貨郎擔(dān)的程序?qū)崿F(xiàn)了利用窮舉法解決貨郎擔(dān)問(wèn)題，可以在城市個(gè)數(shù)和各地費(fèi)用給定的情況下利用窮舉法逐一計(jì)算出每一條路線(xiàn)的費(fèi)用，并從中選出費(fèi)用最小的路線(xiàn)。從而求出問(wèn)題的解（2）費(fèi)用矩陣：費(fèi)用矩陣的主要內(nèi)容是動(dòng)態(tài)生成二維數(shù)組。首先由鍵盤(pán)輸入自然數(shù)，費(fèi)用矩陣的元素由隨機(jī)數(shù)產(chǎn)生，并取整，把生成的矩陣存放在二維數(shù)組中，最后把矩陣內(nèi)容輸出到文件和屏幕上。它采用分支界限法，分支限界法的基本思想是對(duì)包含具有約束條件的最優(yōu)化問(wèn)題的所有可行解的解（數(shù)目有限）空間進(jìn)行搜索。該算法在具體執(zhí)行時(shí)，把全部可行的解空間不斷分割為越來(lái)越小的子集，并為每個(gè)子集內(nèi)的解計(jì)算一個(gè)下界或上界。動(dòng)態(tài)生成二維n*n的數(shù)組程序利用指針表示數(shù)組的行和列，并逐一分配空間，在輸入n的數(shù)值后，系統(tǒng)自動(dòng)分配空間，生成n*n的數(shù)組，并產(chǎn)生隨機(jī)數(shù)填充數(shù)組，最后將結(jié)果輸入到指定文件中。：貨郎擔(dān)的問(wèn)題，我認(rèn)為窮舉法相對(duì)比而言是比較初級(jí)的方法，費(fèi)時(shí)耗力，適合在練習(xí)時(shí)選用，但是在實(shí)際問(wèn)題中不建議采用?？唆斔箍柣蛘咂绽锬匪惴ㄇ笕∽钚∩蓸?shù)的方法來(lái)解決貨郎擔(dān)的問(wèn)題是更適合現(xiàn)實(shí)解決問(wèn)題的。我認(rèn)為程序可以用switch函數(shù)來(lái)將函數(shù)分成幾個(gè)部分更人性化，比如分為解決問(wèn)題的的選項(xiàng)，輸出結(jié)果選項(xiàng)，退出程序選項(xiàng)等。再有就是費(fèi)用矩陣的值可以從文件中讀取，而結(jié)果也可以直接放在指定文件中，這樣在實(shí)際應(yīng)用中比較廣泛。動(dòng)態(tài)生成二維數(shù)組的程序我認(rèn)為如果按照規(guī)范性，我的方法是中規(guī)中矩的，畢竟再向下延伸，生成三維的數(shù)組，需要三層的指針來(lái)實(shí)現(xiàn)。但是就程序的簡(jiǎn)化程度和計(jì)算機(jī)處理時(shí)間來(lái)說(shuō)，我認(rèn)為這樣雙層指針的算法有些太占用內(nèi)存，畢竟要給行和列各分配n個(gè)空間。我通過(guò)與同學(xué)的交流，我發(fā)現(xiàn)可以用1位數(shù)組來(lái)實(shí)現(xiàn)二維的n*n的數(shù)組。首先分配n*n的空間，然后通過(guò)循環(huán)在一行的數(shù)據(jù)達(dá)到n時(shí)自動(dòng)換行。這樣程序得到了一定的簡(jiǎn)化，并且減少了一定的內(nèi)存使用。我認(rèn)為這種方法是比較貼合實(shí)際的。在計(jì)算機(jī)軟件專(zhuān)業(yè)中，算法分析與設(shè)計(jì)是一門(mén)非常重要的課程，很多人為它如癡如醉。很多問(wèn)題的解決，程序的編寫(xiě)都要依賴(lài)它，在軟件還是面向過(guò)程的階段，就有程序=算法+數(shù)據(jù)結(jié)構(gòu)這個(gè)公式。算法的學(xué)習(xí)對(duì)于培養(yǎng)一個(gè)人的邏輯思維能力是有極大幫助的，它可以培養(yǎng)我們養(yǎng)成思考分析問(wèn)題，解決問(wèn)題的能力。如果一個(gè)算法有缺陷，或不適合某個(gè)問(wèn)題，執(zhí)行這個(gè)算法將不會(huì)解決這個(gè)問(wèn)題。不同的算法可能用不同的時(shí)間、空間或效率來(lái)完成同樣的任務(wù)。一個(gè)算法的優(yōu)劣可以用空間復(fù)雜性和時(shí)間復(fù)雜度來(lái)衡量。算法可以使用自然語(yǔ)言、偽代碼、流程圖等多種不同的方法來(lái)描述。計(jì)算機(jī)系統(tǒng)中的操作系統(tǒng)、語(yǔ)言編譯系統(tǒng)、數(shù)據(jù)庫(kù)管理系統(tǒng)以及各種各樣的計(jì)算機(jī)應(yīng)用系統(tǒng)中的軟件，都必須使用具體的算法來(lái)實(shí)現(xiàn)。算法設(shè)計(jì)與分析是計(jì)算機(jī)科學(xué)與技術(shù)的一個(gè)核心問(wèn)題。因此，學(xué)習(xí)算法無(wú)疑會(huì)增強(qiáng)自己的競(jìng)爭(zhēng)力，提高自己的修為，為自己增彩。篇二：算法個(gè)人心得算法學(xué)習(xí)心得: 算法這個(gè)詞是在我在大學(xué)第一次c語(yǔ)言課上聽(tīng)到的，當(dāng)時(shí)老師講的是程序=算法+數(shù)據(jù)結(jié)構(gòu)，算法是一個(gè)程序的靈魂。當(dāng)時(shí)我什么也不懂，不知道什么叫數(shù)據(jù)結(jié)構(gòu)，什么叫算法，它們是干什么的我也不明白。然而經(jīng)歷了大學(xué)四年的學(xué)習(xí)，現(xiàn)在的我對(duì)算法有了一個(gè)較為清晰的認(rèn)識(shí)，對(duì)于它的作用也有了深刻的體會(huì)。所謂算法簡(jiǎn)單來(lái)說(shuō)就是指解題方案的準(zhǔn)確而完整的描述，是一系列解決問(wèn)題的清晰指令，也就是說(shuō)算法告訴計(jì)算機(jī)怎么做，以此來(lái)解決問(wèn)題。同一個(gè)問(wèn)題存在多種算法來(lái)解決它，但是這些算法存在著優(yōu)劣之分，好的算法速度快，效率高，占用空間小，差的算法不僅復(fù)雜難懂，而且效率低，對(duì)機(jī)器要求還高，當(dāng)然，有時(shí)候算法之間存在一種互補(bǔ)關(guān)系，有些算法效率高，節(jié)省時(shí)間，但浪費(fèi)空間，另外一些算法可能速度上慢些，但是空間比較節(jié)約，這時(shí)候我們就應(yīng)該根據(jù)實(shí)際要求，和具體情況來(lái)采取相應(yīng)的算法來(lái)解決問(wèn)題。，算法時(shí)間復(fù)雜度分析，算法的漸近時(shí)間復(fù)雜度等內(nèi)容。因?yàn)樗惴ㄖg的比較就是通過(guò)時(shí)間復(fù)雜度和空間復(fù)雜度來(lái)來(lái)比較的，第一章的主要目的就是讓我們學(xué)會(huì)去分析一個(gè)算法的復(fù)雜度，以后就可以通過(guò)對(duì)復(fù)雜度的分析來(lái)評(píng)價(jià)算法的好壞。第二章講的是分治法，任何一個(gè)可以用計(jì)算機(jī)求解的問(wèn)題所需的計(jì)算時(shí)間都與其規(guī)模有關(guān)。問(wèn)題的規(guī)模越小，越容易直接求解，解題所需的計(jì)算時(shí)間也越少，分治法的設(shè)計(jì)思想就是，將一個(gè)難以直接解決的大問(wèn)題，分割成一些規(guī)模較小的相同問(wèn)題，以便各個(gè)擊破，分而治之。在這一章中我們講到了尋找第k個(gè)元素，矩陣相乘，尋找最近點(diǎn)對(duì)等幾個(gè)使用分治法的經(jīng)典例子，最后還將講到了傅里葉變換的問(wèn)題。以前我們學(xué)到的歸并排序，二分搜索其實(shí)也是基于分治法思想的。能采用分治法來(lái)解決的問(wèn)題通常有如下幾個(gè)特征： 1)該問(wèn)題的規(guī)?？s小到一定的程度就可以容易地解決 2)該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題，即該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。3)利用該問(wèn)題分解出的子問(wèn)題的解可以合并為該問(wèn)題的解； 4)該問(wèn)題所分解出的各個(gè)子問(wèn)題是相互獨(dú)立的，即子問(wèn)題之間不包含公共的子子問(wèn)題。在用分治法解決實(shí)際問(wèn)題時(shí)，我們疑問(wèn)究竟各個(gè)子問(wèn)題的規(guī)模應(yīng)該怎樣才為適當(dāng)？從大量實(shí)踐中發(fā)現(xiàn)，在用分治法設(shè)計(jì)算法時(shí)，最好使子問(wèn)題的規(guī)模大致相同。換句話(huà)說(shuō)，將一個(gè)問(wèn)題分成大小相等的k個(gè)子問(wèn)題的處理方法是行之有效的，這就是一種平衡的思想。第三章主要講動(dòng)態(tài)規(guī)劃問(wèn)題。這一章的內(nèi)容我覺(jué)得是算法設(shè)計(jì)思想中最難，也最有趣的這部分。什么叫動(dòng)態(tài)規(guī)劃，動(dòng)態(tài)規(guī)劃的思想是什么？動(dòng)態(tài)規(guī)劃采用自頂向下的方式分析問(wèn)題，自底向上的方式遞推求值，將待求解的問(wèn)題分解成若干個(gè)子問(wèn)題，先求解子問(wèn)題，并把子問(wèn)題的解存儲(chǔ)起來(lái)以便以后用來(lái)計(jì)算所需要求的解。簡(jiǎn)言之，動(dòng)態(tài)規(guī)劃的基本思想就是把全局的問(wèn)題化為局部的問(wèn)題，為了全局最優(yōu)必須局部最優(yōu)?！岸嚯A段決策問(wèn)題是根據(jù)問(wèn)題本身的特點(diǎn)，將其求解的過(guò)程劃分為若干個(gè)相互獨(dú)立又相互聯(lián)系的階段，在每一個(gè)階段都需要做出決策，并且在一個(gè)階段的決策確定以后再轉(zhuǎn)移到下一個(gè)階段，在每一階段選取其最優(yōu)決策，從而實(shí)現(xiàn)整個(gè)過(guò)程總體決策最優(yōu)的目的”（引用）。還記得期末考試中的最后一道關(guān)于任意給定一個(gè)數(shù)，從所給的牌中用最少的牌組成這個(gè)數(shù)，這個(gè)問(wèn)題其實(shí)就可以用動(dòng)態(tài)規(guī)劃來(lái)解決。本科期間，在算法課上老師在動(dòng)態(tài)規(guī)劃這一章不布置的一個(gè)作業(yè)跟這個(gè)題目類(lèi)似，當(dāng)時(shí)的題目是找錢(qián)問(wèn)題，問(wèn)題是這樣描述的：有n種不同面值的硬幣，各硬幣面值存于數(shù)組t[1:n]，現(xiàn)用這些面值的錢(qián)來(lái)找錢(qián)，編程計(jì)算找錢(qián)m的最少硬幣數(shù)及各個(gè)面值。分析如下：假設(shè)對(duì)于i = 1...n1，所需最少的硬幣數(shù)count(i)已知，那么對(duì)于n，所需的硬幣數(shù)為min(count(i)+ count(ni)), i=1...n1。于是一個(gè)直觀(guān)的方法是用遞歸計(jì)算。但是，遞歸過(guò)程中，每次計(jì)算count(i)，都會(huì)重復(fù)計(jì)算 count(1)....count(i1)。這樣時(shí)間復(fù)雜度就是o(n^2)。我們可以從1開(kāi)始記錄下每個(gè)錢(qián)數(shù)所需的硬幣枚數(shù)，避免重復(fù)計(jì)算，為了能夠輸出硬幣序列，我們還需要記錄下每次新加入的硬幣。下面給出用動(dòng)態(tài)規(guī)劃解決此問(wèn)題的遞推式：參數(shù)說(shuō)明： 當(dāng)只用面值為t[1],t[2],?t[n]來(lái)找出錢(qián)j時(shí)，所用的硬幣的最小個(gè)數(shù)記為c(i,j),則c(i,j)的遞推方程為：運(yùn)用這個(gè)遞推式，我們可以從下往上記錄各個(gè)j所需要的應(yīng)兵書(shū)i，最后當(dāng)j=m時(shí)，所對(duì)應(yīng)的i就是我們要求的。第四章講的是集合算法，這一章的內(nèi)容是我第一次接觸，以前沒(méi)有學(xué)過(guò)。這一章主要講了平攤分析，unionfind，finding the depth，以及23樹(shù)等內(nèi)容，平攤分析教會(huì)我們?nèi)绾螐恼w的角度去更精確的分析算法的時(shí)間復(fù)雜度，unionfind sets是一種簡(jiǎn)單的用途廣泛的集合，并查集是若干個(gè)不相交集合，能夠?qū)崿F(xiàn)較快的合并和判斷元素所在集合的操作，一般采取樹(shù)形結(jié)構(gòu)來(lái)存儲(chǔ)并查集，并利用一個(gè)rank數(shù)組來(lái)存儲(chǔ)集合的深度下界，在查找操作時(shí)進(jìn)行路徑壓縮使后續(xù)的查找操作加速，finding the depth 確定深度問(wèn)題。為了既能求得各點(diǎn)在原先樹(shù)中的正確深度、又能使時(shí)間復(fù)雜度較小，需要使用具有路徑壓縮功能的finddepth指令，同時(shí)還需要采取一些輔助手段來(lái)保證深度計(jì)算的正確性。23樹(shù)具有以下幾個(gè)特點(diǎn)：任一內(nèi)結(jié)點(diǎn)（非葉結(jié)點(diǎn)）均有2個(gè)或3個(gè)兒子。從根到每片樹(shù)葉的路徑長(zhǎng)度相等。內(nèi)結(jié)點(diǎn)中只存放便于查找的信息，而葉結(jié)點(diǎn)中存放原始數(shù)據(jù)。第五章主要講了隨機(jī)算法。在隨機(jī)算法中，我們不要求算法對(duì)所有可能的輸入均正確計(jì)算，只要求出現(xiàn)錯(cuò)誤的可能性小到可以忽略的程度。另外我們也不要求對(duì)同一輸入算法每次執(zhí)行時(shí)給出相同的結(jié)果。我們所關(guān)心的是算法在執(zhí)行時(shí)，是否能夠產(chǎn)生真正隨機(jī)的結(jié)果。有不少問(wèn)題，目前只有效率很差的確定性求解算法，但用隨機(jī)算法去求解，可以很快地獲得相當(dāng)可信的結(jié)果。隨機(jī)算法通常分為兩大類(lèi):las vegas算法、monte carlo算法。las vegas算法總是給出正確的結(jié)果，但在少數(shù)應(yīng)用中，可能出現(xiàn)求不出解的情況。此時(shí)需再次調(diào)用算法進(jìn)行計(jì)算， carlo算法通常不能保證計(jì)算出的結(jié)果總是正確，一般只能斷定所給解的正確性不小于p（1/2＜p＜1）。通過(guò)反復(fù)執(zhí)行算法（即以增大算法的執(zhí)行時(shí)間為代價(jià)），能夠使發(fā)生錯(cuò)誤的概率小到可以忽略的程度。第五章還講到素?cái)?shù)測(cè)試，其中介紹了相關(guān)定理，重點(diǎn)講了millerrabin算法。第六章介紹了計(jì)算模型，這一章主要介紹了有關(guān)計(jì)算的一些本質(zhì)問(wèn)題，random access machines(隨機(jī)存取機(jī)，簡(jiǎn)稱(chēng)ram)，存儲(chǔ)程序模型rasp（random access stored program），圖靈機(jī)（turning machine）以及各個(gè)計(jì)算模型之間的關(guān)系。第七章介紹了np完全問(wèn)題，主要包括近似算法（approximation algorithms），非確定性turing機(jī) ndtm，確定性turing機(jī) dtm，以及之間的區(qū)別，np完全經(jīng)典問(wèn)題等內(nèi)容。經(jīng)過(guò)一學(xué)期的算法學(xué)習(xí)，我對(duì)算法的了解進(jìn)一步加深，曾經(jīng)學(xué)習(xí)過(guò)的內(nèi)容得到進(jìn)一步鞏固，同時(shí)沒(méi)有接觸的內(nèi)容也讓我有了新的認(rèn)識(shí)。作為一名計(jì)算機(jī)專(zhuān)業(yè)的學(xué)生，算法是一門(mén)基礎(chǔ)學(xué)科，它里面包含的思想無(wú)處不在，學(xué)好算法分析，對(duì)于在自己的方向上獲得啟示，體會(huì)更深有著重大作用。所以，我們應(yīng)該培養(yǎng)對(duì)算法的興趣，將算法的運(yùn)用融入到生活當(dāng)中，比如找錢(qián)問(wèn)題就是個(gè)很好的例子，通過(guò)具體的生活實(shí)例來(lái)讓算法變得更加有魅力，有吸引力,以此來(lái)激發(fā)對(duì)算法的興趣。篇三：算法設(shè)計(jì)與分析學(xué)習(xí)總結(jié) 算法分析與設(shè)計(jì) 學(xué)