1 S# ~& E0 G/ {. [ V" Y1 D* K+ a- I0 o. h) I
举个栗子,直观了解蒙特卡洛方法: Z L. ]2 F) m. a. K
3 m3 c9 T7 `8 n" Z P5 c/ D) N 9 E+ U; {' z% G: I% d& V7 _8 J8 `假设我们要计算一个不规则图形的面积,那么图形的不规则程度和分析性计算(比如:积分)的复杂程度是成正比的。蒙特卡洛方法是怎么计算的呢?假想你有一袋豆子,把豆子均匀地朝这个图形上撒,然后数这个图形之中有多少颗豆子,这个豆子的数目就是图形的面积。当你的豆子越小,撒的越多的时候,结果就越精确。在这里我们要假定豆子都在一个平面上,相互之间没有重叠。 # {0 T# [/ ?% k/ r# s- f / \, W5 u6 \' b) g/ q# A& R2 i Y; a. m. c
* _8 H9 ^4 d8 z$ h
) Z% X* ^1 N4 H8 E5 `3 o* U
, {! F+ I% u$ s* r% A- N, {2 s" c) \8 O2 t$ p% @+ h
蒙特卡罗方法通过抓住事物运动的几何数量和几何特征,利用数学方法来加以模拟,即进行一种数字模拟实验。它是以一个概率模型为基础,按照这个模型所描绘的过程,通过模拟实验的结果,作为问题的近似解。 * f# h/ B, i; N M. h2 v$ Z1 \9 X' r1 i h+ E
. k, P# k9 D8 d. E蒙特卡罗方法与一般计算方法有很大区别,一般计算方法对于解决多维或因素复杂的问题非常困难,而蒙特卡罗方法对于解决这方面的问题却比较简单。其特点如下: ; G# y- U$ V7 @ C7 h( D* y ]- k 3 |# K6 r' q$ d7 ?; G4 [& t& |% k' b. V9 a( {: r
a、直接追踪粒子,物理思路清晰,易于理解;( ]( l ^% K4 [' p
$ }+ A" E( a% U
3 X6 x ]* F0 R2 D: B
b、采用随机抽样的方法,较真切的模拟粒子输运的过程,反映了统计涨落的规律;$ o: I1 {1 K: `! p; P& q: C
' Y0 ^1 L: p0 W3 |) u
8 F, y" x8 Z5 G! \3 m- h Vc、不受系统多维、多因素等复杂性的限制,是解决复杂系统粒子输运问题的好方法 9 q. }6 s3 ^" y, t( k: s6 F2 `/ \; `9 [3 n, [+ ^# _
2 U6 s4 p8 H, m+ E
等等8 K" V3 J" `; }
r, P$ u9 m/ D3 a
) r- W) ^3 C6 k$ v6 z( ~' p% n. h 02 数据拟合、参数估计、插值等数据处理算法( f! l, k8 y1 ^* }! s2 t, p3 x6 ~! y: f$ i) t
我们通常会遇到大量的数据需要处理,而处理数据的关键就在于这些算法,通常使用 Matlab 作为工具。 , |" B: D) g& ~. x) E9 U; g; P / g& a- h9 X# W! ^ . {8 p( P5 g' D数据拟合在数学建模比赛中中有应用,与图形处理有关的问题很多与拟合有关系,一个例子就是 98 年数学建模美国赛 A 题,生物组织切片的三维插值处理,94 年 A 题逢山开路,山体海拔高度的插值计算,还有吵的沸沸扬扬可能会考的“非典”问题也要用到数据拟合算法,观察数据的走向进行处理。2 @* R; A' ^' K0 u* {; C$ x! P1 O6 F
% S; N1 G! l7 p' ^# K, r3 k 7 l- K" r% A1 C4 t3 p % A; o+ L0 J* H6 C; L5 D: i ) Y+ K" r |# W& `$ w " x* j5 @# ?' @; {; U- d, u# n4 s8 ~+ @1 N& b9 I+ ~2 }& H
此类问题在 MATLAB 中有很多现成的函数可以调用,熟悉 MATLAB,这些方法都能游刃有余的用好。$ c1 W* E9 |" f. u! }+ S8 A- `4 y: R
; f+ _: [# Y S4 h) J, M& I! W遇到这类问题,求解就是关键了,比如 98 年 B 题,用很多不等式完全可以把问题刻画清楚,因此列举出规划后用 Lindo、Lingo 等软件来进行解决比较方便,所以还需要熟悉这两个软件。4 u- b; z! T! h( ^9 q
) h) H2 e+ G1 I$ Z8 S0 u* o
& @' G+ c s4 r/ e; ]
04 图论算法 . D B* M o* n$ ]/ w这类问题算法有很多,包括:Dijkstra、Floyd、Prim、Bellman-Ford,最大流,二分匹配等问题。 6 @8 C+ z% G! _+ w3 l, ~- I9 Z, |8 [- ~5 Z8 s& C
' ], `5 ~( f1 {( D
关于此类图论算法,可参考 IntroductiontoAlgorithms--算法导论,关于图算法的第22章-第26章。 * V0 Y6 P" V: h) k7 C/ d1 h ; `( |% X. R5 e' J% J0 k# H F T6 _/ p: g. b2 j( ]: }) }
) ]) K G1 \- r, K+ K! V; e U# r# H& x+ w- z F. y
" `: I) D1 n% O4 @% F$ v. a' }
05 动态规划、回溯搜索、分治算法、分支定界等计算机算法+ k7 `$ ~$ k, v& q z4 g4 [
在数学建模竞赛中,如:92 年 B 题用分枝定界法,97年 B 题是典型的动态规划问题,此外 98 年 B 题体现了分治算法。 * B0 E. V1 C. D- k5 k/ I7 W( b8 Q2 {" H0 E
3 a0 j9 Y3 `5 a- y/ x {+ w) s 06 最优化理论的三大经典算法:模拟退火法、神经网络、遗传算法2 u' y% l4 ^+ C& q% ~, J) `
这十几年来最优化理论有了飞速发展,模拟退火法、神经网络、遗传算法这三类算法发展很快。 : ^/ \& X7 R5 c1 J6 I0 {! A( Y& ^5 h! l4 O J7 E1 }
( M: d& n1 Y+ A: G. p2 h H
在数学建模竞赛中:比如 97 年 A 题的模拟退火算法,00 年 B 题的神经网络分类算法,01 年 B 题这种难题也可以使用神经网络。 3 K# ?1 F9 z5 y3 ]3 L0 Z ' G, X. T0 ^1 ]9 g5 ~" z" X: {% Z; e% f
还有美国竞赛 89 年 A 题也和 BP 算法有关系,当时是 86 年刚提出 BP 算法,89 年就考了,说明赛题可能是当今前沿科技的抽象体现。 ! I& b& r& j7 C) B4 g * M! d O1 z6 {* b& t: }# R: o) e2 y$ @3 G3 h0 s; O/ u. T" B' f
03 年 B 题伽马刀问题也是目前研究的课题,目前算法最佳的是遗传算法。& J% V6 N$ e7 E6 C3 b' R0 c
0 v7 q6 {: b s
1 k* x& [" e6 k& T- o
; d+ l& h. i+ S8 q5 O
/ v; `$ H0 U) p r' I6 H1 j. S / R* w( }1 u- U; R 2 Y, S* s { i" N + H9 Y/ I% w y. \, V 5 u$ B6 F8 T2 p. u$ n0 {- g+ d2 ~/ B" b* c7 W; Q
07 网格算法和穷举法 ! V3 R! A7 Y' H: n4 b: |& V7 w网格算法和穷举法一样,只是网格法是连续问题的穷举。8 B( l# e( B' Z
7 K) f& |, t n0 P
/ Z3 T/ {) D$ I0 m5 X& b比如要求在 N 个变量情况下的最优化问题,那么对这些变量可取的空间进行采点,比如在 [a;b] 区间内取 M+1 个点,那么这样循环就需要进行 (M+1)N 次运算,所以计算量很大。% a/ U, v6 c6 t% x
- ]2 h. R _! ]: J v: k- k - J' C, _! r: G在数学建模竞赛中:比如 97 年 A 题、99 年 B 题都可以用网格法搜索,这种方法最好在运算速度较快的计算机中进行,还有要用高级语言来做,最好不要用MATLAB 做网格,否则会算很久。7 h4 j; i7 A& k) F