數(shù)學建模競賽中應當掌握的十類算法

數(shù)學建模競賽中應當掌握的十類算法蒙特卡羅算法數(shù)據(jù)處理算法數(shù)學規(guī)劃算法圖論算法動態(tài)規(guī)劃、回溯搜索、分治算法、分支定界三大非經典算法網格算法和窮舉法連續(xù)離散化方法數(shù)值分析算法圖象處理算法第2頁,共34頁，星期六，2024年，5月1、蒙特卡羅算法

該算法又稱隨機性模擬算法，是通過計算機仿真來解決問題的算法，同時可以通過模擬可以來檢驗自己模型的正確性，是比賽時必用的方法第3頁,共34頁，星期六，2024年，5月

蒙特卡羅(MonteCarlo)方法，或稱計算機隨機模擬方法，是一種基于“隨機數(shù)”的計算方法。這一方法源于美國在第一次世界大戰(zhàn)進研制原子彈的“曼哈頓計劃”。該計劃的主持人之一、數(shù)學家馮·諾伊曼用馳名世界的賭城—摩納哥的MonteCarlo—來命名這種方法，為它蒙上了一層神秘色彩。第4頁,共34頁，星期六，2024年，5月

考慮平面上的一個邊長為1的正方形及其內部的一個形狀不規(guī)則的“圖形”，如何求出這個“圖形”的面積呢？MonteCarlo方法是這樣一種“隨機化”的方法：向該正方形“隨機地”投擲N個點落于“圖形”內，則該“圖形”的面積近似為M/N。第5頁,共34頁，星期六，2024年，5月

另一類形式與MonteCarlo方法相似，但理論基礎不同的方法—“擬蒙特卡羅方法”

(Quasi-MonteCarlo方法)—近年來也獲得迅速發(fā)展。我國數(shù)學家華羅庚、王元提出的“華—王”方法即是其中的一例。這種方法的基本思想是“用確定性的超均勻分布序列(數(shù)學上稱為LowDiscrepancySequences)代替MonteCarlo方法中的隨機數(shù)序列。對某些問題該方法的實際速度一般可比MonteCarlo方法提出高數(shù)百倍，并可計算精確度。第6頁,共34頁，星期六，2024年，5月具體實現(xiàn)的matlab代碼：---------------------------------------------------------------------------------------------------functionval=ballvol(n,m)%BALLVOLComputevolumeofunitballinR^n%%Computesthevolumeofthen-dimensionalunitball%usingmonte-carlomethod.%usage:val=BallVol(n,m)%where:n=dimension%m=numberofrealisations%Ifthesecondargumentisomitted,1e4istakenasdefaultform.%(c)1998,RolfKrause,krause@math.fu-berlin.deM=1e4;error=0;if(nargin<1|nargin>2),error('wrongnumberofarguments');endifnargin==2,M=m;endR=rand(n,M);in=0;fori=1:Mif(norm(R(:,i),2)<=1.0),in=in+1;endendval=2^n*in/M;第7頁,共34頁，星期六，2024年，5月2、數(shù)據(jù)擬合、參數(shù)估計、插值等數(shù)據(jù)處理算法

數(shù)據(jù)擬和:從給出的一大堆數(shù)據(jù)中找出規(guī)律，即設法構造一條曲線(擬和曲線)反映數(shù)據(jù)點總的趨勢，以消除其局部波動。參數(shù)估計：對給定的統(tǒng)計問題，在建立了統(tǒng)計模型以后，我們的任務就是依據(jù)樣本對未知總體進行各種推斷，參數(shù)估計是統(tǒng)計推斷的重要內容之一。包括點估計方法、頻率替換法、矩法、極大似然估計法插值法是函數(shù)逼近的一種重要方法，包括多項式插值、分段插值和三角插值第8頁,共34頁，星期六，2024年，5月3、數(shù)學規(guī)劃算法

線性規(guī)劃、整數(shù)規(guī)劃、多元規(guī)劃、二次規(guī)劃等規(guī)劃類問題（建模競賽大多數(shù)問題屬于最優(yōu)化問題，很多時候這些問題可以用數(shù)學規(guī)劃算法來描述，通常使用Lindo、Lingo軟件實現(xiàn)）

第9頁,共34頁，星期六，2024年，5月4、圖論算法

這類算法可以分為很多種，包括最短路、網絡流、二分圖等算法，涉及到圖論的問題可以用這些方法解決，需要認真準備第10頁,共34頁，星期六，2024年，5月5、動態(tài)規(guī)劃、回溯搜索、分治算法、分支定界

這些算法是算法設計中比較常用的方法，很多場合可以用到競賽中第11頁,共34頁，星期六，2024年，5月動態(tài)規(guī)劃

它建立在最優(yōu)原則的基礎上。采用動態(tài)規(guī)劃方法，可以優(yōu)雅而高效地解決許多用貪婪算法或分而治之算法無法解決的問題。動態(tài)規(guī)劃方法在解決背包問題、圖象壓縮、矩陣乘法鏈、最短路徑、無交叉子集和元件折疊等方面的有很大作用。第12頁,共34頁，星期六，2024年，5月算法思想

