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

《数学建模竞赛中应当掌握的十类算法课件.ppt》由会员分享，可在线阅读，更多相关《数学建模竞赛中应当掌握的十类算法课件.ppt（34页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数学建模竞赛中应当掌握的十类算法第1页，此课件共34页哦蒙特卡蒙特卡罗算法算法 数据数据处理算法理算法 数学数学规划算法划算法 图论算法算法 动态规划、回溯搜索、分治算法、分支定划、回溯搜索、分治算法、分支定界界 三大非三大非经典算法典算法 网格算法和网格算法和穷举法法 连续离散化方法离散化方法 数数值分析算法分析算法 图象象处理算法理算法 第2页，此课件共34页哦1、蒙特卡、蒙特卡罗算法算法 该算法又称随机性模算法又称随机性模拟算法，是通算法，是通过计算机算机仿真来解决仿真来解决问题的算法，同的算法，同时可以通可以通过模模拟可以来可以来检验自己模型的正确性，是比自己模型的正确性，是比赛时必必

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

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

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

5、putes 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 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 arg

6、uments);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页，此课件共34页哦2、数据、数据拟合、参数估合、参数估计、插、插值等数据等数据处理算法理算法 数据数据拟和和:从从给出的一大堆数据中找出出的一大堆数据中找出规律，即律，即设法构造一条曲法构造一条曲线(拟和曲和曲线)反映数据点反映数据点总的的趋势，以消除其局部波，以消除其局部波动。参数估参数估计：对给定的定的统计问题，在建立了，在建立了统计模型以后，我模型以后，我们的任的任务就是依

7、据就是依据样本本对未知未知总体体进行各种推断，参数估行各种推断，参数估计是是统计推断的重要推断的重要内容之一。包括点估内容之一。包括点估计方法、方法、频率替率替换法、矩法、矩法、极大似然估法、极大似然估计法法 插插值法是函数逼近的一种重要方法，包括多法是函数逼近的一种重要方法，包括多项式插式插值、分段插、分段插值和三角插和三角插值第8页，此课件共34页哦3、数学、数学规划算法划算法 线性性规划、整数划、整数规划、多元划、多元规划、二次划、二次规划等划等规划划类问题（建模（建模竞赛大多数大多数问题属属于最于最优化化问题，很多，很多时候候这些些问题可以用可以用数学数学规划算法来描述，通常使用划算法

8、来描述，通常使用Lindo、Lingo软件件实现）第9页，此课件共34页哦4、图论算法算法 这类算法可以分算法可以分为很多种，包括最短路、很多种，包括最短路、网网络流、二分流、二分图等算法，涉及到等算法，涉及到图论的的问题可以用可以用这些方法解决，需要些方法解决，需要认真准真准备 第10页，此课件共34页哦5、动态规划、回溯搜索、分治算法、分支定界 这些算法是算法些算法是算法设计中比中比较常用的方法，常用的方法，很多很多场合可以用到合可以用到竞赛中中 第11页，此课件共34页哦动态规划划 它建立在最它建立在最优原原则的基的基础上。采用上。采用动态规划方法，可以划方法，可以优雅而高效地解决雅而高

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

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

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

12、时可以找到所需要的解。因此，可以找到所需要的解。因此，这些方些方法通常能法通常能够用来求解用来求解规模很大的模很大的问题。第14页，此课件共34页哦 回溯方法回溯方法 这种方法被用来种方法被用来设计货箱装船、背包、最箱装船、背包、最大完大完备子子图、旅行商和、旅行商和电路板排列路板排列问题的的求解算法。求解算法。第15页，此课件共34页哦算法思想算法思想 回溯（回溯（backtracking）是一种系）是一种系统地搜索地搜索问题解答的方法。解答的方法。为了了实现回溯，首先需要回溯，首先需要为问题定定义一个解空一个解空间（solution space），），这个空个空间必必须至少包含至少包含问题

13、的一个解（可能的一个解（可能是最是最优的）。的）。下一步是下一步是组织解空解空间以便它能被容易地搜索。以便它能被容易地搜索。典型的典型的组织方法是方法是图或或树。第16页，此课件共34页哦分治算法分治算法 君主和殖民者君主和殖民者们所成功运用的分而治之策略也所成功运用的分而治之策略也可以运用到高效率的可以运用到高效率的计算机算法的算机算法的设计过程中。程中。利用利用这一策略可以解决如下一策略可以解决如下问题：最小最大：最小最大问题、矩、矩阵乘法、残缺棋乘法、残缺棋盘、排序、排序、选择和和计算算一个几何一个几何问题找出二找出二维空空间中距离最近的中距离最近的两个点。两个点。第17页，此课件共34

