1、蒙特卡羅算法：
在大多數(shù)建模賽題中都離不開計(jì)算機(jī)的仿真，隨機(jī)性模擬是非常常見的算法之一。 m8 i6 o( l$ y( c7 V5 Y9 d! l
舉個(gè)例子就是97年的A題，每個(gè)零件都有自己的標(biāo)定值，也都有自己的容差等級，而求解最優(yōu)的組合方案將要面對著的是一個(gè)極其復(fù)雜的公式和108種容差選取方案，根本不可能去解析求解的，那如何去找到最優(yōu)的方案呢？隨機(jī)性模擬搜索最優(yōu)方案就是其中的一種方法，在每個(gè)零件可行的區(qū)間中按照正態(tài)分布隨機(jī)的選取一個(gè)標(biāo)定值和選取一個(gè)容差值作為一種方案，然后通過蒙特卡羅算法仿真出大量的方案，從中選取一個(gè)最佳的。另一個(gè)例子就是去年的彩票第二問，要求設(shè)計(jì)一種更好的方案，首先方案的優(yōu)劣決定于很多復(fù)雜的因素，同樣不可能刻畫出一個(gè)模型進(jìn)行求解，只能靠隨機(jī)仿真模擬。 6 u1 h. z" Y, R0 Y4 Y
2、數(shù)據(jù)擬合、參數(shù)估計(jì)、插值等算法：
數(shù)據(jù)擬合在很多賽題中有應(yīng)用，與圖形處理有關(guān)的問題很多與擬合有關(guān)系，一個(gè)例子就是98年美賽A題，生物組織切片的三維插值處理，94年A題逢山開路，山體海拔高度的插值計(jì)算，還有吵的沸沸揚(yáng)揚(yáng)可能會(huì)考的非典問題也要用到數(shù)據(jù)擬合算法，觀察數(shù)據(jù)的走向進(jìn)行處理。此類問題在Matlab中有很多數(shù)據(jù)處理現(xiàn)成的函數(shù)可以調(diào)用，熟悉Matlab，這些方法都能游刃有余的做好。 $ X/ Z Y5 V/ ~* c- m% y
3、規(guī)劃類問題算法： 2 M S0 A @: h8 A
競賽中很多問題都和數(shù)學(xué)規(guī)劃有關(guān)，可以說不少的模型都可以歸結(jié)為一組不等式組作為約束條件、幾個(gè)函數(shù)表達(dá)式作為目標(biāo)函數(shù)的問題，遇到這類問題，求解就是關(guān)鍵了，比如98B，用很多不等式完全可以把問題刻畫清楚，因此列舉出規(guī)劃后用Lindo、Lingo等軟件來進(jìn)行解決比較方便，所以還需要熟悉這兩個(gè)軟件。
4、圖論問題： 5 z" Z0 ~5 B/ Q& k$ D7 `2 M
98B、00B、95鎖具裝箱等問題體現(xiàn)了圖論問題的重要性，這類問題算法有很多，包括：Dijkstra、Floyd、Prim、Bellman-Ford，最大流，二分匹配等問題。每一個(gè)算法認(rèn)真的話都應(yīng)該寫一遍，否則到比賽時(shí)再寫就晚了， - U7 {# L& r% ]
5、計(jì)算機(jī)算法設(shè)計(jì)中的問題：
計(jì)算機(jī)算法設(shè)計(jì)包括很多內(nèi)容：動(dòng)態(tài)規(guī)劃、回溯搜索、分治算法、分支定界。比如92B用分支定界法，97B是典型的動(dòng)態(tài)規(guī)劃問題，此外98B體現(xiàn)了分治算法。這方面問題和acm中的問題類似，推薦的書籍有《計(jì)算機(jī)算法設(shè)計(jì)與分析》電子工業(yè)出版社等與計(jì)算機(jī)算法有關(guān)的書。 & R# q( }/ ]1 v/ g
6、最優(yōu)化理論的三大非經(jīng)典算法：
模擬退火法、神經(jīng)網(wǎng)絡(luò)、遺傳算法。這十幾年來最優(yōu)化理論有了飛速發(fā)展，這三類算法發(fā)展很快，近幾年的賽題越來越復(fù)雜，很多問題沒有什么很好的模型可以借鑒，于是這三類算法很多時(shí)候可以派上用場，比如：97A的模擬退火算法、00B的神經(jīng)網(wǎng)絡(luò)分類算法、象01B這種難題也可以使用神經(jīng)網(wǎng)絡(luò)、還有美國競賽89A也和BP算法有關(guān)系，當(dāng)時(shí)是86年剛提出BP算法，89年就考了，說明賽題可能是當(dāng)今前沿科技的抽象體現(xiàn)。03B伽馬刀問題也是目前研究的課題，目前算法最佳的是遺傳算法。
7、網(wǎng)格算法和窮舉算法
網(wǎng)格算法和窮舉法一樣，只是網(wǎng)格法是連續(xù)問題的窮舉。比如要求在N個(gè)變量情況下的最優(yōu)化問題，那么可以對這些變量可取的空間進(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ì)算量很大。 7 o% w/ @7 n% {2 l4 L- t/ n
比如97年A題、99年B題都可以用網(wǎng)格法搜索，這種方法最好在運(yùn)算速度叫快的計(jì)算機(jī)中進(jìn)行，還有要用高級語言來做，最好不要用Matlab做網(wǎng)格，否則會(huì)算很久的。窮舉法大家都熟悉，就不說了。
8、一些連續(xù)離散化方法
大部分物理問題的編程解決，都和這種方法有一定的聯(lián)系，物理問題是反映我們生活在一個(gè)連續(xù)的世界中，計(jì)算機(jī)求解只認(rèn)離散的變量，所以需要將連續(xù)量進(jìn)行離散處理，這種方法應(yīng)用很廣，大都和上面的很多算法有關(guān)，事實(shí)上，網(wǎng)格算法、蒙特卡羅算法、模擬退火都用了這個(gè)思想。 % F# T2 ]3 d+ N; x" w: w
9、數(shù)值分析算法
這類算法是針對高級語言而專門設(shè)的，如果你用的是Matlab、Mathematica，大可不必準(zhǔn)備，因?yàn)橄髷?shù)值分析中有很多函數(shù)一般的數(shù)學(xué)工具是具備的。 C6 {" f; [) T. |
10、圖象處理算法 / ]# Q' h% }, e# T, E
01A中需要你會(huì)讀bmp圖象、98美賽A需要你知道三維插值計(jì)算，03B要求更高，不但需要編程計(jì)算還要進(jìn)行處理，而數(shù)模論文中也有很多圖片需要展示，因此圖象處理就是關(guān)鍵，做好這類問題，重要的是把Matlab學(xué)好，特別是圖象處理的部分。 |
|
