天天看點

2023美賽ABCDEF題思路代碼資料分享

2023美賽ABCDEF題思路代碼資料分享

從2016年開始,每年美賽MCM/ICM各出3題,即總共六題。

MCM俗稱數學模組化競賽,有三道題:problem A , problem B 和problem C。A題是連續型的題,B題是離散型的題,C題是資料處理的題,大都是會給出大量的表格資料進行資料處理。

ICM俗稱交叉學科競賽,有三道題:problem D, problem E, problem F。與mcm不同的是,題目上會給你一些參考的資料,友善你盡快找到查資料的方向。problem D是運籌學和網絡科學等類型的題目,problem E近往年都是關于環境方面的綜合題目,現在改成了可持續性題目。problem F是政策的題目。

2023美賽ABCDEF題思路代碼資料分享

總的來說,MCM 偏自然、理工,而ICM偏社科、人文。更多的模組化er更傾向于選擇MCM的ABC題。MCM出的題目更偏向于運用數理知識模組化解決,ICM則更偏重于運用跨學科知識,以下是自2016年起每年選題人數比例:

2023美賽ABCDEF題思路代碼資料分享
2023美賽ABCDEF題思路代碼資料分享

2016-2022年曆年參賽隊伍數如下圖所示:

2023美賽ABCDEF題思路代碼資料分享

由上圖可知除了2020年疫情原因,參賽人數整體為逐年增長趨勢。

2023美賽ABCDEF題思路代碼資料分享

這個是美賽常用的模型代碼,以及各題型常用的代碼!

比賽時會分享各個賽題的思路代碼模型以及講解視訊!

2023美賽ABCDEF題思路代碼資料分享
2023美賽ABCDEF題思路代碼資料分享

數學模組化競賽中應當掌握的十類算法:

1、蒙特卡羅算法

該算法又稱随機性模拟算法,是通過計算機仿真來解決問題的算法,同時可以通過模拟

可以來檢驗自己模型的正确性,是比賽時必用的方法;

2、資料拟合、參數估計、插值等資料處理算法

比賽中通常會遇到大量的資料需要處理,而處理資料的關鍵就在于這些算法,通常使用

Matlab 作為工具;

3、線性規劃、整數規劃、多元規劃、二次規劃等規劃類問題

模組化競賽大多數問題屬于最優化問題,很多時候這些問題可以用數學規劃算法來描述,

通常使用 Lindo、Lingo 軟體實作;

4、圖論算法

這類算法可以分為很多種,包括最短路、網絡流、二分圖等算法,涉及到圖論的問題可

以用這些方法解決,需要認真準備;

5、動态規劃、回溯搜尋、分治算法、分支定界等計算機算法

這些算法是算法設計中比較常用的方法,很多場合可以用到競賽中)

6、最優化理論的三大非經典算法