14、页哦算法思想算法思想 分而治之方法与分而治之方法与软件件设计的模的模块化方法非常相化方法非常相似。似。为了解决一个大的了解决一个大的问题，可以：，可以：1)把它把它分成两个或多个更小的分成两个或多个更小的问题；2)分分别解决每解决每个小个小问题；3)把各小把各小问题的解答的解答组合起来，合起来，即可得到原即可得到原问题的解答。小的解答。小问题通常与原通常与原问题相似，可以相似，可以递归地使用分而治之策略来解决。地使用分而治之策略来解决。第18页，此课件共34页哦 例例2-1 找出找出伪币 给你一个装有你一个装有1 6个硬个硬币的的袋子。袋子。1 6个硬个硬币中有一个是中有一个是伪造的，并且造的

15、，并且那个那个伪造的硬造的硬币比真的硬比真的硬币要要轻一些。你的一些。你的任任务是找出是找出这个个伪造的硬造的硬币。为了帮助你完了帮助你完成成这一任一任务，将提供一台可用来比，将提供一台可用来比较两两组硬硬币重量的重量的仪器，利用器，利用这台台仪器，可以知道两器，可以知道两组硬硬币的重量是否相同。的重量是否相同。第19页，此课件共34页哦 比比较硬硬币1与硬与硬币2的重量。假如硬的重量。假如硬币1比硬比硬币2轻，则硬硬币1是是伪造的；假如硬造的；假如硬币2比硬比硬币1轻，则硬硬币2是是伪造的。造的。这样就完成了任就完成了任务。假如两硬假如两硬币重量相等，重量相等，则比比较硬硬币3和硬和硬币4。

16、同。同样，假如有一个硬，假如有一个硬币轻一些，一些，则寻找找伪币的任的任务完成。假如两硬完成。假如两硬币重量相等，重量相等，则继续比比较硬硬币5和硬和硬币6。按照。按照这种方式，可以种方式，可以最多通最多通过8次比次比较来判断来判断伪币的存在并找出的存在并找出这一一伪币。第20页，此课件共34页哦 假如把假如把1 6硬硬币的例子看成一个大的的例子看成一个大的问题。第一步，把。第一步，把这一一问题分成两个小分成两个小问题。随机。随机选择8个硬个硬币作作为第第一一组称称为A组，剩下的，剩下的8个硬个硬币作作为第二第二组称称为B组。这样，就把，就把1 6个硬个硬币的的问题分成两个分成两个8硬硬币的的

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

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

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

20、组只有两个硬只有两个硬币，因此不必再因此不必再细分。比分。比较组中两个硬中两个硬币的重量，可以立即知道哪一个硬的重量，可以立即知道哪一个硬币轻一些。一些。较轻的硬的硬币就是所要找的就是所要找的伪币。第22页，此课件共34页哦分枝定界 类似于回溯法，分枝定界法在搜索解空似于回溯法，分枝定界法在搜索解空间时，也，也经常使用常使用树形形结构来构来组织解空解空间。然而与回溯法不同的是，回溯算。然而与回溯法不同的是，回溯算法使用深度法使用深度优先方法搜索先方法搜索树结构，而分枝定界一般用构，而分枝定界一般用宽度度优先或最小耗先或最小耗费方法来搜索方法来搜索这些些树。本章与第。本章与第1 6章所考察章所考

21、察的的应用完全相同，因此，可以很容易比用完全相同，因此，可以很容易比较回溯法与分枝定回溯法与分枝定界法的异同。相界法的异同。相对而言，分枝定界算法的解空而言，分枝定界算法的解空间比回溯法比回溯法大得多，因此当内存容量有限大得多，因此当内存容量有限时，回溯法成功的可能性更，回溯法成功的可能性更大大 第23页，此课件共34页哦算法思想 分枝定界（分枝定界（branch and bound）是另一种系）是另一种系统地搜索解空地搜索解空间的方法，它与回溯法的主要区的方法，它与回溯法的主要区别在于在于对E-节点的点的扩充方式。充方式。每个活每个活节点有且点有且仅有一次机会有一次机会变成成E-节点。当一个

22、点。当一个节点点变为E-节点点时，则生成从生成从该节点移点移动一步即可到达的所有新一步即可到达的所有新节点。点。在生成的在生成的节点中，抛弃那些不可能点中，抛弃那些不可能导出（最出（最优）可行解的）可行解的节点，点，其余其余节点加入活点加入活节点表，然后从表中点表，然后从表中选择一个一个节点作点作为下一个下一个E-节点。从活点。从活节点表中取出所点表中取出所选择的的节点并点并进行行扩充，直充，直到找到解或活到找到解或活动表表为空，空，扩充充过程才程才结束。束。第24页，此课件共34页哦 有两种常用的方法可用来有两种常用的方法可用来选择下一个下一个E-节点点（虽然也可能存在其他的方法）：然也可能

