數(shù)學(xué)建模競賽中應(yīng)當(dāng)掌握的十類算法

1、 蒙特卡羅算法蒙特卡羅算法 數(shù)據(jù)處理算法數(shù)據(jù)處理算法 數(shù)學(xué)規(guī)劃算法數(shù)學(xué)規(guī)劃算法 圖論算法圖論算法 動(dòng)態(tài)規(guī)劃、回溯搜索、分治算法、分支定動(dòng)態(tài)規(guī)劃、回溯搜索、分治算法、分支定界界 三大非經(jīng)典算法三大非經(jīng)典算法 網(wǎng)格算法和窮舉法網(wǎng)格算法和窮舉法 連續(xù)離散化方法連續(xù)離散化方法 數(shù)值分析算法數(shù)值分析算法 圖象處理算法圖象處理算法 該算法又稱隨機(jī)性模擬算法，是通過計(jì)算機(jī)該算法又稱隨機(jī)性模擬算法，是通過計(jì)算機(jī)仿真來解決問題的算法，同時(shí)可以通過模擬仿真來解決問題的算法，同時(shí)可以通過模擬可以來檢驗(yàn)自己模型的正確性，是比賽時(shí)必可以來檢驗(yàn)自己模型的正確性，是比賽時(shí)必用的方法用的方法 蒙特卡羅蒙特卡羅(Monte C

2、arlo)方法，或稱計(jì)算機(jī)方法，或稱計(jì)算機(jī)隨機(jī)模擬方法，是一種基于隨機(jī)模擬方法，是一種基于“隨機(jī)數(shù)隨機(jī)數(shù)”的的計(jì)算方法。這一方法源于美國在第一次世計(jì)算方法。這一方法源于美國在第一次世界大戰(zhàn)進(jìn)研制原子彈的界大戰(zhàn)進(jìn)研制原子彈的“曼哈頓計(jì)劃曼哈頓計(jì)劃”。該計(jì)劃的主持人之一、數(shù)學(xué)家馮該計(jì)劃的主持人之一、數(shù)學(xué)家馮諾伊曼用諾伊曼用馳名世界的賭城馳名世界的賭城摩納哥的摩納哥的Monte Carlo來命名這種方法，為它蒙上了一層神秘色來命名這種方法，為它蒙上了一層神秘色彩。彩。 考慮平面上的一個(gè)邊長為考慮平面上的一個(gè)邊長為1的正方形及其內(nèi)的正方形及其內(nèi)部的一個(gè)形狀不規(guī)則的部的一個(gè)形狀不規(guī)則的“圖形圖形”，如何

3、求，如何求出這個(gè)出這個(gè)“圖形圖形”的面積呢？的面積呢？Monte Carlo方方法是這樣一種法是這樣一種“隨機(jī)化隨機(jī)化”的方法：向該正的方法：向該正方形方形“隨機(jī)地隨機(jī)地”投擲投擲N個(gè)點(diǎn)落于個(gè)點(diǎn)落于“圖形圖形”內(nèi)，內(nèi)，則該則該“圖形圖形”的面積近似為的面積近似為M/N。 另一類形式與另一類形式與Monte Carlo方法相似，但理方法相似，但理論基礎(chǔ)不同的方法論基礎(chǔ)不同的方法“擬蒙特卡羅方法擬蒙特卡羅方法” (Quasi-Monte Carlo方法方法)近年來也獲得近年來也獲得迅速發(fā)展。我國數(shù)學(xué)家華羅庚、王元提出迅速發(fā)展。我國數(shù)學(xué)家華羅庚、王元提出的的“華華王王”方法即是其中的一例。這種方法即

