在线时间 90 小时 最后登录 2018-12-27 注册时间 2016-4-22 听众数 17 收听数 0 能力 20 分 体力 23381 点 威望 2 点 阅读权限 200 积分 7508 相册 0 日志 0 记录 0 帖子 126 主题 100 精华 1 分享 0 好友 6
升级 50.16%
TA的每日心情 开心 2018-6-4 15:01
签到天数: 7 天
[LV.3]偶尔看看II
群组 : 2018年大象老师国赛优
群组 : 高考备战
群组 : 2018中小学数学建模冬
2 T7 n6 f n& ]3 M& U/ `# D+ P 数学建模比赛 是本科生和研究生阶段最重要的比赛之一,包括全国大学生数学建模竞赛(俗称“国赛”)和美国大学生数学建模竞赛(俗称“美赛”)。在这些比赛中取得好成绩,不仅有助于保研、有助于找工作,更重要的是形成科学的思维模式。下面列举了十大算法,在数学建模竞赛中有着无比广泛而重要的应用。3 A% K7 d& |# d7 r& H! k
D1 `$ K) W- c$ e9 ?, d9 W& q
01
. g: i# Q, P6 A2 j% V
) l3 l( N5 w9 B3 Z5 W! f M* [/ C
蒙特卡罗算法
5 ^: B3 ^# o7 [ 1946 年,美国拉斯阿莫斯国家实验室的三位科学家 JohnvonNeumann, Stan Ulam和 Nick Metropolis 共同发明了蒙特卡罗方法。6 l) Z2 w) |4 g/ R9 g7 F$ k0 @
蒙特卡罗方法(Monte Carlo method),又称随机抽样或统计模拟方法,是一种以概率统计理论为指导的一类非常重要的数值计算方法。此方法使用随机数(或更常见的伪随机数)来解决很多计算问题的方法。
6 I1 I, H: H8 f& A* g3 ^
7 ~4 a$ Q+ J, h5 }$ ~' F 由于传统的经验方法由于不能逼近真实的物理过程,很难得到满意的结果,而蒙特卡罗方法由于能够真实地模拟实际物理过程,故解决问题与实际非常符合,可以得到很圆满的结果。- p3 u+ Y9 P, R# `
5 f$ t" N2 @4 q1 e% o/ f4 W" T) B
蒙特卡罗方法的基本原理及思想如下:
$ Q# w/ H9 h3 s& n$ _: Y/ ^$ E( S 1 o. C' U' I6 D( o9 _; S: k- _) I
当所求解问题是某种随机事件出现的概率,或者是某个随机变量的期望值时,通过某种“实验”的方法,以这种事件出现的频率估计这一随机事件的概率,或者得到这个随机变量的某些数字特征,并将其作为问题的解。
7 q! K: j; ?9 j/ M+ a* G
7 n; M$ b! Y9 x x. q 举个栗子,直观了解蒙特卡洛方法: ! x. K/ h2 j* [, J8 d; l5 N# I
7 a4 r1 U D! M8 r
假设我们要计算一个不规则图形的面积,那么图形的不规则程度和分析性计算(比如:积分)的复杂程度是成正比的。蒙特卡洛方法是怎么计算的呢?假想你有一袋豆子,把豆子均匀地朝这个图形上撒,然后数这个图形之中有多少颗豆子,这个豆子的数目就是图形的面积。当你的豆子越小,撒的越多的时候,结果就越精确。在这里我们要假定豆子都在一个平面上,相互之间没有重叠。) y. H" ~, m- {, T2 O* v T
- f, l& W7 j% j* w
- x1 K. D; a# \2 a% C" m" t# l 蒙特卡罗方法通过抓住事物运动的几何数量和几何特征,利用数学方法来加以模拟,即进行一种数字模拟实验。它是以一个概率模型为基础,按照这个模型所描绘的过程,通过模拟实验的结果,作为问题的近似解。
5 p) H6 q, K$ K
" b. U" Z! \$ r0 n- ?2 x ~1 a( g/ P 蒙特卡罗方法与一般计算方法有很大区别,一般计算方法对于解决多维或因素复杂的问题非常困难,而蒙特卡罗方法对于解决这方面的问题却比较简单。其特点如下:
- _5 M8 e/ J# B' o/ x4 |& U5 q & x- C; b4 ^ [
a、 直接追踪粒子,物理思路清晰,易于理解;
) w: I& y, ?; Y6 \; t+ Z7 V, T1 O + g, w" E- p" @) g$ b x
b、 采用随机抽样的方法,较真切的模拟粒子输运的过程,反映了统计涨落的规律;/ g+ |8 h( v' B h6 n
9 X0 W2 l; }! l8 w H
c、 不受系统多维、多因素等复杂性的限制,是解决复杂系统粒子输运问题的好方法等等* l9 z* i D# s. D/ E' d
+ t `+ C l; y7 [" S
02
c! |5 R) I2 P' `$ X1 v4 @! V
6 f* j$ v! g3 M0 j. n5 w 数据拟合、参数估计、插值等数据处理算法
8 f# T9 D& m5 u- t* w ' W4 Z, i5 ?4 ?
我们通常会遇到大量的数据需要处理,而处理数据的关键就在于这些算法,通常使用 Matlab 作为工具。0 D, |! t7 H, ^( r, ^3 L4 B
! g6 N) a2 q/ k" r# c 数据拟合在数学建模比赛中中有应用,与图形处理有关的问题很多与拟合有关系,一个例子就是 98 年数学建模美国赛 A 题,生物组织切片的三维插值处理,94 年 A 题逢山开路,山体海拔高度的插值计算,还有吵的沸沸扬扬可能会考的“非典”问题也要用到数据拟合算法,观察数据的走向进行处理。
, F4 E, }" S7 V 5 a* b: m8 w2 i7 l( x2 j' z
+ m1 ]) Q6 \8 H+ l1 A O" `
此类问题在 MATLAB 中有很多现成的函数可以调用,熟悉 MATLAB,这些方法都能游刃有余的用好。% G# m+ B7 p% w& b1 U
! \7 a9 N6 w. [8 d& { 03
* A# ]+ t( x' E! C3 k' M- t1 u4 W
( X9 s3 W3 ~# _ Q/ v5 G 线性规划、整数规划、多元规划、二次规划等规划类问题
, g% g3 F( q$ k K0 z) P * c: U o$ L3 E( W
数学建模竞赛中很多问题都和数学规划有关,可以说不少的模型都可以归结为一组不等式作为约束条件、几个函数表达式作为目标函数的问题。
7 @! y$ S7 Z [* z8 F- x 1 ]6 p1 x) J# K
遇到这类问题,求解就是关键了,比如 98 年 B 题,用很多不等式完全可以把问题刻画清楚,因此列举出规划后用 Lindo、Lingo 等软件来进行解决比较方便,所以还需要熟悉这两个软件。
2 o; i/ h8 W f6 L
' k6 u }4 _" l 04
9 o" l, V0 _, U: e7 ~$ H/ U; [
1 a3 g, M( v# ^( R3 J# x 图论算法
/ a, a1 V* @' G/ J/ K- N 5 |5 y" h$ `( B$ N
这类问题算法有很多,包括:Dijkstra、Floyd、Prim、Bellman-Ford,最大流,二分匹配等问题。1 \ v; J. q& Z, }) Y7 H
8 g. L0 F% a' I+ x; Z+ H$ {/ g0 D 关于此类图论算法,可参考 IntroductiontoAlgorithms--算法导论,关于图算法的第22章-第26章。, n+ C7 ]- L5 Z9 y( t( N
$ F+ o l" Z; C: k
" c* r2 G9 x' K/ P6 Z" [( G' T " {/ [* E- E. \; U! _- k& g
* O% D& T! _- C9 i" G 05
' R6 [/ Z# O/ U9 ?
: w0 V& ~% j. F" i) ^; X3 S 动态规划、回溯搜索、分治算法、分支定界等计算机算法
% |9 c2 q- t2 _: ?& f
- {, V3 \* j" i% D! x9 K 在数学建模竞赛中,如:92 年 B 题用分枝定界法,97年 B 题是典型的动态规划问题,此外 98 年 B 题体现了分治算法。
3 z0 {: q1 G# ^! k1 G! X9 A
) g" J' u3 ]9 n# F) H$ S
3 v) D2 p6 K0 y/ b/ m
这方面问题和 ACM 程序设计竞赛中的问题类似,推荐看一下算法导论,与《计算机算法设计与分析》(电子工业出版社)等与计算机算法有关的书。& O' ]* A& P& v5 [; C
' u3 r2 m4 F& k: n3 W& I5 |$ a/ [ 06
0 U/ u, S7 V6 p, d% f3 h6 x
! R' J6 X4 L- ?; r
最优化理论的三大经典算法:模拟退火法、神经网络、遗传算法
5 R' n& a; I% R " ^2 ]' v' G5 c- y8 D
这十几年来最优化理论有了飞速发展,模拟退火法、神经网络、遗传算法这三类算法发展很快。
9 T# T# o1 _/ e3 ~ x & E# d. y: P0 g- n7 |/ G1 j$ s" @
在数学建模竞赛中:比如 97 年 A 题的模拟退火算法,00 年 B 题的神经网络分类算法,01 年 B 题这种难题也可以使用神经网络。6 S0 Z* }2 ^- r6 d9 R7 @
! Y$ l$ [. _% C0 r, K, M
还有美国竞赛 89 年 A 题也和 BP 算法有关系,当时是 86 年刚提出 BP 算法,89 年就考了,说明赛题可能是当今前沿科技的抽象体现。+ H6 A5 t% i4 r I y% a( I: l3 K
* m1 I9 d8 F: s- D- n: i 03 年 B 题伽马刀问题也是目前研究的课题,目前算法最佳的是遗传算法。1 a6 M1 p3 z) c& d. O0 y0 m0 F2 a
& @, p8 G1 i, {' H7 K, I3 |7 w1 S

* c( ] k1 i) x$ h/ Z% t : ~3 a; t% |2 j3 V7 p9 o. s: }: B
0 ~% u% f5 V4 \$ _/ o: R( p 07
9 l3 {9 [ h2 \8 P# R ) C2 R F( O# T) Y. B+ {2 i
网格算法和穷举法
2 @( I- v$ j5 r , I; k% Z* |! p" Q4 Z* o, I
网格算法和穷举法一样,只是网格法是连续问题的穷举。% o5 k9 L. w) p2 b7 z
5 Y3 u8 I8 C1 {6 J) g' C 比如要求在 N 个变量情况下的最优化问题,那么对这些变量可取的空间进行采点,比如在 [a;b] 区间内取 M+1 个点,那么这样循环就需要进行 (M+1)N 次运算,所以计算量很大。
8 r3 w# n6 B4 l: i1 T+ h& h
3 J" z0 O) E1 v# ? 在数学建模竞赛中:比如 97 年 A 题、99 年 B 题都可以用网格法搜索,这种方法最好在运算速度较快的计算机中进行,还有要用高级语言来做,最好不要用MATLAB 做网格,否则会算很久。
+ W2 m1 c1 u& ]
0 \/ u$ V% R" T' |! J+ Q x! v 
5 G8 A' \1 x1 Z, X* E, J
7 I$ W5 V: H" j% R" G1 @6 h. t+ c 穷举法大家都熟悉,自不用多说了。
7 D9 ~- K' a1 }& k, _9 f* `. Y. ]8 V . q* L$ |' B: e- n8 e
08
1 S2 n4 W+ I; u( Q# X- V4 @
/ L: w+ V6 [. a 一些连续离散化方法
" Q7 ^+ x c( ^1 [9 D( G
) s' N: _& P5 p8 z- _ T 大部分物理问题的编程解决,都和这种方法有一定的联系。物理问题是反映我们生活在一个连续的世界中,计算机只能处理离散的量,所以需要对连续量进行离散处理。
# W5 M! s) b2 i2 e
, {" i8 g$ X K7 V8 K2 |2 n& L 这种方法应用很广,而且和上面的很多算法有关。事实上,网格算法、蒙特卡罗算法、模拟退火都用了这个思想。
6 q$ d1 C: R. q* |
: `/ H8 U3 H% h; i5 q* g. ` 09
% f# m& x, y7 j# r5 X( k) o
' Z. Y( ^* U5 {% i9 x
数值分析算法
3 O6 h! m7 b& U! d% E
9 s7 p; @- v5 e5 s) ?2 s7 E5 a% r 数值分析(numericalanalysis),是数学的一个分支,主要研究连续数学(区别于离散数学)问题的算法。
3 V5 p6 ]. B/ i$ V8 n5 t7 k7 q4 ^ & M! D5 y$ c% x! K
如果在比赛中采用高级语言进行编程的话,那一些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用。8 b- `( }5 o6 y4 P, E4 F H
^. N) w$ M8 @. c$ r- r
这类算法是针对高级语言而专门设的,如果你用的是 MATLAB、Mathematica,大可不必准备,因为像数值分析中有很多函数一般的数学软件是具备的。; `; g1 x4 J5 M6 N% ^3 ?4 \
( [: \! x& i. k, Y6 ^ 10
, H' k5 J& s3 s4 \ ! {- G5 w; ]: D# w8 {5 ~
图象处理算法
- Z) Z4 d ]/ z8 X( ^+ K
$ }1 {/ O: U" L 在数学建模竞赛中:比如 01 年 A 题中需要你会读 BMP 图象、美国赛 98 年 A 题需要你知道三维插值计算,03 年 B 题要求更高,不但需要编程计算还要进行处理,而数模论文中也有很多图片需要展示,因此图象处理就是关键。做好这类问题,重要的是把 MATLAB 学好,特别是图象处理的部分。4 S3 t+ E; R' x2 h% T9 ]) a2 M
- [; |; i# k6 F1 a
6 G7 V2 w2 O; a( h; ^( p) A
9 T. W, J0 _' S. { r. @, ?# d) _
zan