《汽车导航系统.pdf》由会员分享,可在线阅读,更多相关《汽车导航系统.pdf(6页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、1/6 汽车导航系统 摘要:汽车GPS导航系统是以全球24颗定位人造卫星为基础,向全球各地全天候地提供三维位置、三维速度等信息的一种无线电导航定位系统。它由三部分构成,一是地面控制部分,由主控站、地面天线、滥测站及通讯辅助系统组成。二是空间部分,由 24 颗卫星组成,分布在 6 个轨道平面。三是用户装置部分,由 GPS 接收机和卫星天线组成。现在民用的定位精度可达 10 米内。本文根据采用图论求两个定点之间的最短路径,其中应用Dijkstra算法(双标号法),即对图中的点 v 进行标号,分别记录 v 到 v 之间的最短路径和 v 到 v 最短路径上前一邻点的下标用来标识路径,从而可以由终点到起
2、点进行反向追踪,最终找到最短路径。然后根据网路标记出最短路径发送给用户,从而问题得以解决。关键词:GPS 导航,图论,最短路径,Dijkstia 算法,综合分析,迭代。2/6 一:问题重述 随着经济和社会的高速发展,时间变得越来越宝贵,在这个越发忙碌的生活里,交通变得让人越来越头痛,人类迫切的想找到这样一种设备来掌握自己的时间,于是导航仪便应用而生,其内置的 GPS 天线会接收到来自环绕地球的 24 颗GPS 卫星中的至少 3 颗所传递的数据信息,结合储存在车载导航仪内的电子地图,通过 GPS 卫星信号确定的位置坐标与此相匹配,进行确定汽车在电子地图中的准确位置,这就是平常所说的定位功能。在定
3、位的基础上,可以通过多功能显视器,提供最佳行车路线,前方路况以及最近的加油站、饭店、旅馆等信息。假如不幸 GPS 信号中断,你因此而迷了路,也不用担心,GPS 已记录了你的行车路线,你还可以按原路返回。当然,这些功能都离不开已经事先编制好的使用地区的地图软件。二:模型假设(一)假设所经过路线的交通情况和拥挤情况一致(二)所走路线车速都相同(三)把车辆与交通路口当作有向图的顶点,忽略质量与形状。3/6 三:符号说明 iV 顶点的标号 sV 起点的标号()iP V 起点sV到iV的最短路径 i iV前面一个邻点的下标 I 标号的点的集合 J 没标号的点的集合 A 弧集 空集 ijw iV到jV路径
4、的权 ijT 顶点到jV最小弧 四:模型建立与求解 步骤 1:给拐点进行编号iV,即有向图的顶点。步骤 2:点sV标号(0,s),表示从1V到1V的距离为 0,sV为起点。步骤 3 找出已标号的点的集合I,没标号的点的集合J,求出弧集(,)|,ijijAv vvI vJ,这个弧集是指所有从已标号的点到未标号的点的集合。步骤 4,如果上述弧集A,表明从所有已经赋予标号4/6 的顶点出发,不再有这样的弧,它的另一顶点尚未标号,则计算结束。对于已标号的顶点,可求得从1V到达这个顶点的最短路,对于没标号的顶点,则不存在从1V到达这个顶点的路。如果弧集A ,转步骤 5。步骤 5,对弧集A中的每一条弧(,
5、)ijv v,计算()ijiijTP Vw 在所有的中,找到其值为最小的弧,假设为(,)stv v。需要注意的是,若上述ijT值为最小的弧有多条,且这些弧的第二个顶点jvv 相同,则表明存在多条最优路径,因此,jv应得到多个双标号。最后,给弧(,)stv v终点tv赋予双标号(),)tP Vs。返回步骤 3。经上述一个循环的计算,将求出1V到一个顶点jv的最短路及长度,从而使一个顶点jv得到双标号。若图中总共有n个顶点,故最多计算1n个循环,即可得到最后结果。求解过程如下,取定顶点和边以后,便可进行计算得到:给定起点1v的标号(0,)s,则表示从1v到1v的距离1()0P v,1v为起点。则开
6、始时标号的集合1 Iv,没标号的点的集合234567891011121314,Jv v v v v v v v vvvvv,弧集1214(,)|,(,),(,)ijijAv vvI vJv vv v 12112()01600TP vw 14114()01800TP vw 5/6 121412min,min1600,18001600TTT米 给弧12(,)v v的终点2v以双标号(1600,1)。这样我们就把距离1v最短路径求出。下面按照图的最短路径方法继续求得第二部为:12,Iv v;34567891011121314,Jv v v v v v v vvvvv;142326(,)|,(,),(
7、,),(,)ijijAv vvI vJv vv vv v 则所求得的弧为:14114()0 18001800TP vw;23223()160016003200TP vw;26226()160042005800TP vw;14232614min,min1800,3200,58001800TTTT;给弧14(,)v v的终点4v以标号为(1800,1)。按照上述类型,我们利用迭代的方法,最终可以得到我们所需要的最短路径。五:模型优缺点分析 本文所建立的模型主要有以下优点:本文利用图论知识求的最短路径,及任意一段也是最短路,采用树生长的过程来求指定顶点到其余顶点的最短路径,综合分析可以知道Dijkstra算法,利用迭代法倒推出那套我们所需的路径,这种方法简明易了,可以迅速求出最短路径。6/6 本文主要有以下缺点:模型假设中是假定路面状况都一致,故每条路线只需考虑距离就行,但实际上这是不对的,路面状况和交通状况,再加上车速,我们需要正确对待这些客观因素。所以该模型可以在时间最短的基础上来改善模型。参考文献:(1)赵静,但琦,数学建模与数学实验,高等教育,2002。(2)吴清烈,尤海燕,运筹学,XX,东南大学,2004.附件:最短路线.jpg
限制150内