4、是其中的一例。這種方法的基本思想是方法的基本思想是“用確定性的超均勻分用確定性的超均勻分布序列布序列(數(shù)學(xué)上稱為數(shù)學(xué)上稱為Low Discrepancy Sequences)代替代替Monte Carlo方法中的隨方法中的隨機(jī)數(shù)序列。對(duì)某些問題該方法的實(shí)際速度機(jī)數(shù)序列。對(duì)某些問題該方法的實(shí)際速度一般可比一般可比Monte Carlo方法提出高數(shù)百倍，方法提出高數(shù)百倍，并可計(jì)算精確度。并可計(jì)算精確度。具體實(shí)現(xiàn)的matlab代碼：-function val = ballvol(n, m)% BALLVOL Compute volume of unit ball in Rn% Computes th

5、e volume of the n-dimensional unit ball % using monte-carlo method.% usage: val = BallVol(n, m)% where: n = dimension % m = number of realisations% If the second argument is omitted, 1e4 is taken as default for m.% (c) 1998, Rolf Krause, krausemath.fu-berlin.deM = 1e4;error = 0;if(nargin 2), error(w

6、rong number of arguments); endif nargin = 2, M = m; end R = rand(n, M);in = 0;for i=1:Mif(norm(R(:,i),2) = 1.0), in = in+1; endendval = 2n*in/M; 數(shù)據(jù)擬和數(shù)據(jù)擬和: 從給出的一大堆數(shù)據(jù)中找出規(guī)律，從給出的一大堆數(shù)據(jù)中找出規(guī)律，即設(shè)法構(gòu)造一條曲線即設(shè)法構(gòu)造一條曲線(擬和曲線擬和曲線)反映數(shù)據(jù)點(diǎn)反映數(shù)據(jù)點(diǎn)總的趨勢，以消除其局部波動(dòng)?？偟内厔荩韵渚植坎▌?dòng)。 參數(shù)估計(jì)：對(duì)給定的統(tǒng)計(jì)問題，在建立了統(tǒng)參數(shù)估計(jì)：對(duì)給定的統(tǒng)計(jì)問題，在建立了統(tǒng)計(jì)模型以后，我們的任

7、務(wù)就是依據(jù)樣本對(duì)未計(jì)模型以后，我們的任務(wù)就是依據(jù)樣本對(duì)未知總體進(jìn)行各種推斷，參數(shù)估計(jì)是統(tǒng)計(jì)推斷知總體進(jìn)行各種推斷，參數(shù)估計(jì)是統(tǒng)計(jì)推斷的重要內(nèi)容之一。包括點(diǎn)估計(jì)方法、頻率替的重要內(nèi)容之一。包括點(diǎn)估計(jì)方法、頻率替換法、矩法、極大似然估計(jì)法換法、矩法、極大似然估計(jì)法 插值法是函數(shù)逼近的一種重要方法，包括插值法是函數(shù)逼近的一種重要方法，包括多項(xiàng)式插值、分段插值和三角插值多項(xiàng)式插值、分段插值和三角插值 線性規(guī)劃、整數(shù)規(guī)劃、多元規(guī)劃、二次規(guī)線性規(guī)劃、整數(shù)規(guī)劃、多元規(guī)劃、二次規(guī)劃等規(guī)劃類問題（建模競賽大多數(shù)問題屬劃等規(guī)劃類問題（建模競賽大多數(shù)問題屬于最優(yōu)化問題，很多時(shí)候這些問題可以用于最優(yōu)化問題，很多時(shí)候這

8、些問題可以用數(shù)學(xué)規(guī)劃算法來描述，通常使用數(shù)學(xué)規(guī)劃算法來描述，通常使用LindoLindo、LingoLingo軟件實(shí)現(xiàn)）軟件實(shí)現(xiàn)） 這類算法可以分為很多種，包括最短路、這類算法可以分為很多種，包括最短路、網(wǎng)絡(luò)流、二分圖等算法，涉及到圖論的問網(wǎng)絡(luò)流、二分圖等算法，涉及到圖論的問題可以用這些方法解決，需要認(rèn)真準(zhǔn)備題可以用這些方法解決，需要認(rèn)真準(zhǔn)備 這些算法是算法設(shè)計(jì)中比較常用的方法，這些算法是算法設(shè)計(jì)中比較常用的方法，很多場合可以用到競賽中很多場合可以用到競賽中 它建立在最優(yōu)原則的基礎(chǔ)上。采用動(dòng)態(tài)規(guī)它建立在最優(yōu)原則的基礎(chǔ)上。采用動(dòng)態(tài)規(guī)劃方法，可以優(yōu)雅而高效地解決許多用貪劃方法，可以優(yōu)雅而高效地解決

