数学建模社区-数学中国
标题:
借鉴经验3——进阶篇
[打印本页]
作者:
森之张卫东
时间:
2015-8-1 11:17
标题:
借鉴经验3——进阶篇
由于我这四年基本上没有做过连续题,所以下面的内容都是关于离散的。数模离不开数学基础。一般,
, V/ T$ N7 H1 P m0 V$ l
离散问题大都是最优化问题,所以《
运筹学》和《离散数学》
是必看的。看《运筹学》的话要明白怎么
6 c# P3 p! ]& K* P9 [! ^
建立规划模型,包括线性规划、整数规划、多目标规划等。学完这些知识后就可以开始尝试看一些数模
% N' \ N5 N# Z/ x. [7 `. ~ X
题,开始自己建立模型了。但是,这些是远远不够的模型建立后要会分析和求解,需要算法的积累。在
- S3 _. Y) I+ O& M- o V" ~
比赛时有大量的数据需要处理,模型也会相对复杂,只掌握一个单纯型法的手算显然是不行的。算法的
, J( `; d! z, T0 {# w
学习推荐两本书,
入门级别的王晓东的《算法设计与分析》,
然后看
《算法导论》。
这里推荐从贪心
% I* ?- r- ^( ]1 L' L& B
看起,
贪心问题
对于初学者来说比较容易理解,一些经典的流程安排问题建议大家自己写程序实现一下,
/ |6 c( [# o, x
可以印象深刻。贪心虽然是最简单的算法,但在数学建模中仍然很常用。
4 ~, r2 u: \3 m% a, e0 x
然后看
动态规划
,相对与贪心来说,动态规划要抽象很多,所以不仅要看书上的介绍,建议结合网上
5 g3 m, c6 a, v1 h8 s+ H
的经典教程——背包九讲一起学习。
% P! O5 O1 }) ^- ~5 d* j8 P
但是一些不是特别容易实现的动态规划技巧,比如树形DP、斜率优化、插头DP等,有兴趣可以看看,
- h% }( p! |1 n# _% M$ \
但在数模中一般用处不大。
" @* G% v/ h* O- `- T s- ~' n
图论
也是相对庞大的一块内容,这里建议大家先看完《离散数学》中图的基本概念后,从最短路、最
1 X7 Y/ H* d; c; ?9 s
小生成树算法看起。因为这些算法都是比较常用的,如04年国赛的奥运会问题和11年国赛的交巡警平
' Z. J% K7 O3 d% T% H' ~& f
台设置问题都有用到。
6 u7 S5 R( q/ N+ M" Y6 S# G
接着学习一些二分图匹配的算法,包括匈牙利和KM,理解怎么建图,怎么进行匹配。这些算法属于
* P2 V" f1 {: J2 _0 G# t
进阶部分,我们学校曾经在09和11年国赛时把最优化模型转化为二分图匹配的两篇文章分别获得了国
( h' y; z( }! n3 L4 o, o4 s
二和国一。
+ L; t, c" J9 C9 ~
此外有时间可以研究一下网络流算法,虽然这几年的国赛都少有涉及,但是DINIC和ISAP之类的算法
K2 o0 N6 J3 o* o1 o
思想本身就很精妙,值得学习积累。
( @, ]' O0 L( G
演化算法
在数学建模中也非常常用,这里推荐先看模拟退火,算法思想简洁,代码实现也比较容易。
( @! K4 g; n( R
然后可以看一些粒子群优化算法,包括用粒子群优化算法解决多目标规划的问题(MOPSO),我个
3 J# U2 k9 g. c
人觉得是对多目标规划问题的一种比较好的求解方案。此外可以掌握些遗传算法、
/ _# A& P: {& x9 Q7 A$ o
differential evolution等算法。
; z/ }2 O' h4 b$ l. {
其他一些评估模型的常用算法,
如TOPSIS、熵权系数也建议掌握。
J/ H& ^! J3 S* P6 e0 x* g r* Z- _
排队论的几个模型在很多地方都适用,也尽量掌握。对于这些常用的算法,
建议一支队伍能准备
$ e# v: ~) ]6 X2 Y- W
一套模板,
确保上面的程序每个都看过、用过,最好加上必要的注释,包括算法复杂度、重要参数的意义等。
- y9 b S; c# R( W/ _6 T
, b. ] n+ ^# _' s; ] S
. N8 K6 U/ {0 i0 V5 Q) }
& O9 L6 ]1 B' H' K: L( K/ h
% E; I; F+ Z$ B
在正式比赛或是实际应用中,没有任何问题会和教科书上的完全一样,这就需要知识的“活学活用”。
" ?, l+ c# e ]5 G
当看了一个数模题后,不要急着去看别人的答案,自己想想该怎么做,到网上找找相关的背景资料,
$ E6 _) K* a. P/ p1 t5 f; q
想个几天实在没有思路再去看答案,仔细琢磨下为什么要这么做。
当然,数学建模中“
现学现卖
”也
/ T# a& Y) n4 U# k
是一种很重要的能力,能找到一种解决方法,并快速地学会它,然后将其应用到解决问题中。
- _( {" {, v. B- }( A7 \
最后,要说的还是要有爱,有爱才有付出,有爱才有坚持,当然爱不能只挂在嘴上,要付诸行动才行。
0 D% ~" f- A/ O K' y
2 u' j# M' E- q, R5 @. }5 g
作者:
walkintherain
时间:
2015-8-1 21:54
嘎嘎嘎嘎嘎嘎嘎嘎嘎
% U6 E2 r+ L c1 e. T7 U' ?
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5