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

1、 蒙特卡罗算法蒙特卡罗算法 数据处理算法数据处理算法 数学规划算法数学规划算法 图论算法图论算法 动态规划、回溯搜索、分治算法、分支定动态规划、回溯搜索、分治算法、分支定界界 三大非经典算法三大非经典算法 网格算法和穷举法网格算法和穷举法 连续离散化方法连续离散化方法 数值分析算法数值分析算法 图象处理算法图象处理算法 该算法又称随机性模拟算法，是通过计算机该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟仿真来解决问题的算法，同时可以通过模拟可以来检验自己模型的正确性，是比赛时必可以来检验自己模型的正确性，是比赛时必用的方法用的方法 蒙特卡罗蒙特卡罗(Monte C

2、arlo)方法，或称计算机方法，或称计算机随机模拟方法，是一种基于随机模拟方法，是一种基于“随机数随机数”的的计算方法。这一方法源于美国在第一次世计算方法。这一方法源于美国在第一次世界大战进研制原子弹的界大战进研制原子弹的“曼哈顿计划曼哈顿计划”。该计划的主持人之一、数学家冯该计划的主持人之一、数学家冯诺伊曼用诺伊曼用驰名世界的赌城驰名世界的赌城摩纳哥的摩纳哥的Monte Carlo来命名这种方法，为它蒙上了一层神秘色来命名这种方法，为它蒙上了一层神秘色彩。彩。 考虑平面上的一个边长为考虑平面上的一个边长为1的正方形及其内的正方形及其内部的一个形状不规则的部的一个形状不规则的“图形图形”，如何

3、求，如何求出这个出这个“图形图形”的面积呢？的面积呢？Monte Carlo方方法是这样一种法是这样一种“随机化随机化”的方法：向该正的方法：向该正方形方形“随机地随机地”投掷投掷N个点落于个点落于“图形图形”内，内，则该则该“图形图形”的面积近似为的面积近似为M/N。 另一类形式与另一类形式与Monte Carlo方法相似，但理方法相似，但理论基础不同的方法论基础不同的方法“拟蒙特卡罗方法拟蒙特卡罗方法” (Quasi-Monte Carlo方法方法)近年来也获得近年来也获得迅速发展。我国数学家华罗庚、王元提出迅速发展。我国数学家华罗庚、王元提出的的“华华王王”方法即是其中的一例。这种方法即

4、是其中的一例。这种方法的基本思想是方法的基本思想是“用确定性的超均匀分用确定性的超均匀分布序列布序列(数学上称为数学上称为Low Discrepancy Sequences)代替代替Monte Carlo方法中的随方法中的随机数序列。对某些问题该方法的实际速度机数序列。对某些问题该方法的实际速度一般可比一般可比Monte Carlo方法提出高数百倍，方法提出高数百倍，并可计算精确度。并可计算精确度。具体实现的matlab代码：-function val = ballvol(n, m)% BALLVOL Compute volume of unit ball in Rn% Computes th