9、許多用貪婪算法或分而治之算法無法解決的問題。婪算法或分而治之算法無法解決的問題。動(dòng)態(tài)規(guī)劃方法在解決背包問題、圖象壓縮、動(dòng)態(tài)規(guī)劃方法在解決背包問題、圖象壓縮、矩陣乘法鏈、最短路徑、無交叉子集和元矩陣乘法鏈、最短路徑、無交叉子集和元件折疊等方面的有很大作用。件折疊等方面的有很大作用。 和貪婪算法一樣，在動(dòng)態(tài)規(guī)劃中，可將一個(gè)和貪婪算法一樣，在動(dòng)態(tài)規(guī)劃中，可將一個(gè)問題的解決方案視為一系列決策的結(jié)果。不問題的解決方案視為一系列決策的結(jié)果。不同的是，在貪婪算法中，每采用一次貪婪準(zhǔn)同的是，在貪婪算法中，每采用一次貪婪準(zhǔn)則便做出一個(gè)不可撤回的決策，而在動(dòng)態(tài)規(guī)則便做出一個(gè)不可撤回的決策，而在動(dòng)態(tài)規(guī)劃中，還要考察

10、每個(gè)最優(yōu)決策序列中是否包劃中，還要考察每個(gè)最優(yōu)決策序列中是否包含一個(gè)最優(yōu)子序列。含一個(gè)最優(yōu)子序列。 尋找問題的解的一種可靠的方法是首先列出所有尋找問題的解的一種可靠的方法是首先列出所有候選解，然后依次檢查每一個(gè)，在檢查完所有或候選解，然后依次檢查每一個(gè)，在檢查完所有或部分候選解后，即可找到所需要的解。理論上，部分候選解后，即可找到所需要的解。理論上，當(dāng)候選解數(shù)量有限并且通過檢查所有或部分候選當(dāng)候選解數(shù)量有限并且通過檢查所有或部分候選解能夠得到所需解時(shí)，上述方法是可行的。不過，解能夠得到所需解時(shí)，上述方法是可行的。不過，在實(shí)際應(yīng)用中，很少使用這種方法，因?yàn)楹蜻x解在實(shí)際應(yīng)用中，很少使用這種方法，因

11、為候選解的數(shù)量通常都非常大（比如指數(shù)級(jí)，甚至是大數(shù)的數(shù)量通常都非常大（比如指數(shù)級(jí)，甚至是大數(shù)階乘），即便采用最快的計(jì)算機(jī)也只能解決規(guī)模階乘），即便采用最快的計(jì)算機(jī)也只能解決規(guī)模很小的問題。對(duì)候選解進(jìn)行系統(tǒng)檢查的方法有多很小的問題。對(duì)候選解進(jìn)行系統(tǒng)檢查的方法有多種，其中回溯和分枝定界法是比較常用的兩種方種，其中回溯和分枝定界法是比較常用的兩種方法。按照這兩種方法對(duì)候選解進(jìn)行系統(tǒng)檢查通常法。按照這兩種方法對(duì)候選解進(jìn)行系統(tǒng)檢查通常會(huì)使問題的求解時(shí)間大大減少（無論對(duì)于最壞情會(huì)使問題的求解時(shí)間大大減少（無論對(duì)于最壞情形還是對(duì)于一般情形）。事實(shí)上，這些方法可以形還是對(duì)于一般情形）。事實(shí)上，這些方法可以使我

