《智能交通系统中几种最短路径算法分析.pdf》由会员分享，可在线阅读，更多相关《智能交通系统中几种最短路径算法分析.pdf（3页珍藏版）》请在三一文库上搜索。
1、? 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http:/ 智能交通系统中几种最短路径算法分析 王 林,石金峰 (辽宁工程技术大学 测绘与地理科学学院,辽宁阜新123000 ) 摘 要:最短路径选择是智能交通系统的重要研究课题,它能够根据存储在电子地图中的道路网的拓扑关系,实时 准确地规划出最短路径。目前的最短路径算法主要有4种,即Dijkstra搜索算法 、A3 算法 、A3 优先算法 、A3 双向 分层启发式算法,每一种算法都有不同的执行标准,例如有的算法考虑获取最短
2、路径,但没有考虑算法运行时间;有 的算法同时考虑在运行时间和获取最短路径这两个方面。详细分析这4种算法的路径算法,比较其优劣 。 关键词:Dijkstra搜索算法;A3 算法;A3 优先算法;A3 双向分层启发式算法 中图分类号: TD173 + . 2 文献标识码:A 文章编号:100825696 (2009) 0220110203 Analysis of the Shortest Path Algorithmin ITS WAN G Lin ,SHI Jin2feng (Departmentof Geomatics , Liaoning TechnologyUniversity, Fuxi
3、n 123000 Liaoning, China ) Abstract :The shortest pat h to the IntelligentTransportationSystem is to choose an importantresearch topic , it can be stored in the electronic map of the road networktopologyrelationshipbetween the real2 time and accurate planning of the shortest pat h. At present , the
4、shortest pat h algorit hm , there are four kinds , as : Dijkstraalgorit hm , A 3 algorit hm , A 3algorit hm priority , A 3heuristic two2tiered ; each has a differentmethod of implementationof the standards , such as access to some algorit hm to consider the shortest pat h , but the algorit hm does n
5、ot take the time to run ; some algorit hms running at the same time to consider the time and accessto the shortest pat h to these two areas. This article detailed analysis of the four algorit hms. Key words :Dijkst ra algorit hm ;A 3 algorit hm ;A 3 algorit hm priority ;A 3 heuristic two2tiered 收稿日期
6、:2008212215 作者简介:王 林 ( 1983 ) , 男,硕士研究生,研究方向:大地测量. 随着科技和经济的发展,我国城市的机动车保有量正以 每年15 %的高速率增长,明显超过了交通基础设施的建设速 度 。过多的车辆使我国的城市交通基础设施承受着巨大的 压力 。单纯依赖扩建道路和加强硬件设施来缓解交通问题 的传统方法从经济上和土地资源上都已不可行。为提高交 通效率,减少交通拥挤带来的安全隐患,并减少环境污染和 能源消耗,人们提出了通过综合运用现代信息与通讯技术等 手段的智能交通系统。最短路径计算是智能交通中的最基 础环节,在智能交通中起着至关重要的作用。本文主要通过 对目前最常用的四
7、种最短路径算法的分析来阐述各种方法 的利弊 。 1 Dijkst ra算法 Dijkstra算法是典型最短路径算法,是一种按路径长度 递增的顺序产生最短路径的方法,此方法的基本思想是:以 一个节点V1作为原点,求该节点到其他各节点的最短路径。 把图1中所有节点分成2组,OPEN表存储已经产生但还没 有扩展的节点,CLOSED表存储已经扩展的节点 (最短路径 点)。按最短路径长度递增的顺序,逐个把OPEN表的节点 加到CLOSED表中,直到从V1出发可以到达所有节点都已 包括在CLOSED表 中 。在 这 个 过 程 中,总 保 持 从V1到 CLOSED 表各节点的最短路径都不大于从 V1 到
8、 OPEN 表 的任何节点的最短路径长度。另外,每个顶点对应一个距离 值,CLOSED表的节点对应的距离值就是从V1到此节点的 只包括CLOSED表的节点为中间节点的最短路径长度, OPEN表的节点对应的距离值是从V1到此节点的只包括 CLOSED 表的节点为中间节点的最短路径长度。 Dijkstra 算法主要特点是以起终点为中心向外层层扩 展,直到扩展到终点为止。图1表示了Dijkstra算法的搜索 空间 。Dijkstra算法能得出最短路径的最优解,但由于它遍 历计算的节点很多,所以效率低 。 图1 Dijkstra算法的搜索空间 ? 1994-2009 China Academic Jo
9、urnal Electronic Publishing House. All rights reserved. http:/ 第3期王 林,等:智能交通系统中几种最短路径算法分析 2 A3 算法 A 3 算法是目前广为流行的路径规划启发式算法 ,它是 一种最佳优先搜索算法,对实现道路网的最佳优先搜索十分 有用 4 。A3 算法已应用于各个领域,而不仅仅是车辆路径 规划,如机器人和其他要求最小费用的领域。引入启发式信 息会提高效率 。启发式是一种经验方法,即是一种以牺牲完 备性要求为代价来提高搜索效率的技巧。启发式信息有助 于确定哪个节点 “最有希望” 生成哪些后继节点和修剪那些 相关分支 。通
10、过选择合适的估价函数,A3 算法寻找最优路 径所使用的搜索空间比经典Dijkstra算法小 。采用启发信 息的目的是提供一个节点距离目标节点有多远的估计,以使 搜索算法优先考虑最有希望的节点,即具有最小估价函数的 节点 。定义节点n的启发式估价函数f( n)为 f(n)=g( n) + h (n) . (1) 式中: g( n)是从原点到当前节点n的实际费用, h( n)是从当 前节点到目标节点的最小费用的估计函数,则A3 算法优先 搜索具有最小f( n)的节点 。图2为A3 算法的示例。 图2 A3算法示例 A3 算法的实现步骤如下: 1)设开始的OPEN 表仅包含原节点 ,其费用值为0 ,
11、即g 值为0。令CLOSED表为空,设其他节点的费用为。 2) 若OPEN表为空 ,则宣告失败;否则,选取OPEN 表 中具有最小f 值的点,并叫做最佳节点BEST,把B EST是 目标节点,转至步骤 (3) , 若BEST不是目标节点,则根据地 图数据库包含的联接路段属性扩展并生成B EST的后继节 点 。对于每一个后继节点 n, 进行下列过程: 计算节点n的费用,公式为 g( n) = B EST费用+从B EST到n的费用. 如果n与OPEN表上的人任一节点相同,判断n是否 具有最低的g值,若是最低的g值,用n的费用代替OPEN 表中相同的节点费用,且建立匹配节点的 后 向 指 针 指
12、向 B EST。 如果n在CLOSED表中与一节点相匹配,检查节点n 是否具有最小的g值,如果节点n具有最小的g值,则用节 点n的费用代替匹配节点的费用,并把匹配节点的后向指针 指向B EST ,并把该匹配节点移OPEN表 。 如果n不在OPEN表上,也不在CLOSED表上,则把 n的后向指针指向B EST ,并把n放入OPEN表中 。计算节 点n的估价函数 f(n)=g( n) + h (n) . 重复第二步 。 3) 从B EST节点回溯,即从B EST的后向指针一直到原 节点遍历节点;最后报告解路径。 例如,节点1的启发式距离h(1)是根据A3 原理得到 的 , h (1)是根据 A3
13、原理得到的 ,h (1)计算公式为 h(1)=K? ( X 1-X2) 2 + (Y1-Y2) 2 .(2) 式中: X1、Y1是节点1的坐标, X2、Y2是节点 Z( 目标节点) 的坐标, K是启发式的比例因子,目的使距离变为欧式距离。 从原点到节点1的实际费用g(1)为5 + 4 = 9(5 m是原 点到节点A的距离,4 m是从节点A到节点1的距离)。 3 A3 优先算法 人们通过研究发现,驾驶员喜欢大多数时间在高速公路 上行驶,而不是在交叉口较多的路段行驶。而A3 优先算法 就是根据驾驶员的偏好进行设计的,是A3 算法的改进 。 确保车辆在高速公路上行驶的方法是使除了高速公路 以外的道路
14、使启发式函数 ( 2)乘以一个大于1的数 。如图3 描述了高速公路比其他道路具有较高的优先权。 从图3中可以看出,所有的节点(1 ,2和3)到原点的距 离是相同的 。假设它们的( x, y)坐标相同,那么它们的启发 式函数h( n)也该相同 。 对于正常的A3 算法,被扩展的节点是根据点在OPEN 表中的位置确定的,具有最小估价函数的节点首先被扩展。 但是对于A3 优先算法高速公路被赋予较高的优先权,因 此,节点2将首先被扩展。尽管从原点到节点2的距离等于 原点到节点1、3的距离,通过节点1、3的启发式函数乘以一 个比1大的数值使得节点2的启发式函数比它们小,因此, 节点2将首先被扩展。 ?1
15、11? ? 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http:/ 交 通 科 技 与 经 济 第11卷 图3 A3 优先算法示例 由于高速公路赋予了较高优先权,将获得一个具有驾驶 员偏好的最优路径。这个最优路径可能不是距离最短的,但 可能会更快地到达目的节点,这是由于车辆在高速公路上可 以以较高的速度行驶。通过试验验证,当原点与目标节点不 在一个区域时,A3 优先算法将比A3 算法搜索空间小。 4 A3 双向分层启发式算法 对最短路径算法和A3 算法的研究,将使我们能够
16、把它 们推广至一个双向搜索算法。在前面算法的讨论中,总是假 定算法从给定原节点到目标节点搜索最小费用路径,这被称 为前向搜索 。实际上,从目标节点到原节点进行后向搜索应 该产生同样的结果(只要每一条路段原费用是相同的 ) , 通常 称为后向搜索,这导致了双向搜索的思想。 双向搜索的基本过程是从原节点到目标节点计算最小 费用路径(前向搜索) ,同时,计算从目标节点到原点的最小 费用路径 (后向搜索)。如果搜索算法在单处理机上运行,算 法必须在前面和后面搜索之间迅速切换,双向搜索至少可以 减少搜索空间50 % ,因此,算法的运行时间比非双向搜索少 很多 。由A3 算法检查的搜索空间与双向搜索算法检
17、查的 搜索空间之间的一般关系如图4所示 。 图4 单向和双向搜索启发式搜索的搜索空间 理想情况是双向搜索在中间相遇,但是如果从原节点 到目标节点存在N条不同的路径,搜索可能不在中间相遇, 2种搜索可能在相遇前几乎找到完整路径,或者一个找到完 整路径而另一个在它们相遇前几乎找到一条完整路径。换 言之,存在重复工作。例如一个仅考虑旅行费用的启发式估 价函数的不正确终止标准,可能导致双向启发式搜索工作量 为单向启发式搜索的2倍 。因此,终止标准和启发式估价函 数的选择对于正确执行双向启发式搜索很重要。 为了消除这种最坏情况,必须设计一个较好的前向和后 向启发式搜索切换标准。在双向算法中。前向和后向搜
18、索 算法不是交替进行的,它取决于最佳节点的启发式估价函数 f( n)。如果在前向搜索中当前节点的估价函数小于后向搜 索当前节点的估价函数,这就意味着在前向搜索中当前节点 更靠近目标节点,此时执行前向搜索。反之,则执行后向搜 索 。因为2个方向的搜索不是交替执行的,能够大大地节省 算法的运行时间。 路网具有很自然的分层结构,高速公路在顶层,而人行 横道在底部,这导致一个更有效的分层搜索算法的思想。基 本思想是首先进行抽象空间的搜索,而不是在整个原有问题 空间搜索 。抽象空间是问题空间的简化,即忽略了不重要的 细节(例如先在高速公路的路段上进行搜索 ) , 然后再搜索抽 象空间获得结果的基础上再添
19、上原有空间的细节。选择简 化的表达可以导致问题求解能力和效率的提高。 为了实现分层搜索算法和简化路径规划任务,导航地图 数据库需要分层构造,分层地图数据库的层数越高,抽象表 达的细节越少。因为一个较高层的抽象空间比它底层的搜 索空间要含较少的节点和线段,所以在抽象空间的搜索常常 产生不完全的解(但为了减少搜索时间)。抽象空间的节点 可以是原空间的区域或原始节点的子集,显然在搜索过程中 需要在不同层次间切换,以充分利用分层结构。在层次切换 和决定何时切换到不同层过程中,避免系统额外的开销对算 法的效率起着重要作用。 与其他算法相比,双向启发式分层搜索的搜索空间最 小,当原点和目标节点相距较远时,
20、此算法的运行时间最短。 实际上,构造一个满足所讨论的最佳抽象分层条件的数 据库或者算法是非常困难的。对车辆导航来说,用道路级别 为路径规划定义一个分层结构是很自然的。尽管达到理论 上的最佳分层是困难得,但基于分层搜索的双向启发式搜索 在非常大的地图数据库中进行路径规划仍是最流行算法。 5 结束语 通过对4种算法的时间复杂度进行分析,得出如下结 论: 1) 原节点与目标节点在同一区域内搜索 20 个节点 : Djikstras算法所花费的时间为425 s ,平均用时21. 3 s,排名 第4 ;A3 单向搜索算法所花费的时间为92 s ,平均用时4. 6 s ,排名第2 ;A 3 优先搜索算法所
21、花费的时间为 82 s,平均用 时4. 1 s ,排名第1 ;A3 双向分层搜索算法所花费的时间为 106 s ,平均用时5. 3 s,排名第3。 2)原节点与目标节点不在同一区域内搜索20个节点: Djikstras 算法所花费的时间为 1 040 s ,平均用时52 s,排名 第4 ;A3 单向搜索算法所花费的时间为241. 4 s平均用时 12. 07 s ,排名第3 ;A3 优先搜索算法所花费的时间为225 s, 平均用时11. 25 s ,排名第2; A3 双向分层搜索算法所花费 的时间为194. 2 s ,平均用时9. 71 s,排名第1。 通过以上结论可以看出当原节点与目标节点在
22、同一区 域时,使用A3 优先搜索时间最短,效率最高;当原节点与目 标节点在不同区域时,使用A3 双向分层搜索算法搜索时间 最短,效率最高,其次是A3 优先搜索算法。 参考文献 1黄 卫,陈里得.智能运输系统(ITS )概论 M .北京:人民交通出 版社,2001. 2寇有观.城市智能运输系统的分析与设计J .交通与计算机, 2001 ,31 (1) :8212. 3王震宇,黄 卫.中国智能运输系统体系结构发展研究J .东南 大学学报:自然科学版,2001 ,31 (3) :85289. 4杨佩昆.智能交通运输系统体系结构 M .上海:同济大学出版 社,2001. 5王 炜,徐吉谦.城市交通规划理论及应用 M .南京:东南大学 出版社,1998.责任编辑:张德福 ?211?