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

1、数学建模竞赛中应当掌握的十类算法蒙特卡罗算法 数据处理算法 数学规划算法 图论算法 动态规划、回溯搜索、分治算法、分支定界 三大非经典算法 网格算法和穷举法 连续离散化方法 数值分析算法 图象处理算法 1、蒙特卡罗算法 该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟可以来检验自己模型的正确性，是比赛时必用的方法 蒙特卡罗(Monte Carlo)方法，或称计算机随机模拟方法，是一种基于“随机数”的计算方法。这一方法源于美国在第一次世界大战进研制原子弹的“曼哈顿计划”。该计划的主持人之一、数学家冯诺伊曼用驰名世界的赌城摩纳哥的Monte Carlo来命名这种方法，为

2、它蒙上了一层神秘色彩。 考虑平面上的一个边长为1的正方形及其内部的一个形状不规则的“图形”，如何求出这个“图形”的面积呢？Monte Carlo方法是这样一种“随机化”的方法：向该正方形“随机地”投掷N个点落于“图形”内，则该“图形”的面积近似为M/N。 另一类形式与Monte Carlo方法相似，但理论基础不同的方法“拟蒙特卡罗方法” (Quasi-Monte Carlo方法)近年来也获得迅速发展。我国数学家华罗庚、王元提出的“华王”方法即是其中的一例。这种方法的基本思想是“用确定性的超均匀分布序列(数学上称为Low Discrepancy Sequences)代替Monte Carlo方法

3、中的随机数序列。对某些问题该方法的实际速度一般可比Monte Carlo方法提出高数百倍，并可计算精确度。具体实现的matlab代码：-function val = ballvol(n, m)% BALLVOL Compute volume of unit ball in Rn% Computes the volume of the n-dimensional unit ball % using monte-carlo method.% usage: val = BallVol(n, m)% where: n = dimension % m = number of realisations%

4、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(wrong number of arguments); endif nargin = 2, M = m; end R = rand(n, M);in = 0;for i=1:Mif(norm(R(:,i),2) = 1.0), in = in+1; endendval = 2n*in/M;4、图论

5、算法 这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备 5、动态规划、回溯搜索、分治算法、分支定界 这些算法是算法设计中比较常用的方法，很多场合可以用到竞赛中 动态规划 它建立在最优原则的基础上。采用动态规划方法，可以优雅而高效地解决许多用贪婪算法或分而治之算法无法解决的问题。动态规划方法在解决背包问题、图象压缩、矩阵乘法链、最短路径、无交叉子集和元件折叠等方面的有很大作用。算法思想 回溯（backtracking）是一种系统地搜索问题解答的方法。为了实现回溯，首先需要为问题定义一个解空间（solution space），这个空间必须至

6、少包含问题的一个解（可能是最优的）。 下一步是组织解空间以便它能被容易地搜索。典型的组织方法是图或树。分治算法 君主和殖民者们所成功运用的分而治之策略也可以运用到高效率的计算机算法的设计过程中。利用这一策略可以解决如下问题：最小最大问题、矩阵乘法、残缺棋盘、排序、选择和计算一个几何问题找出二维空间中距离最近的两个点。 算法思想 分而治之方法与软件设计的模块化方法非常相似。为了解决一个大的问题，可以： 1) 把它分成两个或多个更小的问题； 2) 分别解决每个小问题； 3) 把各小问题的解答组合起来，即可得到原问题的解答。小问题通常与原问题相似，可以递归地使用分而治之策略来解决。 例2-1 找出伪

7、币 给你一个装有1 6个硬币的袋子。1 6个硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这个伪造的硬币。为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，利用这台仪器，可以知道两组硬币的重量是否相同。 分枝定界 类似于回溯法，分枝定界法在搜索解空间时，也经常使用树形结构来组织解空间。然而与回溯法不同的是，回溯算法使用深度优先方法搜索树结构，而分枝定界一般用宽度优先或最小耗费方法来搜索这些树。本章与第1 6章所考察的应用完全相同，因此，可以很容易比较回溯法与分枝定界法的异同。相对而言，分枝定界算法的解空间比回溯法大得多，因此当内存容量有限时，回溯法成功

8、的可能性更大 算法思想 分枝定界（branch and bound）是另一种系统地搜索解空间的方法，它与回溯法的主要区别在于对E-节点的扩充方式。每个活节点有且仅有一次机会变成E-节点。当一个节点变为E-节点时，则生成从该节点移动一步即可到达的所有新节点。在生成的节点中，抛弃那些不可能导出（最优）可行解的节点，其余节点加入活节点表，然后从表中选择一个节点作为下一个E-节点。从活节点表中取出所选择的节点并进行扩充，直到找到解或活动表为空，扩充过程才结束。 有两种常用的方法可用来选择下一个E-节点（虽然也可能存在其他的方法）： 1) 先进先出（F I F O） 即从活节点表中取出节点的顺序与加入节

9、点的顺序相同，因此活节点表的性质与队列相同。 2) 最小耗费或最大收益法在这种模式中，每个节点都有一个对应的耗费或收益。如果查找一个具有最小耗费的解，则活节点表可用最小堆来建立，下一个E-节点就是具有最小耗费的活节点；如果希望搜索一个具有最大收益的解，则可用最大堆来构造活节点表，下一个E-节点是具有最大收益的活节点。6、模拟退火法、神经网络、遗传算法 模拟退火法（Simulated Annealing）是Kirkpatrick等人在一九八三年提出并成功地应用在组合最佳化問題中，它是蒙特卡罗演算法的推广。 人工神经网络的基本结构: 递归网络和前馈网络 人工神经网络的典型模型有:自适应谐振理论(A

10、RT)、 Kohonen 网络 、 反向传播(BP)网络 、 Hopfield网 遗传算法（ ，简称）是以自然选择和遗传理论为基础，将生物进化过程中适者生存规则与群体内部染色体的随机信息交换机制相结合的搜索算法。遗传算法是具有生成检测的迭代过程的搜索算法。基本流程如图所示。可见，遗传算法是一种群体型操作，该操作以群体中的所有个体为对象。选择（）、交叉（）和变异（）是遗传算法的三个主要操作算子。遗传算法包含如下个基本要素：参数编码、生成初始群体、适应度评估检测、选择、交叉操作、变异7、网格算法和穷举法 网格算法和穷举法都是暴力搜索最优点的算法，在很多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具 穷举法是基于计算机特点而进行解题的思维方法。一般是在一时找不出解决问题的更好途径时，可以根据问题中的部分条件（约束条件）将所有可能解的情况列举出来，然后通过一一验证是否符合整个问题的求解要求，而得到问题的解。这种解决问题的方法我们称之为穷举算法。穷举法特点是