数学建模算法有哪些?
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很重要,尤其是图像处理部分。