发布时间 : 星期日 文章最短路径问题-数学建模比赛 - 图文更新完毕开始阅读7c27e9d783c758f5f61fb7360b4c2e3f56272561
2015大学生数学建模竞赛
承诺书
我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生数学建模竞赛参赛规则》（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）。
我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。
我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。
我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性。如有违反竞赛章程和参赛规则的行为，我们将受到严肃处理。
我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。
我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的报名参赛队号为（8位数字组成的编号）： 所属学校（请填写完整的全名）：泉州师范学院 参赛队员 (打印并签名) ：
（论文纸质版与电子版中的以上信息必须一致，只是电子版中无需签名。以上内容请仔细核对，提交后将不再允许做任何修改。如填写错误，论文可能被取消评奖资格。）
日期： 2015 年 5 月 17 日 赛区评阅编号（由赛区组委会评阅前进行编号）：
目录
1
1.摘要…………………………………………………..3 2.问题的重述及分析…………………………………..4 3.符号说明……………………………………………..4 4.模型的分析，建立和求解…………………………..5 5.模型的评价和改进…………………………………..10 6.参考文献……………………………………………..10 7.附录…………………………………………………..11
最短路径问题
摘要
2
由于保安资源有限，根据学校的实际情况与需求，泉州师院数学专业新引进了智能机器人---大白，目的是让他自动在校园巡逻，以确保校园的安全。对于题中所给的三个问题，研究在不同现实背景下的最优线路设计问题，即研究在约束条件下的最短路径问题。针对本案例，我们采用了大量的科学分析方法，利用图论中的各种知识，采用数据结构里的最短路径算法,也叫Dijkstra算法，对最优线路的设计进行建模并使用MATLAB和lingo软件进行编程求解。进行了一系列反复验证，得出如下结果：
（1） 问题一：根据所给问题与数据，先将题目中给出的地点，及其之间的线路看
做是一个赋权连通简单无向图，使用几何画板优化出地图，利用图论中最短路径算法的知识建立起“远距离优先模型” ，求出最优线路。在此基础上，通过观察分析计算对上述结果进行修正，然后，再采用穷举法对问题结果进行验证，结果与最终答案相吻合，最后确定了问题一的最优路线为：问题一：根据所给问题与数据，先将题目中给出的地点，及其之间的线路看做是一个赋权连通简单无向图，使用几何画板优化出地图，利用图论中最短路径算法的知识建立起“远距离优先模型” ，求出最优线路。在此基础上，通过观察分析计算对上述结果进行修正，然后，再采用穷举法对问题结果进行验证，结果与最终答案相吻合，最后确定了问题一的最优路线为：A3?A2?A4?A13?A10?A9?A8?A9?A5?A6?A8?A6?A7?A8?A7?A11?A10?A11?A12?A1?A2?A13?A1?A13?A12
（2） 问题二：根据所给问题，当大白巡逻到6时，接到报警说1处有恐怖分子，
需要尽快赶到现场，即求地点6到地点1之间的最短路径。利用迪杰斯特拉算法（Dijkstra算法）建立起“两点间最短距离模型” ，再运用MATLAB进行编程并求解。最后得到了问题二的最优路线为：6?8?7?11?12?1。 （3） 问题三：我们给定大白一个具体任务：大白巡逻完图中标号的所有地点所用
时间最短的线路。将图中的线路看作直线，画出优化地图，同第二问，也是求最短路径问题，结合问题二的“两点间最短距离模型”，建立“最近插入法模型”，用lingo编写程序并求解，最后对问题结果进行验证，确定了问题三的最优线路为：A3 ?A2? A1? A12? A11? A10 ?A13 ?A4 ?A5 ?A9? A8 ?A7 ?A8 ?A6。
（关键词：最短路径、赋权连通简单无向图、迪杰斯特拉算法（Dijkstra算法）、最近插入法、图论、穷举法、几何画板、matlab）
3
一、 问题重述
问题背景：由于保安资源有限，根据学校的实际情况，为了保证校园安全，也为了学生能更安全，放心的在校园里生活，泉州师院数学专业引进了智能机器人大白来巡逻校园。根据题目所给数据，运用数学建模方法，将实际复杂的问题理想模型简化，设计出满足题目要求的校园路径，有很重要的显示意义。 试建立数学模型讨论下列问题：
1.请为大白规划一条路径，使得他可以用最少的时间走遍所有的路。当然，有些路径走多遍是允许的。所有路径的距离详见附录。
2.大白巡逻到6时，接到报警说1处有恐怖分子，他应该怎么走才能最快到达1. 3.请你为大白再布置一个实际的任务，并给出解答。我们给定的任务是：大白如何走
可以用最少的时间走遍所有的地点。
二、问题的分析
对于问题一，要求在最短时间内，大白在路径可重复行走的情况下巡逻完所有的路，我们首先对该问题进行优化，假定在外部条件（道路、人为等外部因素）的影响下，大白速度始终不变的情况下，把最短时间问题优化成最短距离问题。利用图论中最短路径算法，我们建立起“远距离优先模型”，使用该模型以及几何画板作图求得最优解。
对于问题二，当大白巡逻到6时，接到报警说1处有恐怖分子，即要在最短时间内到达地点1处，同样也为最短距离问题。相比于问题一，要求到达特定点1处的最短距离，路径自然不能重复行走，即问题一所建立的模型将无法再继续使用。因此，我们将这个问题再进一步优化为：两点间的最短距离问题。针对这一问题，我们想到使用迪杰斯特拉算法（Dijkstra算法）建立“两点间最短距离模型” ，用MATLAB编写程序，利用这一程序来求解我们所需要的最短距离及其所走的路径。
对于问题三，要求大白用最短时间巡逻完图中编号的所有地点的最短路线，同样也是求最短距离问题。这个问题类似于“中国快递员问题”，由此受到启发并结合问题二的“两点间最短距离模型”，建立“最近插入法模型”，用lingo编写程序并求解出最优线路。
三、模型的假设与符号说明
3.1模型的假设
1.假设大白在校园内单位时间内行走的路程是不变的，即速度V保持不变。 2.假设大白的状态始终良好且行动能量始终充足，不会中途停下。
3.1符号说明
V 表示大白的行走速度
Ai 表示数字i所标示的地点
AiAj
表示数字i所标示的地点到数字j所标示的地点之间的距离
Inf 表示无直达路径
V 表示Ai的集合（i=1,2,3…..,12,13）
4