算法

1、 蒙特卡罗算法（该算法又称随机性模拟算法，是通过计算机仿真来解决 问题的算法，同时可以通过模拟可以来检验自己模型的正确性，是比赛时必 用的方法）

2、数据拟合、参数估计、插值等数据处理算法（比赛中通常会遇到大量的数 据需要处理，而处理数据的关键就在于这些算法，通常使用Matlab 作为工具）

数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通 常使用Lindo、Lingo 软件实现）

4、图论算法Dijkstra 、 Floyd 、 Prim 、 Bellman-Ford ，最大流，二分匹配等问题。（这类算法可以分为很多种，包括最短路、网络流、二分图等算 法，涉及到图论的问题可以用这些方法解决，需要认真准备）

5、动态规划、回溯搜索、分治算法、分支定界等计算机算法（这些算法是算 法设计中比较常用的方法，很多场合可以用到竞赛中）

问题是用来解决一些较困难的最优化问题的算法，对于有些问题非常有帮助， 但是算法的实现比较困难，需慎重使用）

多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种 暴力方案，最好使用一些高级语言作为编程工具）

8、一些连续离散化方法（很多问题都是实际来的，数据可以是连续的，而计 算机只认的是离散的数据，因此将其离散化后进行差分代替微分、求和代替 积分等思想是非常重要的）

9、数值分析算法（如果在比赛中采用高级语言进行编程的话，那一些数值分 析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编 写库函数进行调用）

中也应该要不乏图片的，这些图形如何展示以及如何处理就是需要解决的问

题，通常使用Matlab 进行处理）

11. 层次分析法 马尔可夫链 主成分析法

12. 统计分析 回归分析

13. 单目标决策

14. 欧氏距离判别、fisher判别

基础知识

1.数学物理方程

2数学分析,

3组合数学

4图论

5最优化理论

6运筹学

美国数学建模比赛有感

不得不承认，当老师通知我们队得了美国数学建模一等奖时，我的心情是万分激动，甚至觉得，这很有可能就是我的大学生活最有意义并且最值得怀念的一件事。岁月似水，无情的冲刷着我们过去的记忆，然而这段艰辛而又充实的历程却铭刻在我的心中，时时都能鲜活地浮现在脑海中。

我觉得，之所以我们能够取得满意的成绩，在各项因素中，坚持不懈是最关键的。自从零六年秋一直到今年美国数模前夕，我们始终坚持不断的充实着数学建模知识，不管是寒暑假还是在课程繁重的业余时间。虽然在刚开始的时候，对数学建模的概念还很模糊，更别提什么排队论、目标规划、神经网络这些高深的理论。但是，通过坚持不懈的自学和一点一滴的积累，到了全国数学建模前夕，我们基本上对这些复杂的理论知识都有了一个较为系统和完善的理解，并能够灵活运用其中的一些解决各类数学建模问题。冰冻三尺，非一日之寒，只有靠日积月累才能不断的充实数学建模知识，才能在最终的竞赛上充满信心，取得好的成绩。

在数学建模中，要求几天之内提交一份高质量的论文，单靠一个人单枪匹马是很困难的，队员们必须通力合作才能取得优异成绩，这一点，我们深有感触。良好的合作必须建立在合理的组队与分工之上。美国数学建模既要求具有扎实的数学基础，也要有熟练的编程能力，还要有良好的英语表达和写作能力，我们就是按照这个标准进行组队的。通过较长时间的交流合作，我们彼此之间在各个方面都有了比较深入的了解，建模时，大家既能够在各自的责任范围内充分发挥所长，同时又能经行有效的交流和沟通，保证了信息的畅通，工作效率自然很高。

还有一点，就是必须具备良好的心理素质。记得全国数学建模中，我们的成绩并不理想，当时我们对就有人因此退出。其实现在看来，失败了也没有什么，更何况通过一年多的自学我们掌握了不少的数学知识。经过一段时间的心理调整，我们毅然决定重整旗鼓，卷土重来，毅然报了美国数学建模。全国数学建模的失手并没有在我们心中留下太多的阴影，相反我们总结经验和教训，并重新组队，进一步提高了整个队的综合实力。我们都是铁了心报了美国数学建模，不拿一等奖誓不罢休。整个寒假大部分时间我们都在背单词、看模型、学论文，甚至是大年初三，当其他人都沉浸在节日的喜庆时，我独自一人捧着一本美国数学建模优秀论文集埋头苦读。想到能得美国一等奖，再苦再累也值得！

