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

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