GPS导航.docx

GPS导航两地时间最短路程最短路线
摘要
随着科学技术的不断发展,近几年GPS导航定位技术在我们的生活及出行中发挥着越来越重要的作用,具有高效率、高精度、多功能等特点。用GPS导航两地时间最短和路程最短路线问题,是基于现如今日益发展成熟的车载GPS导航系统,要求能够在给出起点和终点的条件下分别导出两种路径方案并显示具体的路线。对此,我们设置了特定情境下数学模型的建立与求解,即假设是从淄博到济南两地,并且路途中车况路况良好,即不发生堵车车子出故障等问题。所以,我们需要收集的信息有从淄博到济南两地之间的具体道路信息以及路线走向等,并且要具体分析若求两地时间最短和距离最短编程时需要哪些信息,哪些信息可以为计算机规划路线等。
在现今飞速的城市化建设中, 人们物质生活质量不断提高, 城市人口数也不断的攀升增长, 公共资源的匮乏以及配置的不合理问题日益突出。如何快速、准确地获取道路实时路况信息, 选择一条最佳路径以避开拥堵路段, 用最短时间到达目的地, 成为目前人们出行最关注的焦点。传统的交通信息采集技术有固定线圈、视频监控和雷达测速等。
针对问题一的最短路径问题,我们建立了最短路径算法模型,通过查找资料,我们找到了一些切实可行的算法,针对其原理及算法实现做了相关讨论和研究,并最终确立了引用dijkstra最短路径算法来实现模型的建立与求解。最终得到了在我们的假设背景下从淄博到济南的最短路径。针对问题而的最短时间问题,我们建立了最短时间算法模型,同问题一略有不同的是最短时间我们采用全程高速的路线,通过对比从淄博到济南的几条高速路线,并结合路线情况以及车况等因素,得出了最短时间的合理路线,实现了对模型的求解与计算。
传统的求最短路径算法,算法的复杂度与节点数 N 的幂次方成正比,如狄克斯特累算法,复杂度为 O(N3) ,当节点数较大时,,因此在算法的时间复杂度上的优越性是极其明显的,而这几种算法与传统算法的精确度、可靠性也相差不大,实践证明: 对于具体问题,本文所探讨的算法具有更大的实用性和可操作性。而对于最短时间算法则是考虑到各方面因素综合权衡,得出结论,所以更具有实用性。
关键词: GPS导航技术;最短路径;最短时间;导航路线;dijkstra最短路径算法。
正文
一. 问题重述
题目要求在GPS导航系统中输入两个地点作为起点和终点,用GPS导航出两地之间时间最短和距离最短的路线并在系统中显示路线,基于现如今日益发达的科学技术与车载GPS技术以及人们对较高生活水平的追求,这无疑具有重大的作用与意义。

随着科学技术的发展和社会的不断进步,人们的生活已经发生了翻天覆地的变化,生活水平也不断提高,出行过程中,GPS导航更是起了很大的作用。所以针对所给题目,要想给出两地之间时间最短和距离最短的导航路线,必须充分了解两地之间的路况信息以及都有哪些路线可供选择,并且要切实比较计算好时间最短和路程最短问题。此外,若用编程实现最短距离和最短路程的求解,还需要了解如何将所知信息输入到计算机中为己所用。给出合理的假设,使问题得以合理求解,建立合理的模型给出最合理的方案是最终目标。

对于给定问题和实际情况,我们做了如下假设:
假设汽车在高速路段行驶车速为100km/