数学建模社区-数学中国
标题: 数学建模竞赛必须要掌握的十个算法 [打印本页]
作者: 佛自业障 时间: 2018-10-29 10:01
标题: 数学建模竞赛必须要掌握的十个算法
[attach]242204[/attach]
8 m6 Z5 U& A9 e# }" L
数学建模比赛是本科生和研究生阶段最重要的比赛之一，包括全国大学生数学建模竞赛（俗称“国赛”）和美国大学生数学建模竞赛（俗称“美赛”）。在这些比赛中取得好成绩，不仅有助于保研、有助于找工作，更重要的是形成科学的思维模式。下面列举了十大算法，在数学建模竞赛中有着无比广泛而重要的应用。
1 d) M5 U8 \$ ^# a. ?0 ]
' T" `# ^; y% I. o 01
4 h; l6 O) r7 f, J. z- j! J, ^+ |: H7 I; K, K5 U
蒙特卡罗算法
9 n; G: f0 E1 P. V1946 年，美国拉斯阿莫斯国家实验室的三位科学家 JohnvonNeumann, Stan Ulam和 Nick Metropolis 共同发明了蒙特卡罗方法。
! h5 G" s& h9 r6 D! S8 v* U4 p蒙特卡罗方法（Monte Carlo method），又称随机抽样或统计模拟方法，是一种以概率统计理论为指导的一类非常重要的数值计算方法。此方法使用随机数（或更常见的伪随机数）来解决很多计算问题的方法。
5 Q! |( q7 |! E" I3 o7 L& a. X" h3 |: \
由于传统的经验方法由于不能逼近真实的物理过程，很难得到满意的结果，而蒙特卡罗方法由于能够真实地模拟实际物理过程，故解决问题与实际非常符合，可以得到很圆满的结果。4 p9 S( f, x/ _2 @
, v/ U& e2 O0 W+ ]
蒙特卡罗方法的基本原理及思想如下：4 E* t6 L. e" G% q' m" j( c! R
+ N! k( d8 J7 n当所求解问题是某种随机事件出现的概率，或者是某个随机变量的期望值时，通过某种“实验”的方法，以这种事件出现的频率估计这一随机事件的概率，或者得到这个随机变量的某些数字特征，并将其作为问题的解。
9 F$ X# N1 ~2 K8 n' s' f* P$ A- r3 I N$ ]: O( H
举个栗子，直观了解蒙特卡洛方法：7 V8 X9 D5 F; W" U% u- T0 J& k" N
# Z( F1 R* f1 _7 s5 j( X* X3 |+ s
假设我们要计算一个不规则图形的面积，那么图形的不规则程度和分析性计算（比如：积分）的复杂程度是成正比的。蒙特卡洛方法是怎么计算的呢？假想你有一袋豆子，把豆子均匀地朝这个图形上撒，然后数这个图形之中有多少颗豆子，这个豆子的数目就是图形的面积。当你的豆子越小，撒的越多的时候，结果就越精确。在这里我们要假定豆子都在一个平面上，相互之间没有重叠。7 y3 y% Y1 A1 p Y
: d8 ?) h' H) k/ I
[attach]242205[/attach]
' P- E) S7 y: G7 g蒙特卡罗方法通过抓住事物运动的几何数量和几何特征，利用数学方法来加以模拟，即进行一种数字模拟实验。它是以一个概率模型为基础，按照这个模型所描绘的过程，通过模拟实验的结果，作为问题的近似解。
: z1 \" C9 a) B. R+ A
) p' w( R4 \5 E+ j' O- ?蒙特卡罗方法与一般计算方法有很大区别，一般计算方法对于解决多维或因素复杂的问题非常困难，而蒙特卡罗方法对于解决这方面的问题却比较简单。其特点如下：# i4 P. Q! m; {) M& Y
0 C$ \* A/ x2 V4 u& G
a、直接追踪粒子，物理思路清晰，易于理解；; E# S1 _$ I8 U
/ I0 Z5 I4 Y7 e' F# Qb、采用随机抽样的方法，较真切的模拟粒子输运的过程，反映了统计涨落的规律；2 B4 V$ H! G9 Z. E4 d- t2 X
2 }) x! K9 k$ ]- D* k5 Mc、不受系统多维、多因素等复杂性的限制，是解决复杂系统粒子输运问题的好方法等等7 n+ g. i$ W" s w
7 ^# ?! e& |: n
02
5 [- ^5 \' y9 G5 X' @
$ z5 O. V9 w/ g' _$ B
数据拟合、参数估计、插值等数据处理算法
p0 b1 V4 }! Y2 U
: q$ ?8 G% K: N2 k. d8 g* p
我们通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用 Matlab 作为工具。+ Q7 m0 {3 X2 Z. h" m9 d
7 l) | l2 F* _; o6 n数据拟合在数学建模比赛中中有应用，与图形处理有关的问题很多与拟合有关系，一个例子就是 98 年数学建模美国赛 A 题，生物组织切片的三维插值处理，94 年 A 题逢山开路，山体海拔高度的插值计算，还有吵的沸沸扬扬可能会考的“非典”问题也要用到数据拟合算法，观察数据的走向进行处理。
- w E% t* k# ?. {7 B
, ~0 ?$ ]0 I4 z# P6 x; `[attach]242206[/attach]
: F3 J7 f* D% c& T: y w4 V
此类问题在 MATLAB 中有很多现成的函数可以调用，熟悉 MATLAB，这些方法都能游刃有余的用好。
1 m% |; G) m8 b8 u% f F
* u; r: Y g$ |) y. }, Z 03
0 B$ n" [) f. P8 e( m1 V$ w. L) Y6 E% @- [
线性规划、整数规划、多元规划、二次规划等规划类问题
2 |# [' Q- v3 u: {
/ e* L, ^; r* v9 Y" ^% I
数学建模竞赛中很多问题都和数学规划有关，可以说不少的模型都可以归结为一组不等式作为约束条件、几个函数表达式作为目标函数的问题。 u, d( u' M: m
a* }8 L3 D: f/ x, u: k/ g
遇到这类问题，求解就是关键了，比如 98 年 B 题，用很多不等式完全可以把问题刻画清楚，因此列举出规划后用 Lindo、Lingo 等软件来进行解决比较方便，所以还需要熟悉这两个软件。& m% ~. p' ~- Q* k ]
0 B" H7 J* v7 p! A 04
V. M3 y$ C2 P& i9 N5 c
! o) k# x. v I4 V9 J9 Y图论算法
! r. C s! e) H# T- J! B1 a9 l) X+ z+ x. H
这类问题算法有很多，包括：Dijkstra、Floyd、Prim、Bellman-Ford，最大流，二分匹配等问题。
6 F$ | p* u- M' u; x
V3 `! _2 G9 ]8 [6 M关于此类图论算法，可参考 IntroductiontoAlgorithms--算法导论，关于图算法的第22章-第26章。2 M1 N0 z$ N* t; M7 y% M3 i, k# u
' f4 e. O: }) E# S4 E[attach]242207[/attach]
0 Q9 y8 X/ v9 O* v5 @0 }. o* e- o

' f' k) ~3 I. r
( J% s$ |/ Y, R' I' a8 J 05
8 z \* k7 F2 u4 b; J& f6 c) r- u. a+ T( L6 T" ^* l- `2 {1 m
动态规划、回溯搜索、分治算法、分支定界等计算机算法
- o* D* `) M6 z
9 N5 Q9 K7 \( e- y/ i& [' r& }. D, k
在数学建模竞赛中，如：92 年 B 题用分枝定界法，97年 B 题是典型的动态规划问题，此外 98 年 B 题体现了分治算法。
% J; H) {8 F6 u9 l) m6 C9 Q3 B) U2 w" i; |% y% r9 \
[attach]242208[/attach]
) K5 C4 V5 N/ a% U这方面问题和 ACM 程序设计竞赛中的问题类似，推荐看一下算法导论，与《计算机算法设计与分析》（电子工业出版社）等与计算机算法有关的书。$ N. b9 k/ B" N3 Y" o' ?
{- u' ?( A* G
06
0 z. V/ @ U+ F# |
9 B& S# G" F. q3 C1 X- [
最优化理论的三大经典算法：模拟退火法、神经网络、遗传算法
* y$ h$ E h. j* M6 [5 }2 }& |
) N' p! d$ V8 y8 Z D这十几年来最优化理论有了飞速发展，模拟退火法、神经网络、遗传算法这三类算法发展很快。
4 Y+ |, j }$ x+ a* h3 z! N# [& {+ F3 {
在数学建模竞赛中：比如 97 年 A 题的模拟退火算法，00 年 B 题的神经网络分类算法，01 年 B 题这种难题也可以使用神经网络。
8 X2 A+ [6 y2 _: ]
5 B: }" w7 ]& _" P/ `; y- w1 F还有美国竞赛 89 年 A 题也和 BP 算法有关系，当时是 86 年刚提出 BP 算法，89 年就考了，说明赛题可能是当今前沿科技的抽象体现。
7 _0 K, a3 |7 E0 X1 T/ e! D$ E% m
03 年 B 题伽马刀问题也是目前研究的课题，目前算法最佳的是遗传算法。
! t% f9 z' Y6 D/ o6 M0 _ {, m" Q, ~

$ A8 V' P0 _, M
$ p; f$ k3 t4 k% W- |8 L9 G. A
07
* u0 J @7 o6 Q! P4 O& Y* _, x- B9 F/ C. d! |% q1 ]& z
网格算法和穷举法
/ V/ T9 F3 q4 A2 O) }
3 G$ g5 t3 K) W: {; h+ `# P
网格算法和穷举法一样，只是网格法是连续问题的穷举。
j' q) k' p, N, y0 Z0 S' m% T
# q6 C4 x+ E& g& [; `比如要求在 N 个变量情况下的最优化问题，那么对这些变量可取的空间进行采点，比如在 [a;b] 区间内取 M+1 个点，那么这样循环就需要进行 (M+1)N 次运算，所以计算量很大。
/ [+ `+ P! ^# H7 F! g* d. Z; }' L6 Y- W( ^! ?0 ?
在数学建模竞赛中：比如 97 年 A 题、99 年 B 题都可以用网格法搜索，这种方法最好在运算速度较快的计算机中进行，还有要用高级语言来做，最好不要用MATLAB 做网格，否则会算很久。
$ k( f$ v" j# `9 c! e2 q( e7 N# s( }
4 E# y9 ^! V6 K/ T
: d# L. v2 u( Z3 q. ~1 b4 \穷举法大家都熟悉，自不用多说了。
5 R% y8 i9 p! i# M0 q2 ~* F6 q
: N0 G4 y, v2 c& K' u4 U* K9 P+ l 08
* o: j5 A0 y, L
4 f+ B- Y0 v( J! ~* @4 ^8 o一些连续离散化方法
9 c" K6 t: A u6 B: c5 W0 B2 j
. N' E5 U$ q7 M" ?; q" t
大部分物理问题的编程解决，都和这种方法有一定的联系。物理问题是反映我们生活在一个连续的世界中，计算机只能处理离散的量，所以需要对连续量进行离散处理。
& w$ S" d+ m0 L q L8 [ T7 b* C
0 j/ a0 z8 f3 M% i" `0 V这种方法应用很广，而且和上面的很多算法有关。事实上，网格算法、蒙特卡罗算法、模拟退火都用了这个思想。7 J+ J. L1 H" x( ~* I2 W
% ]; Z: [ E, H& o
09
2 T* m5 m0 Y$ [
! W8 ?4 J. h& R3 t
数值分析算法
- q/ Y' v8 i3 c
+ i( S7 w B6 C# `6 K# H F
数值分析（numericalanalysis），是数学的一个分支，主要研究连续数学（区别于离散数学）问题的算法。
) y1 f2 M4 V% T4 ]( N r1 G
: z5 ?, @- r9 Q; X' z如果在比赛中采用高级语言进行编程的话，那一些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用。; @$ T" N- e* r2 c8 U6 {
8 M- ~8 v2 A1 T# _
这类算法是针对高级语言而专门设的，如果你用的是 MATLAB、Mathematica，大可不必准备，因为像数值分析中有很多函数一般的数学软件是具备的。
/ e, [1 M1 p8 g3 u' z. a, O6 F4 l
0 t5 N j8 w+ e0 o C 10
0 ^0 e0 r, T" |
+ `0 x2 L" ^2 }# A图象处理算法
4 t" J7 G# q4 H, M
7 R+ I- B( d! H3 R2 @在数学建模竞赛中：比如 01 年 A 题中需要你会读 BMP 图象、美国赛 98 年 A 题需要你知道三维插值计算，03 年 B 题要求更高，不但需要编程计算还要进行处理，而数模论文中也有很多图片需要展示，因此图象处理就是关键。做好这类问题，重要的是把 MATLAB 学好，特别是图象处理的部分。& [7 `# N7 \3 e+ p
4 q+ g2 o$ X% S* d" D" y8 }9 Q
- f/ w3 d1 }) v0 A, u7 d
2 x5 q9 A4 W1 F3 x \- P, N b8 ?
. V2 m6 \7 g& C% O: j' i2 e" C" z4 \0 ^
作者: GsBush23 时间: 2018-11-14 14:06
说的太好了。。
( T1 E8 W( n" F& x
作者: pazq18 时间: 2018-12-7 10:00
楼主的帖子怎么样？赶紧试试这里看样子是好东西啊的快速回复给楼主点评论吧) ~$ S( y8 T: s0 Z4 N
| 欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) |
Powered by Discuz! X2.5 |