数学建模十大算法部分带有源代码

1、数学建模竞赛中应当掌握的十类算法图论算法动态规划.回溯搜索、分治算法.分支定 界三大非经典算1. 蒙特卡罗算法该算法又称随机性模拟算法”是通过计算机 仿真来解决问题的算法f同时可以通过模拟 可以来检验自己模型的正确性 是比赛时必 用的方法蒙特卡罗(Monte Carlo)方法f或称计算机随机模拟方法 是一种基于随机数的计算方法。这一方法源于美国在第一次世 界大战进研制原子弹的曼哈顿计划O该计划的主持人之一、数学家冯诺伊曼用驰名世界的赌城一摩纳哥的Monte Carlo来命名这种方法 为它蒙上了一层神秘色考虑平面上的一个边长为1的正方形及其内 部的一个形状不规则的图形 如何求 出这个图形的面积呢

2、？ Monte Carlo方 法是这样一种随机化的方法：向该正 方形随机地投掷N个点落于图形内,则该图形的面积近似为M/N。if宀遵 話甑融j 鷲6矗4次臨te- H 学即用ovvn 去、;as$+M Lc .J形不Sequen 机藪序 翩ragXfunction val = ballvol(n, m)% BALLVOL Compute volume of unit ball in RAn% Computes the volume of the n-dimensional unit ball% using monte-carlo method% usage: val = BallVol(n,

3、m)% where: n 二 dimension% m = number of realisations% If the second argument is omitted, 1e4 is taken as default for m. % (c) 1998, Rolf Krause, krausemath.fu-berlin.deM = 1e4;error = 0;if(nargin 2), error(fwrong number of arguments*); end if nargin = 2, M = m; endR = rand(n, M);in = 0;for i=1:Mif(n

4、orm(R(:,i),2) 很多时候这些问题可以用 数学规划算法来描述 通常使用Lindo. Lingo软件实现）4. 图论算法这类算法可以分为很多种 包括最短路、 网络流.二分图等算法,涉及到图论的问 题可以用这些方法解决 需要认真准备5、动态规划、回溯搜索、分治算法、分支定界这些算法是算法设计中比较常用的方法, 很多场合可以用到竞赛中动态规划它建立在最优原则的基础上。采用动态规划方法,可以优雅而高效地解决许多用贪 婪算法或分而治之算法无法解决的问题。动态规划方法在解决背包问题.图象压缩、 矩阵乘法链、最短路径、无交叉子集和元 件折叠等方面的有很大作用。算法思想和贪婪算法一样f在动态规划中,

5、可将一个问题的解决方案视为一系列决策的结果。不同的是 在贪婪算法中f每采用一次贪婪准则便做出一个不可撤回的决策 而在动态规划中 还要考察每个最优决策序列中是否包含一个最优子序列。副窗解方常情以时向 瞬或逸过选大sn&通坏可 贈上候不贅决需查曇的大 册更分为至解畐检于嘗鬍 筋完理番冒能的異蚤检熏 J&USSD畫聲比进厶撞求 呦書一法S8S算系是歐实集紧 謝一妙述您的进界奨。选签 霍找且少大鑒枝吊 7检肆时很吊舉分方屠大行通 _次即翟非采对和退垣法 薛依宥需中噩01 一 SW- 瞬后后量所国吊即题回这的于養些 然專到应通审照舅避证这 可逸解得际量-SM按回疋专 将提i共一台可用来比發两组 硬币重量

6、的仪器，利用这台仪器，可以知道 两组硬币的重量是否相同。比较硬币1与硬币2的重量。假如硬币1比硬币 2轻f则硬币1是伪造的；假如硬币2比硬币1 轻,则硬币2是伪造的。这样就完成了任务。 假如两硬币重量相等 则比较硬币3和硬币4。 同样假如有一个硬币轻一些 则寻找伪币 的任务完成。假如两硬币重量相等 则继续 比较硬币5和硬币6。按照这种方式f可以最 多通过8次比较来判断伪币的存在并找出这一 伪币。假如把1 6硬币的例子看成一个大的问题。第一步, 把这_问题分成两个小问题。随机选择8个硬币作 为第一组称为A组,剩下的8个硬币作为第二组称 为B组。这样,就把1 6个硬币的问题分成两个8硬 币的问题来

7、解决。第二步,判断A和B组中是否有 伪币。可以利用仪器来比较A组硬币和B组硬币的 重量。假如两组硬币重量相等,则可以判断伪币不 存在。假如两组硬币重量不相等,则存在伪币,并 且可以判断它位于较轻的那一组硬币中。最后,在 第三步中,用第二步的结果得出原先1 6个硬币问 题的答案。若仅仅判断硬币是否存在,则第三步非 常简单。无论A组还是B组中有伪币,都可以推断 这1 6个硬币中存在伪币。因此仅仅通过一次重 量的比较,就可以判断伪币是否存在。现在假设需要识别出这一伪币。把两个或三个硬币的情况作 为不可再分的小问题。注意如果只有一个硬币 1 6硬币的问题就被分为两个8硬币（A组和B组）的问 题。通过比

8、较这两组硬币的重量 可以判断伪币是否存在。 如果没有伪币,则算法终止。否则,继续划分这两组硬币来 寻找伪币。假设B是轻的那一组,因此再把它分成两组,每 组有4个硬币。称其中一组为B1，另一组为B2。比较这两组, 肯定有一组轻一些。如果B1轻f则伪币在Bl中z再将Bl又 分成两组 每组有两个硬币 因此活节 点表的性质与队列相同。2）最小耗费或最大收益法在这种模式中f每个 节点都有一个对应的耗费或收益。如果查找一 个具有最小耗费的解f则活节点表可用最小堆 来建立 下一个E-节点就是具有最小耗费的活节点；如果希望搜索一个具有最大收益的解则可用最大堆来构造活节点表 下一个E-节点16、模拟退火法、神经

9、网络、遗传算/5模拟退火法(Simulated Annealina )是薔E神经侖络的基本结构:递归网络和前馈网 人工神经网络的典型模型有:自道应酬理论(ART). Kohonen网络、反面扉(BP)网 鉤.Hopfield网X遗传算法(Genetic Algoritms , 简称GA)是以自然选择和遗传理论为基础,将生 物进化过程中适者生存规则与群体内部染色体的随 机信息交换机制相结合的搜索算法。遗传算法是具 有”生成+检测“的迭代过程的搜索算法。基本流程 如图丄所示。可见,遗传算法是一种群体型操作, 该操作以群体中的所有个体为对象。选择(s eI ection)、交叉(crossover)

10、 变异(mutation)是遗传算法的三个全要 操作算子。遗传算法包含如下6个基本要素:参数 编码.生成初始群体.适应度评估检测.选择.交 叉操作、变异交找 I 片小 I童L I7. 网格算法和穷举法网格算法和穷举法都是暴力搜索最优点的算法,在很多竞赛题中有应用,当重点讨 论模型本身而轻视算法的时候”可以使用这种暴力方案 最好使用一些高级语言作 为编程工具穷举法是基于计算机特点而逬行解题的思维方法。一般是在一时找不出解决问题的更好 途径时 可以根据问题中的部分条件（约束 条件）将所有可能解的情况列举出来 然后通过一一验证是否符合整个问题的求解要求而得到问题的鶴这种解决问题的方法我们 称之为穷举算法。穷举法特点是算法简单，但运行时所花费的时间量大。&连续离散化方法很多问题都是实际来的 数据可以是连续的 而计算机只认的是离散的数据,因此将其离散 化后进行差分代替微分、求和代替积分等思想 是非常重要的9.数值分析算法如果在比赛中采用高级语言进行编程的话 那一些数值分析中常用的算法比如方程组 求解、矩阵运算.函数积分等算法就需要 额外编写库函数进行调用10.图象处理算法赛题中有一类问题与图形有关，即使与图 形无关 论文中也应该要不乏图