12、們避免對(duì)很大的候選解集合進(jìn)行檢查，同時(shí)使我們避免對(duì)很大的候選解集合進(jìn)行檢查，同時(shí)能夠保證算法運(yùn)行結(jié)束時(shí)可以找到所需要的解。能夠保證算法運(yùn)行結(jié)束時(shí)可以找到所需要的解。因此，這些方法通常能夠用來求解規(guī)模很大的問因此，這些方法通常能夠用來求解規(guī)模很大的問題。題。 這種方法被用來設(shè)計(jì)貨箱裝船、背包、最這種方法被用來設(shè)計(jì)貨箱裝船、背包、最大完備子圖、旅行商和電路板排列問題的大完備子圖、旅行商和電路板排列問題的求解算法。求解算法。 回溯（回溯（backtrackingbacktracking）是一種系統(tǒng)地搜索問）是一種系統(tǒng)地搜索問題解答的方法。為了實(shí)現(xiàn)回溯，首先需要為題解答的方法。為了實(shí)現(xiàn)回溯，首先需要為

13、問題定義一個(gè)解空間（問題定義一個(gè)解空間（solution spacesolution space），），這個(gè)空間必須至少包含問題的一個(gè)解（可能這個(gè)空間必須至少包含問題的一個(gè)解（可能是最優(yōu)的）。是最優(yōu)的）。 下一步是組織解空間以便它能被容易地搜索。下一步是組織解空間以便它能被容易地搜索。典型的組織方法是圖或樹。典型的組織方法是圖或樹。 君主和殖民者們所成功運(yùn)用的分而治之策略君主和殖民者們所成功運(yùn)用的分而治之策略也可以運(yùn)用到高效率的計(jì)算機(jī)算法的設(shè)計(jì)過也可以運(yùn)用到高效率的計(jì)算機(jī)算法的設(shè)計(jì)過程中。利用這一策略可以解決如下問題：最程中。利用這一策略可以解決如下問題：最小最大問題、矩陣乘法、殘缺棋盤、排序

14、、小最大問題、矩陣乘法、殘缺棋盤、排序、選擇和計(jì)算一個(gè)幾何問題選擇和計(jì)算一個(gè)幾何問題找出二維空間找出二維空間中距離最近的兩個(gè)點(diǎn)。中距離最近的兩個(gè)點(diǎn)。 分而治之方法與軟件設(shè)計(jì)的模塊化方法非常分而治之方法與軟件設(shè)計(jì)的模塊化方法非常相似。為了解決一個(gè)大的問題，可以：相似。為了解決一個(gè)大的問題，可以： 1) 1) 把它分成兩個(gè)或多個(gè)更小的問題；把它分成兩個(gè)或多個(gè)更小的問題； 2) 2) 分別分別解決每個(gè)小問題；解決每個(gè)小問題； 3) 3) 把各小問題的解答組把各小問題的解答組合起來，即可得到原問題的解答。小問題通合起來，即可得到原問題的解答。小問題通常與原問題相似，可以遞歸地使用分而治之常與原問題相似

15、，可以遞歸地使用分而治之策略來解決。策略來解決。 例例2-1 2-1 找出偽幣找出偽幣 給你一個(gè)裝有給你一個(gè)裝有1 61 6個(gè)硬幣個(gè)硬幣的袋子。的袋子。1 61 6個(gè)硬幣中有一個(gè)是偽造的，并個(gè)硬幣中有一個(gè)是偽造的，并且那個(gè)偽造的硬幣比真的硬幣要輕一些。你且那個(gè)偽造的硬幣比真的硬幣要輕一些。你的任務(wù)是找出這個(gè)偽造的硬幣。為了幫助你的任務(wù)是找出這個(gè)偽造的硬幣。為了幫助你完成這一任務(wù)，將提供一臺(tái)可用來比較兩組完成這一任務(wù)，將提供一臺(tái)可用來比較兩組硬幣重量的儀器，利用這臺(tái)儀器，可以知道硬幣重量的儀器，利用這臺(tái)儀器，可以知道兩組硬幣的重量是否相同。兩組硬幣的重量是否相同。 比較硬幣比較硬幣1 1與硬幣與

