2022年数学建模经典算 .pdf

《2022年数学建模经典算 .pdf》由会员分享，可在线阅读，更多相关《2022年数学建模经典算 .pdf（18页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、能够保证算法运行结束时可以找到所需要的解。因此，这些方法通常能够用来求解规模很大的问题。本章集中阐述回溯方法，这种方法被用来设计货箱装船、背包、最大完备子图、旅行商和电路板排列问题的求解算法。 1 算法思想回溯（ b a c k t r a c k i n g）是一种系统地搜索问题解答的方法。为了实现回溯，首先需要为问题定义一个解空间（solution space ） ，这个空间必须至少包含问题的一个解（可能是最优的）。在迷宫老鼠问题中，我们可以定义一个包含从入口到出口的所有路径的解空间；精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共

3、18 页在具有 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 迷宫的解

4、空间。从 ( 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 的值，从根到叶的路径中的一些解或全部解可能是不可行的。一旦定义了解空间的组织方法， 这个空间即可按深度优先的方法从开始节点进行搜索。 在

5、迷宫老鼠问题中， 开始节点为入口节点 ( 1 , 1 )；在 0 / 1背包问题中，开始节点为根节点 A。开始节点既是一个活节点又是一个 E-节点（expansion node ） 。从 E-节点可移动到一个新节点。如果能从当前的E-节点移动到一个新节点，那么这个新节点将变成一个活节点和新的 E-节点，旧的 E-节点仍是一个活节点。如果不能移到一个新节点，当前的E-节点就 “死”了（即不再是一个活精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 18 页节点） ，那么便只能返回到最近被考察的活节点（回溯），这 个活节点变成了新的 E-节点

6、。当我们已经找到了答案或者回溯尽了所有的活节点时，搜索过程结束。例 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。从这个位置，能移动到(

7、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。

8、 图 1 6 - 1中， 从( 1 , 3 )出发 有两个可能的移动，精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 18 页但没有一个是可行的。所以E-节点( 1 , 3 )死亡，回溯到最近被检查的活节点 ( 1 , 2 )。在这个位置也没有可行的移动，故这个节点也死亡了。唯一留下的活节点是 ( 1 , 1 )。这个节点再次变为E-节点，它可移动到 ( 2 , 1 )。现在活节点为 ( 1 , 1 )，( 2 , 1 )。继续下去，能到达点( 3 , 3 )。此时，活节点表为 ( 1 , 1 )，( 2 , 1 )，( 3 , 1 )

9、，( 3 , 2 )，( 3 , 3 )，这即是到达出口的路径。程序 5 - 1 3是一个在迷宫中寻找路径的回溯算法。贪心算法一、算法思想贪心法的基本思路：从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。 当 达到某算法中的某一步不能再继续前进时，算法停止。该算法存在问题：1. 不能保证求得的最后解是最佳的；2. 不能用来求最大或最小解问题；3. 只能求满足某些约束条件的可行解的范围。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 18 页实现该算法的过程：从问题的某一初始解出发；while 能朝给定总目标前进一

10、步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）每次选取单位容量

11、价值最大的物品，成为解本题的策略。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 18 页源程序2、单源最短路径 一个有向图 G，它的每条边都有一个非负的权值 ci,j ，“ 路径长度 ” 就是所经过的所有边的权值之和。 对于源点需要找出从源点出发到达其他所有结点的最短路径。E.Dijkstra 发明的贪婪算法可以解决最短路径问题。算法的主要思想是：分步求出最短路径，每一步产生一个到达新目的顶点的最短路径。下一步所能达到的目的顶点通过如 下贪婪准则选取：在未产生最短路径的顶点中，选择路径最短的目的顶点。 设置顶点集合 S并不断作贪心选择

12、来扩充这个集合。当且仅当顶点到该顶点的最短路径已知时该顶点属于集合S。初始时 S中只含源。设 u 为 G 中一顶点，我们把从源点到u 且中间仅经过集合 S 中的顶点的路称为从源到u 特殊 路径，并把这个特殊路径记录下来（例如程序中的disti，j）。 每次从 V-S 选出具有最短特殊路径长度的顶点u，将 u 添加到 S中，同时对特殊路径长度进行必要的修改。 一旦 V=S，就得到从源到其他所有顶点的最短路径，也就得到问题的解。Dijkstra.pas 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 18 页3、机器调度 现有 N 项任务和

13、无限多台机器。任务可以在机器上处理。每件任务开始时间和完成时间有下表：任务 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. 运用

14、贪心思想：在每一步前进的选择上，选取相对当前城市耗油量最小的航线；2. 图解：若从 1 出发，有图：总耗油量 =14 1-2-5-3-4-1 但若路线改为： 1-5-3-4-2-1，则总耗油量 =13 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 18 页所以，这样的贪心法并不能得出最佳解。3. 改善方案：从所有城市出发的信心过程，求最优的。编程：1. 数据结构：城市联系网络图的描述(图的邻接矩阵的描述 )：const c=array1.5,1.5 of integer=(0,1,2,7,5), (1,0,4,4,3), (2,4,0

15、,1,2), (7,4,1,0,3); 2. 贪心过程：begin 初始化所有城市的算途径标志；设置出发城市 V；for i:=1 to n-1 do n-1 个城市 begin s:=从 V 至所有未曾到过的城市的边集中耗油量最少的那个城市；累加耗油量；V:=s；精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 18 页设 V 城市的访问标志；end; 最后一个城市返回第一个城市，累加耗油量；end; 3. 主过程：实现改善方案begin for i:=1 to n do begin cost1:=maxint; 初始化 调用贪心过程，

16、返回本次搜索耗油量cost；if costcost1 then 替换；end; 输出；end. type dim1=array0.11 of integer; const c:array1.5,1.5 of integer=(0,1,2,7,5), (1,0,4,4,3), (2,4,0,1,2), 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 18 页(7,4,1,0,3), (5,3,2,3,0); n=5; p=5; var tour:dim1; best:dim1; visit:array1.n of 0.1; cost,co

17、st1: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 (iv) and (visiti=0) and (cv,i 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页，共 18 页一、分支限界法：分支限界法类似于回

18、溯法， 也是一种在问题的解空间树T 上搜索问题解的算法。但在一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出T 中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件 的解中找出使用某一目标函数值达到极大或极小的解，即在某种意义下的最优解。由于求解目标不同，导致分支限界法与回溯法在解空间树 T 上的搜索方式也不相同。回溯法以深度优先的方式搜索解空间树 T，而分支限界法则以广度优先或以最小耗费优先的方式搜 索解空间树 T。分支限界法的搜索策略是：在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展对点。为

19、了有效地选择下一扩展结点，以加速搜索的进程，在每一活结点处，计算一个函数值（限界），并根据这些已计算出的函 数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。二、分支限界法的基本思想：分支限界法常以广度优先或以最小耗费（最大效益） 优先的方式搜索问题的解空间树。 问题的解空间树是表示问题解空间的一棵有序树，常见的有子集树和排列树。在搜索问题的解空间树时，分支限界法与回溯法对当前扩展结点所使用的扩展方式不同。在分支限界精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共

20、18 页法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被子加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。 这个过程一直持续到找到所求的解或活结点表为空时为止。三、选择下一扩展结点的不同方式：从活结点表中选择下一扩展结点的不同方式导致不同的分支限界法。最常见的有以下两种方式：1、队列式 (FIFO)分支限界法：队列式分支限界法将活结点表组织成一个队列，并按队列的先进先出原则选取下一个结点为当前扩展结点。2、优先队列式分支限界法：优

21、先队列式分支限界法将活结点表组织成一个优先队列，交按优先队列中规定的结点优先级选取优先级最高的下一个结点成为当前扩展结点。四、习题：1、0-1 背包： n=3,w=16,15,15,p=45,25,25,c=30 2、单源最短路径：求从起点到终点的最短路径。3、装载问题：有一批共n 个集装箱要装上 2 艘载重量分别为 c1和 c2 的轮船，其中集装箱i 的重量为 wi 且要求确定是否有一个合理精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 18 页的装载方案可将这n 个集装箱装上这2 艘轮船。如果有，找出一种装载方案。4、布线问题：印

22、刷电路板将布线区域划分成n X m 个方格如图a所示。精确的电路布线问题题的解空间树是表示问题解空间的一棵有序树，常见的有子集树和 排列树。在搜索问题的解空间树时，分支限界法与回溯法对当前扩展结点所使用的扩展方式不同。在分支限界法中， 每一个活结点只有一次机会成为扩展结点。 活结点一旦成为扩展结点， 就一次性产生其所有儿子结点。 在这些儿子结点中， 那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被子加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所求的解或活结点表为空时为止。三、选择下一扩展结点的不同方式：从活结点表中选

23、择下一扩展结点的不同方式导致不同的分支限界法。最常见的有以下两种方式：1、队列式 (FIFO)分支限界法：队列式分支限界法将活结点表组织成一个队列，并按队列的先进先出原则选取下一个结点为当前扩展结点。2、优先队列式分支限界法：优先队列式分支限界法将活结点表组织成一个优先队列，交按精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 13 页，共 18 页优先队列中规定的结点优先级选取优先级最高的下一个结点成为当前扩展结点。要求确定连接方格a 的中点到方格 b 的中点的最短布线方案。在布线时，电路只能沿直线或直角布线，如图 b 所示。为了避免线路相交，已布

24、了线的方格做了封锁标记，其它线路不允穿过被封锁的方格。Dijkstra 算法：这一算法可求得有向网格N=(V,A,W) 中从一给定点1v出发到 N中任一点的最短有向路及其长度。该算法在解决关键路线问题、背包问题、某些加工顺序、 中国邮递员问题等问题很有效。 算法过程如下：（0）给所有的点一临时标号1，然后以1v为出发点，1),1( 1),2(, 011PnjTnjwUUjjjnQ,3 ,2。（1）在Q中找k，使得置).(minQjUUjk,PkPQkQ即为时，算法终止，此时）；若进入下一步（若)1(2,njUQQjjvv 至点1的距离，jT表示最短路（jvv ,1）中与jv邻近的点Tjv。（2

25、） 对Q中每一个j，如果则,jkjkUwU精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 14 页，共 18 页,jkjkUwUjTk然后返回步骤（ 1） 。该算法至多经过1n次循环必结束。下面就具体实例编制了（在Matlab 中）程序。例：已知jivv 与之间的有向路长度，求自点1 到点 6 的最短有路。clear; M=1.0e8; 053042024305020精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 15 页，共 18 页w=0 5 M 3 M M M 0 4 2 M M M M 0 2

26、4 3 M M M 0 5 M M M M M 0 2 M M M M M 0; N=6; %共有 n 个顶点n=N; j=2 3 4 5 6; T=ones(1,n); P=1; Q=j; U(1:n)=w(1,:); temp=1; while(temp=N-1) %执行 N-1 次for I=1:(n-1) xx(I)=U( Q(I) ); end for I=1:(n-1) if U( Q(I) )=min(xx); k=Q(I); 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 16 页，共 18 页P=P,k; end end for

27、I2=1:(n-1) if Q(I2)=k k2=I2; end end Q(k2)=; for I3=1:length(Q) if U(k)+w( k,Q(I3) )U( Q(I3) ) U( Q(I3) )=U(k)+w(k,Q(I3); T( Q(I3) )=k; end end n=n-1; temp=temp+1; end for temp=1:N disp(第 1 点到第 ,num2str(temp), 点的最短长度为：,blanks(4),num2str( U(temp) ) ) disp(第 1 点到第 ,num2str(temp), 点的最短路中其前一点的下标精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 17 页，共 18 页为：,blanks(4),num2str( T(temp) ) ) fprintf(n) end 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 18 页，共 18 页