数学建模竞赛中应当掌握的十类算法.ppt

《数学建模竞赛中应当掌握的十类算法.ppt》由会员分享，可在线阅读，更多相关《数学建模竞赛中应当掌握的十类算法.ppt（34页珍藏版）》请在三一办公上搜索。

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%If the second argume

4、nt is omitted,1e4 is taken as default for m.M=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;,2、数据拟合、参数估计、插值等数据处理算法,数据拟和:从给出的一大堆数据中找出规律，即设法构造一条曲线(拟和曲线)反映数据点总的趋势，以消除其局部波动。参数估计：对给定的统计问题，在建立了统计模

5、型以后，我们的任务就是依据样本对未知总体进行各种推断，参数估计是统计推断的重要内容之一。包括点估计方法、频率替换法、矩法、极大似然估计法 插值法是函数逼近的一种重要方法，包括多项式插值、分段插值和三角插值,3、数学规划算法,线性规划、整数规划、多元规划、二次规划等规划类问题（建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo软件实现）,4、图论算法,这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备,5、动态规划、回溯搜索、分治算法、分支定界,这些算法是算法设计中比较常用的方法，很多

6、场合可以用到竞赛中,动态规划,它建立在最优原则的基础上。采用动态规划方法，可以优雅而高效地解决许多用贪婪算法或分而治之算法无法解决的问题。动态规划方法在解决背包问题、图象压缩、矩阵乘法链、最短路径、无交叉子集和元件折叠等方面的有很大作用。,算法思想,和贪婪算法一样，在动态规划中，可将一个问题的解决方案视为一系列决策的结果。不同的是，在贪婪算法中，每采用一次贪婪准则便做出一个不可撤回的决策，而在动态规划中，还要考察每个最优决策序列中是否包含一个最优子序列。,寻找问题的解的一种可靠的方法是首先列出所有候选解，然后依次检查每一个，在检查完所有或部分候选解后，即可找到所需要的解。理论上，当候选解数量有

7、限并且通过检查所有或部分候选解能够得到所需解时，上述方法是可行的。不过，在实际应用中，很少使用这种方法，因为候选解的数量通常都非常大（比如指数级，甚至是大数阶乘），即便采用最快的计算机也只能解决规模很小的问题。对候选解进行系统检查的方法有多种，其中回溯和分枝定界法是比较常用的两种方法。按照这两种方法对候选解进行系统检查通常会使问题的求解时间大大减少（无论对于最坏情形还是对于一般情形）。事实上，这些方法可以使我们避免对很大的候选解集合进行检查，同时能够保证算法运行结束时可以找到所需要的解。因此，这些方法通常能够用来求解规模很大的问题。,回溯方法,这种方法被用来设计货箱装船、背包、最大完备子图、旅

8、行商和电路板排列问题的求解算法。,算法思想,回溯（backtracking）是一种系统地搜索问题解答的方法。为了实现回溯，首先需要为问题定义一个解空间（solution space），这个空间必须至少包含问题的一个解（可能是最优的）。下一步是组织解空间以便它能被容易地搜索。典型的组织方法是图或树。,分治算法,君主和殖民者们所成功运用的分而治之策略也可以运用到高效率的计算机算法的设计过程中。利用这一策略可以解决如下问题：最小最大问题、矩阵乘法、残缺棋盘、排序、选择和计算一个几何问题找出二维空间中距离最近的两个点。,算法思想,分而治之方法与软件设计的模块化方法非常相似。为了解决一个大的问题，可以：

9、1)把它分成两个或多个更小的问题；2)分别解决每个小问题；3)把各小问题的解答组合起来，即可得到原问题的解答。小问题通常与原问题相似，可以递归地使用分而治之策略来解决。,例2-1 找出伪币 给你一个装有1 6个硬币的袋子。1 6个硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这个伪造的硬币。为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，利用这台仪器，可以知道两组硬币的重量是否相同。,比较硬币1与硬币2的重量。假如硬币1比硬币2轻，则硬币1是伪造的；假如硬币2比硬币1轻，则硬币2是伪造的。这样就完成了任务。假如两硬币重量相等，则比较硬币3和硬币4。同