16、硬幣2 2的重量。假如硬幣的重量。假如硬幣1 1比硬幣比硬幣2 2輕，則硬幣輕，則硬幣1 1是偽造的；假如硬幣是偽造的；假如硬幣2 2比硬幣比硬幣1 1輕，則硬幣輕，則硬幣2 2是偽造的。這樣就完成了任務(wù)。是偽造的。這樣就完成了任務(wù)。假如兩硬幣重量相等，則比較硬幣假如兩硬幣重量相等，則比較硬幣3 3和硬幣和硬幣4 4。同樣，假如有一個(gè)硬幣輕一些，則尋找偽幣同樣，假如有一個(gè)硬幣輕一些，則尋找偽幣的任務(wù)完成。假如兩硬幣重量相等，則繼續(xù)的任務(wù)完成。假如兩硬幣重量相等，則繼續(xù)比較硬幣比較硬幣5 5和硬幣和硬幣6 6。按照這種方式，可以最。按照這種方式，可以最多通過多通過8 8次比較來判斷偽幣的存在并找

17、出這一次比較來判斷偽幣的存在并找出這一偽幣。偽幣。 假如把假如把1 61 6硬幣的例子看成一個(gè)大的問題。第一步，硬幣的例子看成一個(gè)大的問題。第一步，把這一問題分成兩個(gè)小問題。隨機(jī)選擇把這一問題分成兩個(gè)小問題。隨機(jī)選擇8 8個(gè)硬幣作個(gè)硬幣作為第一組稱為為第一組稱為A A組，剩下的組，剩下的8 8個(gè)硬幣作為第二組稱為個(gè)硬幣作為第二組稱為B B組。這樣，就把組。這樣，就把1 61 6個(gè)硬幣的問題分成兩個(gè)個(gè)硬幣的問題分成兩個(gè)8 8硬幣硬幣的問題來解決。第二步，判斷的問題來解決。第二步，判斷A A和和B B組中是否有偽幣。組中是否有偽幣。可以利用儀器來比較可以利用儀器來比較A A組硬幣和組硬幣和B B組

18、硬幣的重量。假組硬幣的重量。假如兩組硬幣重量相等，則可以判斷偽幣不存在。假如兩組硬幣重量相等，則可以判斷偽幣不存在。假如兩組硬幣重量不相等，則存在偽幣，并且可以判如兩組硬幣重量不相等，則存在偽幣，并且可以判斷它位于較輕的那一組硬幣中。最后，在第三步中，斷它位于較輕的那一組硬幣中。最后，在第三步中，用第二步的結(jié)果得出原先用第二步的結(jié)果得出原先1 61 6個(gè)硬幣問題的答案。個(gè)硬幣問題的答案。若僅僅判斷硬幣是否存在，則第三步非常簡單。無若僅僅判斷硬幣是否存在，則第三步非常簡單。無論論A A組還是組還是B B組中有偽幣，都可以推斷這組中有偽幣，都可以推斷這1 61 6個(gè)硬幣個(gè)硬幣中存在偽幣。因此，僅僅