同时做好赛前准备也很重要。不光是知识上的储备，还要有充沛的精力和健壮的身体，毕竟美国数学建模要苦战四天四夜。因此，赛前，我们都把身心调整到最佳状态，并为四天的比赛从小到要用的粉笔、黑板都准备得相当充分。总之，一切都要服务于这次比赛。

我们的成功，与指导老师何仁斌的辅导是分不开的。在比赛的关键时候，老师的点拨起到了关键性的作用。这里要再一次感谢何老师。

在美国数学建模中，我们收获的不光是优异的成绩，从中，我们还收获到了比成绩更加值得珍贵的友谊，团队合作能力和沟通交流能力。这些经历必将使我们受益终身。

3A非线性交调的频率设计 拟合、规划

93B足球队排名 图论、层次分析、整数规划

94A逢山开路 图论、插值、动态规划

94B锁具装箱问题 图论、组合数学

95A飞行管理问题 非线性规划、线性规划

95B天车与冶炼炉的作业调度 动态规划、排队论、图论

96A最优捕鱼策略 微分方程、优化

96B节水洗衣机 非线性规划

97A零件的参数设计 非线性规划

97B截断切割的最优排列 随机模拟、图论

98A一类投资组合问题 多目标优化、非线性规划

98B灾情巡视的最佳路线 图论、组合优化

99A自动化车床管理 随机优化、计算机模拟

99B钻井布局 0-1规划、图论

00A DNA序列分类 模式识别、Fisher判别、人工神经网络 00B钢管订购和运输 组合优化、运输问题

01A血管三维重建 曲线拟合、曲面重建

01B 工交车调度问题 多目标规划

02A车灯线光源的优化 非线性规划

02B彩票问题 单目标决策

03A SARS的传播 微分方程、差分方程 03B 露天矿生产的车辆安排 整数规划、运输问题

04A奥运会临时超市网点设计 统计分析、数据处理、优化 04B电力市场的输电阻塞管理 数据拟合、优化

05A长江水质的评价和预测

05B DVD在线租赁

预测评价、数据处理 随机规划、整数规划

第二篇：数学建模十大经典算法

数学建模十大经典算法

一、蒙特卡罗算法

19xx年，美国拉斯阿莫斯国家实验室的三位科学家John von Neumann,Stan Ulam 和 Nick Metropolis

共同发明了，蒙特卡罗方法。

此算法被评为20世纪最伟大的十大算法之一 。

蒙特卡罗方法（Monte Carlo method），又称随机抽样或统计模拟方法，是一种以概率统计理论为指导的一类非常重要的数值计算方法。此方法使用随机数（或更常见的伪随机数）来解决很多计算问题的方法。由于传统的经验方法由于不能逼近真实的物理过程，很难得到满意的结果，而蒙特卡罗方法由于能够真实地模拟实际物理过程，故解决问题与实际非常符合，可以得到很圆满的结果。 蒙特卡罗方法的基本原理及思想如下：

当所求解问题是某种随机事件出现的概率，或者是某个随机变量的期望值时，通过某种“实验”的方法，以这种事件出现的频率估计这一随机事件的概率，或者得到这个随机变量的某些数字特征，并将其作为问题的解。

有一个例子可以使你比较直观地了解蒙特卡洛方法：

假设我们要计算一个不规则图形的面积，那么图形的不规则程度和分析性计算（比如，积分）的复杂程度是成正比的。蒙特卡洛方法是怎么计算的呢？假想你有一袋豆子，把豆子均匀地朝这个图形上撒，然后数这个图形之中有多少颗豆子，这个豆子的数目就是图形的面积。当你的豆子越小，撒的越多的时候，结果就越精确。

在这里我们要假定豆子都在一个平面上，相互之间没有重叠。

蒙特卡罗方法通过抓住事物运动的几何数量和几何特征，利用数学方法来加以模拟，即进行一种数字模拟实验。它是以一个概率模型为基础，按照这个模型所描绘的过程，通过模拟实验的结果，作为问题的近似解。

蒙特卡罗方法与一般计算方法有很大区别，一般计算方法对于解决多维或因素复杂的问题非常困难，而蒙特卡罗方法对于解决这方面的问题却比较简单。其特点如下：

I、 直接追踪粒子，物理思路清晰，易于理解。

II、 采用随机抽样的方法，较真切的模拟粒子输运的过程，反映了统计涨落的规律。

III、不受系统多维、多因素等复杂性的限制，是解决复杂系统粒子输运问题的好方法。等等。

二、数据拟合、参数估计、插值等数据处理算法

