启发式搜索
"启发"( heuristic)是关于发现和发明规则及方法的研究。在状态空间搜索中, 启发式被定义成一系列规则, 它从状态空间中选择最有希望到达问题解的路径。人工智能问题求解者在两种基本情况下运用启发式策略:
1.一个问题由于在问题陈述和数据获取方面固有的模糊性可能使它没有一个确定的解。医疗诊断即是一例。所给出的一系列症状可能有多个原因; 医生运用启发搜索来选择最有可能的论断并依此产生治疗的计划。视觉问题又是一例。看到的景物经常是模糊的, 各个物体在其连接、范围和方向上可以有多个解释。光所造成的幻觉加大了这些模糊性, 视觉系统可运用启发式策略选择一给定景象的最有可能解释。
2.一个问题可能有确定解, 但是求解过程中的计算机代价令人难以接受。在很多问题(如国际象棋)中, 状态空间的增长特别快, 可能的状态数随着搜索的深度呈指数级增长、分解。在这种情况下, 穷尽式搜索策略, 诸如深度优先或广度优先搜索,在一个给定的较实际的时空内很可能得不到最终的解。启发式策略通过指导搜索向最有希望的方向前进降低了复杂性。通过仔细考虑, 删除某些状态及其延伸, 启发式算法可以消除组合爆炸, 并得到令人能接受的解。
然而, 和发明创造的所有规则一样, 启发式策略也是极易出错的。在解决问题过程中启发仅仅是下一步将要采取措施的一个猜想。它常常根据经验和直觉来判断。由于启发式搜索只有有限的信息,诸如当前Open表中状态的描述,要想预测进一步搜索过程中状态空间的具体的行为很难办到。一个启发式搜索可能得到一个次最佳解, 也可能一无所获。这是启发式搜索固有的局限性。这种局限性不可能由所谓更好的启发式策略或更有效的搜索算法来消除。
启发式策略及算法设计一直是人工智能的核心问题。博奕和定理证明是两个最古老的应用: 二者都需要启发式知识来剪枝以减少状态空间。显然, 检查数学领域中每一步推理或棋盘上每一步可能的移动是不可行的。启发式搜索常常仅是实践中的解答。
近来, 专家系统的研究把启发式策略作为问题求解的一个重要部分。当一个专家解决问题时, 他检查所获取的信息并作出决定。实际上, 专家用来解决问题的"拇指法则"很大程度上是启发式的。这些启发性知识被专家系统的设计者提取出来并形成规则。
通常启发式算法由两部分组成: 启发方法和使用该方法搜索状态空间的算法。本章先介绍最好优先搜索的算法, 再讨论启发式算法的设计和评估。
在一字棋游戏中(图4.5), 穷尽搜索的组合数很大。第一步移动共有九种移法 , 每一种又有八种对应走法……依次类推, 这个问题在穷尽搜索策略下需考虑9!个状态。
根据对称性可以减少搜索空间的数目。棋盘上很多构造是等价的。譬如, 第一步实际上只有三种移法, 角、边的中央以及网络正中。在状态空间的第二层上, 由对称性可进一步减少到12×7!种。在图5.1 中可见到该状态空间比最初的状态空间要小, 但它在扩展过程中还要继续分解。
然而, 一个简单的启发式策略几乎可以整个地消除复杂的搜索过程。首先, 将棋子移到棋盘上×有最多的赢线的点。最初的三种状态显示在图5.2中。若两种状态有相等的赢的机率, 取其中的第一个。这样的话,可设计一种算法(完全实现启发式搜索), 它选择并移到具有最高启发值的状态。在这种情况下, ×占椐网络的中间点, 其它的各种状态都不再考虑, 它们的延伸状态同时也给消除
了。如图5.3 所示三分之二的状态空间就这样给剪枝了。
第一步走完后, 对方只能有两种走法(见图5.3)。无论选择哪种走法,我方均可以通过启发式搜索选择下一步可能的走法。在搜索过程中, 每一步只需估价一下单个节点的子结点; 不需要强力搜索。图5.3 显示了游戏前三步简化了的搜索过程。每种状态都标记了它的启发值。
要精确地计算待检查的状态的数目比较难, 但可以大致计算它的上限。一盘棋最多走九步, 每步的下一步平均有四、五种走法。这样大约就是4.5×9, 近40种状态, 比9!改善了很多。
5.1 启发信息和估计函数
人工智能的核心课题是问题求解。所谓"问题求解"就是在广义图中寻找一条从初始状态出发, 到达目标状态的解树。例如旅行问题是解决从出发点到达目的地的路线和工具问题; 机器人装配机器, 就是给出把一堆零件变成一台机器的一系列操作; 定理证明就是寻找一条从前提条件到达结论的通路等等。
在实际解决一个具体问题时, 人们常常把一个具有复杂联系的实际问题抽象化,保留某些主要因素, 忽略掉大量次要因素, 从而将这个实际问题转化成具有明确结构的有限状态空间问题, 这个空间中的状态和变化规律都是已知的有限集合, 因此可以找到一个求解该问题的算法。
然而, 在智能活动中使用最多的不是具有完备性的算法, 而是不一定完备的启发式方法。其原因有二:
首先, 大多数情况下, 智能系统不知道与实际问题有关的全部信息, 因而无法知道该问题的全部状态空间, 不可能用一套算法来求解其中的所有问题, 这样就只能依靠部分状态空间和一些特殊的经验性规则来求解其中的部分问题。
其次, 有些问题在理论上存在求解算法, 但是在工程实践中, 这些算法不是效率太低, 就是根本无法实现, 为了提高解题的效率, 不得不放弃使用这些算法, 而求助于一些经验性的启发式规则。
例如在博弈问题中, 计算机为了保证最后胜利, 可以将所有可能的走法都试一遍, 然后选择最佳走步。这样的算法是可以找到的, 但计算所需的时空代价十分惊人。就可能有的棋局数讲, 一字棋是9!=3.6×105, 西洋跳棋是1078, 国际象棋是10120, 围棋是10761。假设每步可能选择一种棋局, 用极限并行速度(10-104年/步)计算, 国际象棋的算法也得1016年即1亿亿年才可以算完, 而我们已知的宇宙史才 100亿年!
由此看来, 启发式的问题求解, 不仅在实践上是需要的, 而且在理论上也是必不可少的。
对问题空间进行搜索时, 提高搜索效率需要有和被解问题的解有关的大量控制性知识作为搜索的辅助性策略。有两种极端的情况: 一种是没有任何这种控制性知识作为搜索的依据, 因而搜索的每一步完全是随意的, 如随机搜索; 另一种是有充分控制性知识作为依据, 因而搜索的每步选择都是正确的, 这种搜索叫最佳搜索。一般情况是介于二者之间, 这些控制性信息反映在估价函数之中。
估价函数的任务就是估计待搜索结点的重要程度, 给它们排定次序。估价函数f(x)可以是任意一种函数, 如有的定义它是结点x处于最佳路径上的概率, 或是x结点和目标结点之间的距离, 或是x格局的得分等等。一般来说, 估价一个结点的价值, 必须综合考虑两方面的因素: 已经付出的代价和将要付出的代
价。在此, 我们把估价函数f(n)定义为从初始结点经过n 结点到达目标结点的最小代价路径的代价估计值, 它的一般形式是: f(n)=g(n)+h(n) 其中g(n)是从初始结点到n的实际代价, h(n)是从n到目标结点的最佳路径的估计代价, 主要是h(n)体现了搜索的启发信息。因为实际代价g(n)可以根据生成的搜索树实际计算出来, 而估计代价h(n)却依赖于某种经验估计, 它来源于我们对问题的解的某些特性的认识, 这些特性可以帮助我们更快地找到问题的解。
一般地, 在f(n)中, g(n)的比重越大, 越倾向于广度优先搜索方式; h(n)的比重越大, 越倾向于深度优先搜索方式。
g(n)的作用一般是不可忽略的, 因为它代表了从初始结点经过n 到达目标结点的总代价估值中实际已付出的那一部分。保持g(n)项就保持了搜索的广度优先趋势, 这有利于搜索的完备性, 但影响搜索的效率。在特殊情况下, 如果只希望找到达到目标结点的路径而不关心已付出的代价, 则g(n)的作用可以忽略。另外, h(n)> >g(n)时, 也可以忽略g(n), 这时有f(n)=h(n), 这有利于搜索的效率, 但影响搜索的完备性。
给定一个问题后, 根据问题的特性和解的特性, 可以有多种方法定义估价函数, 用不同的估价函数指导搜索, 其效果可以相差很远。因此,必须尽可能选择最能体现问题特性的, 最佳的估价函数。
5.2 启发式搜索算法
5.2.1 局部择优搜索法(瞎子爬山法)
实现启发式搜索最简单的方法是瞎子爬山法(hill climbing)。瞎子爬山法在搜索过程中扩展当前结点并估价它的子结点。最优的子结点被选择并进一步扩展; 该子结点的兄弟结点和父结点都不再保留。当搜索达到一种状态, 该状态比它的所有子结点都要好, 则搜索停止。瞎子爬山法可以这样理解──一个盲人急切地想登上山顶, 他总是沿着最陡的山路向上爬, 直到再不能找到新的路径。瞎子爬山法有这样一个缺陷: 一个错误的启发知识可能导致搜索无法沿着正确的路径前进, 从而增加了搜索的深度, 甚至是无穷尽地搜索。由于瞎子爬山法不保存所走过的结点信息, 故瞎子爬山算法无法修正错误的路径。
瞎子爬山法还可能在一个局部的最佳点上停止。当搜索到一个结点, 它的估计代价比任一个子结点都要小, 则算法结束。如果此时并不是目标状态, 而只是一个局部最优结点, 则该算法就不能得到目标解。因此, 在一个限定的环境下, 瞎子爬山法可能会极大地提高搜索效率, 但是对于整个搜索空间, 就有可能无法得到最佳解。重排九宫游戏就是一个突出的例子。为了将一个特定的格局移到它的目标位置上, 常常需要移动已经在其目标位置上的将牌。这对于完成拼图是必要的, 但它显然暂时恶化了拼板上的状态。由于"更好"并不是"最好", 瞎子爬山法无法区别局部和全局最优解。处理这个问题时有许多种方法, 譬如随时地修正估价函数来突破局部最优的限制。但是总的来说, 没有一种方法能保证瞎子爬山法的最佳效率。下面介绍一个瞎子爬山法的例子──跳棋程序。
在人工智能中, Samuel的跳棋程序最早应用该方法。在跳棋程序中, 不仅运用了启发式搜索, 还实现了简单的学习功能。
跳棋程序中根据几个不同启发值的总和来估算棋局的状态: ∑aixii
其中xi是棋局的一系列特征, 如残局优势、残局棋子力量分布, 中心点位置
的控制等。这些xi的系数由它在整个估值中所处的重要性来确定。也就是说, 如果残局优势比控制中心点重要, 则残局优势的系数要大。
该程序将搜索空间扩展到一定局数并根据多项式估值函数估算该局中所有状态值。根据5.4.2节介绍的极大极小法, 程序可倒推出图中所有状态的估值。游戏者根据结点的最佳状态走棋; 对手走棋后, 根据新的棋局状态, 整个过程将再来一遍。
若多项式估值函数导向一系列不能取胜的移动, 程序将调整其系数以提高能力。具有较大系数的因素由于在输棋原因中占很大比重, 它的系数将减小, 而较小的系数将增大以提高相关因素的影响力。如果取胜则情况相反。通过与人或其自身的不同版本对抗, 程序不断训练学习。
可以看出, 跳棋游戏在学习过程中采用的是瞎子爬山法, 通过对多项式估值函数的局部的改进来提高自身的性能。该程序能不断改进到水平很高为止。然而, 由于算法依靠瞎子爬山法, 它不可避免地具有某些限制。例如, 由于采用的不是全局的策略, 程序容易被对手利用某种启发策略导向陷阱。同样, 程序的自学习功能容易被对手的随手棋所迷惑; 例如, 老对手灵活地采用多种策略, 或
故意乱下棋, 这就会使多项式估值函数的系数随意性很大, 从而全面降低了程序的能力。
上例表明, 尽管瞎子爬山法有其局限性, 但是若估价函数选取得当并能够避免局部最优解和无穷搜索时, 它就会充分发挥搜索的高效率。总之, 启发式搜索需要一个具有很多启发信息的算法, 而最好优先搜索就提供了这一算法。
5.2.2 最好优先搜索法(有序搜索法)
和第四章中所提到的深度优先及广度优先搜索算法一样, 最好优先搜索算法也使用了两张表来记录结点信息: 在Open表中保留所有已生成而未考察的结点; 在Closed表中记录已访问过的结点。算法中有一步是根据某些启发信息, 按结点距离目标状态的长度大小重排Open表中的结点这样。循环中的每一步只考虑Open表中状态最好的结点, 这就是最好优先搜索算法,又称为有序搜索法。其数据结构(Open表)既不同于广度优先使用的队(先进先出), 也不同于深度优先使用的栈(后进先出) , 而是一个按结点的启发估计函数值的大小为序排列的一个表, 有时也称为"优先队"。进入优先队的结点不是简单地排在队尾(或队首), 而是根据其估值的大小插入队中合适的位置, 每次从队中优先取出估值最小的结点加以扩展。
最好优先搜索的算法描述如下:
PROCEDURE BEST-FIRST-SEARCH
INITIALIZE:OPEN=[START];CLOSED=[ ];
WHILE OPEN≠[ ] DO
BEGIN
REMOVE THE NEXT STATE FROM OPEN, CALL IT X;
IF X IS A GOAL THEN RETURN THE SOLUTION PATH THAT LED TO X; PROCESS X,GENERATING ALL ITS CHILDREN;
FOR EACH CHILD OF X
DO CASE
THE CHILD IS NOT ALREADY ON OPEN OR CLOSED:
BEGIN
ASSIGN A HEURISTIC VALUE TO THE CHILD STATE;
ADD THE CHILD STATE TO OPEN;
END;
THE CHILD IS ALREADY ON OPEN:
IF THE CHILD WAS REACHED ALONG A SHORTER PATH THAN
THE STATE CURRENLTY ON OPEN
THEN GIVE THE STATE ON OPEN THIS SHORTER PATH VALUE
THE CHILD IS ALREADY ON CLOSED:
IF THE CHILD WAS REACHED ALONG A SHORTER PATH THAN
THE STATE CURRENLTY ON CLOSED
THEN
BEGIN
GIVE THE STATE ON CLOSED THIS SHORTER PATH VALUE; MOVE THIS STATE FROM CLOSED TO OPEN
END
END;
PUT X ON CLOSED;
RE-ORDER STATES ON OPEN ACCORDING TO HEURISTIC MERIT
(BEST VALUES FIRST)
END;
RETURN(FAILURE); %OPEN IS EXHAUSTED
END.
在每一次重复中, 最好优先搜索算法从Open表中取出第一个元素, 如果该元素满足目标条件, 则算法返回到达该元素的搜索路径。在这里, 每个结点都保留父结点的信息, 以保证返回完整的搜索路径。
若Open表的第一个元素不是目标结点, 则算法应用相应的规则进行一系列操作来产生它的子结点。如果子结点的状态已在Open(或Closed表)中, 则算法保证新的状态记录两个求解路径中花费小的一个, 不保留重复的状态。这样, 当Open表(或Closed表)中的结点再一次被发现时, 通过刷新它的祖先结点的历史记录, 算法就极有可能得到到达目标结点的更短的路径。
接着, 最好优先搜索法估算Open表中每个结点的状态的启发值, 按照值的大小重新排序, 将值最小的状态放在表头。
图5.4是一个层次式状态空间, 有些结点旁边标上了相应的启发值。标上值的那些状态都是在最好优先搜索中实际生成的。在这张图中, 启发搜索算法扩展的状态都已显示; 算法无需搜索所有的状态空间。最好优先搜索算法的目标是尽可能地减小搜索空间而得到解, 启发信息给得越多, 处理的状态就越少。
下面给出了这张图的最好优先搜索算法的运行过程。假定P是目标状态, 则到P 的路径上的结点状态有较低的启发值。在这里, 启发信息难免会有错误; 状态O比P的值小而先被检查。然而, 不象瞎子爬山法, 该算法本身有纠错功能, 能从此状态返回并找到正确的目标状态。
1. Open=[A5]; Closed=[ ]
2. 估算A5; Open=[B4,C4,D6]; Closed=[A5]
3. 估算B4; Open=[C4,E5,F5,D6]; Closed=[B4,A5]
4. 估算C4; Open=[H3,G4,E5,F5,D6]; Closed=[C4,B4,A5]
5. 估算H3; Open=[O2,P3,G4,E5,F5,D6]; Closed=[H3,C4,B4,A5]
6. 估算O2; Open=[P3,G4,E5,F5,D6]; Closed=[O2,H3,C4,B4,A5]
7. 估算P3; 已得到解!
图5.5是算法执行了五次循环后的状态空间图。Open表和Closed 表中的状态以不同的亮度显示。Open表中记录搜索的当前结点, Closed表中保存已考察过的状态。
最好优先搜索算法总是从Open表中选取最"好"的状态进行扩展。但是, 由于启发信息有时可能出错, 故算法并不丢弃其它的状态而把它们保留在Open表中。当某一个启发信息将搜索导向错误路径时, 算法可以从Open表中检索先前产生的" 次最好"状态, 并且将考察方向转向空间的另一部分上。如图5.4, 当算法发现状态B 的子结点有很差的启发值时, 搜索转移到C, 但B的子结点都保留在Open表中, 以防算法在未来的某一步再一次转向它们。在最好优先搜索算法中, 就象第四章中的算法一样, 当某一路径无法到达目标解时, 可使搜索转到另一条路径上。
5.2.3 启发估计函数的实现
不同的启发策略对解决九宫问题有不同的影响。图5.6 显示了九宫问题的起始状态、目标状态以及搜索过程中产生的前三个状态。
最简单的启发策略是计算每种格局下与目标结点的格局相比时位置不符的将牌数目。从感觉上来说, 这种策略很有效, 因为在其它条件相同的情况下, 位置不符将牌数目越少, 它看上去和最终目标越近, 因而是检验的下一个状态。
但是, 这种策略并没有充分利用所能获得的信息, 它没有考虑将牌所需移动的距离。一个"较好"的启发策略是将牌移到目标位置上时所需移动距离的总和相加作为启发值。
这两种策略都没有考虑将牌逆转时的情况, 也就是, 如果两块将牌相邻但
是和目标格局相比位置相反, 这至少需要移动两次才能将它们移到正确的位置上, 将这一点加以考虑的启发策略对每一对逆转将牌乘以一个小倍数(如2)。图5.8显示的就是将这三种策略运用到图5.6的三个子状态情况下所得到的结果。
在图5.8中, "距离总和" 策略看上去比仅仅计算位置不符将牌数目的策略提供了一个更精确的估算。而且, 由于在这些状态中, 没有直接给出逆位数, 故都给予估值。第四种策略克服了仅计算将牌逆转数目策略的局限, 它将位置不符将牌数目总和与2倍将牌逆转数目相加。
这个例子说明, 设计一个好的启发策略具有相当的难度。设计算法的目标就是利用有限的信息作出一个明智的选择。上述策略都忽略了一些重要的信息, 需加以改进。好的启发策略的设计是一个经验问题, 判断和直觉是很重要的因素, 但是衡量的最终尺度则是具体应用时的效果。
由于所有的启发策略都可能出错, 每一种搜索算法都可能导向错误的路径, 但是在深度优先搜索中, 可用深度计数探查无效路径来解决这个问题。这个思想也可运用到启发式搜索中。如果两种状态具有相等的启发值, 通常先考察离根较近的那个状态。这个状态极有可能就处在到达目标状态的最佳路径上。可用一个深度计数来记录从起始状态到其子孙状态的距离。计数起始值为0, 每搜索一层计数值加1。这个值可加到启发值上, 层数越浅的状态越优先。
这样, 就得到了估计函数f, 它由两个因素所组成:
f(n)=g(n)+h(n)
其中g(n)是状态n到达起始状态的路径的实际长度, h(n)是状态n到目标状态的最佳路径的启发值。
在九宫问题中, 可令h(n)为位置不符的将牌数目。若将这个估计函数值运用到图5.6的子状态中, 它们的f值分别是6,4,6(见图5.9)。
各个状态的f(n)值这里f(n)=g(n)+h(n)
g(n)=从n到初始状态的实际长度 h(n)=位置不符的将牌数目
图5.9 九宫图的估计函数f值
在图5.10中, 使用上面所定义的f函数得到一个完整的搜索树。每种状态都以一个字母及它的估计函数值f来标记。每种状态头部的数字显示该状态从Open 表中取出时的顺序。有些状态没有数字标记, 这是因为当算法结束时, 这些状态仍在Open表中。
图5.10 启发式搜索产生的九宫图状态空间
产生图5.10的一系列过程如下:
1.open=[a4]; closed=[]
2.open=[c4,b6,d6]; closed=[a4]
3.open=[e5,f5,g6,b6,d6]; closed=[a4,c4]
4.open=[f5,h6,g6,b6,d6,i7]; closed=[a4,c4,e5]
5.open=[j5,h6,g6,b6,d6,k7,i7]; closed=[a4,c4,e5,f5]
6.open=[l5,h6,g6,b6,d6,k7,i7];
closed=[a4,c4,e5,f5,j5]
7.open=[m5,h6,g6,b6,d6,n7,k7,i7];
closed=[a4,c4,e5,f5,j5,l5]
8.成功,m=目标状态!
在第3步中, e和f都具有相等的启发值5。先检查状态e并产生它的子结点h和i。尽管h同f一样具有相等的位置不符的将牌数目, 但它在整个状态空间中所处层数要深。深度函数g(n)使算法在第4步中选择f作为考察对象。此时, 算法回退一层并继续搜索过程。此时的状态空间图以及相应的Open表、Closed表见图5.11。
事实上, 估计函数f中的g使搜索具有广度优先的性质, 这就使整个搜索免于被一个错误的估计值所误导。当算法沿着一条不断返回"好"估值但实际上是错误的路径搜索时, g值将不断增加并最终在f中占主导地位, 从而迫使搜索回退到一个具有较小f值的路径。这就保证算法不会永远沿着一条路径搜索下去。在5.3节中, 将讨论在何种条件下, 最好优先算法使用f一定能得到一条最短的路径。
当估计函数f运用到最好优先搜索算法上时, 它提供了启发式搜索的一般规则。总结如下:
1.根据产生式规则和一些其它的操作生成当前考察结点的子状态。
2.检查每个状态以前是否已经考察过(已在Open表或Closed表中), 以防止循环。
3.每个状态n都赋以f(n)值。其中f=g+h, h 值使搜索沿着具有较好启
发值的状态所处路径前进; g值防止搜索在一条无效的路径上无限
继续下去。
4.Open表中的状态按f值排序。这些状态在未被考察或未找到到目标
状态时一直保存, 通过保存这些状态,算法能随时从一无效路径上
返回。Open 表中可能保存有状态空间中不同层次的状态, 以充分
保证能随时转移搜索方向。
5.通过设计Open表和Closed表的存贮方式, 可提高算法的效率。例
如, 将Open表处理为一个堆栈能够缩短排序的时间。
最好优先搜索算法是启发式搜索的一个较常用算法。它支持多种估计函数的使用, 既可用于目标驱动搜索, 又可用于数据驱动搜索, 它是检验启发式搜索行为的一个基础。因为它的普遍性, 最好优先搜索可和多种启发策略一起使用。
应用启发策略的另一个有趣的方法是可信度的运用。它在专家系统中被用来衡量一条规则所产生的结果的可信程度。当一个专家考虑一个问题时, 他经常给出所得结论正确的可能程度。同样, 专家系统使用可信度方法来选择具有最高可信度的结果作为最终结论, 而具有较小可信度的状态不予考虑。在下节中将讲述这种方法。
数学模型按照不同的分类标准有许多种类： 1.按照模型的数学方法分，有几何模型，图论模型，微分方程模型。概率模型，最优控制模型，规划论模型，马氏链模型。 2.按模型的特征分，有静态模型和动态模型，确定性模型和随机模型，离散模型和连续性模型，线性模型和非线性模型。 3.按模型的应用领域分，有人口模型，交通模型，经济模型，生态模型，资源模型。环境模型。 4.按建模的目的分，有预测模型，优化模型，决策模型，控制模型等。 5.按对模型结构的了解程度分，有白箱模型，灰箱模型，黑箱模型。 数学建模的十大算法： 蒙特卡洛算法（该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟可以来检验自己模型的正确性，比较好用的算法。） 数据拟合、参数估计、插值等数据处理算法（比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用matlab作为工具。） 线性规划、整数规划、多元规划、二次规划等规划类问题（建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用lingo、lingdo软件实现）图论算法（这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备。） 动态规划、回溯搜索、分治算法、分支定界等计算机算法（这些算法是算法设计中比较常用的方法，很多场合可以用到竞赛中） 最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法（这些问题时用来解决一些较困难的最优化问题的算法，对于有些问题非常有帮助，但是算法的实现比较困难，需谨慎使用） 网格算法和穷举法（当重点讨论模型本身而情史算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具） 一些连续离散化方法（很多问题都是从实际来的，数据可以是连续的，而计算机只认得是离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的。 数值分析算法（如果在比赛中采用高级语言进行编程的话，那一些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用。） 图像处理算法（赛题中有一类问题与图形有关，即使与图形无关，论文中也应该要不乏图片的，这些图形如何展示以及如何处理就是需要解决的问题，通常使用matlab来处理问题。） 数学建模方法 统计：1.预测与预报2.评价与决策3.分类与判别4.关联与因果 优化：5.优化与控制 预测与预报 ①灰色预测模型（必须掌握） 满足两个条件可用： a数据样本点个数少，6-15个 b数据呈现指数或曲线的形式 ②微分方程预测（备用） 无法直接找到原始数据之间的关系，但可以找到原始数据变化速度之间的关系，通过公式
1. 什么是数学模型与数学建模 简单地说：数学模型就是对实际问题的一种数学表述。 具体一点说：数学模型是关于部分现实世界为某种目的的一个抽象的简化的数学结构。 更确切地说：数学模型就是对于一个特定的对象为了一个特定目标，根据特有的内在规律，做出一些必要的简化假设，运用适当的数学工具，得到的一个数学结构。数学结构可以是数学公式，算法、表格、图示等。 数学建模就是建立数学模型，建立数学模型的过程就是数学建模的过程（见数学建模过程流程图）。数学建模是一种数学的思考方法，是运用数学的语言和方法，通过抽象、简化建立能近似刻划并"解决"实际问题的一种强有力的数学手段。 2.美国大学生数学建模竞赛的由来： 1985年在美国出现了一种叫做MCM的一年一度大大学生数学模型（1987年全称为Mathematical Competition in Modeling,1988年改全称为Mathematical Contest in Modeling,其所写均为MCM）。这并不是偶然的。在1985年以前美国只有一种大学生数学竞赛（The william Lowell Putnam mathematial Competition,简称Putman(普特南）数学竞赛），这是由美国数学协会（MAA--即Mathematical Association of America的缩写）主持，于每年12月的第一个星期六分两试进行，每年一次。在国际上产生很大影响，现已成为国际性的大学生的一项著名赛事。该竞赛每年2月或3月进行。 我国自1989年首次参加这一竞赛，历届均取得优异成绩。经过数年参加美国赛表明，中国大学生在数学建模方面是有竞争力和创新联想能力的。为使这一赛事更广泛地展开，1990年先由中国工业与应用数学学会后与国家教委联合主办全国大学生数学建模竞赛（简称CMCM），该项赛事每年9月进行。
第四章动态规划 §1 引言 1.1 动态规划的发展及研究内容 动态规划（dynamic programming）是运筹学的一个分支，是求解决策过程（decision process）最优化的数学方法。20世纪50年代初R. E. Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优性原理（principle of optimality），把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法—动态规划。1957年出版了他的名著《Dynamic Programming》，这是该领域的第一本著作。 动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。 虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划（如线性规划、非线性规划），只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。 应指出，动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种特殊算法（如线性规划是一种算法）。因而，它不象线性规划那样有一个标准的数学表达式和明确定义的一组规则，而必须对具体问题进行具体分析处理。因此，在学习时，除了要对基本概念和方法正确理解外，应以丰富的想象力去建立模型，用创造性的技巧去求解。 例1 最短路线问题 下面是一个线路网，连线上的数字表示两点之间的距离（或费用）。试寻求一条由A 到G距离最短（或费用最省）的路线。 例2 生产计划问题 工厂生产某种产品，每单位（千件）的成本为1（千元），每次开工的固定成本为3（千元），工厂每季度的最大生产能力为6（千件）。经调查，市场对该产品的需求量第一、二、三、四季度分别为2，3，2，4（千件）。如果工厂在第一、二季度将全年的需求都生产出来，自然可以降低成本（少付固定成本费），但是对于第三、四季度才能上市的产品需付存储费，每季每千件的存储费为0.5（千元）。还规定年初和年末这种产品均无库存。试制定一个生产计划，即安排每个季度的产量，使一年的总费用（生产成本和存储费）最少。 1.2 决策过程的分类 根据过程的时间变量是离散的还是连续的，分为离散时间决策过程（discrete-time decision process）和连续时间决策过程（continuous-time decision process）；根据过程的演变是确定的还是随机的，分为确定性决策过程（deterministic decision process）和随
数学建模常用的十种解题方法 摘要 当需要从定量的角度分析和研究一个实际问题时，人们就要在深入调查研究、了解对象信息、作出简化假设、分析内在规律等工作的基础上，用数学的符号和语言，把它表述为数学式子，也就是数学模型，然后用通过计算得到的模型结果来解释实际问题，并接受实际的检验。这个建立数学模型的全过程就称为数学建模。数学建模的十种常用方法有蒙特卡罗算法；数据拟合、参数估计、插值等数据处理算法；解决线性规划、整数规划、多元规划、二次规划等规划类问题的数学规划算法；图论算法；动态规划、回溯搜索、分治算法、分支定界等计算机算法；最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法；网格算法和穷举法；一些连续离散化方法；数值分析算法；图象处理算法。 关键词：数学建模；蒙特卡罗算法；数据处理算法；数学规划算法；图论算法 一、蒙特卡罗算法 蒙特卡罗算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟可以来检验自己模型的正确性，是比赛时必用的方法。在工程、通讯、金融等技术问题中, 实验数据很难获取, 或实验数据的获取需耗费很多的人力、物力, 对此, 用计算机随机模拟就是最简单、经济、实用的方法; 此外, 对一些复杂的计算问题, 如非线性议程组求解、最优化、积分微分方程及一些偏微分方程的解⑿, 蒙特卡罗方法也是非常有效的。 一般情况下, 蒙特卜罗算法在二重积分中用均匀随机数计算积分比较简单, 但精度不太理想。通过方差分析, 论证了利用有利随机数, 可以使积分计算的精度达到最优。本文给出算例, 并用MA TA LA B 实现。 1蒙特卡罗计算重积分的最简算法-------均匀随机数法 二重积分的蒙特卡罗方法(均匀随机数) 实际计算中常常要遇到如()dxdy y x f D ??,的二重积分, 也常常发现许多时候被积函数的原函数很难求出, 或者原函数根本就不是初等函数, 对于这样的重积分, 可以设计一种蒙特卡罗的方法计算。 定理 1 )1( 设式()y x f ,区域 D 上的有界函数, 用均匀随机数计算()??D dxdy y x f ,的方法: (l) 取一个包含D 的矩形区域Ω,a ≦x ≦b, c ≦y ≦d , 其面积A =(b 一a) (d 一c) ; ()j i y x ,,i=1,…,n 在Ω上的均匀分布随机数列,不妨设()j i y x ,, j=1，…k 为落在D 中的k 个随机数, 则n 充分大时, 有
第八章 层次分析法 层次分析法（Analytic Hierarchy Process ，简称AHP ）是对一些较为复杂、较为模糊的问题作出决策的简易方法，它特别适用于那些难于完全定量分析的问题。它是美国运筹学家T. L. Saaty 教授于70年代初期提出的一种简便、灵活而又实用的多准则决策方法。 §1 层次分析法的基本原理与步骤 人们在进行社会的、经济的以及科学管理领域问题的系统分析中，面临的常常是一个由相互关联、相互制约的众多因素构成的复杂而往往缺少定量数据的系统。层次分析法为这类问题的决策和排序提供了一种新的、简洁而实用的建模方法。 运用层次分析法建模，大体上可按下面四个步骤进行： （i ）建立递阶层次结构模型； （ii ）构造出各层次中的所有判断矩阵； （iii ）层次单排序及一致性检验； （iv ）层次总排序及一致性检验。 下面分别说明这四个步骤的实现过程。 1.1 递阶层次结构的建立与特点 应用AHP 分析决策问题时，首先要把问题条理化、层次化，构造出一个有层次的结构模型。在这个模型下，复杂问题被分解为元素的组成部分。这些元素又按其属性及关系形成若干层次。上一层次的元素作为准则对下一层次有关元素起支配作用。这些层次可以分为三类： （i ）最高层：这一层次中只有一个元素，一般它是分析问题的预定目标或理想结果，因此也称为目标层。 （ii ）中间层：这一层次中包含了为实现目标所涉及的中间环节，它可以由若干个层次组成，包括所需考虑的准则、子准则，因此也称为准则层。 （iii ）最底层：这一层次包括了为实现目标可供选择的各种措施、决策方案等，因此也称为措施层或方案层。 递阶层次结构中的层次数与问题的复杂程度及需要分析的详尽程度有关，一般地层次数不受限制。每一层次中各元素所支配的元素一般不要超过9个。这是因为支配的元素过多会给两两比较判断带来困难。 下面结合一个实例来说明递阶层次结构的建立。 例1 假期旅游有1P 、2P 、3P 3个旅游胜地供你选择，试确定一个最佳地点。 在此问题中，你会根据诸如景色、费用、居住、饮食和旅途条件等一些准则去反复比较3个侯选地点。可以建立如下的层次结构模型。 目标层O 选择旅游地 准则层C 景色 费用 居住 饮食 旅途 措施层P 1P 2P 3P 1.2 构造判断矩阵 层次结构反映了因素之间的关系，但准则层中的各准则在目标衡量中所占的比重并不一定相同，在决策者的心目中，它们各占有一定的比例。 在确定影响某因素的诸因子在该因素中所占的比重时，遇到的主要困难是这些比重常常不易定量化。此外，当影响某因素的因子较多时，直接考虑各因子对该因素有多大程度的影响时，常常会因考虑不周全、顾此失彼而使决策者提出与他实际认为的
数学建模常用的十大算法==转 (2011-07-24 16:13:14) 转载▼ 1. 蒙特卡罗算法。该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟来检验自己模型的正确性，几乎是比赛时必用的方法。 2. 数据拟合、参数估计、插值等数据处理算法。比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用MA TLAB 作为工具。 3. 线性规划、整数规划、多元规划、二次规划等规划类算法。建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo 软件求解。 4. 图论算法。这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备。 5. 动态规划、回溯搜索、分治算法、分支定界等计算机算法。这些算法是算法设计中比较常用的方法，竞赛中很多场合会用到。 6. 最优化理论的三大非经典算法：模拟退火算法、神经网络算法、遗传算法。这些问题是用来解决一些较困难的最优化问题的，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用。 7. 网格算法和穷举法。两者都是暴力搜索最优点的算法，在很多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具。 8. 一些连续数据离散化方法。很多问题都是实际来的，数据可以是连续的，而计算机只能处理离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的。 9. 数值分析算法。如果在比赛中采用高级语言进行编程的话，那些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用。 10. 图象处理算法。赛题中有一类问题与图形有关，即使问题与图形无关，论文中也会需要图片来说明问题，这些图形如何展示以及如何处理就是需要解决的问题，通常使用MA TLAB 进行处理。 以下将结合历年的竞赛题，对这十类算法进行详细地说明。 以下将结合历年的竞赛题，对这十类算法进行详细地说明。 2 十类算法的详细说明 2.1 蒙特卡罗算法 大多数建模赛题中都离不开计算机仿真，随机性模拟是非常常见的算法之一。 举个例子就是97 年的A 题，每个零件都有自己的标定值，也都有自己的容差等级，而求解最优的组合方案将要面对着的是一个极其复杂的公式和108 种容差选取方案，根本不可能去求解析解，那如何去找到最优的方案呢？随机性模拟搜索最优方案就是其中的一种方法，在每个零件可行的区间中按照正态分布随机的选取一个标定值和选取一个容差值作为一种方案，然后通过蒙特卡罗算法仿真出大量的方案，从中选取一个最佳的。另一个例子就是去年的彩票第二问，要求设计一种更好的方案，首先方案的优劣取决于很多复杂的因素，同样不可能刻画出一个模型进行求解，只能靠随机仿真模拟。 2.2 数据拟合、参数估计、插值等算法 数据拟合在很多赛题中有应用，与图形处理有关的问题很多与拟合有关系，一个例子就是98 年美国赛A 题，生物组织切片的三维插值处理，94 年A 题逢山开路，山体海拔高度的插值计算，还有吵的沸沸扬扬可能会考的“非典”问题也要用到数据拟合算法，观察数据的
数学建模常用方法 建模常用算法,仅供参考： 1、蒙特卡罗算法（该算法又称随机性模拟算法,是通过计算机仿真来解决问题的算法,同时可以通过模拟可以来检验自己模型的正确性,是比赛时必 用的方法） 2、数据拟合、参数估计、插值等数据处理算法（比赛中通常会遇到大量的数据需要处理,而处理数据的关键就在于这些算法,通常使用M a t l a b作为工具） 3、线性规划、整数规划、多元规划、二次规划等规划类问题（建模竞赛大多数问题属于最优化问题,很多时候这些问题可以用数学规划算法来描述,通 常使用L i n d o、L i n g o软件实现） 4、图论算法（这类算法可以分为很多种,包括最短路、网络流、二分图等算法,涉及到图论的问题可以用这些方法解决,需要认真准备） 5、动态规划、回溯搜索、分治算法、分支定界等计算机算法（这些算法是算法设计中比较常用的方法,很多场合可以用到竞赛中） 6、最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法（这些问题是用来解决一些较困难的最优化问题的算法,对于有些问题非常有帮助,但是算法的实现比较困难,需慎重使用） 7、网格算法和穷举法（网格算法和穷举法都是暴力搜索最优点的算法,在很多竞赛题中有应用,当重点讨论模型本身而轻视算法的时候,可以使用这种 暴力方案,最好使用一些高级语言作为编程工具） 8、一些连续离散化方法（很多问题都是实际来的,数据可以是连续的,而计 算机只认的是离散的数据,因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的） 9、数值分析算法（如果在比赛中采用高级语言进行编程的话,那一些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用） 10、图象处理算法（赛题中有一类问题与图形有关,即使与图形无关,论文 中也应该要不乏图片的,这些图形如何展示以及如何处理就是需要解决的问题,通常使用M a t l a b进行处理） 一、在数学建模中常用的方法： 1.类比法 2.二分法 3.量纲分析法 4.差分法 5.变分法 6.图论法 7.层次分析法 8.数据拟合法 9.回归分析法 10.数学规划（线性规划、非线性规划、整数规划、动态规划、目标规划） 11.机理分析 12.排队方法
数学建模10种常用算法 1、蒙特卡罗算法（该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟可以来检验自己模型的正确性，是比赛时必用的方法） 2、数据拟合、参数估计、插值等数据处理算法（比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用Matlab作为工具） 3、线性规划、整数规划、多元规划、二次规划等规划类问 题（建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo软件实现） 4、图论算法（这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备） 5、动态规划、回溯搜索、分治算法、分支定界等计算机算法（这些算法是算法设计中比较常用的方法，很多场合可以用到竞赛中） 6、最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法（这些问题是用来解决一些较困难的最优化问题的算法，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用） 7、网格算法和穷举法（网格算法和穷举法都是暴力搜索最优点的算法，在很多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具） 8、一些连续离散化方法（很多问题都是实际来的，数据可以是连续的，而计算机只认的是离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的） 9、数值分析算法（如果在比赛中采用高级语言进行
编程的话，那一些数值分析中常用的算法比如方程组 求解、矩阵运算、函数积分等算法就需要额外编写库 函数进行调用） 10、图象处理算法（赛题中有一类问题与图形有关， 即使与图形无关，论文中也应该要不乏图片的，这些 图形如何展示以及如何处理就是需要解决的问题，通 常使用Matlab进行处 参数估计 C.F. 20世纪60年代,随着电子计算机的 。参数估计有多种方法，有最小二乘法、极大似然法、极大验后法、最小风险法和极小化极大熵法等。在一定条件下，后面三个方法都与极大似然法相同。最基本的方法是最小二乘法和极大似然法. 基本介绍 参数估计（parameter 尽可能接近的参数 误差 平方和 θ,使已知数据Y 最大,这里P(Y│θ)是数据Y P(Y│θ)。在实践中这是困难的，一般可假设P（Y│θ
数学建模有下面十种常用算法, 可供参考： 1.蒙特卡罗算法（该算法又称随机性模拟算法，是通过计算机仿真来解决问 题的算法，同时可以通过模拟可以来检验自己模型的正确性，是比赛时必用的方法） 2.数据拟合、参数估计、插值等数据处理算法（比赛中通常会遇到大量的数 据需要处理，而处理数据的关键就在于这些算法，通常使用Matlab作为工具） 3.线性规划、整数规划、多元规划、二次规划等规划类问题（建模竞赛大多 数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo软件实现） 4.图论算法（这类算法可以分为很多种，包括最短路、网络流、二分图等算 法，涉及到图论的问题可以用这些方法解决，需要认真准备） 5.动态规划、回溯搜索、分治算法、分支定界等计算机算法（这些算法是算 法设计中比较常用的方法，很多场合可以用到竞赛中） 6.最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法（这些 问题是用来解决一些较困难的最优化问题的算法，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用） 7.网格算法和穷举法（网格算法和穷举法都是暴力搜索最优点的算法，在很 多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具） 8.一些连续离散化方法（很多问题都是实际来的，数据可以是连续的，而计 算机只认的是离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的） 9.数值分析算法（如果在比赛中采用高级语言进行编程的话，那一些数值分 析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用） 10.图象处理算法（赛题中有一类问题与图形有关，即使与图形无关，论文中 也应该要不乏图片的，这些图形如何展示以及如何处理就是需要解决的问题，通常使用Matlab 进行处理）
第六章排队论模型 排队论起源于1909年丹麦电话工程师A. K．爱尔朗的工作，他对电话通话拥挤问题进行了研究。1917年，爱尔朗发表了他的著名的文章—“自动电话交换中的概率理论的几个问题的解决”。排队论已广泛应用于解决军事、运输、维修、生产、服务、库存、医疗卫生、教育、水利灌溉之类的排队系统的问题，显示了强大的生命力。 排队是在日常生活中经常遇到的现象，如顾客到商店购买物品、病人到医院看病常常要排队。此时要求服务的数量超过服务机构（服务台、服务员等）的容量。也就是说，到达的顾客不能立即得到服务，因而出现了排队现象。这种现象不仅在个人日常生活中出现，电话局的占线问题，车站、码头等交通枢纽的车船堵塞和疏导，故障机器的停机待修，水库的存贮调节等都是有形或无形的排队现象。由于顾客到达和服务时间的随机性。可以说排队现象几乎是不可避免的。 排队论（Queuing Theory）也称随机服务系统理论，就是为解决上述问题而发展的一门学科。它研究的内容有下列三部分： （i）性态问题，即研究各种排队系统的概率规律性，主要是研究队长分布、等待时间分布和忙期分布等，包括了瞬态和稳态两种情形。 （ii）最优化问题，又分静态最优和动态最优，前者指最优设计。后者指现有排队系统的最优运营。 （iii）排队系统的统计推断，即判断一个给定的排队系统符合于那种模型，以便根据排队理论进行分析研究。 这里将介绍排队论的一些基本知识，分析几个常见的排队模型。 §1 基本概念 1.1 排队过程的一般表示 下图是排队论的一般模型。 凡要求服务的对象统称为顾客，为顾客服务的人或物称为服务员，由顾客和服务员组成服务系统。对于一个服务系统来说，如果服务机构过小，以致不能满足要求服务的众多顾客的需要，那么就会产生拥挤现象而使服务质量降低。因此，顾客总希望服务机构越大越好，但是，如果服务机构过大，人力和物力方面的开支也就相应增加，从而会造成浪费，因此研究排队模型的目的就是要在顾客需要和服务机构的规模之间进行权衡决策，使其达到合理的平衡。 1.2 排队系统的组成和特征 一般的排队过程都由输入过程、排队规则、服务过程三部分组成，现分述如下： 1.2.1 输入过程 输入过程是指顾客到来时间的规律性，可能有下列不同情况： （i）顾客的组成可能是有限的，也可能是无限的。 （ii）顾客到达的方式可能是一个—个的，也可能是成批的。 （iii）顾客到达可以是相互独立的，即以前的到达情况对以后的到达没有影响；否则是相关的。 （iv）输入过程可以是平稳的，即相继到达的间隔时间分布及其数学期望、方差等数字特征都与时间无关，否则是非平稳的。
数学建模中常见的十 大模型
精品文档 数学建模常用的十大算法==转 (2011-07-24 16:13:14) 转载▼ 1. 蒙特卡罗算法。该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟来检验自己模型的正确性，几乎是比赛时必用的方法。 2. 数据拟合、参数估计、插值等数据处理算法。比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用MA TLAB 作为工具。 3. 线性规划、整数规划、多元规划、二次规划等规划类算法。建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo 软件求解。 4. 图论算法。这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备。 5. 动态规划、回溯搜索、分治算法、分支定界等计算机算法。这些算法是算法设计中比较常用的方法，竞赛中很多场合会用到。 6. 最优化理论的三大非经典算法：模拟退火算法、神经网络算法、遗传算法。这些问题是用来解决一些较困难的最优化问题的，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用。 7. 网格算法和穷举法。两者都是暴力搜索最优点的算法，在很多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具。 8. 一些连续数据离散化方法。很多问题都是实际来的，数据可以是连续的，而计算机只能处理离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的。 9. 数值分析算法。如果在比赛中采用高级语言进行编程的话，那些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用。 10. 图象处理算法。赛题中有一类问题与图形有关，即使问题与图形无关，论文中也会需要图片来说明问题，这些图形如何展示以及如何处理就是需要解决的问题，通常使用MATLAB 进行处理。 以下将结合历年的竞赛题，对这十类算法进行详细地说明。 以下将结合历年的竞赛题，对这十类算法进行详细地说明。 2 十类算法的详细说明 2.1 蒙特卡罗算法 大多数建模赛题中都离不开计算机仿真，随机性模拟是非常常见的算法之一。 举个例子就是97 年的A 题，每个零件都有自己的标定值，也都有自己的容差等级，而求解最优的组合方案将要面对着的是一个极其复杂的公式和108 种容差选取方案，根本不可能去求解析解，那如何去找到最优的方案呢？随机性模拟搜索最优方案就是其中的一种方法，在每个零件可行的区间中按照正态分布随机的选取一个标定值和选取一个容差值作为一种方案，然后通过蒙特卡罗算法仿真出大量的方案，从中选取一个最佳的。另一个例子就是去年的彩票第二问，要求设计一种更好的方案，首先方案的优劣取决于很多复杂的因素，同样不可能刻画出一个模型进行求解，只能靠随机仿真模拟。 2.2 数据拟合、参数估计、插值等算法 数据拟合在很多赛题中有应用，与图形处理有关的问题很多与拟合有关系，一个例子就是98 年美国赛A 题，生物组织切片的三维插值处理，94 年A 题逢山开路，山体海拔高度的 收集于网络，如有侵权请联系管理员删除
数学建模方法详解--三种最常用算法 一、层次分析法 层次分析法[1] (analytic hierarchy process，AHP)是美国著名的运筹学家T．L．Saaty教授于20世纪70年代初首先提出的一种定性与定量分析相结合的多准则决策方法[2，3，4]．该方法是社会、经济系统决策的有效工具，目前在工程计划、资源分配、方案 排序、政策制定、冲突问题、性能评价等方面都有广泛的应用． (一) 层次分析法的基本原理 层次分析法的核心问题是排序，包括递阶层次结构原理、测度原理和排序原理[5]．下面分别予以介绍． 1．递阶层次结构原理 一个复杂的结构问题可以分解为它的组成部分或因素，即目标、准则、方案等．每一个因素称为元素．按照属性的不同把这 些元素分组形成互不相交的层次，上一层的元素对相邻的下一层的全部或部分元素起支配作用，形成按层次自上而下的逐层支配 关系．具有这种性质的层次称为递阶层次． 2．测度原理 决策就是要从一组已知的方案中选择理想方案，而理想方案一般是在一定的准则下通过使效用函数极大化而产生的．然而对 于社会、经济系统的决策模型来说，常常难以定量测度．因此，层次分析法的核心是决策模型中各因素的测度化．3．排序原理
层次分析法的排序问题，实质上是一组元素两两比较其重要性，计算元素相对重要性的测度问题．(二) 层次分析法的基本步骤 层次分析法的基本思路与人对一个复杂的决策问题的思维、判断过程大体上是一致的[1] ． 1．成对比较矩阵和权向量 为了能够尽可能地减少性质不同的诸因素相互比较的困难，提高结果的准确度．T ．L ．Saaty 等人的作法，一是不把所有因 素放在一起比较，而是两两相互对比，二是对比时采用相对尺度． 假设要比较某一层n 个因素n C C ,,1对上层一个因素O 的影响，每次取两个因素i C 和j C ，用ij a 表示i C 和j C 对O 的影响之比， 全部比较 结 果 可 用 成 对 比 较 阵 1 ,0,ij ij ji n n ij A a a a a 表示，A 称为正互反矩阵．一般地，如果一个正互反阵 A 满足： , ij jk ik a a a ,,1,2,,i j k n （1） 则A 称为一致性矩阵，简称一致阵．容易证明n 阶一致阵A 有下列性质： ①A 的秩为1，A 的唯一非零特征根为n ；②A 的任一列向量都是对应于特征根 n 的特征向量． 如果得到的成对比较阵是一致阵，自然应取对应于特征根n 的、归一化的特征向量（即分量之和为1）表示诸因素n C C ,, 1对 上层因素O 的权重，这个向量称为权向量．如果成对比较阵A 不是一致阵，但在不一致的容许范围内，用对应于A 最大特征根(记
数学建模方法详解--三十四种常用算法 目录 一、主成分分析法 (2) 二、因子分析法 (5) 三、聚类分析 (9) 四、最小二乘法与多项式拟合 (16) 五、回归分析（略） (22) 六、概率分布方法（略） (22) 七、插值与拟合（略） (22) 八、方差分析法 (23) 九、逼近理想点排序法 (28) 十、动态加权法 (29) 十一、灰色关联分析法 (31) 十二、灰色预测法 (33) 十三、模糊综合评价 (35) 十四、隶属函数的刻画（略） (37) 十五、时间序列分析法 (38) 十六、蒙特卡罗(MC)仿真模型 (42) 十七、BP神经网络方法 (44) 十八、数据包络分析法（DEA） (51) 十九、多因素方差分析法（）基于SPSS） (54) 二十、拉格朗日插值 (70) 二十一、回归分析（略） (75) 二十二、概率分布方法（略） (75) 二十三、插值与拟合（略） (75) 二十四、隶属函数的刻画（参考《数学建模及其方法应用》） (75) 二十五、0-1整数规划模型（参看书籍） (75) 二十六、Board评价法（略） (75) 二十七、纳什均衡（参看书籍） (75) 二十八、微分方程方法与差分方程方法（参看书籍） (75) 二十九、莱斯利离散人口模型（参看数据） (75) 三十、一次指数平滑预测法（主要是软件的使用） (75) 三十一、二次曲线回归方程（主要是软件的使用） (75) 三十二、成本-效用分析（略） (75) 三十三、逐步回归法（主要是软件的使用） (75) 三十四、双因子方差分析（略） (75)
一、主成分分析法 一）、主成分分析法介绍： 主成分分析（principal components analysis，PCA）又称：主分量分析，主成分回归分析法。旨在利用降维的思想，把多指标转化为少数几个综合指标。它是一个线性变换。这个变换把数据变换到一个新的坐标系统中，使得任何数据投影的第一大方差在第一个坐标(称为第一主成分)上，第二大方差在第二个坐标(第二主成分)上，依次类推。主成分分析经常用减少数据集的维数，同时保持数据集的对方差贡献最大的特征。这是通过保留低阶主成分，忽略高阶主成分做到的。这样低阶成分往往能够保留住数据的最重要方面。但是，这也不是一定的，要视具体应用而定。 二）、主成分分析法的基本思想： 在实证问题研究中，为了全面、系统地分析问题，我们必须考虑众多影响因素。这些涉及的因素一般称为指标，在多元统计分析中也称为变量。因为每个变量都在不同程度上反映了所研究问题的某些信息，并且指标之间彼此有一定的相关性，因而所得的统计数据反映的信息在一定程度上有重叠。在用统计方法研究多变量问题时，变量太多会增加计算量和增加分析问题的复杂性，人们希望在进行定量分析的过程中，涉及的变量较少，得到的信息量较多。主成分分析正是适应这一要求产生的，是解决这类题的理想工具。 同样，在科普效果评估的过程中也存在着这样的问题。科普效果是很难具体量化的。在实际评估工作中，我们常常会选用几个有代表性的综合指标，采用打分的方法来进行评估，故综合指标的选取是个重点和难点。如上所述，主成分分析法正是解决这一问题的理想工具。因为评估所涉及的众多变量之间既然有一定的相关性，就必然存在着起支配作用的因素。根据这一点，通过对原始变量相关矩阵内部结构的关系研究，找出影响科普效果某一要素的几个综合指标，使综合指标为原来变量的线性拟合。这样，综合指标不仅保留了原始变量的主要信息，且彼此间不相关，又比原始变量具有某些更优越的性质，就使我们在研究复杂的科普效果评估问题时，容易抓住主要矛盾。上述想法可进一步概述为：设某科普效果评估要素涉及个指标，这指标构成的维随机向量为。对作正交变换，令，其中为正交阵，的各分量是不相关的，使得的各分量在某个评估要素中的作用容易解释，这就使得我们有可能从主分量中选择主要成分，削除对这一要素影响微弱的部分，通过对主分量的重点分析，达到对原始变量进行分析的目的。的各分量是原始变量线性组合，不同的分量表示原始变量之间不同的影响关系。由于这些基本关系很可能与特定的作用过程相联系，主成分分析使我们能从错综复杂的科普评估要素的众多指标中，找出一些主要成分，以便有效地利用大量统计数据，进行科普效果评估分析，使我们在研究科普效果评估问题中，可能得到深层次的一些启发，把科普效果评估研究引向深入。 例如，在对科普产品开发和利用这一要素的评估中，涉及科普创作人数百万人、科普作品发行量百万人、科普产业化（科普示范基地数百万人）等多项指标。经过主成分分析计算，最后确定个或个主成分作为综合评价科普产品利用和开发的综合指标，变量数减少，并达到一定的可信度，就容易进行科普效果的评估。 三）、主成分分析法的数学模型： 其中：
数学建模中常见的十大 模型 Document serial number【KKGB-LBS98YT-BS8CB-BSUT-BST108】
数学建模常用的十大算法==转 (2011-07-24 16:13:14) 1. 蒙特卡罗算法。该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟来检验自己模型的正确性，几乎是比赛时必用的方法。 2. 数据拟合、参数估计、插值等数据处理算法。比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用MATLAB 作为工具。 3. 线性规划、整数规划、多元规划、二次规划等规划类算法。建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo 软件求解。 4. 图论算法。这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备。 5. 动态规划、回溯搜索、分治算法、分支定界等计算机算法。这些算法是算法设计中比较常用的方法，竞赛中很多场合会用到。 6. 最优化理论的三大非经典算法：模拟退火算法、神经网络算法、遗传算法。这些问题是用来解决一些较困难的最优化问题的，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用。 7. 网格算法和穷举法。两者都是暴力搜索最优点的算法，在很多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具。
8. 一些连续数据离散化方法。很多问题都是实际来的，数据可以是连续的，而计算机只能处理离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的。 9. 数值分析算法。如果在比赛中采用高级语言进行编程的话，那些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用。 10. 图象处理算法。赛题中有一类问题与图形有关，即使问题与图形无关，论文中也会需要图片来说明问题，这些图形如何展示以及如何处理就是需要解决的问题，通常使用MATLAB 进行处理。 以下将结合历年的竞赛题，对这十类算法进行详细地说明。 以下将结合历年的竞赛题，对这十类算法进行详细地说明。 2 十类算法的详细说明 蒙特卡罗算法 大多数建模赛题中都离不开计算机仿真，随机性模拟是非常常见的算法之一。 举个例子就是97 年的A 题，每个零件都有自己的标定值，也都有自己的容差等级，而求解最优的组合方案将要面对着的是一个极其复杂的公式和108 种容差选取方案，根本不可能去求解析解，那如何去找到最优的方案呢随机性模拟搜索最优方案就是其中的一种方法，在每个零件可行的区间中按照正态分布随机的选取一个标定值和选取一个容差值作为一种方案，然后通过蒙特卡罗算法仿真出大量的方案，从中选取一个最佳的。另一个例子就是去年的彩票第二问，要求设计一种更好的方案，首先方案的优劣取决于很多复杂的因素，同样不可能刻画出一个模型进行求解，只能靠随机仿真模拟。
第一讲国赛历年赛题总览 一、历年国赛赛题（时间） 1992年，国赛第一年，30+高校 （A）作物生长的施肥效果问题（北理工：叶其孝） 统计、非线性回归的方法 （B）化学试验室的实验数据分解问题（复旦：谭永基） 无明确方法，解应用题 1993年，国赛第二年 （A）通讯中非线性交互的频率设计问题（北大：谢衷洁）非线性回归 （B）足球甲级联赛排名问题（清华：蔡大用） 评价与决策。如：评价老师，评价学校，评价食堂，评价篮球教练 1994年，国赛第三年 （A）山区修建公路的设计造价问题（西电大：何大可） 价格问题，优化问题 （B）锁具的制造、销售和装箱问题（复旦：谭永基等） 优化问题，同时带一部分统计问题
1995年，国赛第四年 （A）飞机的安全飞行调度问题（复旦：谭永基等） 优化问题 （B）天车与冶炼炉的作业调度问题（浙大：刘祥官等）优化问题 1996年，国赛第五年 （A）最优捕鱼策略问题（北师大：刘来福） 微分方程的问题 （B）节水洗衣机的程序设计问题（重大：付鹂） 偏微分方程，也可以用优化 1997年，国赛第六年 （A）零件参数优化设计问题（清华：姜启源） 优化问题 （B）金刚石截断切割问题（复旦：谭永基等） 优化问题 1998年，国赛第七年 （A）投资的收益和风险问题（浙大：陈述平） 多目标优化问题 （B）灾情的巡视路线问题（上海海运学院：丁松康）
网络优化问题、图论 1999年，国赛第八年（开始出现专科组） （A）自动化车床控制管理问题（北大：孙山泽） 优化问题 （B）地质勘探钻井布局问题（郑州大学：林诒勋）优化问题 （C）煤矸石堆积问题（太原理工大学：贾晓峰） 排列的问题 2000年，国赛第九年 （A）DNA序列的分类问题（北京工业大学：孟大志）分类问题 （B）钢管的订购和运输问题（武汉大学：费甫生）优化问题 （C）飞越北极问题（复旦大学：谭永基） 椭球面计算问题，几何问题 （D）空洞探测问题（东北电力学院：关信） 偏统计问题 2001年，国赛第十年 （A）三维血管重建问题（浙江大学：汪国昭）
数学建模竞赛中应当掌握的十类算法 排名如下： 1、蒙特卡罗算法（该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟可以来检验自己模型的正确性，是比赛时必用的方法） 2、数据拟合、参数估计、插值等数据处理算法（比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用Matlab作为工具） 3、线性规划、整数规划、多元规划、二次规划等规划类问题（建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo软件实现） 4、图论算法（这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备） 5、动态规划、回溯搜索、分治算法、分支定界等计算机算法（这些算法是算法设计中比较常用的方法，很多场合可以用到竞赛中） 6、最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法（这些问题是用来解决一些较困难的最优化问题的算法，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用） 7、网格算法和穷举法（网格算法和穷举法都是暴力搜索最优点的算法，在很多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具） 8、一些连续离散化方法（很多问题都是实际来的，数据可以是连续的，而计算机只认的是离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的） 9、数值分析算法（如果在比赛中采用高级语言进行编程的话，那一些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用） 10、图象处理算法（赛题中有一类问题与图形有关，即使与图形无关，论文中也应该要不乏图片的，这些图形如何展示以及如何处理就是需要解决的问题，通常使用Matlab进行处理） 8.1 遗传算法的概念 是建立在自然选择和自然遗传学机理基础上的迭代自适应概率性搜索算法，在1975年由Holland教授提出。 生物的进化是一个奇妙的优化过程，它通过选择淘汰，突然变异，基因遗传等规律产生适应环境变化的优良物种。遗传算法是根据生物进化思想而启发得出的一种全局优化算法。 遗传算法的概念最早是由Bagley J.D在1967年提出的；而开始遗传算法的理论和方法的系统性研究的是1975年，这一开创性工作是由Michigan大学的 J.H.Holland所实行。当时，其主要目的是说明自然和人工系统的自适应过程。