數(shù)學(xué)建模十大經(jīng)典算法

1、數(shù)學(xué)建模十大經(jīng)典算法一、蒙特卡羅算法1946年,美國拉斯阿莫斯國家實(shí)驗(yàn)室的三位科學(xué)家John von Neumann,Stan Ulam 和 Nick Metropolis共同發(fā)明了,蒙特卡羅方法。此算法被評(píng)為20世紀(jì)最偉大的十大算法之一。蒙特卡羅方法(Monte Carlo method,又稱隨機(jī)抽樣或統(tǒng)計(jì)模擬方法,是一種以概率統(tǒng)計(jì)理論為指導(dǎo)的一類非常重要的數(shù)值計(jì)算方法。此方法使用隨機(jī)數(shù)(或更常見的偽隨機(jī)數(shù)來解決很多計(jì)算問題的方法。由于傳統(tǒng)的經(jīng)驗(yàn)方法由于不能逼近真實(shí)的物理過程,很難得到滿意的結(jié)果,而蒙特卡羅方法由于能夠真實(shí)地模擬實(shí)際物理過程,故解決問題與實(shí)際非常符合,可以得到很圓滿的結(jié)果。蒙

2、特卡羅方法的基本原理及思想如下:當(dāng)所求解問題是某種隨機(jī)事件出現(xiàn)的概率,或者是某個(gè)隨機(jī)變量的期望值時(shí),通過某種“實(shí)驗(yàn)”的方法,以這種事件出現(xiàn)的頻率估計(jì)這一隨機(jī)事件的概率,或者得到這個(gè)隨機(jī)變量的某些數(shù)字特征,并將其作為問題的解。有一個(gè)例子可以使你比較直觀地了解蒙特卡洛方法:假設(shè)我們要計(jì)算一個(gè)不規(guī)則圖形的面積,那么圖形的不規(guī)則程度和分析性計(jì)算(比如,積分的復(fù)雜程度是成正比的。蒙特卡洛方法是怎么計(jì)算的呢?假想你有一袋豆子,把豆子均勻地朝這個(gè)圖形上撒,然后數(shù)這個(gè)圖形之中有多少顆豆子,這個(gè)豆子的數(shù)目就是圖形的面積。當(dāng)你的豆子越小,撒的越多的時(shí)候,結(jié)果就越精確。在這里我們要假定豆子都在一個(gè)平面上,相互之間沒

3、有重疊。蒙特卡羅方法通過抓住事物運(yùn)動(dòng)的幾何數(shù)量和幾何特征,利用數(shù)學(xué)方法來加以模擬,即進(jìn)行一種數(shù)字模擬實(shí)驗(yàn)。它是以一個(gè)概率模型為基礎(chǔ),按照這個(gè)模型所描繪的過程,通過模擬實(shí)驗(yàn)的結(jié)果,作為問題的近似解。蒙特卡羅方法與一般計(jì)算方法有很大區(qū)別,一般計(jì)算方法對(duì)于解決多維或因素復(fù)雜的問題非常困難,而蒙特卡羅方法對(duì)于解決這方面的問題卻比較簡(jiǎn)單。其特點(diǎn)如下:I、直接追蹤粒子,物理思路清晰,易于理解。II、采用隨機(jī)抽樣的方法,較真切的模擬粒子輸運(yùn)的過程,反映了統(tǒng)計(jì)漲落的規(guī)律。III、不受系統(tǒng)多維、多因素等復(fù)雜性的限制,是解決復(fù)雜系統(tǒng)粒子輸運(yùn)問題的好方法。等等。二、數(shù)據(jù)擬合、參數(shù)估計(jì)、插值等數(shù)據(jù)處理算法插值已知一些

4、點(diǎn)可能知道原函數(shù),得到的函數(shù)點(diǎn)均在上面,用一個(gè)函數(shù)近似逼近。而擬合也知道一些點(diǎn),不知道函數(shù),構(gòu)造的函數(shù)點(diǎn)不一定在上面,可以分布在周圍,但是點(diǎn)到直線的誤差的平方和要達(dá)到最小。(最小二乘法二次三次擬合就可以了,五次擬合就已經(jīng)變形了誤差大。我們通常會(huì)遇到大量的數(shù)據(jù)需要處理,而處理數(shù)據(jù)的關(guān)鍵就在于這些算法,通常使用Matlab作為工具。數(shù)據(jù)擬合在數(shù)學(xué)建模比賽中中有應(yīng)用,與圖形處理有關(guān)的問題很多與擬合有關(guān)系,一個(gè)例子就是98年數(shù)學(xué)建模美國賽A題,生物組織切片的三維插值處理,94年A題逢山開路,山體海拔高度的插值計(jì)算,還有吵的沸沸揚(yáng)揚(yáng)可能會(huì)考的“非典”問題也要用到數(shù)據(jù)擬合算法,觀察數(shù)據(jù)的走向進(jìn)行處理。此類

5、問題在 MATLAB 中有很多現(xiàn)成的函數(shù)可以調(diào)用,熟悉MATLAB,這些方法都能游刃有余的用好。三、線性規(guī)劃、整數(shù)規(guī)劃、多元規(guī)劃、二次規(guī)劃等規(guī)劃類問題數(shù)學(xué)建模競(jìng)賽中很多問題都和數(shù)學(xué)規(guī)劃有關(guān),可以說不少的模型都可以歸結(jié)為一組不等式作為約束條件、幾個(gè)函數(shù)表達(dá)式作為目標(biāo)函數(shù)的問題,遇到這類問題,求解就是關(guān)鍵了,比如98年B題,用很多不等式完全可以把問題刻畫清楚,因此列舉出規(guī)劃后用 Lindo 、 Lingo 等軟件來進(jìn)行解決比較方便,所以還需要熟悉這兩個(gè)軟件。四、圖論算法這類問題算法有很多,最佳巡邏路線,最短路,最大流問題等包括: Dijkstra 、 Floyd 、 Prim 、 Bellman-

6、Ford ,最大流,二分匹配等問題。關(guān)于此類圖論算法,可參考Introduction to Algorithms-算法導(dǎo)論,關(guān)于圖算法的第22章-第26章。同時(shí),本BLOG內(nèi)經(jīng)典算法研究系列,對(duì)Dijkstra算法有所簡(jiǎn)單描述,經(jīng)典算法研究系列:二、Dijkstra 算法初探。五、動(dòng)態(tài)規(guī)劃、回溯搜索、分治算法、分支定界等計(jì)算機(jī)算法在數(shù)學(xué)建模競(jìng)賽中,如:92 年B題用分枝定界法, 97年B題是典型的動(dòng)態(tài)規(guī)劃問題,此外 98 年 B 題體現(xiàn)了分治算法。這方面問題和 ACM 程序設(shè)計(jì)競(jìng)賽中的問題類似,推薦看一下算法導(dǎo)論,與計(jì)算機(jī)算法設(shè)計(jì)與分析(電子工業(yè)出版社等與計(jì)算機(jī)算法有關(guān)的書。四,五均為優(yōu)化問題

7、。六、最優(yōu)化理論的三大經(jīng)典算法:模擬退火法、神經(jīng)網(wǎng)絡(luò)、遺傳算法這十幾年來最優(yōu)化理論有了飛速發(fā)展,模擬退火法、神經(jīng)網(wǎng)絡(luò)、遺傳算法這三類算法發(fā)展很快。在數(shù)學(xué)建模競(jìng)賽中:比如97年A題的模擬退火算法,00年B題的神經(jīng)網(wǎng)絡(luò)分類算法,01年B題這種難題也可以使用神經(jīng)網(wǎng)絡(luò),還有美國競(jìng)賽89年A題也和 BP 算法有關(guān)系,當(dāng)時(shí)是86年剛提出BP算法,89年就考了,說明賽題可能是當(dāng)今前沿科技的抽象體現(xiàn)。03 年 B 題伽馬刀問題也是目前研究的課題,目前算法最佳的是遺傳算法。另,本人對(duì)人工智能非常感興趣,遺傳算法已在本BLOG內(nèi)有所闡述,七、網(wǎng)格算法和窮舉法網(wǎng)格算法和窮舉法一樣,只是網(wǎng)格法是連續(xù)問題的窮舉。比如要

8、求在 N 個(gè)變量情況下的最優(yōu)化問題,那么對(duì)這些變量可取的空間進(jìn)行采點(diǎn),比如在 a; b 區(qū)間內(nèi)取 M +1 個(gè)點(diǎn),就是 a; a +( b ? a =M; a +2 ( b ? a =M ; ;b那么這樣循環(huán)就需要進(jìn)行 ( M + 1 N 次運(yùn)算,所以計(jì)算量很大。在數(shù)學(xué)建模競(jìng)賽中:比如 97 年 A 題、 99 年 B 題都可以用網(wǎng)格法搜索,這種方法最好在運(yùn)算速度較快的計(jì)算機(jī)中進(jìn)行,還有要用高級(jí)語言來做,最好不要用MATLAB 做網(wǎng)格,否則會(huì)算很久。窮舉法大家都熟悉,自不用多說了。八、一些連續(xù)離散化方法(計(jì)算機(jī)仿真大部分物理問題的編程解決,都和這種方法有一定的聯(lián)系。物理問題是反映我們生活在一個(gè)

9、連續(xù)的世界中,計(jì)算機(jī)只能處理離散的量,所以需要對(duì)連續(xù)量進(jìn)行離散處理。這種方法應(yīng)用很廣,而且和上面的很多算法有關(guān)。事實(shí)上,網(wǎng)格算法、蒙特卡羅算法、模擬退火都用了這個(gè)思想。九、數(shù)值分析算法(插值,擬合,積分,微分?jǐn)?shù)值分析(numerical analysis,是數(shù)學(xué)的一個(gè)分支,主要研究連續(xù)數(shù)學(xué)(區(qū)別于離散數(shù)學(xué)問題的算法。如果在比賽中采用高級(jí)語言進(jìn)行編程的話,那一些數(shù)值分析中常用的算法比如方程組求解、矩陣運(yùn)算、函數(shù)積分等算法就需要額外編寫庫函數(shù)進(jìn)行調(diào)用。這類算法是針對(duì)高級(jí)語言而專門設(shè)的,如果你用的是MATLAB現(xiàn)成的函數(shù)、 Mathematica ,大可不必準(zhǔn)備,因?yàn)橄駭?shù)值分析中有很多函數(shù)一般的數(shù)學(xué)軟件是具備的。十、圖象處理算法在數(shù)學(xué)建