数学建模比赛最短路径问题

2015大学生数学建模竞赛承诺书我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生数学建模竞赛参赛规则》（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性。如有违反竞赛章程和参赛规则的行为，我们将受到严肃处理。我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。我们参赛选择的题号是（从A/B/C/D中选择一项填写）：B 我们的报名参赛队号为（8位数字组成的编号）：所属学校（请填写完整的全名）：泉州师范学院参赛队员(打印并签名)：1.蔡惠芳1213010272.肖丁福1213010283.李雅萍121301020指导教师或指导教师组负责人(打印并签名)：杨昔阳 （论文纸质版与电子版中的以上信息必须一致，只是电子版中无需签名。以上内容请仔细核对，提交后将不再允许做任何修改。如填写错误，论文可能被取消评奖资格。）日期：2015年5月17日赛区评阅编号（由赛区组委会评阅前进行编号）：目录1.摘要…………………..32.问题的重述及分析…………………..43.符号说明……………..44.模型的分析，建立和求解…………..55.模型的评价和改进…………………..106.参考文献……………..107.附录…………………..11最短路径问题摘要 由于保安资源有限，根据学校的实际情况与需求，泉州师院数学专业新引进了智能机器人---大白，目的是让他自动在校园巡逻，以确保校园的安全。对于题中所给的三个问题，研究在不同现实背景下的最优线路设计问题，即研究在约束条件下的最短路径问题。针对本案例，我们采用了大量的科学分析方法，利用图论中的各种知识，采用数据结构里的最短路径算法,也叫Dijkstra算法，对最优线路的设计进行建模并使用MATLAB和lingo软件进行编程求解。进行了一系列反复验证，得出如下结果：问题一：根据所给问题与数据，先将题目中给出的地点，及其之间的线路看做是一个赋权连通简单无向图，使用几何画板优化出地图，利用图论中最短路径算法的知识建立起“远距离优先模型”，求出最优线路。在此基础上，通过观察分析计算对上述结果进行修正，然后，再采用穷举法对问题结果进行验证，结果与最终答案相吻合，最后确定了问题一的最优路线为：问题一：根据所给问题与数据，先将题目中给出的地点，及其之间的线路看做是一个赋权连通简单无向图，使用几何画板优化出地图，利用图论中最短路径算法的知识建立起“远距离优先模型”，求出最优线路。在此基础上，通过观察分析计算对上述结果进行修正，然后，再采用穷举法对问题结果进行验证，结果与最终答案相吻合，最后确定了问题一的最优路线为：问题二：根据所给问题，当大白巡逻到6时，接到报警说1处有恐怖分子，需要尽快赶到现场，即求地点6到地点1之间的最短路径。利用迪杰斯特拉算法（Dijkstra算法）建立起“两点间最短距离模型”，再运用MATLAB进行编程并求解。最后得到了问题二的最优路线为：68711121。问题三：我们给定大白一个具体任务：大白巡逻完图中标号的所有地点所用时间最短的线路。将图中的线路看作直线，画出优化地图，同第二问，也是求最短路径问题，结合问题二的“两点间最短距离模型”，建立“最近插入法模型”，用lingo编写程序并求解，最后对问题结果进行验证，确定了问题三的最优线路为：A3A2A1A12A11A10A13A4A5A9A8A7A8A6。（关键词：最短路径、赋权连通简单无向图、迪杰斯特拉算法（Dijkstra算法）、最近插入法、图论、穷举法、几何画板、matlab）问题重述问题背景：由于保安资源有限，根据学校的实际情况，为了保证校园安全，也为了学生能更安全，放心的在校园里生活，泉州师院数学专业引进了智能机器人大白来巡逻校园。根据题目所给数据，运用数学建模方法，将实际复杂的问题理想模型简化，设计出满足题目要求的校园路径，有很重要的显示意义。试建立数学模型讨论下列问题：1.请为大白规划一条路径，使得他可以用最少的时间走遍所有的路。当然，有些路径走多遍是允许的。所有路径的距离详见附录。2.大白巡逻到6时，接到报警说1处有恐怖分子，他应该怎么走才能最快到达1.3.请你为大白再布置一个实际的任务，并给出解答。我们给定的任务是：大白如何走可以用最少的时间走遍所有的地点。二、问题的分析对于问题一，要求在最短时间内，大白在路径可重复行走的情况下巡逻完所有的路，我们首先对该问题进行优化，假定在外部条件（道路、人为等外部因素）的影响下，大白速度始终不变的情况下，把最短时间问题优化成最短距离问题。利用图论中最短路径算法，我们建立起“远距离优先模型”，使用该模型以及几何画板作图求得最优解。对于问题二，当大白巡逻到6时，接到报警说1处有恐怖分子，即要在最短时间内到达地点1处，同样也为最短距离问题。相比于问题一，要求到达特定点1处的最短距离，路径自然不能重复行走，即问题一所建立的模型将无法再继续使用。因此，我们将这个问题再进一步优化为：两点间的最短距离问题。针对这一问题，我们想到使用迪杰斯特拉算法（Dijkstra算法）建立“两点间最短距离模型”，用MATLAB编写程序，利用这一程序来求解我们所需要的最短距离及其所走的路径。对于问题三，要求大白用最短时间巡逻完图中编号的所有地点的最短路线，同样也是求最短距离问题。这个问题类似于“中国快递员问题”，由此受到启发并结合问题二的“两点间最短距离模型”，建立“最近插入法模型”，用lingo编写程序并求解出最优线路。三、模型的假设与符号说明3.1模型的假设1.假设大白在校园内单位时间内行走的路程是不变的，即速度V保持不变。2.假设大白的状态始终良好且行动能量始终充足，不会中途停下。3.1符号说明 V 表示大白的行走速度 表示数字i所标示的地点 表示数字i所标示的地点到数字j所标示的地点之间的距离Inf表示无直达路径V表示的集合（i=1,2,3…..,12,13）E表示路径存在的集合G（V，E）表示带权邻接图min表示行走路的过程中所经过的距离path表示行走路线四、模型的建立及求解4.1.建模前准备1.数据处理将题目所给图形数据进行处理整合，优化，使之便于思考。首先利用几何画板将题目所给的泉州师院的地图优化为如图（1）所示；其次，将题目所给的各地点之间的距离进行数据处理，两地点间的无直达路径则用inf表示，整合到excel表格中，表（1）所示。图(1)表（1）2.图论中最短路径的问题通常归属为三类：a.单源最短路径问题：包括确定起点的最短路径问题和确定终点的最短路径问题。确定终点与确定起点的最短路径问题相反。在无向图中，确认终点的问题与确认起点的问题完全等同，在有向图中确定了终点的问题等同于把所有路径方向反转为确定起点的问题。b.确定终点的最短路径问题：即已知起点和终点，求两结点之间的最短路径。c.全局最短路径问题：求局中所有的最短路径。3.迪杰斯特拉算法（Dijkstra算法）迪杰斯特拉(Dijkstra)算法是典型的最短路径路由算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解。其基本思想是，设置顶点集合S并不断地作中心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。4.中国邮递员问题著名图论问题之一。邮递员从邮局出发送信，要求对辖区内每条街，都至少通过一次，再回邮局。在此条件下，怎样选择一条最短路线？此问题由中国数学家管梅谷于1960年首先研究并给出算法，故名。用图论的语言描述就是指在一个边赋权的图中找一个闭道，使得这个闭道经过每一条边，并且闭道上所以边的权和最小。如果图本身就是一个欧拉图，那么这个闭道就是欧拉闭道。如果图不是欧拉图，那么就有一些边可能会经过至少两次。.4.2.1.“远距离优先模型”的建立问题一在速度V保持不变的情况下，属于图论中最短路径的问题分类中的第c类问题,全局最短路径问题：求局中所有的最短路径。在行走路径是可以重复行走的条件下，要是全局路径最短，则如果有重复行走到路径，那么重复行走的路径必须要尽可能的短，反过来说，路径长的路就尽量只走一次。考虑这样的约束条件，在行走到每一地点遇岔路时，则优先行走路径长的岔路；若岔路的路径等长，则优先行走通往未走过路径多的岔路。我们以这种行走规则为模型，并称之为“远距离优先模型”。4.2.2“远距离优先模型”的求解1．将题中所给的地图与数据优化处理成加权无向图如图（1）所示。现考虑大白要将所有的路都走遍，必然不可能所有的路都只走一遍，容易看出这一地点只有一条路可走。于是，为了避免重复走,考虑从出发，利用远距离优先模型求解。让大白优先走远距离的路，重复走的路径都是尽可能短，以达到走完全局路程最短，行走时间最少的目的。解得其一条路线为：路径总长度为：2+5+1+1+5+2+6+2+2+3+6+2+2+5+1+1+5+1+1+1+2+2+1+1+1+1=622．利用穷举法列举多种路线验证上诉路径是否为所求的最优解，例如一下三种路线:路线一：路径总长度为：2+2+2+1+5+5+2+1+1+2+6+1+1+2+1+2+1+1+5+5+5+1+3+3+6=66路线二：路径总长度:2+2+2+3+6+5+1+5+5+1+1+1+6+1+1+5+2+5+2+1+2+1+1+1+2=65路线三：路径总长度为：5+2+2+2+1+1+2+2+1+1+1+1+2+5+1+6+5+5+5+1+2+2+2+3+3+6=693．路线一、二、三的路径总长度分别为：66、65、69，均大于我们利用“远距离优先模型”所求路径的总长度62。即大白行走的最优路线如图二所示，其路线为：。路径总长度为：62。图（2）4.3.1“两点间最短距离模型”的建立将途中校园地点看做节点（i=1,2，…13），可知该网络是一个加权无向图。巡逻员大白要在最短时间内到达目的地。依据问题的要求及相关假设，建立相应的模型并进行求解。我们先引入最小生成树的简单定义：给定一个无向连通带权邻接图G（V，E）中的每一条边权值为C。如果G的子图G‘是一个包含G中所有定点的子图，那么G’成为G的生成树，如果G‘的边的权值最小，那么G’成为G的最小生成树。根据题目意思，定义：权为两地点间的距离，如下表线路权线路权21112126151253522165定义V为，，，，，，，，，，，，的集合。定义E为,,,,,,,,,，,,,,,,,，,的集合G=（V，E）表示带权邻接图，即表（1）汇总excel表格正是此带权邻接矩阵。根据迪杰斯特拉算法（Dijkstra算法）在全局选取一点作为中心，向外层层扩展，直到扩展到终点为止的思想建立模型求解第二问。在全局中选取一点X作为中心（即大白此时的位置），根据带权邻接矩阵表（1），所示向外层层扩展到终点Y（大白应去的指定位置）为止，在这过程中用path记录扩展的路线，用min记录扩展过程中所经过的距离。以此想法建立起模型，并称之为“两点间最短距离模型”。 4.3.2“两点间最短距离模型”的求解针对问题二，要求两个确定点间的最短路径问题，采用数据结构里的最短路径算法,也叫Dijkstra算法,再运用MATLAB进行编程，MATLAB的编程程序见附录2，最后求得最短距离min与最短距离的行走路path如下，即A6A8A7A11A12A1。线路图如图（3）所示：图（3）4.4.1“最近插入法模型”的建立针对问题三，我们所提出的实际问题是：要使大白在最短的时间内走完所有的地点，即相当于求所有点都连接起来的最短距离。有些地点有好几条不同的线路可以走，要使行走过所有点的距离最短，就要使有多条线路可走的地点走最短的线路。再结合“中国邮递员问题”，从而建立了“最近插入法模型”。4.4.2“最近插入法模型”的求解针对问题三的求解，还是先考虑到了A3这个只有一条线路可走的地点。则由A3出发，大白在每一地点遇岔路时，则优先行走路径短的岔路；若岔路的路径等长，则优先行走通往未走过地点多的岔路。这样就得到了一条路线，在此基础上，通过观察分析计算对上述结果进行修正，然后，再采用穷举法对问题结果进行验证，结果与最终答案相吻合，最后确定了问题一的最优路线为：A3A2A1A12A11A10A13A4A5A9A8A7A8A6。如图（4）所示：图（4）五、模型的评价与改进方向5.1模型的优点： 1.优点在于利用matlab、lingo软件程序大大节约了计算量。 2.模型配予图片分析，形象化，直观，形象，易理解。 3.语言、符号简单.5.2模型的缺点： 模型相对理想化，忽略了道路、环境、机器等影响因素。5.3模型的改进方向：对于不可避免的误差纳入计算，使结果更加贴近生活、真实化。六、参考文献[1].傅家良.运筹学方法与模型[M].上海,复旦大学出版社.2006年；[2].刘来福，曾文艺.数学模型与数学建模（第二版）.北京：北京师范大学出版社，2002；[3].蔡锁章.数学建模原理与方法.北京：海洋出版社；七、附录附录1：学校地图：附录2：第二题matlab程序编程：function[min,path]=dijkstra(a,start,terminal)n=size(a,1);label(start)=0;f(start)=start;fori=1:nifi~=startlabel(i)=inf;end,ends(1)=start;u=start;whilelength(s)<nfori=1:nins=0;forj=1:length(s)ifi==s(j)ins=1;end,endifins==0v=i;iflabel(v)>(label(u)+a(u,v))label(v)=(label(u)+a(u,v));f(v)=u;end,end,endv1=0;k=inf;fori=1:nins=0;forj=1:length(s)ifi==s(j)ins=1;end,endifins==0v=i;ifk>label(v)k=label(v);v1=v;end,end,ends(length(s)+1)=v1;u=v1;endmin=label(terminal);path(1)=terminal;i=1;whilepath(i)~=start;path(i+1)=f(path(i));i=i+1;endpath(i)=start;L=length(path);path=path(L:-1:1);[min,path]=dijkstra(a,6,1)min=11path=68711121附录:3：第三题lingo程序编程:model:sets:didian/1..13/:u;link(didian,didian)/1,21,121,132,32,42,134,54,135,65,96,76,87,87,118,99,1010,1110,1311,1212,13/:c,X;endsetsdata:c=02100000100000100000100000100000100000100000100000100000212025100000100000100000100000100000100000100000100000110000020100000100000100000100000100000100000100000100000100000100000100000510000001100000100000100000100000100000100000100000510000010000010000010610000010000031000001000001000001000001000001000001000001000006052100000100000100000100000100000100000100000100000100000