和貪婪算法一樣，在動態(tài)規(guī)劃中，可將一個問題的解決方案視為一系列決策的結果。不同的是，在貪婪算法中，每采用一次貪婪準則便做出一個不可撤回的決策，而在動態(tài)規(guī)劃中，還要考察每個最優(yōu)決策序列中是否包含一個最優(yōu)子序列。

第13頁,共34頁，星期六，2024年，5月

尋找問題的解的一種可靠的方法是首先列出所有候選解，然后依次檢查每一個，在檢查完所有或部分候選解后，即可找到所需要的解。理論上，當候選解數(shù)量有限并且通過檢查所有或部分候選解能夠得到所需解時，上述方法是可行的。不過，在實際應用中，很少使用這種方法，因為候選解的數(shù)量通常都非常大（比如指數(shù)級，甚至是大數(shù)階乘），即便采用最快的計算機也只能解決規(guī)模很小的問題。對候選解進行系統(tǒng)檢查的方法有多種，其中回溯和分枝定界法是比較常用的兩種方法。按照這兩種方法對候選解進行系統(tǒng)檢查通常會使問題的求解時間大大減少（無論對于最壞情形還是對于一般情形）。事實上，這些方法可以使我們避免對很大的候選解集合進行檢查，同時能夠保證算法運行結束時可以找到所需要的解。因此，這些方法通常能夠用來求解規(guī)模很大的問題。第14頁,共34頁，星期六，2024年，5月

回溯方法

這種方法被用來設計貨箱裝船、背包、最大完備子圖、旅行商和電路板排列問題的求解算法。第15頁,共34頁，星期六，2024年，5月算法思想

回溯（backtracking）是一種系統(tǒng)地搜索問題解答的方法。為了實現(xiàn)回溯，首先需要為問題定義一個解空間（solutionspace），這個空間必須至少包含問題的一個解（可能是最優(yōu)的）。下一步是組織解空間以便它能被容易地搜索。典型的組織方法是圖或樹。第16頁,共34頁，星期六，2024年，5月分治算法

君主和殖民者們所成功運用的分而治之策略也可以運用到高效率的計算機算法的設計過程中。利用這一策略可以解決如下問題：最小最大問題、矩陣乘法、殘缺棋盤、排序、選擇和計算一個幾何問題——找出二維空間中距離最近的兩個點。

第17頁,共34頁，星期六，2024年，5月算法思想

分而治之方法與軟件設計的模塊化方法非常相似。為了解決一個大的問題，可以：1)把它分成兩個或多個更小的問題；2)分別解決每個小問題；3)把各小問題的解答組合起來，即可得到原問題的解答。小問題通常與原問題相似，可以遞歸地使用分而治之策略來解決。第18頁,共34頁，星期六，2024年，5月

例2-1[找出偽幣]給你一個裝有16個硬幣的袋子。16個硬幣中有一個是偽造的，并且那個偽造的硬幣比真的硬幣要輕一些。你的任務是找出這個偽造的硬幣。為了幫助你完成這一任務，將提供一臺可用來比較兩組硬幣重量的儀器，利用這臺儀器，可以知道兩組硬幣的重量是否相同。第19頁,共34頁，星期六，2024年，5月

比較硬幣1與硬幣2的重量。假如硬幣1比硬幣2輕，則硬幣1是偽造的；假如硬幣2比硬幣1輕，則硬幣2是偽造的。這樣就完成了任務。假如兩硬幣重量相等，則比較硬幣3和硬幣4。同樣，假如有一個硬幣輕一些，則尋找偽幣的任務完成。假如兩硬幣重量相等，則繼續(xù)比較硬幣5和硬幣6。按照這種方式，可以最多通過8次比較來判斷偽幣的存在并找出這一偽幣。第20頁,共34頁，星期六，2024年，5月

假如把16硬幣的例子看成一個大的問題。第一步，把這一問題分成兩個小問題。隨機選擇8個硬幣作為第一組稱為A組，剩下的8個硬幣作為第二組稱為B組。這樣，就把16個硬幣的問題分成兩個8硬幣的問題來解決。第二步，判斷A和B組中是否有偽幣?？梢岳脙x器來比較A組硬幣和B組硬幣的重量。假如兩組硬幣重量相等，則可以判斷偽幣不存在。假如兩組硬幣重量不相等，則存在偽幣，并且可以判斷它位于較輕的那一組硬幣中。最后，在第三步中，用第二步的結果得出原先16個硬幣問題的答案。若僅僅判斷硬幣是否存在，則第三步非常簡單。無論A組還是B組中有偽幣，都可以推斷這16個硬幣中存在偽幣。因此，僅僅通過一次重量的比較，就可以判斷偽幣是否存在。第21頁,共34頁，星期六，2024年，5月