5、e 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 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(w

6、rong 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; 数据拟和数据拟和: 从给出的一大堆数据中找出规律，从给出的一大堆数据中找出规律，即设法构造一条曲线即设法构造一条曲线(拟和曲线拟和曲线)反映数据点反映数据点总的趋势，以消除其局部波动。总的趋势，以消除其局部波动。 参数估计：对给定的统计问题，在建立了统参数估计：对给定的统计问题，在建立了统计模型以后，我们的任

7、务就是依据样本对未计模型以后，我们的任务就是依据样本对未知总体进行各种推断，参数估计是统计推断知总体进行各种推断，参数估计是统计推断的重要内容之一。包括点估计方法、频率替的重要内容之一。包括点估计方法、频率替换法、矩法、极大似然估计法换法、矩法、极大似然估计法 插值法是函数逼近的一种重要方法，包括插值法是函数逼近的一种重要方法，包括多项式插值、分段插值和三角插值多项式插值、分段插值和三角插值 线性规划、整数规划、多元规划、二次规线性规划、整数规划、多元规划、二次规划等规划类问题（建模竞赛大多数问题属划等规划类问题（建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用于最优化问题，很多时候这

8、些问题可以用数学规划算法来描述，通常使用数学规划算法来描述，通常使用LindoLindo、LingoLingo软件实现）软件实现） 这类算法可以分为很多种，包括最短路、这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备题可以用这些方法解决，需要认真准备 这些算法是算法设计中比较常用的方法，这些算法是算法设计中比较常用的方法，很多场合可以用到竞赛中很多场合可以用到竞赛中 它建立在最优原则的基础上。采用动态规它建立在最优原则的基础上。采用动态规划方法，可以优雅而高效地解决许多用贪划方法，可以优雅而高效地解决

9、许多用贪婪算法或分而治之算法无法解决的问题。婪算法或分而治之算法无法解决的问题。动态规划方法在解决背包问题、图象压缩、动态规划方法在解决背包问题、图象压缩、矩阵乘法链、最短路径、无交叉子集和元矩阵乘法链、最短路径、无交叉子集和元件折叠等方面的有很大作用。件折叠等方面的有很大作用。 和贪婪算法一样，在动态规划中，可将一个和贪婪算法一样，在动态规划中，可将一个问题的解决方案视为一系列决策的结果。不问题的解决方案视为一系列决策的结果。不同的是，在贪婪算法中，每采用一次贪婪准同的是，在贪婪算法中，每采用一次贪婪准则便做出一个不可撤回的决策，而在动态规则便做出一个不可撤回的决策，而在动态规划中，还要考察

10、每个最优决策序列中是否包划中，还要考察每个最优决策序列中是否包含一个最优子序列。含一个最优子序列。 寻找问题的解的一种可靠的方法是首先列出所有寻找问题的解的一种可靠的方法是首先列出所有候选解，然后依次检查每一个，在检查完所有或候选解，然后依次检查每一个，在检查完所有或部分候选解后，即可找到所需要的解。理论上，部分候选解后，即可找到所需要的解。理论上，当候选解数量有限并且通过检查所有或部分候选当候选解数量有限并且通过检查所有或部分候选解能够得到所需解时，上述方法是可行的。不过，解能够得到所需解时，上述方法是可行的。不过，在实际应用中，很少使用这种方法，因为候选解在实际应用中，很少使用这种方法，因

11、为候选解的数量通常都非常大（比如指数级，甚至是大数的数量通常都非常大（比如指数级，甚至是大数阶乘），即便采用最快的计算机也只能解决规模阶乘），即便采用最快的计算机也只能解决规模很小的问题。对候选解进行系统检查的方法有多很小的问题。对候选解进行系统检查的方法有多种，其中回溯和分枝定界法是比较常用的两种方种，其中回溯和分枝定界法是比较常用的两种方法。按照这两种方法对候选解进行系统检查通常法。按照这两种方法对候选解进行系统检查通常会使问题的求解时间大大减少（无论对于最坏情会使问题的求解时间大大减少（无论对于最坏情形还是对于一般情形）。事实上，这些方法可以形还是对于一般情形）。事实上，这些方法可以使我

12、们避免对很大的候选解集合进行检查，同时使我们避免对很大的候选解集合进行检查，同时能够保证算法运行结束时可以找到所需要的解。能够保证算法运行结束时可以找到所需要的解。因此，这些方法通常能够用来求解规模很大的问因此，这些方法通常能够用来求解规模很大的问题。题。 这种方法被用来设计货箱装船、背包、最这种方法被用来设计货箱装船、背包、最大完备子图、旅行商和电路板排列问题的大完备子图、旅行商和电路板排列问题的求解算法。求解算法。 回溯（回溯（backtrackingbacktracking）是一种系统地搜索问）是一种系统地搜索问题解答的方法。为了实现回溯，首先需要为题解答的方法。为了实现回溯，首先需要为

13、问题定义一个解空间（问题定义一个解空间（solution spacesolution space），），这个空间必须至少包含问题的一个解（可能这个空间必须至少包含问题的一个解（可能是最优的）。是最优的）。 下一步是组织解空间以便它能被容易地搜索。下一步是组织解空间以便它能被容易地搜索。典型的组织方法是图或树。典型的组织方法是图或树。 君主和殖民者们所成功运用的分而治之策略君主和殖民者们所成功运用的分而治之策略也可以运用到高效率的计算机算法的设计过也可以运用到高效率的计算机算法的设计过程中。利用这一策略可以解决如下问题：最程中。利用这一策略可以解决如下问题：最小最大问题、矩阵乘法、残缺棋盘、排序

14、、小最大问题、矩阵乘法、残缺棋盘、排序、选择和计算一个几何问题选择和计算一个几何问题找出二维空间找出二维空间中距离最近的两个点。中距离最近的两个点。 分而治之方法与软件设计的模块化方法非常分而治之方法与软件设计的模块化方法非常相似。为了解决一个大的问题，可以：相似。为了解决一个大的问题，可以： 1) 1) 把它分成两个或多个更小的问题；把它分成两个或多个更小的问题； 2) 2) 分别分别解决每个小问题；解决每个小问题； 3) 3) 把各小问题的解答组把各小问题的解答组合起来，即可得到原问题的解答。小问题通合起来，即可得到原问题的解答。小问题通常与原问题相似，可以递归地使用分而治之常与原问题相似