19、通過一次重量的比較，就中存在偽幣。因此，僅僅通過一次重量的比較，就可以判斷偽幣是否存在?？梢耘袛鄠螏攀欠翊嬖?。 現(xiàn)在假設(shè)需要識(shí)別出這一偽幣。把兩個(gè)或三個(gè)硬幣的情況作現(xiàn)在假設(shè)需要識(shí)別出這一偽幣。把兩個(gè)或三個(gè)硬幣的情況作為不可再分的小問題。注意如果只有一個(gè)硬幣，那么不能判為不可再分的小問題。注意如果只有一個(gè)硬幣，那么不能判斷出它是否就是偽幣。在一個(gè)小問題中，通過將一個(gè)硬幣分?jǐn)喑鏊欠窬褪莻螏?。在一個(gè)小問題中，通過將一個(gè)硬幣分別與其他兩個(gè)硬幣比較，最多比較兩次就可以找到偽幣。這別與其他兩個(gè)硬幣比較，最多比較兩次就可以找到偽幣。這樣，樣，1 61 6硬幣的問題就被分為兩個(gè)硬幣的問題就被分為兩個(gè)8 8硬

20、幣（硬幣（A A組和組和B B組）的問題。組）的問題。通過比較這兩組硬幣的重量，可以判斷偽幣是否存在。如果通過比較這兩組硬幣的重量，可以判斷偽幣是否存在。如果沒有偽幣，則算法終止。否則，繼續(xù)劃分這兩組硬幣來尋找沒有偽幣，則算法終止。否則，繼續(xù)劃分這兩組硬幣來尋找偽幣。假設(shè)偽幣。假設(shè)B B是輕的那一組，因此再把它分成兩組，每組有是輕的那一組，因此再把它分成兩組，每組有4 4個(gè)硬幣。稱其中一組為個(gè)硬幣。稱其中一組為B1B1，另一組為，另一組為B2B2。比較這兩組，肯定。比較這兩組，肯定有一組輕一些。如果有一組輕一些。如果B1B1輕，則偽幣在輕，則偽幣在B1B1中，再將中，再將B1B1又分成兩又分成

21、兩組，每組有兩個(gè)硬幣，稱其中一組為組，每組有兩個(gè)硬幣，稱其中一組為B1aB1a，另一組為，另一組為B1bB1b。比。比較這兩組，可以得到一個(gè)較輕的組。由于這個(gè)組只有兩個(gè)硬較這兩組，可以得到一個(gè)較輕的組。由于這個(gè)組只有兩個(gè)硬幣，因此不必再細(xì)分。比較組中兩個(gè)硬幣的重量，可以立即幣，因此不必再細(xì)分。比較組中兩個(gè)硬幣的重量，可以立即知道哪一個(gè)硬幣輕一些。較輕的硬幣就是所要找的偽幣。知道哪一個(gè)硬幣輕一些。較輕的硬幣就是所要找的偽幣。 類似于回溯法，分枝定界法在搜索解空間時(shí)，也經(jīng)類似于回溯法，分枝定界法在搜索解空間時(shí)，也經(jīng)常使用樹形結(jié)構(gòu)來組織解空間。然而與回溯法不同常使用樹形結(jié)構(gòu)來組織解空間。然而與回溯法

22、不同的是，回溯算法使用深度優(yōu)先方法搜索樹結(jié)構(gòu)，而的是，回溯算法使用深度優(yōu)先方法搜索樹結(jié)構(gòu)，而分枝定界一般用寬度優(yōu)先或最小耗費(fèi)方法來搜索這分枝定界一般用寬度優(yōu)先或最小耗費(fèi)方法來搜索這些樹。本章與第些樹。本章與第1 61 6章所考察的應(yīng)用完全相同，因此，章所考察的應(yīng)用完全相同，因此，可以很容易比較回溯法與分枝定界法的異同。相對(duì)可以很容易比較回溯法與分枝定界法的異同。相對(duì)而言，分枝定界算法的解空間比回溯法大得多，因而言，分枝定界算法的解空間比回溯法大得多，因此當(dāng)內(nèi)存容量有限時(shí)，回溯法成功的可能性更大此當(dāng)內(nèi)存容量有限時(shí)，回溯法成功的可能性更大 分枝定界（分枝定界（branch and boundbra