現(xiàn)在假設需要識別出這一偽幣。把兩個或三個硬幣的情況作為不可再分的小問題。注意如果只有一個硬幣，那么不能判斷出它是否就是偽幣。在一個小問題中，通過將一個硬幣分別與其他兩個硬幣比較，最多比較兩次就可以找到偽幣。這樣，16硬幣的問題就被分為兩個8硬幣（A組和B組）的問題。通過比較這兩組硬幣的重量，可以判斷偽幣是否存在。如果沒有偽幣，則算法終止。否則，繼續(xù)劃分這兩組硬幣來尋找偽幣。假設B是輕的那一組，因此再把它分成兩組，每組有4個硬幣。稱其中一組為B1，另一組為B2。比較這兩組，肯定有一組輕一些。如果B1輕，則偽幣在B1中，再將B1又分成兩組，每組有兩個硬幣，稱其中一組為B1a，另一組為B1b。比較這兩組，可以得到一個較輕的組。由于這個組只有兩個硬幣，因此不必再細分。比較組中兩個硬幣的重量，可以立即知道哪一個硬幣輕一些。較輕的硬幣就是所要找的偽幣。第22頁,共34頁，星期六，2024年，5月分枝定界

類似于回溯法，分枝定界法在搜索解空間時，也經常使用樹形結構來組織解空間。然而與回溯法不同的是，回溯算法使用深度優(yōu)先方法搜索樹結構，而分枝定界一般用寬度優(yōu)先或最小耗費方法來搜索這些樹。本章與第16章所考察的應用完全相同，因此，可以很容易比較回溯法與分枝定界法的異同。相對而言，分枝定界算法的解空間比回溯法大得多，因此當內存容量有限時，回溯法成功的可能性更大

第23頁,共34頁，星期六，2024年，5月算法思想

分枝定界（branchandbound）是另一種系統(tǒng)地搜索解空間的方法，它與回溯法的主要區(qū)別在于對E-節(jié)點的擴充方式。每個活節(jié)點有且僅有一次機會變成E-節(jié)點。當一個節(jié)點變?yōu)镋-節(jié)點時，則生成從該節(jié)點移動一步即可到達的所有新節(jié)點。在生成的節(jié)點中，拋棄那些不可能導出（最優(yōu)）可行解的節(jié)點，其余節(jié)點加入活節(jié)點表，然后從表中選擇一個節(jié)點作為下一個E-節(jié)點。從活節(jié)點表中取出所選擇的節(jié)點并進行擴充，直到找到解或活動表為空，擴充過程才結束。第24頁,共34頁，星期六，2024年，5月

有兩種常用的方法可用來選擇下一個E-節(jié)點（雖然也可能存在其他的方法）：

1)先進先出（FIFO）即從活節(jié)點表中取出節(jié)點的順序與加入節(jié)點的順序相同，因此活節(jié)點表的性質與隊列相同。

2)最小耗費或最大收益法在這種模式中，每個節(jié)點都有一個對應的耗費或收益。如果查找一個具有最小耗費的解，則活節(jié)點表可用最小堆來建立，下一個E-節(jié)點就是具有最小耗費的活節(jié)點；如果希望搜索一個具有最大收益的解，則可用最大堆來構造活節(jié)點表，下一個E-節(jié)點是具有最大收益的活節(jié)點。第25頁,共34頁，星期六，2024年，5月6、模擬退火法、神經網絡、遺傳算法

模擬退火法（SimulatedAnnealing）是Kirkpatrick等人在一九八三年提出并成功地應用在組合最佳化問題中，它是蒙特卡羅演算法的推廣。人工神經網絡的基本結構:遞歸網絡和前饋網絡人工神經網絡的典型模型有:自適應諧振理論(ART)、Kohonen網絡、反向傳播(BP)網絡、Hopfield網第26頁,共34頁，星期六，2024年，5月

遺傳算法（ＧｅｎｅｔｉｃＡｌｇｏｒｉｔｍｓ，簡稱ＧＡ）是以自然選擇和遺傳理論為基礎，將生物進化過程中適者生存規(guī)則與群體內部染色體的隨機信息交換機制相結合的搜索算法。遺傳算法是具有"生成＋檢測"的迭代過程的搜索算法?；玖鞒倘鐖D１所示。可見，遺傳算法是一種群體型操作，該操作以群體中的所有個體為對象。選擇（ｓｅｌｅｃｔｉｏｎ）、交叉（ｃｒｏｓｓｏｖｅｒ）和變異（ｍｕｔａｔｉｏｎ）是遺傳算法的三個主要操作算子。遺傳算法包含如下６個基本要素：參數(shù)編碼、生成初始群體、適應度評估檢測、選擇、交叉操作、變異第27頁,共34頁，星期六，2024年，5月第28頁,共34頁，星期六，2024年，5月7、網格算法和窮舉法

網格算法和窮舉法都是暴力搜索最優(yōu)點的算法，在很多競賽題中有應用，當重點討論模型本身而輕視算法的時候，可以使用這種暴力方案，最好使用一些高級語言作為編程工具第