2.數據處理算法,如數據擬合、參數估計和插值。比賽中通常會有大量的數據需要處理,而處理數據的關鍵就在於這些算法,通常使用MATLAB作為工具。
3.編程算法,如線性規劃、整數規劃、多元規劃和二次規劃。建模競賽中的大部分問題都屬於優化問題,很多時候這些問題都可以用數學規劃算法來描述,通常用Lindo和Lingo軟件來解決。
4.圖論算法。這類算法可以分為很多種,包括最短路徑算法、網絡流算法、二分圖算法等。圖論相關的問題可以用這些方法解決,需要認真準備。
5.計算機算法,如動態規劃、回溯搜索、分治算法、分支定界。這些算法是算法設計中常用的,在比賽中很多場合都會用到。
6.最優化理論的三種非經典算法:模擬退火算法、神經網絡算法和遺傳算法。這些問題用於解決壹些困難的優化問題,對壹些問題很有幫助,但是算法實現比較困難,需要謹慎使用。
7.網格算法和窮舉法。兩者都是蠻力搜索最好的算法,在很多競賽題中都有應用。當我們專註於模型本身而輕視算法的時候,可以使用這種蠻力方案,最好使用壹些高級語言作為編程工具。
8.連續數據的幾種離散化方法。很多問題都是實用的,數據可以是連續的,計算機只能處理離散的數據,所以把它們離散化,貫徹差分代替微分,求和代替積分等思想是非常重要的。
9.數值分析算法。如果在競賽中使用高級語言編程,數值分析中常用的算法,如解方程、矩陣運算、函數積分等,都需要編寫額外的庫函數來調用。
10.圖像處理算法。競賽中有壹類與圖形相關的問題。即使問題與圖形無關,論文中也會需要圖片來說明問題。如何顯示這些圖形,如何處理這些圖形是需要解決的問題,通常用MATLAB來處理。
下面將結合歷年的競賽題詳細講解這十種算法。
下面將結合歷年的競賽題詳細講解這十種算法。
2十種算法的詳細描述
2.1蒙特卡羅算法
大多數建模比賽都離不開計算機模擬,隨機模擬是最常見的算法之壹。
比如1997年的A題,每個零件都有自己的標定值和公差等級,求解最優組合方案會面臨極其復雜的公式和108個公差選擇方案,無法找到解析解。如何找到最優方案?隨機模擬和尋找最優方案是方法之壹。在每個零件的可行區間內,按照正態分布隨機選取壹個標定值和壹個公差值作為方案,然後用蒙特卡羅算法對大量方案進行模擬,選出最佳方案。再比如去年抽簽的第二題,要求有更好的方案。首先,方案的好壞取決於很多復雜的因素,也無法刻畫壹個模型來解決,只能用隨機模擬的方法來模擬。
2.2數據擬合、參數估計、插值等算法
數據擬合在很多遊戲中都有應用,很多圖形處理相關的問題都和擬合有關。壹個例子是1998年美國的A遊戲,生物組織切片的三維插值處理,1994年A遊戲中山峰海拔的插值計算,考試中可能要考的嘈雜的SARS問題。還應該使用數據擬合算法來觀察數據的趨勢,以便進行處理。對於這類問題,MATLAB中有很多現成的函數可以調用。如果妳熟悉MATLAB,這些方法都可以用得很好。
2.3編程類問題算法
競賽中的許多問題都與數學規劃有關。可以說,很多模型都可以歸結為壹組不等式作為約束,幾個函數表達式作為目標函數。遇到這樣的問題,關鍵是要解決。比如1998年的B題,可以用很多不等式描述清楚。所以列出規劃後用Lindo、Lingo等軟件解決比較方便,所以需要熟悉這兩個軟件。
2.4圖論問題
98 B、00 B和95鎖箱裝箱問題反映了圖論的重要性。這類問題有很多算法,包括:Dijkstra,Floyd,Prim,Bellman-Ford,最大流,二進制匹配等等。每個算法都要實現壹次,不然遊戲上寫就來不及了。
2.5計算機算法設計中的問題
計算機算法設計包括很多內容:動態規劃、回溯搜索、分治算法、分支定界。比如1992年,B題是分枝定界法;1997年,問題B是典型的動態規劃問題;另外,1998年的B題體現了分治算法。這方面的問題類似於ACM編程競賽中的問題。推薦閱讀《計算機算法設計與分析》(電子工業出版社)等計算機算法相關的書籍。
2.6最優化理論的三種非經典算法
近十年來,最優化理論發展迅速,模擬退火法、神經網絡和遺傳算法三類算法發展迅速。近幾年的競賽題越來越復雜,很多問題都沒有好的模型可以借鑒,所以這三類算法往往可以派上用場,比如:97 A題的模擬退火算法,00 B題的神經網絡分類算法,01 B題這樣的難題也可以用神經網絡,美國競賽中的89 A題和86、89年剛提出的BP算法也有關系。2003年B題的伽瑪刀問題也是目前的研究課題,目前最好的算法是遺傳算法。
2.7網格算法和窮舉算法
網格算法和窮舉法壹樣,只是網格法是連續問題的窮舉法。比如要求n個變量條件下的優化問題,那麽選取這些變量可取的空間,比如在[a;B]取區間M +1點,為a;a+(b-a)/M;a+2(b-a)/M;…… ;b那麽這個循環需要操作(M+1)N次,所以計算量非常大。比如1997年的A題和1999年的B題,可以用網格法搜索,這種方法最好是運算速度比較快的。
在計算機裏,有高級語言可以做,最好不要用MATLAB做網格,否則時間會很長。窮舉法大家都很熟悉,就不說了。
2.8連續數據離散化的壹些方法
大多數物理問題的編程解法都與此方法有關。物理問題反映出我們生活在壹個連續的世界裏,計算機只能處理離散量,所以需要離散處理連續量。這種方法應用廣泛,和上面很多算法都有關系。其實網格算法、蒙特卡羅算法、模擬退火都是用的這個思路。
2.9數值分析算法
這種算法是專門為高級語言設計的。如果用MATLAB和Mathematica就不用準備了,因為數值分析裏面有很多函數。
2.10圖像處理算法
01,需要會看BMP圖像,1998年,在美國,需要會三維插值計算,2003年,B題,要求更高,不僅編程計算還要處理,數字和模擬論文要顯示的圖片很多,所以圖像處理是關鍵。要做好這類題,學好MATLAB很重要,尤其是圖像處理部分。