交通限制条件下的最短路径算法分析与优化 路径算法分析new

《交通限制条件下的最短路径算法分析与优化 路径算法分析new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第22卷第1期测绘学院学报Vol.22No.12005年3月JournalofInstituteofSurveyingandMappingMar.2005文章编号!1009-427X(2005)01-0062-03交通限制条件下的最短路径算法分析与优化许志海!张昭云"信息工程大学测绘学院!河南郑州450052#摘要!通过对交通网络本身的特点及要求的分析与研究9介绍了一些适合道路网的经典最短路算法和数据存贮模式9探讨了在交通网络路线优化过程中需要特别处理的几个问题9如路口延误禁行状态等9并在理论上给出了相应的解决方案O最后给出了一个路径搜索

2、的实例O关键词!交通网络;最短路径;Distra算法;启发式搜索;交通信息中图分类号!P2S2文献标识码!A地理网络分析是空间分析的一个重要方面常与两点之间的直线距离和方向存在定的关是依据地理网络拓扑关系并通过考察地理网络系其几何和拓扑特性有助于问题的求解元素的空间属性数据对网络的性能特征进行多!."最短路径算法分析方面的分析计算在基于交通网络的地理网络分最短路径问题可分为多种类型在基于交通析中主要包括路径分析服务中心范围的确定网络的路径分析中单源最短路径问题更具有普可达性分析等其核心是对最短路径的求解遍意义其算法有很多种其中采用及启发策略

3、的Distra算法是目前已知的理论上最完善的算法!基于交通网络的最短路径算法分析和优化它以极强的抗差性而得到广泛的普及和应用!.!交通网络的定义及特点!.".!道路网的存贮交通网络一般根据图论的基本理论抽象为赋对于交通网络的表示通常使用的方法是以1权图可以形式化定义为图论为基础根据平面图特性的存储方式常用的ROadWOrk=VR有邻接矩阵邻接表邻接多重表和十字链表等邻接矩阵由于其空间复杂度高一般为O12N=aa6NOdeset+R=NR1。m和关联节点查询速度慢一般为O1而NR=taNyLaN＞aN6V不适于稀疏图的存贮邻接多重表和十字

4、链表由其中V是道路的节点集NR表示道路网中两个于结构和操作比较复杂在实践中的应用也仅限于节点的拓扑关系集合有序对taNy表示节点某些专有领域对于交通网络的存贮和管理邻接a和N之间的一条边谓词LaN表示节点a到表使用最为广泛其空间复杂度为Om+1对于N的通路边权可以用边的几何长度或者长度和路径分析中的关键操作关联节点的查询也其他因素的加权和表示设1=N为一个具体可认为是Om1另外在路径分析算法的实现网络的节点数目m=V为网络中边的数目中对于类似于交通网络的大型稀疏图图的构建交通网络可以看成是带权有向不完全稀疏与撤销耗费的时间是相当可观

5、的对于用邻接矩图它具有以下的特点由于存在转向限制和道路阵表示的图它的构建与撤销分别至少需要122行驶方向限制所以它是有向图存在立体交叉道步即使采取最大相关点或最大相关边法虽然路它是非平面图对于道路网上的一对节点P在一定程度上降低了邻接矩阵在存贮上的空间复G总存在P到G的路径反之亦然因此是强连杂度但要搜索节点的最大相关点或最大相关边通的道路网对应的有向图是不完全的不规范的数目也要耗费大量的时间而且还是具有大量的节点度数不一通常小于5且mO1。1+的无效数据因此在交通网络这样的大型稀疏图12因此是稀疏图交通网络在空间上存在着局应用邻接表来存贮数

6、据已经成为业界的共识其部相关性即任意两节点AB之间的最短路径通表示根据应用角度不同可以分为顺序邻接表收稿日期!2004-09-21;修回日期!2004-12-1S作者简介!许志海(1970-)9男9河南睢县人9博士生9主要从事GIS3S集成研究O第1期许志海等交通限制条件下的最短路径算法分析与优化63FSForWardStar和逆向邻接表BS在一个典型的道路网中假设起点s与终点d最短3BackWardStar等路径长度为z则算法检查的顶点大致落在由点a!."."最短路径常用算法分析的位置所定义的椭圆内其中z=Dista1cesa对于Dik

7、stra算法的改进主要集中于网络存+Dista1ceda对于搜索的节省量的准确分析贮的空间复杂度和算法实现的时间复杂度以及为比较困难对于典型的利用A。方法在类似于道了满足某些具体应用进行一些特殊限制等方面路网这样的稀疏图可得到与112成正比的期望2基于堆结构和桶结构优先级队列的LS算法是研运行时间35"7究得最深入应用也最广泛文献4在基于真!.".$分层路径搜索实交通网络的基础上对17种常用算法中的15种路网图的规模是影响最优路径搜索时间的主进行了验证根据结果给出了基于邻接表的一种要因素如果用合理的方法减少搜索所涉及的顶图存贮结构并推荐了其

8、中的3种算法T@@点和弧的数量将会使路径规划获得有效的加速DKA以及DKD其中T@@算法的基础是图增长采用基于多层地图的分级搜索技术可以实现对路6理论较适合于计算单源点到其他所有