15、，可以递归地使用分而治之策略来解决。策略来解决。 例例2-1 2-1 找出伪币找出伪币 给你一个装有给你一个装有1 61 6个硬币个硬币的袋子。的袋子。1 61 6个硬币中有一个是伪造的，并个硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。你且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这个伪造的硬币。为了帮助你的任务是找出这个伪造的硬币。为了帮助你完成这一任务，将提供一台可用来比较两组完成这一任务，将提供一台可用来比较两组硬币重量的仪器，利用这台仪器，可以知道硬币重量的仪器，利用这台仪器，可以知道两组硬币的重量是否相同。两组硬币的重量是否相同。 比较硬币比较硬币1 1与硬币与

16、硬币2 2的重量。假如硬币的重量。假如硬币1 1比硬币比硬币2 2轻，则硬币轻，则硬币1 1是伪造的；假如硬币是伪造的；假如硬币2 2比硬币比硬币1 1轻，则硬币轻，则硬币2 2是伪造的。这样就完成了任务。是伪造的。这样就完成了任务。假如两硬币重量相等，则比较硬币假如两硬币重量相等，则比较硬币3 3和硬币和硬币4 4。同样，假如有一个硬币轻一些，则寻找伪币同样，假如有一个硬币轻一些，则寻找伪币的任务完成。假如两硬币重量相等，则继续的任务完成。假如两硬币重量相等，则继续比较硬币比较硬币5 5和硬币和硬币6 6。按照这种方式，可以最。按照这种方式，可以最多通过多通过8 8次比较来判断伪币的存在并找

17、出这一次比较来判断伪币的存在并找出这一伪币。伪币。 假如把假如把1 61 6硬币的例子看成一个大的问题。第一步，硬币的例子看成一个大的问题。第一步，把这一问题分成两个小问题。随机选择把这一问题分成两个小问题。随机选择8 8个硬币作个硬币作为第一组称为为第一组称为A A组，剩下的组，剩下的8 8个硬币作为第二组称为个硬币作为第二组称为B B组。这样，就把组。这样，就把1 61 6个硬币的问题分成两个个硬币的问题分成两个8 8硬币硬币的问题来解决。第二步，判断的问题来解决。第二步，判断A A和和B B组中是否有伪币。组中是否有伪币。可以利用仪器来比较可以利用仪器来比较A A组硬币和组硬币和B B组