23、存在其他的方法）：1)先先进先出（先出（F I F O）即从活即从活节点表中取出点表中取出节点的点的顺序与加入序与加入节点的点的顺序相同，因此活序相同，因此活节点表的性点表的性质与与队列相同。列相同。2)最小耗最小耗费或最大收益法在或最大收益法在这种模式中，每个种模式中，每个节点都有一个点都有一个对应的耗的耗费或收益。如果或收益。如果查找一找一个具有最小耗个具有最小耗费的解，的解，则活活节点表可用最小堆点表可用最小堆来建立，下一个来建立，下一个E-节点就是具有最小耗点就是具有最小耗费的活的活节点；如果希望搜索一个具有最大收益的解，点；如果希望搜索一个具有最大收益的解，则可用最大堆来构造活可用最

24、大堆来构造活节点表，下一个点表，下一个E-节点点是具有最大收益的活是具有最大收益的活节点。点。第25页，此课件共34页哦6、模拟退火法、神经网络、遗传算法 模模拟退火法（退火法（Simulated Annealing）是）是Kirkpatrick等人在一九八三年提出并成功地等人在一九八三年提出并成功地应用在用在组合最佳化問題中，它是蒙特卡合最佳化問題中，它是蒙特卡罗演算演算法的推广。法的推广。人工神人工神经网网络的基本的基本结构构:递归网网络和前和前馈网网络人工神人工神经网网络的典型模型有的典型模型有:自适自适应谐振理振理论(ART)、Kohonen 网网络、反向反向传播播(BP)网网络、Ho

25、pfield网网 第26页，此课件共34页哦 遗传算法（算法（，简称）称）是以自然是以自然选择和和遗传理理论为基基础，将生物，将生物进化化过程中适者生程中适者生存存规则与群体内部染色体的随机信息交与群体内部染色体的随机信息交换机制相机制相结合的搜索合的搜索算法。算法。遗传算法是具有算法是具有生成生成检测的迭代的迭代过程的搜索算程的搜索算法。基本流程如法。基本流程如图所示。可所示。可见，遗传算法是一种群体算法是一种群体型操作，型操作，该操作以群体中的所有个体操作以群体中的所有个体为对象。象。选择（）、交叉（）和）、交叉（）和变异（）是异（）是遗传算法的三个主要操作算法的三个主要操作算子。算子。遗

26、传算法包含如下个基本要素：参数算法包含如下个基本要素：参数编码、生、生成初始群体、适成初始群体、适应度度评估估检测、选择、交叉操作、交叉操作、变异异第27页，此课件共34页哦第28页，此课件共34页哦7、网格算法和、网格算法和穷举法法 网格算法和网格算法和穷举法都是暴力搜索最法都是暴力搜索最优点的点的算法，在很多算法，在很多竞赛题中有中有应用，当重点用，当重点讨论模型本身而模型本身而轻视算法的算法的时候，可以使用候，可以使用这种暴力方案，最好使用一些高种暴力方案，最好使用一些高级语言作言作为编程工具程工具 第29页，此课件共34页哦 穷举法是基于法是基于计算机特点而算机特点而进行解行解题的思的

27、思维方法。一般是在一方法。一般是在一时找不出解决找不出解决问题的更好的更好途径途径时，可以根据，可以根据问题中的部分条件（中的部分条件（约束束条件）将所有可能解的情况列条件）将所有可能解的情况列举出来，然后出来，然后通通过一一一一验证是否符合整个是否符合整个问题的求解要求，的求解要求，而得到而得到问题的解。的解。这种解决种解决问题的方法我的方法我们称之称之为穷举算法。算法。穷举法特点是算法法特点是算法简单，但运行但运行时所花所花费的的时间量大。量大。第30页，此课件共34页哦8、连续离散化方法离散化方法 很多很多问题都是都是实际来的，数据可以是来的，数据可以是连续的，的，而而计算机只算机只认的

28、是离散的数据，因此将其离散的是离散的数据，因此将其离散化后化后进行差分代替微分、求和代替行差分代替微分、求和代替积分等思想分等思想是非常重要的是非常重要的 第31页，此课件共34页哦9、数、数值分析算法分析算法 如果在比如果在比赛中采用高中采用高级语言言进行行编程的程的话，那一些数那一些数值分析中常用的算法比如方程分析中常用的算法比如方程组求解、矩求解、矩阵运算、函数运算、函数积分等算法就需要分等算法就需要额外外编写写库函数函数进行行调用用第32页，此课件共34页哦10、图象象处理算法理算法 赛题中有一中有一类问题与与图形有关，即使与形有关，即使与图形无关，形无关，论文中也文中也应该要不乏要不乏图片的，片的，这些些图形如何展示以及如何形如何展示以及如何处理就是需要解理就是需要解决的决的问题，通常使用，通常使用Matlab进行行处理理第33页，此课件共34页哦网站介绍网站介绍放放飞技技术网网www.jiaoyu.info/IT/数学中国数学中国