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

fghui · 发表于 2004-8-15 23:53:30

<

>楼主能否附上最短路进算法中的Dijkstra算法（在matlab中），我水平有限，试不出来。<

>多谢了

luoxin · 发表于 2004-8-18 22:40:48

我觉得思想最重要

conscious · 发表于 2004-8-19 07:45:41

回溯算法
寻找问题的解的一种可靠的方法是首先列出所有候选解，然后依次检查每一个，在检查完
所有或部分候选解后，即可找到所需要的解。理论上，当候选解数量有限并且通过检查所
有或部分候选解能够得到所需解时，上述方法是可行的。不过，在实际应用中，很少使用
这种方法，因为候选解的数量通常都非常大（比如指数级，甚至是大数阶乘），即便采用
最快的计算机也只能解决规模很小的问题。对候选解进行系统检查的方法有多种，其中回
溯和分枝定界法是比较常用的两种方法。按照这两种方法对候选解进行系统检查通常会使
问题的求解时间大大减少（无论对于最坏情形还是对于一般情形）。事实上，这些方法可
以使我们避免对很大的候选解集合进行检查，同时能够保证算法运行结束时可以找到所需
要的解。因此，这些方法通常能够用来求解规模很大的问题。

本章集中阐述回溯方法，这种方法被用来设计货箱装船、背包、最大完备子图、旅行商和
电路板排列问题的求解算法。

  1 算法思想


回溯（b a c k t r a c k i n g）是一种系统地搜索问题解答的方法。为了实现回溯，首
先需要为问题定义一个解空间（ solution space），这个空间必须至少包含问题的一个解
（可能是最优的）。在迷宫老鼠问题中，我们可以定义一个包含从入口到出口的所有路径
的解空间；在具有n 个对象的0 / 1背包问题中（见1 . 4节和2 . 2节），解空间的一个合
理选择是2n 个长度为n 的0 / 1向量的集合，这个集合表示了将0或1分配给x的所有可能方
法。当n= 3时，解空间为{ ( 0 , 0 , 0 )，( 0 , 1 , 0 )，( 0 , 0 , 1 )，( 1 , 0 ,
0 )，( 0 , 1 , 1 )，( 1 , 0 , 1 )，( 1 , 1 , 0 )，( 1 , 1 , 1 ) }。

下一步是组织解空间以便它能被容易地搜索。典型的组织方法是图或树。图1 6 - 1用图的
形式给出了一个3×3迷宫的解空间。从( 1 , 1 )点到( 3 , 3 )点的每一条路径都定义了
3×3迷宫解空间中的一个元素，但由于障碍的设置，有些路径是不可行的。

图1 6 - 2用树形结构给出了含三个对象的0 / 1背包问题的解空间。从i 层节点到i+ 1层
节点的一条边上的数字给出了向量x 中第i个分量的值xi ，从根节点到叶节点的每一条路
径定义了解空间中的一个元素。从根节点A到叶节点H的路径定义了解x= [ 1 , 1 , 1 ]。
根据w 和c 的值，从根到叶的路径中的一些解或全部解可能是不可行的。

一旦定义了解空间的组织方法，这个空间即可按深度优先的方法从开始节点进行搜索。在
迷宫老鼠问题中，开始节点为入口节点( 1 , 1 )；在0 / 1背包问题中，开始节点为根节
点A。开始节点既是一个活节点又是一个E-节点（expansion node）。从E-节点可移动到一
个新节点。如果能从当前的E-节点移动到一个新节点，那么这个新节点将变成一个活节点
和新的E-节点，旧的E-节点仍是一个活节点。如果不能移到一个新节点，当前的E-节点就
“死”了（即不再是一个活节点），那么便只能返回到最近被考察的活节点（回溯），这
个活节点变成了新的E-节点。当我们已经找到了答案或者回溯尽了所有的活节点时，搜索
过程结束。

例4-1 [迷宫老鼠] 考察图16-3a 的矩阵中给出的3×3的“迷宫老鼠”问题。我们将利用图
1 6 -1给出的解空间图来搜索迷宫。