我们通常会遇到大量的数据需要处理， 而处理数据的关键就在于这些算法，通常使用Matlab作为工具。数据拟合在数学建模比赛中中有应用，与图形处理有关的问题很多与拟合有关系，一个例子就是98年数学建模美国赛A题，生物组织切片的三维插值处理，94年A题逢山开路，山体海拔高度的插值计算，还有 吵的沸沸扬扬可能会考的“非典”问题也要用到数据拟合算法，观察数据的走向进行处理。此类问题在 MATLAB 中有很多现成的函数可以调用，熟悉MATLAB，这些方法都能游刃有余的用好。

三、线性规划、整数规划、多元规划、二次规划等规划类问题

数学建模竞赛中很多问题都和数学规划有关，可以说不少的模型都可以归结为一组不等式作为约束条件、几个函数表达式作为目标函数的问题，遇到这类问题，求解就是关键了，比如98年B题，用很多不等式完全可以把问题刻画清楚，因此列举出规划后用 Lindo 、 Lingo 等软件来进行解决比较方便，所以还需要熟悉这两个软件。

四、图论算法

这类问题算法有很多，

包括： Dijkstra 、 Floyd 、 Prim 、 Bellman-Ford ，最大流，二分匹配等问题。

关于此类图论算法，可参考Introduction to Algorithms--算法导论，关于图算法的第22章-第26章。同时，本BLOG内经典算法研究系列，对Dijkstra算法有所简单描述，

经典算法研究系列：二、Dijkstra 算法初探。

五、动态规划、回溯搜索、分治算法、分支定界等计算机算法

在数学建模竞赛中，如:92 年B题用分枝定界法， 97年B题是典型的动态规划问题，此外 98 年 B 题体现了分治算法。

这方面问题和 ACM 程序设计竞赛中的问题类似，

推荐看一下算法导论，与《计算机算法设计与分析》（电子工业出版社）等与计算机算法有关的书。

六、最优化理论的三大经典算法：模拟退火法、神经网络、遗传算法

这十几年来最优化理论有了飞速发展，模拟退火法、神经网络、遗传算法这三类算法发展很快。

在数学建模竞赛中：比如97年A题的模拟退火算法,00年B题的神经网络分类算法，01年B题这种难题也可以使用神经网络，还有美国竞赛89年A题也和 BP 算法有关系，当时是86年刚提出BP算法，89年就考了，说明赛题可能是当今前沿科技的抽象体现。

03 年 B 题伽马刀问题也是目前研究的课题，目前算法最佳的是遗传算法。 另，本人对人工智能非常感兴趣，遗传算法已在本BLOG内有所阐述，

七、网格算法和穷举法

网格算法和穷举法一样，只是网格法是连续问题的穷举。比如要求在 N 个变量情况下的最优化问题，那么对这些变量可取的空间进行采点，比如在 [ a; b ] 区间内取 M +1 个点，

就是 a; a +( b ? a ) =M; a +2 ￠ ( b ? a ) =M ; ?；b

那么这样循环就需要进行 ( M + 1) N 次运算，所以计算量很大。

在数学建模竞赛中：比如 97 年 A 题、 99 年 B 题都可以用网格法搜索，这种方法最好在运算速度较快的计算机中进行，还有要用高级语言来做，最好不要用 MATLAB 做网格，否则会算很久。

穷举法大家都熟悉，自不用多说了。

八、一些连续离散化方法

大部分物理问题的编程解决，都和这种方法有一定的联系。物理问题是反映我们生活在一个连续的世界中，计算机只能处理离散的量，所以需要对连续量进行离散处理。这种方法应用很广，而且和上面的很多算法有关。事实上，网格算法、蒙特卡罗算法、模拟退火都用了这个思想。

九、数值分析算法

数值分析（numerical analysis），是数学的一个分支，主要研究连续数学（区别于离散数学）问题的算法。如果在比赛中采用高级语言进行编程的话，那一些数值分析中常用的算法比 如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用。这类算法是针对高级语言而专门设的，如果你用的是 MATLAB 、 Mathematica ，大可不必准备，因为像数值分析中有很多函数一般的数学软件是具备的。

十、图象处理算法

在数学建模竞赛中：比如01 年 A 题中需要你会读 BMP 图象、美国赛 98 年 A 题需要你知道三维插值计算， 03 年 B 题要求更高，不但需要编程计算还要进行处理，而数模论文中也有很多图片需要展示，因此图象处理就是关键。做好这类问题，重要的是把MATLAB 学好，特别是图象处理的部分。