/ E% ~2 w' q) r+ w- k ) z( `' }$ w) K M. P" W# _4 ?3 Z# H$ e3 m6 G( ^" x' N
三、线性规划、整数规划、多元规划、二次规划等规划类问题 7 d2 }7 W$ z) W8 Z数学建模竞赛中很多问题都和数学规划有关,可以说不少的模型都可以归结为一组不等式作为约束条件 / C; ]% P$ W- l2 o) n$ x+ E& Q7 P 0 c/ S5 @5 g/ j1 i) Y、几个函数表达式作为目标函数的问题,遇到这类问题,求解就是关键了,比如98年B题,用很多不等式: P7 y o, }, Q6 o! ~. F/ i
# S7 X9 S0 y' f4 w9 N+ l. ^8 g
完全可以把问题刻画清楚,因此列举出规划后用 Lindo 、 Lingo 等软件来进行解决比较方便,所以还3 y/ Z0 k: d( i+ G
5 l9 S' ^+ p/ |- O; O3 r# c# U需要熟悉这两个软件。 - Y9 a! c3 p: N9 }/ o1 D. @ G* T5 e$ T* B" u5 G3 F, f& R* l' q+ t, R g
4 D: f) w! e; T
( t) M3 ~* F% i3 w2 u* L4 j% v四、图论算法; t: w v# r5 j- d. U7 d
这类问题算法有很多, 8 Z1 T8 w1 U3 J8 b, ~) X* E5 `# D/ Z包括: Dijkstra 、 Floyd 、 Prim 、 Bellman-Ford ,最大流,二分匹配等问题。& b; m7 U9 S3 N3 D: b" @0 }
5 `6 b. W4 G( e! I% c
" x$ R, W6 r- k& s3 m* x& P ! Y9 v0 X5 T" _$ V# r, i关于此类图论算法,可参考Introduction to Algorithms--算法导论,关于图算法的第22章-第26章。# \+ o% c! X% c) k9 v& z
同时,本BLOG内经典算法研究系列,对Dijkstra算法有所简单描述, " V( ?) R# Y& {# X* z y0 |----------- $ m/ B# S# T. b8 J' M& Z: s经典算法研究系列:二、Dijkstra 算法初探" d' u0 J5 F, T
http://blog.csdn.net/v_JULY_v/archive/2010/12/24/6096981.aspx. L S. c+ o4 f. }7 b- o
& y/ u+ E$ h/ P8 C+ k& w: t
更多,请关注本BLOG 日后更新的博文。 ' W6 i$ _; s1 b / [/ X6 |8 Y: i" T" `% b( \9 N! Q% G5 W% k* e# i' R9 V4 F
5 K! h' ?% d9 s0 ^1 ~) u" b" t1 M' x( X2 F" ]( |
五、动态规划、回溯搜索、分治算法、分支定界等计算机算法 ; I& @$ ?( ^9 F0 S4 r! ~/ h9 ~在数学建模竞赛中,如:92 年B题用分枝定界法, 97年B题是典型的动态规划问题, 6 k, v P# g) ` [3 r此外 98 年 B 题体现了分治算法。 ! g; b' W2 W t4 M! q, U5 @- k+ y: b5 [' B
! t* d( h5 q# D7 m8 |/ P' G5 C
这方面问题和 ACM 程序设计竞赛中的问题类似,! }7 t$ V5 e5 r# i/ P9 g
推荐看一下算法导论,与《计算机算法设计与分析》(电子工业出版社)等与计算机算法有关的书。; i; E" b; G# E+ e
: l7 @9 `# |# n; n; e: S) C5 M * N- x1 d- l9 ]3 v' _ 8 u, G0 }& q6 i % d; p& M! F7 l) k& f3 C9 e j: F六、最优化理论的三大经典算法:模拟退火法、神经网络、遗传算法 2 z5 S/ p7 m, E这十几年来最优化理论有了飞速发展,模拟退火法、神经网络、遗传算法这三类算法发展很快。 + u% a$ y# `3 U# l2 w" c9 Z# b. {
在数学建模竞赛中:比如97年A题的模拟退火算法,00年B题的神经网络分类算法,01年B题这种难题也可 + X0 ~$ b( u8 b4 D, ? 7 G5 {( v7 L- w0 c以使用神经网络,还有美国竞赛89年A题也和 BP 算法有关系,当时是86年刚提出BP算法,89年就考了,# B7 ]3 H r9 D8 l$ q
5 R2 R& ?4 ?- J) \% h( I q
说明赛题可能是当今前沿科技的抽象体现。 7 l7 t5 d4 N: l' {$ k' b03 年 B 题伽马刀问题也是目前研究的课题,目前算法最佳的是遗传算法。 , |) y3 d- \$ D* {0 ~ ; p7 b2 ^. s. f W , |: W) x( f9 ~ * q9 j9 @. L, ^$ K另,本人对人工智能非常感兴趣,遗传算法已在本BLOG内有所阐述,敬请参见。 ( k O' ?# ~- y+ q* m& J---------- 5 B4 Z. k; q7 C; X经典算法研究系列:七、深入浅出遗传算法,透析GA本质" P$ i' Z9 U2 m- D* p6 m
http://blog.csdn.net/v_JULY_v/archive/2011/01/12/6132775.aspx 8 g1 u& r+ `9 ]$ E3 i- D' p9 y; U) N, H: ]- r" P8 R. x z0 M
' V Y7 I' X0 K. `' C% a6 Z! ^9 l5 l9 t4 L0 n! T, O
其它俩大算法,模拟退火法,与神经网络,也定会在本BLOG内日后的博文更新中,详细阐述。- x- z/ J' k7 p V+ s& I H0 c( H
+ y, j4 y# `4 _: b, {2 ^0 r
4 _0 e+ X8 f6 H w
" y G9 Z) ]9 o1 T$ u7 B
q& R* b+ c2 v% `2 r9 t
七、网格算法和穷举法$ H# R+ l/ m3 [/ k( r; u
网格算法和穷举法一样,只是网格法是连续问题的穷举。! G: F+ F. _) e& O4 E0 ]
比如要求在 N 个变量情况下的最优化问题,那么对这些变量可取的空间进行采点, # T2 ^& J. g/ ^7 Q# h% s比如在 [ a; b ] 区间内取 M +1 个点,就是 a; a +( b ? a ) =M; a +2 ¢ ( b ? a ) =M ; …;b 7 h' O. k4 h2 l" P8 u% F6 A* X. x8 Y' |5 Y: t& U. B9 h
那么这样循环就需要进行 ( M + 1) N 次运算,所以计算量很大。. A6 v# P' e+ `. [
, }& P5 v ]/ n( Z8 ]% ~! z" N. e* T. H+ B% I" s; o. W" o- {& P+ |9 u
在数学建模竞赛中:比如 97 年 A 题、 99 年 B 题都可以用网格法搜索,这种方法最好在运算速度较 ; b( w( ?+ y6 e. J! ~* [8 ?& p- `$ U# S: Z4 E2 E# ?
快的计算机中进行,还有要用高级语言来做,最好不要用 MATLAB 做网格,否则会算很久。5 f5 y1 Q0 y0 F' e# Y( W) T
$ Q3 s. ]# G( S3 w8 R b5 ?2 E
穷举法大家都熟悉,自不用多说了。 - { ^4 S4 i% }7 p
/ ?8 H" `1 u/ _1 s$ m0 x
5 h# b. l" o% c
7 @; t) v/ G( g# W