《智能车辆导航系统》PPT课件

《《智能车辆导航系统》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、车载GPS定位技术与应用§1、智能车辆的分类§2、路径规划§3、自主式车辆导航系统的设计§4、中心决定式车辆导航系统的设计第五章智能车辆导航系统6.1智能车辆导航系统的分类智能车辆导航系统是集成了自动车辆定位系统技术、地理信息系统技术、数据库技术、多媒体和现代通信技术等的高科技综合系统。从实现导航功能的角度看，目前可分为两大类：自主式（分布式）车辆导航系统，其定位和路径规划等功能全部在车载设备实现。中心决定式导航系统，它的某些功能需要借助通信网络才能实现。6.2路径规划解决的是：在给定的数字道路地图中寻找从出

2、发地到目的地的最优路线。针对实际应用，可以采用不同的优化标准，如最短行车距离、最少旅行时间、最低通行收费等。计算道路网络中两点之间的最优路线问题都可以归结为求解带权有向图的最短路问题。最短路问题最短路径：就是指在带权有向图中，寻找从指定起点到终点的一条具有最小权值总和的路径。6.2.1经典的最短路算法1、迪杰斯特拉(Dijkstra)算法：由荷兰数学家E.W.Dijkstra于1959年提出的一个适用于非负权值网络的单源最短路算法，是目前求解最短路问题的理论上最完备、应用最广的经典算法，它可以给出从某指定节点

3、到图中所有其他节点的最短路。迪杰斯特拉(Dijkstra)算法主要思想是：按照路径长度逐点增长的方法构造一棵路径树，从而得到从该树的根节点(即指定起点)到其它所有节点的最短路。具体做法是：设集合S存放已经求出的最短路径的终点，初始状态时，集合S中只有一个源点V0。以后每求得一条最短路径(V0，…，Vk)，就将Vk加入到集合S中，直到全部顶点都加入S中为止。51643208562301371732913长度最短路径

4、,V5>813192120按路径长度递增次序产生最短路径算法：1、把V分成两组：（1）S：已求出最短路径的顶点的集合（2）V-S=T：尚未确定最短路径的顶点集合2、将T中顶点按最短路径递增的次序加入到S中，保证：（1）从源点V0到S中各顶点的最短路径长度都不大于从V0到T中任何顶点的最短路径长度（2）每个顶点对应一个距离值S中顶点：从V0到此顶点的最短路径长度T中顶点：从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度3、依据：可以证明V0到T中顶点Vk的最短路径，或是从V0到Vk的直

5、接路径的权值；或是从V0经S中顶点到Vk的路径权值之和。求最短路径步骤1、初始时令S={V0},T={其余顶点}，T中顶点对应的距离值若存在，为弧上的权值若不存在，为2、从T中选取一个其距离值为最小的顶点W，加入S3、对T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值比不加W的路径要短，则修改此距离值4、重复上述步骤，直到S中包含所有顶点，即S=V为止终点从V0到各终点的最短路径及其长度V1V2V3V4V5V6Vj138

6、3032V2:813-------133032V1:13--------------13302220V3:13---------------------192220V4:19---------------

7、-----------------2120V6:20516432085623013717329--------------------------------21--------21每一对顶点之间的最短路径方法一：每次以一个顶点为源点，重复执行Dijkstra算法n次方法二：弗洛伊德(Floyd)算法2、弗洛伊德(Floyd)算法算法思想：逐个顶点试探法求最短路径步骤初始时设

8、置一个n阶方阵，令其对角线元素为0，若存在弧，则对应元素为权值；否则为逐步试着在原直接路径中增加中间顶点，若加入中间点后路径变短，则修改之；否则，维持原值所有顶点试探完毕，算法结束例ACB264311041160230初始：路径：ABACBABCCA046602370加入B：路径：ABABCBABCCACAB0411602370加入A：路径：ABACBABCCACAB0465023