23、nch and bound）是另一種系統(tǒng)地搜索）是另一種系統(tǒng)地搜索解空間的方法，它與回溯法的主要區(qū)別在于對(duì)解空間的方法，它與回溯法的主要區(qū)別在于對(duì)E-E-節(jié)點(diǎn)節(jié)點(diǎn)的擴(kuò)充方式。每個(gè)活節(jié)點(diǎn)有且僅有一次機(jī)會(huì)變成的擴(kuò)充方式。每個(gè)活節(jié)點(diǎn)有且僅有一次機(jī)會(huì)變成E-E-節(jié)節(jié)點(diǎn)。當(dāng)一個(gè)節(jié)點(diǎn)變?yōu)辄c(diǎn)。當(dāng)一個(gè)節(jié)點(diǎn)變?yōu)镋-E-節(jié)點(diǎn)時(shí)，則生成從該節(jié)點(diǎn)移動(dòng)節(jié)點(diǎn)時(shí)，則生成從該節(jié)點(diǎn)移動(dòng)一步即可到達(dá)的所有新節(jié)點(diǎn)。在生成的節(jié)點(diǎn)中，拋棄一步即可到達(dá)的所有新節(jié)點(diǎn)。在生成的節(jié)點(diǎn)中，拋棄那些不可能導(dǎo)出（最優(yōu)）可行解的節(jié)點(diǎn)，其余節(jié)點(diǎn)加那些不可能導(dǎo)出（最優(yōu)）可行解的節(jié)點(diǎn)，其余節(jié)點(diǎn)加入活節(jié)點(diǎn)表，然后從表中選擇一個(gè)節(jié)點(diǎn)作為下一個(gè)入活節(jié)點(diǎn)表，然后從

24、表中選擇一個(gè)節(jié)點(diǎn)作為下一個(gè)E-E-節(jié)點(diǎn)。從活節(jié)點(diǎn)表中取出所選擇的節(jié)點(diǎn)并進(jìn)行擴(kuò)充，節(jié)點(diǎn)。從活節(jié)點(diǎn)表中取出所選擇的節(jié)點(diǎn)并進(jìn)行擴(kuò)充，直到找到解或活動(dòng)表為空，擴(kuò)充過程才結(jié)束。直到找到解或活動(dòng)表為空，擴(kuò)充過程才結(jié)束。 有兩種常用的方法可用來選擇下一個(gè)有兩種常用的方法可用來選擇下一個(gè)E-E-節(jié)點(diǎn)節(jié)點(diǎn)（雖然也可能存在其他的方法）：（雖然也可能存在其他的方法）： 1) 1) 先進(jìn)先出（先進(jìn)先出（F I F OF I F O） 即從活節(jié)點(diǎn)表中取即從活節(jié)點(diǎn)表中取出節(jié)點(diǎn)的順序與加入節(jié)點(diǎn)的順序相同，因此活出節(jié)點(diǎn)的順序與加入節(jié)點(diǎn)的順序相同，因此活節(jié)點(diǎn)表的性質(zhì)與隊(duì)列相同。節(jié)點(diǎn)表的性質(zhì)與隊(duì)列相同。 2) 2) 最小耗費(fèi)或最

25、大收益法在這種模式中，每最小耗費(fèi)或最大收益法在這種模式中，每個(gè)節(jié)點(diǎn)都有一個(gè)對(duì)應(yīng)的耗費(fèi)或收益。如果查找個(gè)節(jié)點(diǎn)都有一個(gè)對(duì)應(yīng)的耗費(fèi)或收益。如果查找一個(gè)具有最小耗費(fèi)的解，則活節(jié)點(diǎn)表可用最小一個(gè)具有最小耗費(fèi)的解，則活節(jié)點(diǎn)表可用最小堆來建立，下一個(gè)堆來建立，下一個(gè)E-E-節(jié)點(diǎn)就是具有最小耗費(fèi)的節(jié)點(diǎn)就是具有最小耗費(fèi)的活節(jié)點(diǎn)；如果希望搜索一個(gè)具有最大收益的解，活節(jié)點(diǎn)；如果希望搜索一個(gè)具有最大收益的解，則可用最大堆來構(gòu)造活節(jié)點(diǎn)表，下一個(gè)則可用最大堆來構(gòu)造活節(jié)點(diǎn)表，下一個(gè)E-E-節(jié)點(diǎn)節(jié)點(diǎn)是具有最大收益的活節(jié)點(diǎn)。是具有最大收益的活節(jié)點(diǎn)。 模擬退火法（模擬退火法（Simulated AnnealingSimulate

