QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 2618|回复: 0
打印 上一主题 下一主题

还在为数学建模的事发愁?带你一起来看看数模竞赛中必备的经典算法

[复制链接]
字体大小: 正常 放大
杨利霞        

5273

主题

82

听众

17万

积分

  • TA的每日心情
    开心
    2021-8-11 17:59
  • 签到天数: 17 天

    [LV.4]偶尔看看III

    网络挑战赛参赛者

    网络挑战赛参赛者

    自我介绍
    本人女,毕业于内蒙古科技大学,担任文职专业,毕业专业英语。

    群组2018美赛大象算法课程

    群组2018美赛护航培训课程

    群组2019年 数学中国站长建

    群组2019年数据分析师课程

    群组2018年大象老师国赛优

    跳转到指定楼层
    1#
    发表于 2021-7-9 17:26 |只看该作者 |倒序浏览
    |招呼Ta 关注Ta
    还在为数学建模的事发愁?带你一起来看看数模竞赛中必备的经典算法1 d$ G& c# C9 n) g% ^  O6 z

    9 E& Y' p) o; `8 Q; s; z- v% t/ y前言/ }. Z1 t! u1 E& O0 e& t/ b8 R$ {
    数学建模比赛是本科生和研究生阶段最重要的比赛之一,包括全国大学生数学建模竞赛(俗称“国赛”)和美国大学生数学建模竞赛(俗称“美赛”)。在这些比赛中取得好成绩,不仅有助于保研、有助于找工作,更重要的是形成科学的思维模式。以下是博主精心整理的两个matlab专栏,包含入门到精通及实战内容,需要的小伙伴可根据自己需求自行订阅。
    & ^6 F/ P, i( e% [- z
    ( X# w+ [* F7 w! z3 L& M

    ; i8 z+ U9 M9 A2 q. `MATLAB-30天带你从入门到精通
    0 {& H. i2 k: D" _) [" i- _# z
    + K/ k/ o& e  f9 W
    # a; ~8 }, R! q
    https://blog.csdn.net/wenyusuran/category_10614422.html: H' ~3 z+ s) z. _6 e8 [' H' x& j
    1 F% E7 v- B0 U, W  L

    & c( O9 q/ o8 l* K3 \/ A3 hMATLAB深入理解高级教程(附源码)
    5 O, r5 B: `" u" v# ~( U" [2 D5 V$ i. j0 s7 I4 ?+ Z" ?( q

    $ I$ b9 u" S6 e. d, z  Vhttps://blog.csdn.net/wenyusuran/category_2239265.html% Q- k+ q( E6 v5 S
    8 {7 s4 j$ g4 f: n" ^: M6 \

    - m& ~0 H/ ]0 v2 T" T" y在博主的资源中也有各种算法的应用实例源代码,需要的小伙伴自取哟。
    . o$ V$ Q9 ^) H4 k% l1 ^7 U2 e! T! [. N7 B) b
    , F& X/ |$ ]& `

    * R. I. L" C' x1 Q4 Z+ y7 o7 |+ y( t! S. J8 c7 f# `# w+ H

    ) S) a! w! |/ b3 O* \& N# h
    " R: _. e* z' b2 t4 n, g: o

    $ Q3 K5 K+ C5 X# C4 C+ i/ n# P7 Q& T# \* J8 V6 D! F- |

    ) F. b0 s2 m; }1 I  N
    * f3 J' t. Q' I5 @) B
    9 T2 {6 r7 B1 r) X
      K: p. J% m% ~* s, {* S
    01  蒙特卡罗算法
    + f9 o) C1 F% q" a1946 年,美国拉斯阿莫斯国家实验室的三位科学家 JohnvonNeumann, Stan Ulam和 Nick Metropolis 共同发明了蒙特卡罗方法。: O" l6 y" N: y5 H- S$ r$ H

    2 d2 y. H6 l# J" o
    + o; J, g) E0 b8 f
    蒙特卡罗方法(Monte Carlo method),又称随机抽样或统计模拟方法,是一种以概率统计理论为指导的一类非常重要的数值计算方法。此方法使用随机数(或更常见的伪随机数)来解决很多计算问题的方法。* ^' i- U" L& u- @2 E/ h0 z9 N7 L5 {& L
    ) i0 b( _) S; s( a5 c3 ^" F

    4 L" V! V" I5 q由于传统的经验方法由于不能逼近真实的物理过程,很难得到满意的结果,而蒙特卡罗方法由于能够真实地模拟实际物理过程,故解决问题与实际非常符合,可以得到很圆满的结果。1 P6 k) [, k& L9 x" R4 e8 }
    4 R/ o5 Y$ @5 ]7 ~: W

    0 |; J7 W* J+ N$ K! p蒙特卡罗方法的基本原理及思想如下:
    $ {( b: W# X; p* U( ?
    & n+ R; V4 N+ s+ @5 f

    ! v/ j9 `! O" l  K当所求解问题是某种随机事件出现的概率,或者是某个随机变量的期望值时,通过某种“实验”的方法,以这种事件出现的频率估计这一随机事件的概率,或者得到这个随机变量的某些数字特征,并将其作为问题的解。
    7 u( Q4 Q7 h- d8 a- E
    2 E4 d' y' M# G  U3 I$ i; N
    . M' R' e6 L$ s) R. F4 Y
    举个栗子,直观了解蒙特卡洛方法:; q3 A9 B- e* B
    : q9 m5 a6 b8 `, e/ A

    8 a$ g& s( d0 F! t1 S假设我们要计算一个不规则图形的面积,那么图形的不规则程度和分析性计算(比如:积分)的复杂程度是成正比的。蒙特卡洛方法是怎么计算的呢?假想你有一袋豆子,把豆子均匀地朝这个图形上撒,然后数这个图形之中有多少颗豆子,这个豆子的数目就是图形的面积。当你的豆子越小,撒的越多的时候,结果就越精确。在这里我们要假定豆子都在一个平面上,相互之间没有重叠。- U" H8 I* W6 o- l! }5 T; M

    # [6 N& X2 H7 k
    - P; |  _! d, m" \) v, Q/ f- S+ O

    ) P  c; ?, c6 {( d$ n
    # I4 a$ h8 }8 T: h* l- r4 ^

    8 [9 k! P" q3 D- H2 f4 j

    0 k! ^7 c7 j" {+ L" _蒙特卡罗方法通过抓住事物运动的几何数量和几何特征,利用数学方法来加以模拟,即进行一种数字模拟实验。它是以一个概率模型为基础,按照这个模型所描绘的过程,通过模拟实验的结果,作为问题的近似解。6 l" Q" e" h) N+ r' [- }" f

    4 t4 S( y/ {! D
    8 q) L- E$ Q7 Q; S# B
    蒙特卡罗方法与一般计算方法有很大区别,一般计算方法对于解决多维或因素复杂的问题非常困难,而蒙特卡罗方法对于解决这方面的问题却比较简单。其特点如下:
    0 m8 `4 Q6 i5 y8 n$ E4 p1 [$ V0 t9 a* x
      V2 K2 N$ f9 _
    a、直接追踪粒子,物理思路清晰,易于理解;/ y% x3 p( I; k- @
    * |* q7 A0 M% L7 v, l9 S

    # P; h6 T' _6 Y3 ab、采用随机抽样的方法,较真切的模拟粒子输运的过程,反映了统计涨落的规律;
    , N' r+ N7 N0 M" I2 I6 C0 p/ g9 T$ P
    4 w" ~& D* X4 \; x1 n" ^/ n, M
    c、不受系统多维、多因素等复杂性的限制,是解决复杂系统粒子输运问题的好方法
    1 u1 F* s. d$ S! E; m3 k  W4 X  d+ m& C8 `$ L. h
    % r; N+ D+ g; r8 D9 C
    等等2 A8 L4 k0 r+ J" Y; Y7 m) l) c

    5 y4 j- f5 c+ e
    $ d8 N; x/ N( w' i+ b
    02  数据拟合、参数估计、插值等数据处理算法5 U* C( x' d  i- `
    我们通常会遇到大量的数据需要处理,而处理数据的关键就在于这些算法,通常使用 Matlab 作为工具。& c% B% E7 x( \9 A# i, T- _8 k

    $ ~. ^/ J* k* `. B1 [( K) _8 \

    & r! A$ l0 d. K( l% |& Z% O& B数据拟合在数学建模比赛中中有应用,与图形处理有关的问题很多与拟合有关系,一个例子就是 98 年数学建模美国赛 A 题,生物组织切片的三维插值处理,94 年 A 题逢山开路,山体海拔高度的插值计算,还有吵的沸沸扬扬可能会考的“非典”问题也要用到数据拟合算法,观察数据的走向进行处理。. i! C7 i% E3 m, t! B

    5 a1 m  _4 u1 C2 M$ W# Y5 Q# D$ I
    1 K, d" U7 z; I& M+ U

    & t: P0 N5 M" L2 G# N$ g" Q

    + K$ {0 S, _4 v  \; {3 }9 L5 ~
    % z1 Z9 @  p+ O7 Y6 C% t4 Z
    7 j+ ^' U5 K+ \8 D; A4 J
    此类问题在 MATLAB 中有很多现成的函数可以调用,熟悉 MATLAB,这些方法都能游刃有余的用好。! T  X# _4 D6 i" d" h

    ! O: ?* S4 i& F: g5 j& X* B

    $ D) Z* u8 S- L5 s) v 03 线性规划、整数规划、多元规划、二次规划等规划类问题7 x% Z' F! b7 Y. M" q# |7 F. J
    数学建模竞赛中很多问题都和数学规划有关,可以说不少的模型都可以归结为一组不等式作为约束条件、几个函数表达式作为目标函数的问题。
    7 t* C+ y, \! U0 @; J! i! ]1 t/ ]) ~- V0 O
    / Y+ L0 [) m/ D! {* {" g& E& _+ J
    遇到这类问题,求解就是关键了,比如 98 年 B 题,用很多不等式完全可以把问题刻画清楚,因此列举出规划后用 Lindo、Lingo 等软件来进行解决比较方便,所以还需要熟悉这两个软件。; Q$ s( O; ^8 Z+ ^- T& U8 t
    * [- ^, I# s# U

    ! U. ~! t- ~# S0 \ 04  图论算法
    ' A; {) T$ [  X! A这类问题算法有很多,包括:Dijkstra、Floyd、Prim、Bellman-Ford,最大流,二分匹配等问题。4 M  i' |2 A  o; a" L, Z( c& J- o

    9 G' L- ^5 w0 s" b4 D# z

    4 X  B3 M4 A; h) e8 F) t( l关于此类图论算法,可参考 IntroductiontoAlgorithms--算法导论,关于图算法的第22章-第26章。) t: W9 `6 X* ]* x- e
    # l8 T2 z/ n& I! `3 ~9 K
    * L+ R6 Y! G+ y2 L2 T: k
    7 C8 ?5 h, O* c# {

    / R$ x( j$ [7 m! W
    " ?8 U" r7 h5 X* t: z# b$ x

    0 _2 x( K7 e( }- A$ c 05  动态规划、回溯搜索、分治算法、分支定界等计算机算法
    4 D/ @. T, c# c8 ]$ ?在数学建模竞赛中,如:92 年 B 题用分枝定界法,97年 B 题是典型的动态规划问题,此外 98 年 B 题体现了分治算法。
    ) \/ E" F5 Q3 A+ L3 p* j3 n+ L" K! n  I' S6 I8 x6 J4 h
    % v: B9 k4 G: T8 U/ \

    $ _4 {: }0 b! k2 K) u! a

    ' f8 E5 y$ a7 r8 P* ^, t) W4 F7 w0 m( _7 @$ d

    & Z2 M3 j! [. X这方面问题和 ACM 程序设计竞赛中的问题类似,推荐看一下算法导论,与《计算机算法设计与分析》(电子工业出版社)等与计算机算法有关的书。/ E# y5 K: C' S! g0 E# F0 F

    0 q) x  c- N! N& t* {

    ( G+ L8 T4 e5 B3 m+ P% j 06  最优化理论的三大经典算法:模拟退火法、神经网络、遗传算法0 Y9 Z2 o3 L1 ]* z
    这十几年来最优化理论有了飞速发展,模拟退火法、神经网络、遗传算法这三类算法发展很快。
    + d  a; Y3 F# j' {6 u7 V" a
    ( O# [5 ~6 ]! l0 q/ |* J- }1 ?
    6 f' T* }- \" g' _; ?) [+ v
    在数学建模竞赛中:比如 97 年 A 题的模拟退火算法,00 年 B 题的神经网络分类算法,01 年 B 题这种难题也可以使用神经网络。6 S* N9 B6 R& v$ A. J  A

    ! H% ]- ^# [; [+ v5 `+ o

    . \2 U4 B7 y$ O3 l2 Z7 d! r6 M还有美国竞赛 89 年 A 题也和 BP 算法有关系,当时是 86 年刚提出 BP 算法,89 年就考了,说明赛题可能是当今前沿科技的抽象体现。8 @/ y4 z2 D% Y) x
    $ s+ k0 E! D4 f' ?; y
    ' @1 ]1 E3 E: Y3 Y2 y- o' e
    03 年 B 题伽马刀问题也是目前研究的课题,目前算法最佳的是遗传算法。$ D  @  V* D0 D/ C/ H; _

    % {' n5 \! i% B; L, R) V5 G
    0 S  h; y- V4 A

    4 f8 R- b- `% z* i* T# k/ f
    1 T2 P( Q# _6 {$ W
    ! D  u8 x0 T& h! M5 F6 W

    + H) W. B5 K" k! X( y6 u+ p" G
    6 F* L- m  o; R, Z9 o* ?
      F: t4 R- F# |3 {3 Z, A

    9 |1 t) q+ H8 v# d( O% I 07  网格算法和穷举法
    " w6 a& j  L! U网格算法和穷举法一样,只是网格法是连续问题的穷举。
    / o' n7 U4 B, u- s" P4 V& r# f
    ! C8 Z' m- m4 |7 }1 z4 g" n) n
    " n5 \( H$ h( P$ W& g& w
    比如要求在 N 个变量情况下的最优化问题,那么对这些变量可取的空间进行采点,比如在 [a;b] 区间内取 M+1 个点,那么这样循环就需要进行 (M+1)N 次运算,所以计算量很大。& Z# s& a3 A6 q+ I4 b; L
    1 R3 U1 c: t  u) Z
      r( b6 G$ `4 H' B
    在数学建模竞赛中:比如 97 年 A 题、99 年 B 题都可以用网格法搜索,这种方法最好在运算速度较快的计算机中进行,还有要用高级语言来做,最好不要用MATLAB 做网格,否则会算很久。
    + Z0 k$ T2 k, Q; B# Y* D5 S/ Y" d" P6 M' Z7 x0 f. o, M! m

    , D1 q5 W. I( R  L3 f穷举法大家都熟悉,自不用多说了。
    4 r* L3 W" ~' {# F* B0 F  m' K  D5 V9 w" e% ^6 ~

    5 y5 f+ d* K1 o9 Q; E/ q8 S7 Z6 } 08 一些连续离散化方法
    $ b) ?$ F- ]2 `大部分物理问题的编程解决,都和这种方法有一定的联系。物理问题是反映我们生活在一个连续的世界中,计算机只能处理离散的量,所以需要对连续量进行离散处理。9 b5 U# K* n8 u) A' h
    $ Q# z! {5 _* H/ O$ a6 O
    ' O) M; J4 i* K; k
    这种方法应用很广,而且和上面的很多算法有关。事实上,网格算法、蒙特卡罗算法、模拟退火都用了这个思想。5 C/ c/ Q$ K' q$ [

      S! ]) M8 e: F( r# {9 H& }

    " N* b. ?& V3 [) S' ?8 h 09 数值分析算法+ b8 n- q  D, V7 f8 }: }9 M4 o9 s
    数值分析(numericalanalysis),是数学的一个分支,主要研究连续数学(区别于离散数学)问题的算法。" }# h, u' y# C5 ]" r
    ) p! h8 S2 k& K. {

    3 z9 E' d8 h  Q; Z3 E7 a. ?! H如果在比赛中采用高级语言进行编程的话,那一些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用。
    ! P- Q) u2 `" l- P3 I3 y( Y# U3 P+ z
    ; g. _7 h0 H) D5 I& K1 O
    # E  T# f9 q& Z$ d6 n6 B3 `
    这类算法是针对高级语言而专门设的,如果你用的是 MATLAB、Mathematica,大可不必准备,因为像数值分析中有很多函数一般的数学软件是具备的。8 y. |5 P  A, k% |9 u  h3 w
    0 A6 ?1 }) G- t, X. I$ A' `
    ) \0 H9 F3 }$ G1 R" g1 W
    10  图象处理算法
    $ w2 I! n! ?5 B+ A" c6 B在数学建模竞赛中:比如 01 年 A 题中需要你会读 BMP 图象、美国赛 98 年 A 题需要你知道三维插值计算,03 年 B 题要求更高,不但需要编程计算还要进行处理,而数模论文中也有很多图片需要展示,因此图象处理就是关键。做好这类问题,重要的是把 MATLAB 学好,特别是图象处理的部分。
    3 `/ [! n6 E. _% E9 u
    ! F: [7 z8 v4 D7 l- ~
    1 Z/ N1 m/ H* v: q9 j3 C

    : O, c: l% E1 H, j
    ! G% ~, S% D# i( I
    ————————————————
    7 G5 {- y0 e3 s版权声明:本文为CSDN博主「文宇肃然」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
    1 D/ m7 N1 F! y$ ]原文链接:https://blog.csdn.net/wenyusuran/article/details/114093268! U* x! N  r/ {7 _* S* E, t" B, I
    $ A3 u4 n0 F5 V/ ]7 @

    ( T5 i$ H/ z% i+ S9 y! m8 Q
    zan
    转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信
    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

    GMT+8, 2026-4-12 20:24 , Processed in 0.350576 second(s), 51 queries .

    回顶部