《最短路径问题》由会员分享，可在线阅读，更多相关《最短路径问题（20页珍藏版）》请在金锄头文库上搜索。
1、2015大学生数学建模竞赛承诺书我们仔细阅读了全国大学生数学建模竞赛章程和全国大学生数学建模竞赛参 赛规则（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网 上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或 其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文 引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性。如有 违反竞赛章程和参赛规则的
2、行为，我们将受到严肃处理。我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展 示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。我们参赛选择的题号是（从A/B/C/D中选择一项填写）：B我们的报名参赛队号为（8位数字组成的编号）：所属学校（请填写完整的全名）：泉州师范学院参赛队员（打印并签名）：_（论文纸质版与电子版中的以上信息必须一致，只是电子版中无需签名。以上内容 请仔细核对，提交后将不再允许做任何修改。如填写错误，论文可能被取消评奖资格。）日期：2015年5月 17日赛区评阅编号（由赛区组委会评阅前进行编号）：目录1. 摘要32. 问题的重述及分
3、析43. 符号说明44. 模型的分析，建立和求解55. 模型的评价和改进106. 参考文献107. 附录11最短路径问题摘要由于保安资源有限，根据学校的实际情况与需求，泉州师院数学专业新引进了智能 机器人-大白，目的是让他自动在校园巡逻，以确保校园的安全。对于题中所给的三 个问题，研究在不同现实背景下的最优线路设计问题，即研究在约束条件下的最短路径 问题。针对本案例，我们采用了大量的科学分析方法，利用图论中的各种知识，采用数 据结构里的最短路径算法，也叫Dijkstra算法，对最优线路的设计进行建模并使用 MATLAB和lingo软件进行编程求解。进行了一系列反复验证，得出如下结果：(1)问题
4、一：根据所给问题与数据，先将题目中给出的地点，及其之间的线路看 做是一个赋权连通简单无向图，使用几何画板优化出地图，利用图论中最短 路径算法的知识建立起“远距离优先模型”，求出最优线路。在此基础上， 通过观察分析计算对上述结果进行修正，然后，再采用穷举法对问题结果进 行验证，结果与最终答案相吻合，最后确定了问题一的最优路线为：问题一： 根据所给问题与数据，先将题目中给出的地点，及其之间的线路看做是一个 赋权连通简单无向图，使用几何画板优化出地图，利用图论中最短路径算法 的知识建立起“远距离优先模型”，求出最优线路。在此基础上，通过观察 分析计算对上述结果进行修正，然后，再采用穷举法对问题结果进
5、行验证， 结果与最终答案相吻合，最后确定了问题一的最优路线为：1-气一 A A A A A A A A A A A A A1310989568678711 A A A A A A A A A101112121311312(2)(3)问题二：根据所给问题，当大白巡逻到6时，接到报警说1处有恐怖分子， 需要尽快赶到现场，即求地点6到地点1之间的最短路径。利用迪杰斯特拉 算法（Dijkstra算法）建立起“两点间最短距离模型”，再运用MATLAB进 行编程并求解。最后得到了问题二的最优路线为：6 ,8 7 11 12、1。 问题三：我们给定大白一个具体任务：大白巡逻完图中标号的所有地点所用 时间最短
6、的线路。将图中的线路看作直线，画出优化地图，同第二问，也是 求最短路径问题，结合问题二的“两点间最短距离模型”建立“最近插入法 模型”，用lingo编写程序并求解，最后对问题结果进行验证，确定了问题三 的最优线路为：A3 A2 A1 A12 A11 A10 A13 A4 A5A9 A8 A7 A8 A6O（关键词:最短路径、赋权连通简单无向图、迪杰斯特拉算法（Dijkstra 算法）、最近插入法、图论、穷举法、几何画板、matlab）一、问题重述问题背景：由于保安资源有限，根据学校的实际情况，为了保证校园安全，也为了 学生能更安全，放心的在校园里生活，泉州师院数学专业引进了智能机器人大白来巡逻
7、 校园。根据题目所给数据，运用数学建模方法，将实际复杂的问题理想模型简化，设计 出满足题目要求的校园路径，有很重要的显示意义。试建立数学模型讨论下列问题：1. 请为大白规划一条路径，使得他可以用最少的时间走遍所有的路。当然，有些路 径走多遍是允许的。所有路径的距离详见附录。2. 大白巡逻到6时，接到报警说1处有恐怖分子，他应该怎么走才能最快到达1.3. 请你为大白再布置一个实际的任务，并给出解答。我们给定的任务是：大白如何走 可以用最少的时间走遍所有的地点。二、问题的分析对于问题一，要求在最短时间内，大白在路径可重复行走的情况下巡逻完所有的路， 我们首先对该问题进行优化，假定在外部条件（道路、
8、人为等外部因素）的影响下，大 白速度始终不变的情况下，把最短时间问题优化成最短距离问题。利用图论中最短路径 算法，我们建立起“远距离优先模型”，使用该模型以及几何画板作图求得最优解。对于问题二，当大白巡逻到6时，接到报警说1处有恐怖分子，即要在最短时间内 到达地点1处，同样也为最短距离问题。相比于问题一，要求到达特定点1处的最短距 离，路径自然不能重复行走，即问题一所建立的模型将无法再继续使用。因此，我们将 这个问题再进一步优化为：两点间的最短距离问题。针对这一问题，我们想到使用迪杰 斯特拉算法（Dijkstra算法）建立“两点间最短距离模型”，用MATLAB编写程序，利 用这一程序来求解我们
9、所需要的最短距离及其所走的路径。对于问题三，要求大白用最短时间巡逻完图中编号的所有地点的最短路线，同样也 是求最短距离问题。这个问题类似于“中国快递员问题”，由此受到启发并结合问题二 的“两点间最短距离模型”，建立“最近插入法模型”，用lingo编写程序并求解出最优 线路。三、模型的假设与符号说明3.1模型的假设1. 假设大白在校园内单位时间内行走的路程是不变的，即速度V保持不变。2. 假设大白的状态始终良好且行动能量始终充足，不会中途停下。3.1符号说明V 表示大白的行走速度A表示数字i所标示的地点4表示数字i所标示的地点到数字j所标示的地点之间的距离Inf表示无直达路径V 表示A的集合（i
10、=1,2,3.，12）13iE表示AA.路径存在的集合G （V, E） 表示A：带权邻接图min表示行走路的过程中所经过的距离path表示行走路线四、模型的建立及求解4.1. 建模前准备1. 数据处理将题目所给图形数据进行处理整合，优化，使之便于思考。首先利用几何画板将 题目所给的泉州师院的地图优化为如图（1）所示；其次，将题目所给的各地点之间的 距离进行数据处理，两地点间的无直达路径则用inf表示，整合到excel表格中，表（1） 所示。史丽一襁ej显冠厂枝天:.： 虱5 后岳两 虻a商 穿 窗二而汇 站昉牌图A1A2A3A4A5A6A 7A8A9A10A11A12A13A102InfInf
11、InfInfInfInfInfInfInf21A22025InfInfInfInfInfInfInfInf1A3Inf20InfInfInfInfInfInfInfInfInfInfA4Inf5Inf01InfInfInfInfInfInfInf5A5InfInfInf106InfInf3InfInfInfInfA6InfInfInfInf6052InfInfInfInfInfA7InfInfInfInfInf501InfInf5InfInfA8InfInfInfInfInf2102InfInfInfInfA9InfInfInfInfInfInfInf206InfInfInfA10InfInf
12、InfInfInfInfInfInf601Inf2A11InfInfInfInfInfInfInfInfInf101InfA122InfInfInfInfInfInfInfInfInf101表（1）2. 图论中最短路径的问题通常归属为三类：a. 单源最短路径问题：包括确定起点的最短路径问题和确定终点的最短路径问题。 确定终点与确定起点的最短路径问题相反。在无向图中，确认终点的问题与确认起点的 问题完全等同，在有向图中确定了终点的问题等同于把所有路径方向反转为确定起点的 问题。b. 确定终点的最短路径问题：即已知起点和终点，求两结点之间的最短路径。c. 全局最短路径问题：求局中所有的最短路径。3
13、. 迪杰斯特拉算法（Dijkstra算法）迪杰斯特拉（Dijkstra）算法是典型的最短路径路由算法，用于计算一个节点到其他 所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。 Dijkstra算法能得出最短路径的最优解。其基本思想是，设置顶点集合S并不断地作中 心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已 知。4. 中国邮递员问题著名图论问题之一。邮递员从邮局出发送信，要求对辖区内每条街，都至少通过一 次，再回邮局。在此条件下，怎样选择一条最短路线？此问题由中国数学家管梅谷于1960 年首先研究并给出算法，故名。用图论的语言描述就是
14、指在一个边赋权的图中找一个闭道，使得这个闭道经过每一 条边，并且闭道上所以边的权和最小。如果图本身就是一个欧拉图，那么这个闭道就是 欧拉闭道。如果图不是欧拉图，那么就有一些边可能会经过至少两次。4.2.1. “远距离优先模型”的建立问题一在速度V保持不变的情况下，属于图论中最短路径的问题分类中的第c类问 题，全局最短路径问题：求局中所有的最短路径。在行走路径是可以重复行走的条件下，要是全局路径最短，则如果有重复行走到路 径，那么重复行走的路径必须要尽可能的短，反过来说，路径长的路就尽量只走一次。 考虑这样的约束条件，在行走到每一地点遇岔路时，则优先行走路径长的岔路；若岔路 的路径等长，则优先行走通往未走过路径多的岔路。我们以这种行走规则为模型，并称之为“远距离优先模型”。4.2.2“远距离优先模型的求解1.将题中所给的地图与数据优化处理成加权无向图如图（1）所示。现考虑大白要将所有的路都走遍，必然不可能所有的路都只走一遍，容易看出A这一地点只有一条路3可走。于是，为了避免重复走AA，考虑从A出发