26、d Annealing）是）是KirkpatrickKirkpatrick等人在一九八三年提出并成功地等人在一九八三年提出并成功地應(yīng)用在組合最佳化問題中，它是蒙特卡羅演應(yīng)用在組合最佳化問題中，它是蒙特卡羅演算法的推廣。算法的推廣。 人工神經(jīng)網(wǎng)絡(luò)的基本結(jié)構(gòu)人工神經(jīng)網(wǎng)絡(luò)的基本結(jié)構(gòu): : 遞歸網(wǎng)絡(luò)和前饋遞歸網(wǎng)絡(luò)和前饋網(wǎng)絡(luò)網(wǎng)絡(luò) 人工神經(jīng)網(wǎng)絡(luò)的典型模型有人工神經(jīng)網(wǎng)絡(luò)的典型模型有: :自適應(yīng)諧振理論自適應(yīng)諧振理論(ART)(ART)、 Kohonen Kohonen 網(wǎng)絡(luò)網(wǎng)絡(luò) 、 反向傳播反向傳播(BP)(BP)網(wǎng)網(wǎng)絡(luò)絡(luò) 、 HopfieldHopfield網(wǎng)網(wǎng) 遺傳算法（遺傳算法（ ，簡稱）是以自然選擇

27、和遺傳理論為基礎(chǔ)，將生簡稱）是以自然選擇和遺傳理論為基礎(chǔ)，將生物進(jìn)化過程中適者生存規(guī)則與群體內(nèi)部染色體的隨物進(jìn)化過程中適者生存規(guī)則與群體內(nèi)部染色體的隨機(jī)信息交換機(jī)制相結(jié)合的搜索算法。遺傳算法是具機(jī)信息交換機(jī)制相結(jié)合的搜索算法。遺傳算法是具有有 生成檢測生成檢測 的迭代過程的搜索算法?；玖鞒痰牡^程的搜索算法?；玖鞒倘缛鐖D圖所示?？梢姡z傳算法是一種群體型操作，所示?？梢?，遺傳算法是一種群體型操作，該操作以群體中的所有個(gè)體為對(duì)象。選擇（該操作以群體中的所有個(gè)體為對(duì)象。選擇（）、交叉（）和）、交叉（）和變異（）是遺傳算法的三個(gè)主要變異（）是遺傳算法的三個(gè)主要操作算子。遺傳算法包含如下個(gè)基本要素：參數(shù)操作算子。遺傳算法包含如下個(gè)基本要素：參數(shù)編碼、生成初始群體、適應(yīng)度評(píng)估檢測、選擇、交編碼、生成初始群體、適應(yīng)度評(píng)估檢測、選擇、交叉操作、變異叉操作、變異 網(wǎng)格算法和窮舉法都是暴力搜索最優(yōu)點(diǎn)的網(wǎng)格算法和窮舉法都是暴力搜索最優(yōu)點(diǎn)的算法，在很多競賽題中有應(yīng)用，當(dāng)重點(diǎn)討算法，在很多競賽題中有應(yīng)用，當(dāng)重點(diǎn)討論模型本身而輕視算法的時(shí)候，可以使用論模型本身而輕視算法的時(shí)候，可以使用這種暴力方案，最好使用一些高級(jí)語言作這種暴力方案，最好使用一些高級(jí)語言作