18、硬币的重量。假组硬币的重量。假如两组硬币重量相等，则可以判断伪币不存在。假如两组硬币重量相等，则可以判断伪币不存在。假如两组硬币重量不相等，则存在伪币，并且可以判如两组硬币重量不相等，则存在伪币，并且可以判断它位于较轻的那一组硬币中。最后，在第三步中，断它位于较轻的那一组硬币中。最后，在第三步中，用第二步的结果得出原先用第二步的结果得出原先1 61 6个硬币问题的答案。个硬币问题的答案。若仅仅判断硬币是否存在，则第三步非常简单。无若仅仅判断硬币是否存在，则第三步非常简单。无论论A A组还是组还是B B组中有伪币，都可以推断这组中有伪币，都可以推断这1 61 6个硬币个硬币中存在伪币。因此，仅仅

19、通过一次重量的比较，就中存在伪币。因此，仅仅通过一次重量的比较，就可以判断伪币是否存在。可以判断伪币是否存在。 现在假设需要识别出这一伪币。把两个或三个硬币的情况作现在假设需要识别出这一伪币。把两个或三个硬币的情况作为不可再分的小问题。注意如果只有一个硬币，那么不能判为不可再分的小问题。注意如果只有一个硬币，那么不能判断出它是否就是伪币。在一个小问题中，通过将一个硬币分断出它是否就是伪币。在一个小问题中，通过将一个硬币分别与其他两个硬币比较，最多比较两次就可以找到伪币。这别与其他两个硬币比较，最多比较两次就可以找到伪币。这样，样，1 61 6硬币的问题就被分为两个硬币的问题就被分为两个8 8硬

20、币（硬币（A A组和组和B B组）的问题。组）的问题。通过比较这两组硬币的重量，可以判断伪币是否存在。如果通过比较这两组硬币的重量，可以判断伪币是否存在。如果没有伪币，则算法终止。否则，继续划分这两组硬币来寻找没有伪币，则算法终止。否则，继续划分这两组硬币来寻找伪币。假设伪币。假设B B是轻的那一组，因此再把它分成两组，每组有是轻的那一组，因此再把它分成两组，每组有4 4个硬币。称其中一组为个硬币。称其中一组为B1B1，另一组为，另一组为B2B2。比较这两组，肯定。比较这两组，肯定有一组轻一些。如果有一组轻一些。如果B1B1轻，则伪币在轻，则伪币在B1B1中，再将中，再将B1B1又分成两又分成

21、两组，每组有两个硬币，称其中一组为组，每组有两个硬币，称其中一组为B1aB1a，另一组为，另一组为B1bB1b。比。比较这两组，可以得到一个较轻的组。由于这个组只有两个硬较这两组，可以得到一个较轻的组。由于这个组只有两个硬币，因此不必再细分。比较组中两个硬币的重量，可以立即币，因此不必再细分。比较组中两个硬币的重量，可以立即知道哪一个硬币轻一些。较轻的硬币就是所要找的伪币。知道哪一个硬币轻一些。较轻的硬币就是所要找的伪币。 类似于回溯法，分枝定界法在搜索解空间时，也经类似于回溯法，分枝定界法在搜索解空间时，也经常使用树形结构来组织解空间。然而与回溯法不同常使用树形结构来组织解空间。然而与回溯法

22、不同的是，回溯算法使用深度优先方法搜索树结构，而的是，回溯算法使用深度优先方法搜索树结构，而分枝定界一般用宽度优先或最小耗费方法来搜索这分枝定界一般用宽度优先或最小耗费方法来搜索这些树。本章与第些树。本章与第1 61 6章所考察的应用完全相同，因此，章所考察的应用完全相同，因此，可以很容易比较回溯法与分枝定界法的异同。相对可以很容易比较回溯法与分枝定界法的异同。相对而言，分枝定界算法的解空间比回溯法大得多，因而言，分枝定界算法的解空间比回溯法大得多，因此当内存容量有限时，回溯法成功的可能性更大此当内存容量有限时，回溯法成功的可能性更大 分枝定界（分枝定界（branch and boundbra

