【正文】 From clown studio建模十大經(jīng)典算法 蒙特卡羅算法。該算法又稱隨機性模擬算法，是通過計算機仿真來解決問題的算法，同時通過模擬可以來檢驗自己模型的正確性。 數(shù)據(jù)擬合、參數(shù)估計、插值等數(shù)據(jù)處理算法。比賽中通常會遇到大量的數(shù)據(jù)需要處理，而處理數(shù)據(jù)的關(guān)鍵就在于這些算法，通常使用Matlab作為工具。線性規(guī)劃、整數(shù)規(guī)劃、多元規(guī)劃、二次規(guī)劃等規(guī)劃類問題。建模競賽大多數(shù)問題屬于最優(yōu)化問題，很多時候這些問題可以用數(shù)學(xué)規(guī)劃算法來描述，通常使用Lindo、Lingo、MATLAB軟件實現(xiàn)。 圖論算法。這類算法可以分為很多種，包括最短路、網(wǎng)絡(luò)流、二分圖等算法，涉及到圖論的問題可以用這些方法解決，需要認(rèn)真準(zhǔn)備。 動態(tài)規(guī)劃、回溯搜索、分治算法、分支定界等計算機算法。這些算法是算法設(shè)計中比較常用的方法，很多場合可以用到競賽中。 最優(yōu)化理論的三大非經(jīng)典算法：模擬退火法、神經(jīng)網(wǎng)絡(luò)、遺傳算法。這些問題是用來解決一些較困難的最優(yōu)化問題的算法，對于有些問題非常有幫助，但是算法的實現(xiàn)比較困難，需慎重使用。 網(wǎng)格算法和窮舉法。網(wǎng)格算法和窮舉法都是暴力搜索最優(yōu)點的算法，在很多競賽題中有應(yīng)用，當(dāng)重點討論模型本身而輕視算法的時候，可以使用這種暴力方案，最好使用一些高級語言作為編程工具。 一些連續(xù)離散化方法。很多問題都是實際來的，數(shù)據(jù)可以是連續(xù)的，而計算機只認(rèn)的是離散的數(shù)據(jù)，因此將其離散化后進行差分代替微分、求和代替積分等思想是非常重要的。 數(shù)值分析算法。如果在比賽中采用高級語言進行編程的話，那一些數(shù)值分析中常用的算法比如方程組求解、矩陣運算、函數(shù)積分等算法就需要額外編寫庫函數(shù)進行調(diào)用。 圖象處理算法。賽題中有一類問題與圖形有關(guān)，即使與圖形無關(guān)，論文中也應(yīng)該要不乏圖片的，這些圖形如何展示以及如何處理就是需要解決的問題，通常使用Matlab進行處理。 歷年全國數(shù)學(xué)建模試題及解法賽題 解法 93A非線性交調(diào)的頻率設(shè)計 擬合、規(guī)劃 93B足球隊排名 圖論、層次分析、整數(shù)規(guī)劃 94A逢山開路 圖論、插值、動態(tài)規(guī)劃 94B鎖具裝箱問題 圖論、組合數(shù)學(xué) 95A飛行管理問題 非線性規(guī)劃、線性規(guī)劃 95B天車與冶煉爐的作業(yè)調(diào)度 動態(tài)規(guī)劃、排隊論、圖論 96A最優(yōu)捕魚策略 微分方程、優(yōu)化 96B節(jié)水洗衣機 非線性規(guī)劃 97A零件的參數(shù)設(shè)計 非線性規(guī)劃 97B截斷切割的最優(yōu)排列 隨機模擬、圖論 98A一類投資組合問題 多目標(biāo)優(yōu)化、非線性規(guī)劃 98B災(zāi)情巡視的最佳路線 圖論、組合優(yōu)化 99A自動化車床管理 隨機優(yōu)化、計算機模擬 99B鉆井布局 01規(guī)劃、圖論 00ADNA序列分類 模式識別、Fisher判別、人工神經(jīng)網(wǎng)絡(luò) 00B鋼管訂購和運輸 組合優(yōu)化、運輸問題 01A血管三維重建 曲線擬合、曲面重建 01B公交車調(diào)度問題 多目標(biāo)規(guī)劃 02A車燈線光源的優(yōu)化 非線性規(guī)劃 02B彩票問題 單目標(biāo)決策 03ASARS的傳播 微分方程、差分方程 03B露天礦生產(chǎn)的車輛安排 整數(shù)規(guī)劃、運輸問題 04A奧運會臨時超市網(wǎng)點設(shè)計 統(tǒng)計分析、數(shù)據(jù)處理、優(yōu)化 04B電力市場的輸電阻塞管理 數(shù)據(jù)擬合、優(yōu)化 05A長江水質(zhì)的評價和預(yù)測 預(yù)測評價、數(shù)據(jù)處理 05BDVD在線租賃 隨機規(guī)劃、整數(shù)規(guī)劃 06A出版資源配置 06B艾滋病療法的評價及療效的預(yù)測07A中國人口增長預(yù)測 07B乘公交，看奧運 多目標(biāo)規(guī)劃 數(shù)據(jù)處理 圖論 08A數(shù)碼相機定位 08B高等教育學(xué)費標(biāo)準(zhǔn)探討09A制動器試驗臺的控制方法分析 09B眼科病床的合理安排 動態(tài)規(guī)劃 10A10B賽題發(fā)展的特點： ：賽題的解決依賴計算機，題目的數(shù)據(jù)較多，手工計算不能完成，如03B，某些問題需要使用計算機軟件，01A。問題的數(shù)據(jù)讀取需要計算機技術(shù)，如00A（大數(shù)據(jù)），01A（圖象數(shù)據(jù)，圖象處理的方法獲得），04A（數(shù)據(jù)庫數(shù)據(jù)，數(shù)據(jù)庫方法，統(tǒng)計軟件包）。計算機模擬和以算法形式給出最終結(jié)果。 解法的多樣性，一道賽題可用多種解法。開放性還表現(xiàn)在對模型假設(shè)和對數(shù)據(jù)處理上。 從歷年競賽題來看，常用的方法：線性規(guī)劃 整數(shù)規(guī)劃 非線性規(guī)劃 動態(tài)規(guī)劃 層次分析法圖論方法 擬合方法 插值方法 隨機方法 微分方程方法各種算法的詳解一、蒙特卡洛算法含義的理解　　以概率和統(tǒng)計理論方法為基礎(chǔ)的一種計算方法。也稱統(tǒng)計模擬方法，是指使用隨機數(shù)（或更常見的偽隨機數(shù)）來解決很多計算問題的方法，它是將所求解的問題同一定的概率模型相聯(lián)系，用計算機實現(xiàn)統(tǒng)計模擬或抽樣，以獲得問題的近似解。 算法實例（有很多相似的例題，包括平行線等）在數(shù)值積分法中，利用求單位圓的1/4的面積來求得Pi/4從而得到Pi。單位圓的1/4面積是一個扇形，它是邊長為1單位正方形的一部分。只要能求出扇形面積S1在正方形面積S中占的比例K=S1/S就立即能得到S1，從而得到Pi的值。怎樣求出扇形面積在正方形面積中占的比例K呢？一個辦法是在正方形中隨機投入很多點，使所投的點落在正方形中每一個位置的機會相等看其中有多少個點落在扇形內(nèi)。將落在扇形內(nèi)的點數(shù)m與所投點的總數(shù)n的比m/n作為k的近似值。P落在扇形內(nèi)的充要條件是 。已知：K=，K，s=1，s1=，求Pi。由，知s1=，而s1=，則Pi=程序：（該算法可以修改后用Mathematica計算或者Matlab）/* 利用蒙特卡洛算法近似求圓周率Pi*/ /*程序使用：VC++ */ include include include define COUNT 800 /*循環(huán)取樣次數(shù)，每次取樣范圍依次變大*/ void main() { double x,y。 int num=0。 int i。 for(i=0。iCOUNT。i++) { x=rand()*。/*RAND_MAX=32767，包含在中*/ y=rand()*。 if((x*x+y*y)=1) num++。 /*統(tǒng)計落在四分之一圓之內(nèi)的點數(shù)*/} printf(Pi值等于：%f\n,num*)。 }結(jié)果：測試6次的結(jié)果顯示：循環(huán)取樣次數(shù)求得的Pi值800800080000800000800000080000000可以看出:隨著點數(shù)的增加，求得的Pi值漸漸接近真實值。如果加入程序：srand(time(NULL))。 ，同時循環(huán)取樣次數(shù)一定，讓取樣結(jié)果隨時間變化，當(dāng)取樣次數(shù)為80000000時，可得6次的結(jié)果顯示： 應(yīng)用的范圍蒙特卡羅方法在金融工程學(xué)，宏觀經(jīng)濟學(xué)，計算物理學(xué)(如粒子輸運計算、量子熱力學(xué)計算、空氣動力學(xué)計算)等領(lǐng)域應(yīng)用廣泛。參考書籍[1]蒙特卡羅方法及其在粒子輸運問題中的應(yīng)用 [2]蒙特卡羅方法引論二、數(shù)據(jù)擬合、參數(shù)估計、插值等數(shù)據(jù)處理算法（1）數(shù)據(jù)擬合在Mathematica中，用Fit對數(shù)據(jù)進行最小二乘擬合：Fit[data,funs,vars]在Matlab中，工具箱（toolboxes）中有曲線擬合工具（curve Fitting）。實例：2010年蘇北賽B題 溫室中的綠色生態(tài)臭氧病蟲害防治 中關(guān)于中華稻蝗密度與水稻減產(chǎn)率之間的關(guān)系可以通過數(shù)據(jù)擬合來觀察（簡單舉例，沒有考慮全部數(shù)據(jù)）數(shù)據(jù)：密度（頭/m2）310203040減產(chǎn)率（%）程序（Mathematica）：data={{3,},{10,},{20,},{30,},{40,}}。a1=Fit[data,{1,x,x^2,x^3},x]Show[ListPlot[data,FillingAxis],Plot[{a1},{x,0,60}]]結(jié)果：+ x2+ x3（2）參數(shù)估計（參考書：概率論與數(shù)理統(tǒng)計）參數(shù)估計為統(tǒng)計推斷的基本問題，分為點估計和區(qū)間估計。點估計：①矩估計法X連續(xù)型隨機變量，概率密度X為離散型隨機變量 分布律為待估參數(shù)，是來自X的樣本，假設(shè)總體X的前階矩存在，為（X連續(xù)型）或（X離散型）（其中是X可能取值的范圍）。一般來說，它們是的函數(shù)?；跇颖揪匾栏怕适諗坑谙鄳?yīng)的總體矩，樣本矩的連續(xù)函數(shù)依概率收斂于相應(yīng)的總體矩的連續(xù)函數(shù)，我們就用樣本矩作為相應(yīng)的總體矩的估計量，而以樣本矩的連續(xù)函數(shù)作為相應(yīng)的總體矩的連續(xù)函數(shù)的估計量。這種估計方法成為矩估計法。②最大似然估計法X連續(xù)型隨機變量 似然函數(shù) 其中是來自X的樣本的聯(lián)合密度。X為離散型隨機變量 似然函數(shù) 其中是來自X的樣本的聯(lián)合分布律。若則稱為的最大似然估計值，稱為的最大似然估計量。這樣，確定最大似然估計量的問題就歸結(jié)為微分學(xué)中的求最大值的問題了。估計量的評選標(biāo)準(zhǔn)為：（1）無偏性（2）有效性（3）相合性區(qū)間估計：對于一個未知量，人們在測量或計算時，常不以得到近似值為滿足，還需要估計誤差，即要求知道近似值的精確程度（亦即所求真值所在的范圍）。這樣的范圍常以區(qū)間的形式給出，同時還給出此區(qū)間包含參數(shù)真值的可信度，這種形式的估計稱為區(qū)間估計，這樣的區(qū)間即所謂置信區(qū)間。正態(tài)總體均值、方差的置信區(qū)間與單側(cè)置信限（置信水平為1）一個正態(tài)總體未知參數(shù)其他參數(shù)樞軸量的分布置信區(qū)間已知未知未知另外還包括兩個正態(tài)總體的情況，其他區(qū)間估計：（01）分布參數(shù)的區(qū)間估計（3）插值含義的理解在離散數(shù)據(jù)的基礎(chǔ)上補插連續(xù)函數(shù)，使得這條連續(xù)曲線通過全部給定的離散數(shù)據(jù)點。插值是離散函數(shù)逼近的重要方法，利用它可通過函數(shù)在有限個點處的取值狀況，估算出函數(shù)在其他點處的近似值（與擬合的不同點在于擬合的函數(shù)不需通過每一個離散點）。插值問題的提法是：假定區(qū)間[a，b］上的實值函數(shù)f（x）在該區(qū)間上 n＋1個互不相同點x0，x1…xn 處的值是f [x0］，…f（xn），要求估算f（x）在[a，b］中某點的值。其做法是：在事先選定的一個由簡單函數(shù)構(gòu)成的有n＋1個參數(shù)C0，C1，…Cn的函數(shù)類Φ(C0，C1，…Cn)中求出滿足條件P（xi）＝f（xi）（i＝0，1，… n）的函數(shù)P(x)，并以P()作為f()的估值。此處f（x）稱為被插值函數(shù)，x0，x1，…xn稱為插值結(jié)(節(jié))點，Φ(C0，C1，…Cn)稱為插值函數(shù)類，上面等式稱為插值條件，Φ（C0，…Cn）中滿足上式的函數(shù)稱為插值函數(shù)，R（x）＝ f（x）－P（x）稱為插值余項。當(dāng)估算點屬于包含x0，x1…xn的最小閉區(qū)間時，相應(yīng)的插值稱為內(nèi)插，否則稱為外插?；绢愋投囗検讲逯翟谝话悴逯祮栴}中，若選取Φ為n次多項式類，由插值條件可以唯一確定一個n次插值多項式滿足上述條件。拉格朗日插值和牛頓插值都屬于多項式插值。拉格朗日插值：設(shè)連續(xù)函數(shù)y = f（x）在[a, b]上對給定n + 1 個不同結(jié)點：分別取函數(shù)值其中 （1）試構(gòu)造一個次數(shù)不超過 n的插值多項式