从迷宫的入口到出口的每一条路径都与图1 6 - 1中从( 1 , 1 )到( 3 , 3 )的一条路径相
对应。然而，图1 6 - 1中有些从( 1 , 1 )到( 3 , 3 )的路径却不是迷宫中从入口到出口
的路径。搜索从点( 1 , 1 )开始，该点是目前唯一的活节点，它也是一个E-节点。为避免
再次走过这个位置，置m a z e( 1 , 1 )为1。从这个位置，能移动到( 1 , 2 )或( 2 ,
1 )两个位置。对于本例，两种移动都是可行的，因为在每一个位置都有一个值0。假定选
择移动到( 1 , 2 )，m a z e( 1 , 2 )被置为1以避免再次经过该点。迷宫当前状态如图
16-3b 所示。这时有两个活节点(1,1) (1,2)。( 1 , 2 )成为E-节点。

在图1 6 - 1中从当前E-节点开始有3个可能的移动，其中两个是不可行的，因为迷宫在这
些位置上的值为1。唯一可行的移动是( 1 , 3 )。移动到这个位置，并置m a z e( 1 , 3
)为1以避免再次经过该点，此时迷宫状态为1 6 - 3 c。图1 6 - 1中，从( 1 , 3 )出发
有两个可能的移动，但没有一个是可行的。所以E-节点( 1 , 3 )死亡，回溯到最近被检查
的活节点( 1 , 2 )。在这个位置也没有可行的移动，故这个节点也死亡了。唯一留下的活
节点是( 1 , 1 )。这个节点再次变为E-节点，它可移动到( 2 , 1 )。现在活节点为( 1
, 1 )，( 2 , 1 )。继续下去，能到达点( 3 , 3 )。此时，活节点表为( 1 , 1 )，( 2
, 1 )，( 3 , 1 )，( 3 , 2 )，( 3 , 3 )，这即是到达出口的路径。

程序5 - 1 3是一个在迷宫中寻找路径的回溯算法。

conscious · 发表于 2004-8-19 07:50:53

<

>贪心算法 <

>一、算法思想 <

