2022年数学建模经典算.docx

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

1、精选学习资料 - - - - - - - - - 回溯算法查找问题的解的一种牢靠的方法是第一列出全部候选解,然后依次检查每一个,在检查完全部或部分候选解后,即可找到所需要的解；理论上,当候选解数量有限并且通过检查所 有或部分候选解能够得到所需解时,上述方法是可行的；不过,在实际应用中,很少使用这种方法,由于候选解的数量通常都特别大（比如指数级,甚至是大数阶乘）,即便采纳最快的运算机也只能解决规模很小的问题；对候选解进行系统检查的方法有多种,其中回溯和分枝定界法是比较常用的两种方法；依据这两种方法对候选解进行系统检查通常会使 问题的求解时间大大削减（无论对于最坏情形仍是对于一般情形）；事实上,这

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

3、 - -精选学习资料 - - - - - - - - - 在具有 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 用图的 形式给出了一个

4、 33 迷宫的解空间；从 1 , 1 点到 3 , 3 点的每一条路径都定义了 33 迷宫解空间中的一个元素,但由于障碍的设置,有些路径是不行行的； 图 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 页精选学习资料 - - - - - - - - - 节点）,那么便只能返回到最近被考察的活节点（回溯）,这 个活节点变成了新

6、的 E-节点；当我们已经找到了答案或者回溯尽了全部的活节点时,搜寻 过程终止；例 4-1 迷宫老鼠 考察图 16-3a 的矩阵中给出的 问题；我们将利用图1 6 -1 给出的解空间图来搜寻迷宫；33 的“迷宫老鼠 ”从迷宫的入口到出口的每一条路径都与图 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 或

7、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 动身 有两个可能

8、的移动,名师归纳总结 - - - - - - -第 3 页,共 18 页精选学习资料 - - - - - - - - - 但没有一个是可行的；所以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 是一个在迷宫中查找路径的回

9、溯算法；贪心算法 一、算法思想 贪心法的基本思路：从问题的某一个初始解动身逐步靠近给定的目标,以尽可能 快的地求得更好的解； 当 达到某算法中的某一步不能再连续前进时,算法停止；该算法存在问题：1. 不能保证求得的最终解是正确的；2. 不能用来求最大或最小解问题；3. 只能求满意某些约束条件的可行解的范畴；名师归纳总结 - - - - - - -第 4 页,共 18 页精选学习资料 - - - - - - - - - 实现该算法的过程：从问题的某一初始解动身；while 能朝给定总目标前进一步do 求出可行解的一个解元素； 由全部解元素组合成问题的一个可行解；二、例题分析1、背包问题 有一个背

10、包,背包涵量是 物品可以分割成任意大小；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）每次选取单位容量价值最大的物品,成为解此题的策略；名师归纳总结 - - - - - - -第 5 页,共 18 页精

11、选学习资料 - - - - - - - - - 源程序2、单源最短路径 一个有向图 G,它的每条边都有一个非负的权值 ci,j ,“路径长度 ” 就是所经过的全部边的权值之和； 对于源点需要找出从源点动身到达其他全部结点的最短 路径；E.Dijkstra 创造的贪婪算法可以解决最短路径问题；算法的主要思想是：分步求出最 短路径,每一步产生一个到达新目的顶点的最短路径；下一步所能达到的目的顶点通过如 下贪婪准就选取：在未产生最短路径的顶点中,选择路径最短的目的顶点； 设置顶点集合 S 并不断作贪心选择来扩充这个集合；当且仅当顶点到该顶点的最短路径 已知时该顶点属于集合 S；初始时 S 中只含源；

12、设 u 为 G 中一顶点,我们把从源点到 u 且中间仅经过集合 S 中的顶点的路称为从源到u 特别 路径,并把这个特别路径记录下来（例如程序中的 disti,j ）； 每次从 V-S 选出具有最短特殊路径长度的顶点 u,将 u 添加到 S 中,同时对特别路径长度进行必要的修改； 一旦 V=S,就得到从源到其他全部顶点的最短路径,也就得到问题的解；Dijkstra.pas 名师归纳总结 - - - - - - -第 6 页,共 18 页精选学习资料 - - - - - - - - - 3、机器调度 现有 N 项任务和无限多台机器；任务可以在机器上处理；每件任务开头时间和完成时间有下表：任务 a

13、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. 图解：

14、如从 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,1,2, 7,4,1,0,3; 2. 贪心过程：begin 初始化全部城市的算途径标志；

15、设置动身城市 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; 初始化 调用贪心过程,返回本次搜寻耗油量 cost；if costcost1 then 替换；end; 输出；en

16、d. 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,cost1:integer; i,j:integer; procedure greedy1g:integer; v

17、ar 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 页精选学习资料 - - - - - - - - - 一、 分支限界法：分支限界法类似于回溯法, 也是一种在问题的解空间树 T 上搜寻问题解的算法；但在一般情况下,分支限界法与回溯法的求解目标不同；回溯法的求解目

18、标是找出 T 中满意约束条件的 全部解,而分支限界法的求解目标就是找出满意约束条件的一个解,或是在满意约束条件 的解中找出访用某一目标函数值达到极大或微小的解,即在某种意义下的最优解；由于求解目标不同,导致分支限界法与回溯法在解空间树 T 上的搜寻方式也不相同；回溯法 以深度优先的方式搜寻解空间树 T,而分支限界法就以广度优先或以最小耗费优先的方式搜 索解空间树 T；分支限界法的搜寻策略是：在扩展结点处,先生成其全部的儿子结点（分支）,然后再从当前的活结点表中选择下一个扩展对点；为了有效地选择下一扩展结点,以 加速搜寻的进程,在每一活结点处,运算一个函数值（限界）,并依据这些已运算出的函 数值

