假如把1 6硬币的例子看成一个大的问题。第一步， 把这一问题分成两个小问题。随机选择8个硬币作 为第一组称为A组，剩下的8个硬币作为第二组称 为B组。这样，就把1 6个硬币的问题分成两个8硬 币的问题来解决。第二步，判断A和B组中是否有 伪币。可以利用仪器来比较A组硬币和B组硬币的 重量。假如两组硬币重量相等，则可以判断伪币不 存在。假如两组硬币重量不相等，则存在伪币，并 且可以判断它位于较轻的那一组硬币中。最后，在 第三步中，用第二步的结果得出原先1 6个硬币问 题的答案。若仅仅判断硬币是否存在，则第三步非 常简单。无论A组还是B组中有伪币，都可以推断 这1 6个硬币中存在伪币。因此，仅仅通过一次重 量的比较，就可以判断伪币是否存在。
分治算法
君主和殖民者们所成功运用的分而治之策略也 可以运用到高效率的计算机算法的设计过程中。 利用这一策略可以解决如下问题：最小最大问 题、矩阵乘法、残缺棋盘、排序、选择和计算 一个几何问题——找出二维空间中距离最近的 两个点。
算法思想
分而治之方法与软件设计的模块化方法非常相 似。为了解决一个大的问题，可以： 1) 把它 分成两个或多个更小的问题； 2) 分别解决每 个小问题； 3) 把各小问题的解答组合起来， 即可得到原问题的解答。小问题通常与原问题 相似，可以递归地使用分而治之策略来解决。
算法思想
分枝定界（branch and bound）是另一种系统地搜 索解空间的方法，它与回溯法的主要区别在于对E-节 点的扩充方式。每个活节点有且仅有一次机会变成E节点。当一个节点变为E-节点时，则生成从该节点移 动一步即可到达的所有新节点。在生成的节点中，抛 弃那些不可能导出（最优）可行解的节点，其余节点 加入活节点表，然后从表中选择一个节点作为下一个 E-节点。从活节点表中取出所选择的节点并进行扩充， 直到找到解或活动表为空，扩充过程才结束。
6、模拟退火法、神经网络、遗传算 法
模拟退火法（SLeabharlann mulated Annealing）是 Kirkpatrick等人在一九八三年提出并成功地 应用在组合最佳化問題中，它是蒙特卡罗演算 法的推广。 人工神经网络的基本结构: 递归网络和前馈网 络 人工神经网络的典型模型有:自适应谐振理论 (ART)、 Kohonen 网络 、 反向传播(BP)网 络 、 Hopfield网
数学建模竞赛中应当 掌握的十类算法
• 蒙特卡罗算法 • 数据处理算法 • 数学规划算法 • 图论算法 • 动态规划、回溯搜索、分治算法、分支定
界 • 三大非经典算法 • 网格算法和穷举法 • 连续离散化方法 • 数值分析算法 • 图象处理算法
1、蒙特卡罗算法
该算法又称随机性模拟算法，是通过计算机 仿真来解决问题的算法，同时可以通过模拟 可以来检验自己模型的正确性，是比赛时必 用的方法
5、动态规划、回溯搜索、分治算法、 分支定界
这些算法是算法设计中比较常用的方法， 很多场合可以用到竞赛中
动态规划
它建立在最优原则的基础上。采用动态规 划方法，可以优雅而高效地解决许多用贪 婪算法或分而治之算法无法解决的问题。 动态规划方法在解决背包问题、图象压缩、 矩阵乘法链、最短路径、无交叉子集和元 件折叠等方面的有很大作用。
7、网格算法和穷举法
网格算法和穷举法都是暴力搜索最优点的 算法，在很多竞赛题中有应用，当重点讨 论模型本身而轻视算法的时候，可以使用 这种暴力方案，最好使用一些高级语言作 为编程工具
2、数据拟合、参数估计、插值 等数据处理算法
数据拟和: 从给出的一大堆数据中找出规律， 即设法构造一条曲线(拟和曲线)反映数据点 总的趋势，以消除其局部波动。
参数估计：对给定的统计问题，在建立了统 计模型以后，我们的任务就是依据样本对未 知总体进行各种推断，参数估计是统计推断 的重要内容之一。包括点估计方法、频率替 换法、矩法、极大似然估计法
插值法是函数逼近的一种重要方法，包括 多项式插值、分段插值和三角插值
3、数学规划算法
线性规划、整数规划、多元规划、二次规 划等规划类问题（建模竞赛大多数问题属 于最优化问题，很多时候这些问题可以用 数学规划算法来描述，通常使用Lindo、 Lingo软件实现）
4、图论算法
这类算法可以分为很多种，包括最短路、 网络流、二分图等算法，涉及到图论的问 题可以用这些方法解决，需要认真准备
考虑平面上的一个边长为1的正方形及其内 部的一个形状不规则的“图形”，如何求 出这个“图形”的面积呢？Monte Carlo方 法是这样一种“随机化”的方法：向该正 方形“随机地”投掷N个点落于“图形”内， 则该“图形”的面积近似为M/N。
另一类形式与Monte Carlo方法相似，但理 论基础不同的方法—“拟蒙特卡罗方法” (Quasi-Monte Carlo方法)—近年来也获得 迅速发展。我国数学家华罗庚、王元提出 的“华—王”方法即是其中的一例。这种方 法的基本思想是“用确定性的超均匀分布 序列(数学上称为Low Discrepancy Sequences)代替Monte Carlo方法中的随 机数序列。对某些问题该方法的实际速度 一般可比Monte Carlo方法提出高数百倍， 并可计算精确度。
蒙特卡罗(Monte Carlo)方法，或称计算机 随机模拟方法，是一种基于“随机数”的 计算方法。这一方法源于美国在第一次世 界大战进研制原子弹的“曼哈顿计划”。 该计划的主持人之一、数学家冯·诺伊曼用 驰名世界的赌城—摩纳哥的Monte Carlo— 来命名这种方法，为它蒙上了一层神秘色 彩。
• 具体实现的matlab代码： • ------------------------------------------------------------------------------------------------
--• function val = ballvol(n, m) • % BALLVOL Compute volume of unit ball in R^n •% • % 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 argument is omitted, 1e4 is taken as default for m. • % (c) 1998, Rolf Krause, krause@math.fu-berlin.de • M = 1e4; • error = 0; • if(nargin <1 | nargin > 2), error('wrong number of arguments'); end • if nargin == 2, M = m; end • R = rand(n, M); • in = 0; • for i=1:M • if(norm(R(:,i),2) <= 1.0), in = in+1; end • end
算法思想
和贪婪算法一样，在动态规划中，可将一个 问题的解决方案视为一系列决策的结果。不同 的是，在贪婪算法中，每采用一次贪婪准则便 做出一个不可撤回的决策，而在动态规划中， 还要考察每个最优决策序列中是否包含一个最 优子序列。
寻找问题的解的一种可靠的方法是首先列出所有候 选解，然后依次检查每一个，在检查完所有或部 分候选解后，即可找到所需要的解。理论上，当 候选解数量有限并且通过检查所有或部分候选解 能够得到所需解时，上述方法是可行的。不过， 在实际应用中，很少使用这种方法，因为候选解 的数量通常都非常大（比如指数级，甚至是大数 阶乘），即便采用最快的计算机也只能解决规模 很小的问题。对候选解进行系统检查的方法有多 种，其中回溯和分枝定界法是比较常用的两种方 法。按照这两种方法对候选解进行系统检查通常 会使问题的求解时间大大减少（无论对于最坏情 形还是对于一般情形）。事实上，这些方法可以 使我们避免对很大的候选解集合进行检查，同时 能够保证算法运行结束时可以找到所需要的解。 因此，这些方法通常能够用来求解规模很大的问 题。
现在假设需要识别出这一伪币。把两个或三个硬币的情况作 为不可再分的小问题。注意如果只有一个硬币，那么不能判 断出它是否就是伪币。在一个小问题中，通过将一个硬币分 别与其他两个硬币比较，最多比较两次就可以找到伪币。这 样，1 6硬币的问题就被分为两个8硬币（A组和B组）的问 题。通过比较这两组硬币的重量，可以判断伪币是否存在。 如果没有伪币，则算法终止。否则，继续划分这两组硬币来 寻找伪币。假设B是轻的那一组，因此再把它分成两组，每 组有4个硬币。称其中一组为B1，另一组为B2。比较这两组， 肯定有一组轻一些。如果B1轻，则伪币在B1中，再将B1又 分成两组，每组有两个硬币，称其中一组为B1a，另一组为 B1b。比较这两组，可以得到一个较轻的组。由于这个组只 有两个硬币，因此不必再细分。比较组中两个硬币的重量， 可以立即知道哪一个硬币轻一些。较轻的硬币就是所要找的 伪币。
例2-1 [找出伪币] 给你一个装有1 6个硬币 的袋子。1 6个硬币中有一个是伪造的，并 且那个伪造的硬币比真的硬币要轻一些。你 的任务是找出这个伪造的硬币。为了帮助你 完成这一任务，将提供一台可用来比较两组 硬币重量的仪器，利用这台仪器，可以知道 两组硬币的重量是否相同。
比较硬币1与硬币2的重量。假如硬币1比硬币 2轻，则硬币1是伪造的；假如硬币2比硬币1 轻，则硬币2是伪造的。这样就完成了任务。 假如两硬币重量相等，则比较硬币3和硬币4。 同样，假如有一个硬币轻一些，则寻找伪币 的任务完成。假如两硬币重量相等，则继续 比较硬币5和硬币6。按照这种方式，可以最 多通过8次比较来判断伪币的存在并找出这一 伪币。
分枝定界
类似于回溯法，分枝定界法在搜索解空间时，也经常 使用树形结构来组织解空间。然而与回溯法不同的 是，回溯算法使用深度优先方法搜索树结构，而分 枝定界一般用宽度优先或最小耗费方法来搜索这些 树。本章与第1 6章所考察的应用完全相同，因此， 可以很容易比较回溯法与分枝定界法的异同。相对 而言，分枝定界算法的解空间比回溯法大得多，因 此当内存容量有限时，回溯法成功的可能性更大