[第六章智能车辆导航系统.ppt

车载GPS定位技术与应用 § 1、智能车辆的分类 § 2、路径规划 § 3、自主式车辆导航系统的设计 § 4、中心决定式车辆导航系统的设计 6.1 智能车辆导航系统的分类 智能车辆导航系统是集成了自动车辆定位系统技术、地理信息系统技术、数据库技术、多媒体和现代通信技术等的高科技综合系统。 从实现导航功能的角度看，目前可分为两大类： 自主式（分布式）车辆导航系统，其定位和路径规划等功能全部在车载设备实现。 中心决定式导航系统，它的某些功能需要借助通信网络才能实现。 6.2 路径规划 解决的是：在给定的数字道路地图中寻找从出发地到目的地的最优路线。针对实际应用，可以采用不同的优化标准，如最短行车距离、最少旅行时间、最低通行收费等。 计算道路网络中两点之间的最优路线问题都可以归结为求解带权有向图的最短路问题。 最短路问题 最短路径：就是指在带权有向图中，寻找从指定起点到终点的一条具有最小权值总和的路径。 6.2.1 经典的最短路算法 1、迪杰斯特拉(Dijkstra)算法： 由荷兰数学家E.W.D ijkstra于1959年提出的一个适用于非负权值网络的单源最短路算法，是目前求解最短路问题的理论上最完备、应用最广的经典算法，它可以给出从某指定节点到图中所有其他节点的最短路。 迪杰斯特拉(Dijkstra)算法主要思想是：按照路径长度逐点增长的方法构造一棵路径树，从而得到从该树的根节点(即指定起点)到其它所有节点的最短路。 具体做法是：设集合S存放已经求出的最短路径的终点，初始状态时，集合S中只有一个源点V0。以后每求得一条最短路径(V0，…，Vk)， 就将Vk加入到集合S中，直到全部顶点都加入S中为止。 求最短路径步骤 1、初始时令 S={V0},T={其余顶点}，T中顶点对应的距离值 若存在V0,Vi，为V0,Vi弧上的权值 若不存在V0,Vi，为? 2、从T中选取一个其距离值为最小的顶点W，加入S 3、对T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值比不加W的路径要短，则修改此距离值 4、重复上述步骤，直到S中包含所有顶点，即S=V为止 每一对顶点之间的最短路径 方法一：每次以一个顶点为源点，重复执行Dijkstra算法n次 方法二：弗洛伊德(Floyd)算法 2、弗洛伊德(Floyd)算法 算法思想：逐个顶点试探法 求最短路径步骤 初始时设置一个n阶方阵，令其对角线元素为0，若存在弧Vi,Vj，则对应元素为权值；否则为? 逐步试着在原直接路径中增加中间顶点，若加入中间点后路径变短，则修改之；否则，维持原值 所有顶点试探完毕，算法结束 6.2.2 算法的时间复杂度估计 （1）一个算法的时间复杂度，就是执行该算法的计算工作量，即算法的时间代价。 为了能够比较客观的评价一个算法的效率，在度量一个算法的工作量时，应该与具体的计算机软硬件因素无关，而只依赖于问题的规模n。 1892年P Bachmann发明了一种表示函数渐进特征的方法，称为大O表示法，它的定义为:当且仅当存在正整数c和n0，使得T(n) cf(n)对所有的n≥n0成立，则称该算法的渐进时间复杂度为T(n)= O(f(n))，简称时间复杂度，它表示当问题规模n充分大时，算法的时间复杂度随n变化。 在使用大O表示法时，需要考虑关键操作的程序步数，在大多数场合里，程序步数与执行频度是一一对应的，如果最后给出的是渐进值，可以直接考虑关键操作的执行频度，找出其与n的函数关系，从而得到渐进时间复杂度。 常见的算法时间复杂度有：常量阶，表示运行时间与问题规模无关或不超过某一常数;线性阶，表示运行时间与问题规模呈线性关系，类似的还有平方阶、 对数阶、指数阶等。 （2）优化运行数据结构 经典Dijkstra算法的核心代码用C语言实现如下: 要降低算法的时间复杂度，关键在于对子循环②加以改进，该子循环的目的是从不断变化的V-S集合中，找出下一条最短路径并返回其父节点指针和累计权值，如果采用各个节点在算法中距离源点的最短路径长度来构造优先级队列，将具有较高优先级的节点放在队列的头部，则能有效提高选择V-S集合中最短路径顶点的效率。 引入堆结构作为优先级队列的存储表示，能大大提高运算效率，k叉堆是一种最普及的堆结构，它把一个关键码集合K = [k0,k1, …，kn-1:}中的所有元素按完全k叉树的顺序存储在一个一维数组中，显然该完全k叉树的高度为[logk(n +k-1)]-1，如图6-1是一个四叉堆优先级队列及其对应的完全四叉树。 堆结构中除了根节点外的所有其它节点i的关键码k[i]必须满足: k[i] ≤k[parent(i)](或者k[i] ≥ k [parent(i)]), i = 1,2,…, n-1 即某个节点的值不小于(不大