19、,从当前活结点表中选择一个最有利的结点作为扩展结点,使搜寻朝着解空间树上有 一个最优解；最优解的分支推动,以便尽快地找出二、分支限界法的基本思想：分支限界法常以广度优先或以最小耗费（最大效益） 优先的方式搜寻问题的解空间树； 问题的解空间树是表示问题解空间的一棵有序名师归纳总结 树,常见的有子集树和排列树；在搜寻问题的解空间树时,分支第 11 页,共 18 页限界法与回溯法对当前扩展结点所使用的扩展方式不同；在分支限界- - - - - - -精选学习资料 - - - - - - - - - 法中,每一个活结点只有一次机会成为扩展结点；活结点一旦成为扩展结点,就一次性产生其全部儿子结点；在这些

20、儿子结点中,那些导致不行行解或导致非最优解的儿子结点被舍弃,其余儿子结点被子加入活结点表中；此后,从活结点表中取下一结点成为当前扩展结点,并重复上述结点扩展过程； 这个过程始终连续到找到所求的解或活结 点表为空时为止；三、选择下一扩展结点的不同方式：从活结点表中选择下一扩展结点的不同方式导致不同的分支限 界法；最常见的有以下两种方式：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、布线问题：印刷电路板将布线区域划分成 a 所示；精确的电路布线问题n X m 个方格如图题的解空间树是表示问题

22、解空间的一棵有序树,常见的有 子集树和 排列树；在搜寻问题的解空间树时,分支限界法与回溯法对当前扩展结点所使用的扩展方式不同；在分支限界法中, 每一个活结点只有一次机会成为扩展结点； 活结点一旦成为扩展结点, 就一次性产 生其全部儿子结点； 在这些儿子结点中, 那些导致不行行解或导致非最优解的儿子结点被舍弃,其余儿子结点被子加入活结点表中；此后,从活结点表中取下一结点成为当前扩展 结点,并重复上述结点 扩展过程；这个过程始终连续到找到所求的解或活结点表为空时为 止；三、选择下一扩展结点的不同方式：从活结点表中选择下一扩展结点的不同方式导致不同的分支限 界法；最常见的有以下两种方式：1、队列式

23、FIFO 分支限界法：队列式分支限界法将活结点表组 织成一个队列,并按队列的 先进先出原就选取下一个结点为当前扩展结点；2、优先队列式分支限界法：优先队列式分支限界法将活结点表 组织成一个优先队列,交按名师归纳总结 - - - - - - -第 13 页,共 18 页精选学习资料 - - - - - - - - - 优先队列中规定的结点优先级选取优先级最高的下一个结点成为当前扩展结点；要求确定连接方格a 的中点到方格 b 的中点的最短布线方案；在布线时,电路只能沿直线或 直角布线,如图 b 所示；为了防止线路相交,已布了线的方格做 了封锁标记,其它线路不允 穿过被封锁的方格；Dijkstra

24、算法：这一算法可求得有向网格 N=V,A,W 中从一给定点 v动身到 N 中任一点的最短有向路及其长度；该算法在解决关键路线问题、背包 问题、某些加工次序、 中国邮递员问题等问题很有效； 算法过程如下：（0）给全部的点一暂时标号1,然后以v为动身点,Pk如QU1,0Ujw 1j2jn,Tj1 1jn,Pj1jn 即为Q23, ,n；Q . 置（1）在 Q 中找 k ,使得UkminUjP,QkQU 1进入下一步（2）；如Q时,算法终止,此时名师归纳总结 点v 至vj的距离,T表示最短路（v ,jvk）中与v邻近的点v；第 14 页,共 18 页（2） 对 Q 中每一个 j ,假如Uw kjUj

25、,就- - - - - - -精选学习资料 - - - - - - - - - UkwkjUj,kTj然后返回步骤（ 1）；该算法至多经过n1次循环必终止；下面就详细实例编制了（在Matlab 中）程序；例：已知v 与 ivj之间的有向路长度,求自点1 到点 6 的最短有路；05304202430 50 20clear; M=1.0e8; 名师归纳总结 - - - - - - -第 15 页,共 18 页精选学习资料 - - - - - - - - - w=0 5 M 3 M M M 0 4 2 M M M M 0 2 4 3 M M M 0 5 M M M M M 0 2 M M M M M

26、 0; N=6; %共有 n 个顶点 n=N; j=2 3 4 5 6; T=ones1,n; P=1; Q=j; U1:n=w1,:; temp=1; whiletemp=N-1 for I=1:n-1 %执行 N-1 次xxI=U QI ; end for I=1:n-1 if U QI =minxx; k=QI; 名师归纳总结 - - - - - - -第 16 页,共 18 页精选学习资料 - - - - - - - - - P=P,k; end end for I2=1:n-1 if QI2=k k2=I2; end end Qk2=; for I3=1:lengthQ if Uk+

27、w k,QI3 U QI3 U QI3 =Uk+wk,QI3; T QI3 =k; end end n=n-1; temp=temp+1; end for temp=1:N disp第 1 点到第 ,num2strtemp,点的最短长度为：,blanks4,num2str Utemp disp第 1 点到第 ,num2strtemp,点的最短路中其前一点的下标名师归纳总结 - - - - - - -第 17 页,共 18 页精选学习资料 - - - - - - - - - 为：,blanks4,num2str Ttemp fprintfn end 名师归纳总结 - - - - - - -第 18 页,共 18 页