10、样，假如有一个硬币轻一些，则寻找伪币的任务完成。假如两硬币重量相等，则继续比较硬币5和硬币6。按照这种方式，可以最多通过8次比较来判断伪币的存在并找出这一伪币。,假如把1 6硬币的例子看成一个大的问题。第一步，把这一问题分成两个小问题。随机选择8个硬币作为第一组称为A组，剩下的8个硬币作为第二组称为B组。这样，就把1 6个硬币的问题分成两个8硬币的问题来解决。第二步，判断A和B组中是否有伪币。可以利用仪器来比较A组硬币和B组硬币的重量。假如两组硬币重量相等，则可以判断伪币不存在。假如两组硬币重量不相等，则存在伪币，并且可以判断它位于较轻的那一组硬币中。最后，在第三步中，用第二步的结果得出原先1

11、 6个硬币问题的答案。若仅仅判断硬币是否存在，则第三步非常简单。无论A组还是B组中有伪币，都可以推断这1 6个硬币中存在伪币。因此，仅仅通过一次重量的比较，就可以判断伪币是否存在。,现在假设需要识别出这一伪币。把两个或三个硬币的情况作为不可再分的小问题。注意如果只有一个硬币，那么不能判断出它是否就是伪币。在一个小问题中，通过将一个硬币分别与其他两个硬币比较，最多比较两次就可以找到伪币。这样，1 6硬币的问题就被分为两个8硬币（A组和B组）的问题。通过比较这两组硬币的重量，可以判断伪币是否存在。如果没有伪币，则算法终止。否则，继续划分这两组硬币来寻找伪币。假设B是轻的那一组，因此再把它分成两组，

12、每组有4个硬币。称其中一组为B1，另一组为B2。比较这两组，肯定有一组轻一些。如果B1轻，则伪币在B1中，再将B1又分成两组，每组有两个硬币，称其中一组为B1a，另一组为B1b。比较这两组，可以得到一个较轻的组。由于这个组只有两个硬币，因此不必再细分。比较组中两个硬币的重量，可以立即知道哪一个硬币轻一些。较轻的硬币就是所要找的伪币。,分枝定界,类似于回溯法，分枝定界法在搜索解空间时，也经常使用树形结构来组织解空间。然而与回溯法不同的是，回溯算法使用深度优先方法搜索树结构，而分枝定界一般用宽度优先或最小耗费方法来搜索这些树。本章与第1 6章所考察的应用完全相同，因此，可以很容易比较回溯法与分枝定

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

14、存在其他的方法）：1)先进先出（F I F O）即从活节点表中取出节点的顺序与加入节点的顺序相同，因此活节点表的性质与队列相同。2)最小耗费或最大收益法在这种模式中，每个节点都有一个对应的耗费或收益。如果查找一个具有最小耗费的解，则活节点表可用最小堆来建立，下一个E-节点就是具有最小耗费的活节点；如果希望搜索一个具有最大收益的解，则可用最大堆来构造活节点表，下一个E-节点是具有最大收益的活节点。,6、模拟退火法、神经网络、遗传算法,模拟退火法（Simulated Annealing）是Kirkpatrick等人在一九八三年提出并成功地应用在组合最佳化問題中，它是蒙特卡罗演算法的推广。人工神经网

15、络的基本结构:递归网络和前馈网络 人工神经网络的典型模型有:自适应谐振理论(ART)、Kohonen 网络、反向传播(BP)网络、Hopfield网,遗传算法（，简称）是以自然选择和遗传理论为基础，将生物进化过程中适者生存规则与群体内部染色体的随机信息交换机制相结合的搜索算法。遗传算法是具有生成检测的迭代过程的搜索算法。基本流程如图所示。可见，遗传算法是一种群体型操作，该操作以群体中的所有个体为对象。选择（）、交叉（）和变异（）是遗传算法的三个主要操作算子。遗传算法包含如下个基本要素：参数编码、生成初始群体、适应度评估检测、选择、交叉操作、变异,7、网格算法和穷举法,网格算法和穷举法都是暴力搜

16、索最优点的算法，在很多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具,穷举法是基于计算机特点而进行解题的思维方法。一般是在一时找不出解决问题的更好途径时，可以根据问题中的部分条件（约束条件）将所有可能解的情况列举出来，然后通过一一验证是否符合整个问题的求解要求，而得到问题的解。这种解决问题的方法我们称之为穷举算法。穷举法特点是算法简单，但运行时所花费的时间量大。,8、连续离散化方法,很多问题都是实际来的，数据可以是连续的，而计算机只认的是离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的,9、数值分析算法,如果在比赛中采用高级语言进行编程的话，那一些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用,10、图象处理算法,赛题中有一类问题与图形有关，即使与图形无关，论文中也应该要不乏图片的，这些图形如何展示以及如何处理就是需要解决的问题，通常使用Matlab进行处理,网站介绍,放飞技术网数学中国开放实验室数学书籍下载数学实验,