23、nch and bound）是另一种系统地搜索）是另一种系统地搜索解空间的方法，它与回溯法的主要区别在于对解空间的方法，它与回溯法的主要区别在于对E-E-节点节点的扩充方式。每个活节点有且仅有一次机会变成的扩充方式。每个活节点有且仅有一次机会变成E-E-节节点。当一个节点变为点。当一个节点变为E-E-节点时，则生成从该节点移动节点时，则生成从该节点移动一步即可到达的所有新节点。在生成的节点中，抛弃一步即可到达的所有新节点。在生成的节点中，抛弃那些不可能导出（最优）可行解的节点，其余节点加那些不可能导出（最优）可行解的节点，其余节点加入活节点表，然后从表中选择一个节点作为下一个入活节点表，然后从

24、表中选择一个节点作为下一个E-E-节点。从活节点表中取出所选择的节点并进行扩充，节点。从活节点表中取出所选择的节点并进行扩充，直到找到解或活动表为空，扩充过程才结束。直到找到解或活动表为空，扩充过程才结束。 有两种常用的方法可用来选择下一个有两种常用的方法可用来选择下一个E-E-节点节点（虽然也可能存在其他的方法）：（虽然也可能存在其他的方法）： 1) 1) 先进先出（先进先出（F I F OF I F O） 即从活节点表中取即从活节点表中取出节点的顺序与加入节点的顺序相同，因此活出节点的顺序与加入节点的顺序相同，因此活节点表的性质与队列相同。节点表的性质与队列相同。 2) 2) 最小耗费或最

25、大收益法在这种模式中，每最小耗费或最大收益法在这种模式中，每个节点都有一个对应的耗费或收益。如果查找个节点都有一个对应的耗费或收益。如果查找一个具有最小耗费的解，则活节点表可用最小一个具有最小耗费的解，则活节点表可用最小堆来建立，下一个堆来建立，下一个E-E-节点就是具有最小耗费的节点就是具有最小耗费的活节点；如果希望搜索一个具有最大收益的解，活节点；如果希望搜索一个具有最大收益的解，则可用最大堆来构造活节点表，下一个则可用最大堆来构造活节点表，下一个E-E-节点节点是具有最大收益的活节点。是具有最大收益的活节点。 模拟退火法（模拟退火法（Simulated AnnealingSimulate

26、d Annealing）是）是KirkpatrickKirkpatrick等人在一九八三年提出并成功地等人在一九八三年提出并成功地应用在组合最佳化問題中，它是蒙特卡罗演应用在组合最佳化問題中，它是蒙特卡罗演算法的推广。算法的推广。 人工神经网络的基本结构人工神经网络的基本结构: : 递归网络和前馈递归网络和前馈网络网络 人工神经网络的典型模型有人工神经网络的典型模型有: :自适应谐振理论自适应谐振理论(ART)(ART)、 Kohonen Kohonen 网络网络 、 反向传播反向传播(BP)(BP)网网络络 、 HopfieldHopfield网网 遗传算法（遗传算法（ ，简称）是以自然选择

27、和遗传理论为基础，将生简称）是以自然选择和遗传理论为基础，将生物进化过程中适者生存规则与群体内部染色体的随物进化过程中适者生存规则与群体内部染色体的随机信息交换机制相结合的搜索算法。遗传算法是具机信息交换机制相结合的搜索算法。遗传算法是具有有 生成检测生成检测 的迭代过程的搜索算法。基本流程的迭代过程的搜索算法。基本流程如如图图所示。可见，遗传算法是一种群体型操作，所示。可见，遗传算法是一种群体型操作，该操作以群体中的所有个体为对象。选择（该操作以群体中的所有个体为对象。选择（）、交叉（）和）、交叉（）和变异（）是遗传算法的三个主要变异（）是遗传算法的三个主要操作算子。遗传算法包含如下个基本要素：参数操作算子。遗传算法包含如下个基本要素：参数编码、生成初始群体、适应度评估检测、选择、交编码、生成初始群体、适应度评估检测、选择、交叉操作、变异叉操作、变异 网格算法和穷举法都是暴力搜索最优点的网格算法和穷举法都是暴力搜索最优点的算法，在很多竞赛题中有应用，当重点讨算法，在很多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作这种暴力方案，最好使用一些高级语言作