模拟退火法、神經網絡、遺傳算法(這些問題是用來解決一些較困難的最優化問題的算

法,對于有些問題非常有幫助,但是算法的實作比較困難,需慎重使用

7、網格算法和窮舉法

網格算法和窮舉法都是暴力搜尋最優點的算法,在很多競賽題中有應用,當重點讨論模

型本身而輕視算法的時候,可以使用這種暴力方案,最好使用一些進階語言作為程式設計工

具;

8、一些連續離散化方法

很多問題都是實際來的,資料可以是連續的,而計算機隻認的是離散的資料,是以将其

離散化後進行差分代替微分、求和代替積分等思想是非常重要的;

9、數值分析算法

如果在比賽中采用進階語言進行程式設計的話,那一些數值分析中常用的算法比如方程組求

解、矩陣運算、函數積分等算法就需要額外編寫庫函數進行調用;

10、圖象處理算法

賽題中有一類問題與圖形有關,即使與圖形無關,論文中也應該要不乏圖檔的,這些圖

形如何展示以及如何處理就是需要解決的問題,通常使用 Matlab 進行處理;

各個算法對應的賽題載體:

1、蒙特卡羅算法:

 在大多數模組化賽題中都離不開計算機的仿真,随機性模拟是非常常見的算法之一。

 舉個例子就是 97 年的 A 題,每個零件都有自己的标定值,也都有自己的容差等級,而求解最優的組合方

案将要面對着的是一個極其複雜的公式和 108 種容差選取方案,根本不可能去解析求解的,那如何去找到

最優的方案呢?随機性模拟搜尋最優方案就是其中的一種方法,在每個零件可行的區間中按照正态分布随

機的選取一個标定值和選取一個容內插補點作為一種方案,然後通過蒙特卡羅算法仿真出大量的方案,從中選

取一個最佳的。另一個例子就是去年的彩票第二問,要求設計一種更好的方案,首先方案的優劣決定于很多複雜的因素,同樣不可能刻畫出一個模型進行求解,隻能靠随機仿真模拟。

2、資料拟合、參數估計、插值等算法:

 資料拟合在很多賽題中有應用,與圖形處理有關的問題很多與拟合有關系,一個例子就是 98 年美賽 A 題,

生物組織切片的三維插值處理,94 年 A 題逢山開路,山體海拔高度的插值計算,還有吵的沸沸揚揚可能會

考的非典問題也要用到資料拟合算法,觀察資料的走向進行處理。此類問題在 Matlab 中有很多資料處理現

成的函數可以調用,熟悉 Matlab,這些方法都能遊刃有餘的做好。

3、規劃類問題算法:

 競賽中很多問題都和數學規劃有關,可以說不少的模型都可以歸結為一組不等式組作為限制條件、幾個

函數表達式作為目标函數的問題,遇到這類問題,求解就是關鍵了,比如 98B,用很多不等式完全可以把

問題刻畫清楚,是以列舉出規劃後用 Lindo、Lingo 等軟體來進行解決比較友善,是以還需要熟悉這兩個軟

件。

4、圖論問題:

 98B、00B、95 鎖具裝箱等問題展現了圖論問題的重要性,這類問題算法有很多,包括:Dijkstra、Floyd、

Prim、Bellman-Ford,最大流,二分比對等問題。每一個算法認真的話都應該寫一遍,否則到比賽時再寫就

晚了,

5、計算機算法設計中的問題:

 計算機算法設計包括很多内容:動态規劃、回溯搜尋、分治算法、分支定界。比如 92B 用分支定界法,

97B 是典型的動态規劃問題,此外 98B 展現了分治算法。這方面問題和 acm 中的問題類似,推薦的書籍有

《計算機算法設計與分析》電子工業出版社等與計算機算法有關的書。

6、最優化理論的三大非經典算法:

 模拟退火法、神經網絡、遺傳算法。這十幾年來最優化理論有了飛速發展,這三類算法發展很快,近幾

年的賽題越來越複雜,很多問題沒有什麼很好的模型可以借鑒,于是這三類算法很多時候可以派上用場,

比如:97A 的模拟退火算法、00B 的神經網絡分類算法、象 01B 這種難題也可以使用神經網絡、還有美國

競賽 89A 也和 BP 算法有關系,當時是 86 年剛提出 BP 算法,89 年就考了,說明賽題可能是當今前沿科技

的抽象展現。03B 伽馬刀問題也是目前研究的課題,目前算法最佳的是遺傳算法。

7、網格算法和窮舉算法

 網格算法和窮舉法一樣,隻是網格法是連續問題的窮舉。比如要求在 N 個變量情況下的最優化問題,那

麼可以對這些變量可取的空間進行采點,比如在[a,b]區間内取 M+1 個點,就是在 a、a+(b-a)/M、

a+2*(b-a)/M、……、b 那麼這樣循環就需要進行(M+1)^N 次運算,是以計算量很大。

比如 97 年 A 題、99 年 B 題都可以用網格法搜尋,這種方法最好在運算速度叫快的計算機中進行,還有要

用進階語言來做,最好不要用 Matlab 做網格,否則會算很久的。窮舉法大家都熟悉,就不說了。

8、一些連續離散化方法

 大部分實體問題的程式設計解決,都和這種方法有一定的聯系,實體問題是反映我們生活在一個連續的世界

中,計算機求解隻認離散的變量,是以需要将連續量進行離散處理,這種方法應用很廣,大都和上面的很

多算法有關,事實上,網格算法、蒙特卡羅算法、模拟退火都用了這個思想。

9、數值分析算法

 這類算法是針對進階語言而專門設的,如果你用的是 Matlab、Mathematica,大可不必準備,因為象數值

分析中有很多函數一般的數學工具是具備的。

10、圖象處理算法

 01A 題中需要你會讀 bmp 圖象、98 美賽 A 需要你知道三維插值計算,03B 要求更高,不但需要程式設計計算

還要進行處理,而數模論文中也有很多圖檔需要展示,是以圖象處理就是關鍵,做好這類問題,重要的是

把 Matlab 學好,特别是圖象處理的部分。

歡迎複制連結到浏覽器中打開,

https://docs.qq.com/doc/DY2lYaE9RaVd2RUhs

比賽時會分享各個賽題的思路代碼模型以及講解視訊!

繼續閱讀