数学建模算法设计简介

《数学建模算法设计简介》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、算法设计简介问题求解概述问题求解的一般步骤：需求分析建模算法设计程序实现测试应用分析输入输出数据，设计合理的数据结构设计适当的算法，确立输入输出之间的函数关系。比如，计算参数模型的函数参数，或者函数逼近（神经网络等方法）建模方法差分方程、差分方程组：抵押贷款买房问题等模型拟合：最小二乘法、三阶样条模型等概率模型：线性回归，随机行为模拟等线性规划：单纯形法等图论建模：最短路径问题、最大流问题等决策论：决策树、序列决策博弈论：囚徒困境问题微分方程、微分方程组建模：人口增长模型、传染病模型…………模型的设计与实现——数据结构数据模型：数据对象，数据对象之间的关系数

2、据对象之间的关系：逻辑结构，物理结构逻辑结构：线性结构，树形结构，图形结构，集合结构物理结构：顺序存储，链式存储，索引存储，散列存储算法设计算法：输入数据算法模块输出结果对于用户来讲，算法模块就是黑匣子算法设计方法算法确定的非确定的传统算法：近似算法：随机算法：智能算法：以100%成功概率求解问题的最优解对解的质量让步对求解成功概率和解的质量让步遗传算法，模拟退火算法，蚁群算法，神经网络算法等等算法设计思想枚举法：也称穷举法。归纳法：也就是通常的找规律。递推法：类似归纳，竞赛中的数学题常常需要递推和归纳。递归法：递归分为直接递归和间接递归，很多问题都需要借助

3、递归思想和方法求解，包括分治、DP的题目。回溯法：也即试探法。迭代法：迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。迭代思想是很多问题求解或代码实现的基本方法。从问题求解基本思路看，算法设计思想有如下几种：算法设计方法（1）——贪心法（1）贪心法(greedymethod)算法思想：在贪婪算法中采用逐步构造最优解的方法。在每个阶段，都做出一个看上去最优的决策(在一定的准则下)。决策一旦做出，就不可再更改。做出贪婪决策的依据称为贪婪准则。贪心法采用的是局部最优策略，而局部最优有时并不保证全局最优。当然，有许多应用问题只要近似最优即可，对这些问题的求

4、解贪心法还是非常实用的。例如，找零钱问题，用贪心法可以求得最优解。算法设计方法（2）——分治法（2）分治法（DivideandConquerMethod）算法思想：把它分成两个或多个更小、更简单的问题；分别解决每个小问题；把各个小问题的解答组合起来，即可得出原问题的解。典型案例：汉诺塔问题算法设计方法（3）——动态规划算法思想：将一个问题的解决方案视为一系列决策的结果，并考察每个最优决策序列中是否包含一个最优子序列。动态规划方法采用最优原则来建立用于计算最优解的递归式。（3）动态规划(DynamicProgramming)最优原则：即不管前面的策略如何，此后

5、的决策必须是基于当前状态的最优决策。若不能保持最优原则，则不可应用动态规划方法。动态规划的数学表现是递归、排列组合，在递归过程中会出现重复计算问题，为了解决这个开销，使用二维表格保存已计算出的结果，以便复用。算法设计方法（4）——算法思想：回溯是一种系统地搜索问题解的方法。为了实现回溯，首先需要为问题定义一个解空间（solutionspace），这个空间必须至少包含问题的一个解（可能是最优的）。（4）回溯法（backtrackingMethod）回溯方法的步骤如下：定义一个解空间，它包含问题的解；用适合于搜索的方式组织该空间；用深度优先法搜索该空间，利用限界

6、函数避免移动到不可能产生解的子空间。算法设计方法（5）——分支定界算法思想：分支定界是另一种系统地搜索解空间的方法，回溯法以深度优先的方式搜索解空间树T，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树T。建立一个活节点表。每个活节点仅有一次机会可以扩充，生成从该节点移动一步即可到达的所有新节点。在生成的节点中，抛弃那些不可能导出（最优）可行解的节点，其余节点加入活节点表。直到找到解或活动表为空，扩充过程才结束。（5）分支限界（branchandbound）算法设计方法（6）——随机算法算法思想：在算法中引入随机因素，即通过随机因素选择算法的下一步

7、操作。在许多情况下，一般算法比较复杂，性能较差，很多具有很好平均运行时间的算法，在最坏的情况下，却具有很坏的性能。采用随机算法可以实现“平均情况下的”良好业绩的希望。（6）随机算法（RandomizedAlgorithms）随机算法对所求解问题的同一个实例用同一随机算法求解两次可能得到完全不同的效果。这两次求解所需要的时间，甚至所得到的结果都可能会有相当大的差别。随机算法包括：数值概率算法蒙特卡罗（MonteCarlo）算法拉斯维加斯（LasVegas）算法舍伍德（Sherwood）算法分治法分治策略：分治法是一种常用的算法技巧，从字面上的看就是“分而治之”

8、的意思，把一个复杂的问题分成两个或更多的相同或相似的