>贪心法的基本思路： ——从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当 达到某算法中的某一步不能再继续前进时，算法停止。 该算法存在问题： 1. 不能保证求得的最后解是最佳的； 2. 不能用来求最大或最小解问题； 3. 只能求满足某些约束条件的可行解的范围。 实现该算法的过程： 从问题的某一初始解出发； while 能朝给定总目标前进一步 do 　　求出可行解的一个解元素； 由所有解元素组合成问题的一个可行解； 二、例题分析 1、[背包问题]有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。 要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。 物品 A B C D E F G 重量 35 30 60 50 40 10 25 价值 10 40 30 50 35 40 30 分析： 目标函数： ∑pi最大 约束条件是装入的物品总重量不超过背包容量：∑wi<=M( M=150) （1）根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？ （2）每次挑选所占空间最小的物品装入是否能得到最优解？ （3）每次选取单位容量价值最大的物品，成为解本题的策略。 源程序 2、[单源最短路径]一个有向图G，它的每条边都有一个非负的权值c[i,j]，“路径长度” 就是所经过的所有边的权值之和。对于源点需要找出从源点出发到达其他所有结点的最短 路径。 　　E.Dijkstra发明的贪婪算法可以解决最短路径问题。算法的主要思想是：分步求出最 短路径，每一步产生一个到达新目的顶点的最短路径。下一步所能达到的目的顶点通过如 下贪婪准则选取：在未产生最短路径的顶点中，选择路径最短的目的顶点。 　　设置顶点集合S并不断作贪心选择来扩充这个集合。当且仅当顶点到该顶点的最短路径 已知时该顶点属于集合S。初始时S中只含源。 　　设u为G中一顶点，我们把从源点到u且中间仅经过集合S中的顶点的路称为从源到u特殊 路径，并把这个特殊路径记录下来（例如程序中的dist[i，j]）。 　　每次从V-S选出具有最短特殊路径长度的顶点u，将u添加到S中，同时对特殊路径长度 进行必要的修改。一旦V=S，就得到从源到其他所有顶点的最短路径，也就得到问题的解 。 Dijkstra.pas 3、[机器调度]现有N项任务和无限多台机器。任务可以在机器上处理。每件任务开始时间 和完成时间有下表： 任务 a b c d e f g 开始(si) 0 3 4 9 7 1 6 完成(fi) 2 7 7 11 10 5 8 　　在可行分配中每台机器在任何时刻最多处理一个任务。最优分配是指使用的机器最少 的可行分配方案。请就本题给出的条件，求出最优分配。 三、练习题： 已知5个城市之间有班机传递邮件，目的是为了寻找一条耗油量较少的飞行路线。5个城市 的联系网络如图所示。图中编号的结点表示城市，两个城市之间的连线上的值表示班机沿 该航线已行的耗油量，并假定从城市i到j和城市j到i之间的耗油量是相同的。 分析： 1. 运用贪心思想： 在每一步前进的选择上，选取相对当前城市耗油量最小的航线； 2. 图解：若从1出发，有图： 总耗油量=14 1-2-5-3-4-1 但若路线改为：1-5-3-4-2-1，则总耗油量=13 所以，这样的贪心法并不能得出最佳解。 3. 改善方案： 从所有城市出发的信心过程，求最优的。 编程： 1. 数据结构： 城市联系网络图的描述(图的邻接矩阵的描述)： const c=array[1..5,1..5] of integer=((0,1,2,7,5), (1,0,4,4,3), (2,4,0,1,2), (7,4,1,0,3)); 2. 贪心过程： begin 初始化所有城市的算途径标志； 设置出发城市V； for i:=1 to n-1 do {n-1个城市} begin s:=从V至所有未曾到过的城市的边集中耗油量最少的那个城市； 累加耗油量； V:=s； 设V城市的访问标志； end; 最后一个城市返回第一个城市，累加耗油量； end; 3. 主过程：实现改善方案 begin for i:=1 to n do begin cost1:=maxint; {初始化} 调用贪心过程，返回本次搜索耗油量cost； if cost<cost1 then 替换； end; 输出； end. type dim1=array[0..11] of integer; const c:array[1..5,1..5] of integer=((0,1,2,7,5), (1,0,4,4,3), (2,4,0,1,2), (7,4,1,0,3), (5,3,2,3,0)); n=5; p=5; var tour:dim1; best:dim1; visit:array[1..n] of 0..1; cost,cost1:integer; i,j:integer; procedure greedy1(g:integer; var tour:dim1; var cost:integer); var v,s,k:integer; function findmin:integer; var i,len,s1:integer; begin len:=maxint; for i:=1 to n do if (i<>v) and (visit=0) and (c[v,i]

conscious · 发表于 2004-8-19 07:53:13

<

>一、分支限界法： <

>分支限界法类似于回溯法，也是一种在问题的解空间树T上搜索问题解的算法。但在一般情 <

>况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出T中满足约束条件的 所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件 的解中找出使用某一目标函数值达到极大或极小的解，即在某种意义下的最优解。 由于求解目标不同，导致分支限界法与回溯法在解空间树T上的搜索方式也不相同。回溯法 以深度优先的方式搜索解空间树T，而分支限界法则以广度优先或以最小耗费优先的方式搜 索解空间树T。分支限界法的搜索策略是：在扩展结点处，先生成其所有的儿子结点（分支 ），然后再从当前的活结点表中选择下一个扩展对点。为了有效地选择下一扩展结点，以 加速搜索的进程，在每一活结点处，计算一个函数值（限界），并根据这些已计算出的函 数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上有 最优解的分支推进，以便尽快地找出一个最优解。 二、分支限界法的基本思想： 分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。问 题的解空间树是表示问题解空间的一棵有序树，常见的有子集树和排列树。在搜索问题 的解空间树时，分支限界法与回溯法对当前扩展结点所使用的扩展方式不同。在分支限界 法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产 生其所有儿子结点。在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被 舍弃，其余儿子结点被子加入活结点表中。此后，从活结点表中取下一结点成为当前扩展 结点，并重复上述结点扩展过程。这个过程一直持续到找到所求的解或活结点表为空时为 止。 三、选择下一扩展结点的不同方式： 从活结点表中选择下一扩展结点的不同方式导致不同的分支限界法。最常见的有以下两种 方式： 1、队列式(FIFO)分支限界法：队列式分支限界法将活结点表组织成一个队列，并按队列的 先进先出原则选取下一个结点为当前扩展结点。 2、优先队列式分支限界法：优先队列式分支限界法将活结点表组织成一个优先队列，交按 优先队列中规定的结点优先级选取优先级最高的下一个结点成为当前扩展结点。 四、习题： 1、0-1背包：n=3,w=[16,15,15],p=[45,25,25],c=30 2、单源最短路径：求从起点到终点的最短路径。 3、装载问题：有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的 重量为wi且 。要求确定是否有一个合理的装载方案可将这n个集装箱装上这 2艘轮船。如果有，找出一种装载方案。 4、布线问题：印刷电路板将布线区域划分成n X m个方格如图a所示。精确的电路布线问题 题的解空间树是表示问题解空间的一棵有序树，常见的有子集树和排列树。在搜索问题 的解空间树时，分支限界法与回溯法对当前扩展结点所使用的扩展方式不同。在分支限界 法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产 生其所有儿子结点。在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被 舍弃，其余儿子结点被子加入活结点表中。此后，从活结点表中取下一结点成为当前扩展 结点，并重复上述结点扩展过程。这个过程一直持续到找到所求的解或活结点表为空时为 止。 三、选择下一扩展结点的不同方式： 从活结点表中选择下一扩展结点的不同方式导致不同的分支限界法。最常见的有以下两种 方式： 1、队列式(FIFO)分支限界法：队列式分支限界法将活结点表组织成一个队列，并按队列的 先进先出原则选取下一个结点为当前扩展结点。 2、优先队列式分支限界法：优先队列式分支限界法将活结点表组织成一个优先队列，交按 优先队列中规定的结点优先级选取优先级最高的下一个结点成为当前扩展结点。 四、习题： 1、0-1背包：n=3,w=[16,15,15],p=[45,25,25],c=30 2、单源最短路径：求从起点到终点的最短路径。 3、装载问题：有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的 重量为wi且 。要求确定是否有一个合理的装载方案可将这n个集装箱装上这 2艘轮船。如果有，找出一种装载方案。 4、布线问题：印刷电路板将布线区域划分成n X m个方格如图a所示。精确的电路布线问题 要求确定连接方格a的中点到方格b的中点的最短布线方案。在布线时，电路只能沿直线或 直角布线，如图b所示。为了避免线路相交，已布了线的方格做了封锁标记，其它线路不允 穿过被封锁的方格。

wyp110110106 · 发表于 2004-8-23 16:37:30

<

>那我们要到那去找那些方法来学习啊　<

>楼主你可以把你多年的收藏的发上了　，我们大家　参考下<

>那样的话　我真的　很感谢你了[em03][em01][em07][em08]

sangbo8888 · 发表于 2004-8-24 01:11:30

有的算法其实是一种思想
像蒙特卡洛算法
这算法所能解决的问题太多了
一一罗列也是不太可能
给出代码也只是针对某一个具体问题的
再说了代码读起来也不太容易懂
要掌握的还是算法本身
然后自己是这写代码
我就是这么做的

sangbo8888 · 发表于 2004-8-24 01:25:24

高首

qinian · 发表于 2004-8-26 01:52:10

<

>请教，分枝定界法有写好的程序吗？我编过几次，太笨了，没弄出来，小弟拜托了！

zzj8704 · 发表于 2004-8-26 05:05:09

自己先搜索一下，到中国运筹学会看看。

		自动登录	找回密码
密码			注-册-帐-号