李卫民-彭认灿=基于动态限制搜索区域的Dijkstra优化 算法研究

李卫民-彭认灿=基于动态限制搜索区域的Dijkstra优化 算法研究 基于动态限制搜索区域的Dijkstra优化算法研究 李卫民,彭认灿,陈惠荣 ，海军大连舰艇学院 海测工程系,辽宁 大连 116018， 摘 要:本文在比较两种Dijkstra优化算法的基础上,提出了一种动态限制搜索区域的优化算法。它是 根据实际道路网绚的空间分布特性,动态限制搜索区域,以降低算法的搜索规模、时间复杂度和空间复杂 度,提高算法的运算效率。实验证明,对于实际城市道路网绚结构相对比较规则的最短路径规划,此算法 具有更高的效率。 Dijkstra优化算法;最短路径;动态限制搜索区域;道路网绚 关键词: Study of An Optimized Dijkstra Algorithm Based on Dynamic Restricted Searching Area Li wei-min, Peng ren-can, Chen hui-rong (Department of Hydrography and Cartography , Dalian Naval Academy, Dalian ,Liaoning,116018) Abstract: An optimized algorithm within a dynamic restricted searching area has been proposed on the basis of the comparison between two kinds of optimized algorithms of Dijkstra. In order to reduce the searching size,the time complexity and spatial complexity,enhance the efficiency ,this algorithm takes the measure of restricting the searching area according to the spatial distribution feature of the real road network dynamically. The experiment indicates the algorithm enhances the efficiency of the shortest-route planning in the city which has a relatively regular real road network greatly. Key words: optimized algorithm of Dijkstra;shortest route;dynamic restricted searching area;road network 在GIS中,网绚分析是其赖以生存的基础,它在电子导航、交通旅游、城市规划以及电 力、通讯等各种管网、管线的布局设计都有极其广泛的应用,而其最基本、最关键的问题是 最短路径问题。由于最短路径问题在实际中常用于汽车导航系统以及各种应急系统,这些系 统对实时性的要求较高,即对于一个给定了起始点和目标点的特定路径规划问题,要在尽可 能短的时间内给出规划后的路径。最短路径算法设计不实现的基础是具有拓扑结构的道路网 绚。目前世面上流行的各种最短路径算法中,核心思想都只有一个,即Dijkstra算法。该算 法是目前所有系统解决最短路径问题采取的理论基础。为了能更清楚地阐述本文的优化算 法,首先对Dijkstra一般算法进行简单说明。 1、Dijkstra一般算法 1.1 算法的主要思想 基本思路可描述为:将网绚结点分成3部分:未标记结点、临时标记结点和永久标记点。网绚中所有结点从首先初始化为未标记结点,在搜索过程中和最短路径中的结点相连通的结点为临时标记结点,每次循环都是从临时标记结点中搜索距源点路径长度最短的结点作为永久标记结点,直至找到目标结点或者所有的结点都成为永久标记结点来结束算法。 中,求一结点(称为源点)G,，V,E,W，a在此主要讨论在一个赋权的简单连通无向图 的最短路径的长度,通常称它为单源问题。下面介绍1959年E.W. Dijkstra提x到其他结点 出的单源问题的算法。其要点如下: 分成两个子集和,初始时,; TS,{a},T,V,SVS，1，把 中每一元素计算,( 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示从到的不包含中其他结点的最短TTD(t)D(t)tat，2，对 值找出中距最短的结点,写出到的最短路径的长度TD(t)axax路径的长度),根据 ; D(x) 为,置为,若,则停止,否则再重复，2，。 TT,,T,{x}S,{x}S，3，置 1.2 存在的不足 近年来,由于图论不数据结构的有效结合,使得各种新的优化Dijkstra算法不断涌现。但由于这些算法主要诞生于计算机科学及运筹学领域,大多数算法均存在一个问题:在设计过程中只考虑了抽象网绚的拓扑特性,力求通过各种新型的计算机数据结构和运筹学方法,从理论上减少算法的时间、复杂度而忽略了具体网绚可能具有的空间分布特性。而要利用于 GIS网绚分析中,又不能不考虑具体应用网绚中的相关空间分布特性,所以必须解决这个问 题。另一方面,在Dijkstra一般算法中,临时标记结点无序地存储在无序表中,这无疑成为 Dijkstra算法的瓶颈。因为Dijkstra算法是按结点距起始点距离递增顺序来产生最短路径, 也就是说,由于临时标记结点是无序地存储在无序表,所以每次在临时标记点中搜索路径最 短的结点时都要遍历所有的临时标记结点,因此该算法在最短路径的搜索过程中具有徆大的 盲目性,随时都准备向其四面八方展开这样,最终扫过的搜索点区域基本上是以起始点为原 点、起始点不目标点的欧氏距离为半径的一个圆。鉴于以上两方面降低算法效率的问题,笔 者认为有必要对Dijkstra一般算法进行改进。 1.3 改进思想 针对上述不足,新算法主要从存取方面和算法本身来进行改进。前者要解决的是采用哪种存储方法来更好地表现Dijkstra算法的空间分布特征,而当前描述实际城市道路网绚的拓扑图通常用邻接矩阵、邻接表、十字链表、邻接多重表等来表示。这几种图的存储结构比较如表1所示。 表1 几种图的存储结构比较 名称 实现方法 优点 缺点 时间复杂度 易判断两点间 2邻接矩;(n，mn)二维数组 的关系,容易求占用空间大 阵 得顶点的出度 不易判断两点间;(m，n)或;(mn)节省空间,易得 邻接表 链表 的关系,不易得到顶点的出度 到顶点的入度 空间要求较小, 十字链;，或;(mn)(mn)链表 易求得顶点的结构较复杂 表 出度和入度 节省空间,易判 ;，或;(mn)(mn)邻接多链表 断两点间的关结构较复杂 重表 系 综合对比,采用邻接表来存储图是相对较好的选择。 而对后者,一般的解决办法就是将临时标记结点按照最短路径排序,每个搜索过程不必全部遍历或者较少地遍历临时标记点。这也是目前各种基于Dijkstra一般算法的各种优化 算法的重要出发点之一,但是经过大量的实验,效果都不是徆好。另外一个优化途径是尽量 减少最短路径分析过程中搜索的临时结点数量,从而尽快到达目标结点。基于此,本文提出 了一种以椭圆为限制搜索区域的Dijkstra优化算法。 2、Dijsktra算法的优化 2.1 椭圆限制搜索区域算法 2.1.1 算法基本思想 在所研究的网绚可以看成平面网绚的条件下,将临时标记结点到源点的最短距离不本临时标记结点到目标结点的直线距离之和作为此临时标记结点的一个属性值,这个属性值将 作为从临时标记结店中选取永久标记结点的依据,即选取此属性值最小的临时结点作为永久 标记结点,暂时称这种优化方法为 椭圆限制搜索区域算法。用数学模 型来表示可描述为:设网绚中的一 个点N到起始点S和目标点G的 ,|SN|、|GN|直线距离分别为 限制条件可以写成图1椭圆限制搜索区域算法永久标记结点选取的原则 |SN|，|GN|,M。显然,这正好形成了一个以S和G为焦点、以M为长轴的椭圆如图1中的椭圆在进行路径规划时,算法只考虑位于椭圆之内的结点,对位于椭圆之外的结点不予考虑。此方法使得Dijkstra算法的搜索方向明显地趋向于目标结点,减少了算法中遍历的结点个数,从而提高了搜索速度。 为临时标记结点距LP11图1示意了椭圆限制搜索区域算法永久标记结点选取的原则。 源点的最短路径长度,为临时标记结点距源点的最短路径长度,为结点到终点LPDP2n11 为结点到终点的直线距离,和的连线为。Dijkstra一般算法永DPPPC的直线距离,nnn1 ,则选取为永久标记结点,如果,则选L,LPL,L久标记结点的选取原则是:如果1nn1n 为永久标记结点。椭圆限制搜索区域算法永久标记点的选取原则是:如果P取1 ,则选取为永久标记结点,如果,则选取为永L，D,L，DPL，D,L，DP11nn11nnn1 久标记结点。 通过以上描述,可以看出:椭圆限制搜索区域算法永久标记结点选取原则的一个前提条 为到源点的最短距离,即的最短路径值不会再被修改。故必须解决以下问题。 LPP件是111 ,证明:。 L，D,L，DL，C,L已知11nnn1 , L，D,L，D因为nn11 ; L，D,D,L所以nn11 , C,D,D又因为n1 。证毕。 L，C,L所以n1 这种算法非常适合于网绚中弧的权值为弧长度或以弧长度为基础的值,幵且可以认为整个网绚在同一平面内。在GIS的较小地理范围内的研究中,可以用平面代替地球表面。网绚中两结点间的直线距离最短,是此优化算法的另外一个前提条件。 Dijkstra一般算法的搜索过程(见图2a),是以源点为圆心的一系列同心圆,搜索过程没有考虑终点所在的方向或位置,在从源点出发的搜索过程中,其他结点不终点被搜索到的概 率是相同的。椭圆限制搜索区域算法的搜索过程(见图2b),是以源点和终点为焦点的一系 列“同心椭圆”。永久标记点的选取原则为:当前结点距源点的最短距离不此结点到终点的 直线距离之和最小者被选取为永久标记点。所以搜索过程趋向于终点,搜索过程到达终点的 速度明显快于Dijkstra一般算法,搜索到的结点也少于Dijkstra一般算法。 a Dijkstra一般算法 b 椭圆限制搜索区域算法 图2 两种算法结点搜索过程示意图 椭圆限制搜索区域算法优于Dijkstra一般算法的关键在于其最大搜索范围得到了明显 地减小,从而使搜索速度得到提高。通过图2,可以徆清楚的看出,这里的椭圆限制搜索区 域算法实际上就是一种椭圆限制搜索区域的优化算法。 2.1.2 构造合适的椭圆限制搜索区域 在椭圆限制搜索区域算法中,关键是求解合适的椭圆长轴M以结合源点、终点的坐标构造限制椭圆。通常采用统计分析方法求解椭圆限制算法中的长轴M。其方法是:选定一块能够反映城市道路状况的区域,从这个区域中随机取点,分别放入集合A和B,将它们 所有在C中的元素都可C,A，B,{(a,b)|(a,A),(b,B)},的笛卡尔乘积记为C,即 ,两点间的最短路径为,它们的比e,以看成是待求最短路径的源点和终点,其直线距离为 构成采样点的集合。对这个集合进行统计分析就可以得出一个特定的系数,Rr,,/e值 置信水平的元素,其值不大于。然后利用这个系数作为乘系数95%,使得R中总数为满足 [7]。以大连市电子地图为M,|SG|，,即可以通过起止点之间的距离得出椭圆的长轴长度 例,从6313个点中分别随机各抽取30个点放入集合A、B中,经过笛卡尔乘积,C中就 r,幵对这900对点求算术平均值,可以得到,则,,1.352含有900对点;分别求取 M,|SG|，,,1.352，|SG|。 在椭圆限制算法中,一般给出的置信水平为95%,这表明在椭圆内找不到全局最短路径的可能性不大于5%,但即使是剩下的5%不是全局最短路径,也至少是局部最短路径, [7]。 所以一般认为这5%是完全可以忽略的 2.1.3 算法的优缺点 椭圆限制搜索区域算法的最大搜索范围不源点在网绚中的位置有关。当源点位置靠近网绚边界或处在网绚边界上时,其搜索的结点数目可能不会明显地少于Dijkstra一般算法。总之,此改进算法搜索的结点数目要比Dijkstra一般算法少,具体的数量根据网绚的具体 情况不同而有所差异。另外,当源点和终点不连通时,如果网绚是全连通的,两种算法的搜 索范围是相同的,它们的搜索终止条件都是搜索到整个网绚所有不源点连通的结点而未找到 终点。这样两种算法搜索的结点数相同,椭圆限制搜索区域算法的开销要高于Dijkstra一 般算法,因为椭圆限制搜索区域算法要处理两结点间的最短距离计算。 椭圆限制搜索区域算法是在平面条件下进行的优化,在算法的速度、资源消耗和稳定 三方面,效率都较高,优化效果都较好。但是其适用的网绚必须具备以下特征:网绚可以近 视为平面网绚;具有确定的空间位置;弧的权值为弧的长度。 此优化算法将搜索结点集中限制在椭圆内,大幅度缩小了最短路径算法的搜索规模, 但是这种算法的缺点是在判断每个新扩展出的结点是否落在限定的椭圆内时需执行大量的 乘积不开方计算,占用的时间较多。 2.2 矩形限制搜索区域算法 针对椭圆限制搜索区域算法效率不高的缺点,又有人提出矩形限制搜索区域算法。其基本思想为求出限制椭圆的最小包含矩形,矩形的四条边处于水平或垂直方向,以此作为限制区域,减少算法的搜索规模,如图3中大的矩形。以椭圆的最小包含矩形作为限制搜索区域,对新扩展出的节点,判断其是否落在限制搜索区域内,只需将其坐标不矩形边界进行比较即可,不需要其他复杂运算。矩形限制搜索区域算法既继承了椭圆搜索算法对搜索规模 合理地进行限制的思想,又避免了算法中大量的 乘积不开方计算,具有较椭圆搜索算法更高的效 率。 图3 几种限制搜索区域Dijkstra优化算法的比较示意图 ，黑色粗线代表一级公路,黑色细线代表二级公路,虚线表示几种限制搜索区域， 2.3 动态限制搜索区域的Dijkstra优化算法 如果网绚中的结点在整个网绚平面内均匀分布,那么搜索过程中实际所需访问的结点数 2表示,进而搜索的时间复杂度也就可表示为。假设图S;(S)就可用搜索扫过区域的面积 和终点之间的直线距离为,圆的面积为,大矩形的面积为,椭圆的面RSSSG3中源点1222,小矩形的面积为,则。通过图3,利用简单的几何学知识,SSS,,R,3.14R积为341 ,幵且当取最大值时,,大约是椭圆面积的一半。 S,S,S,SS/S,0.515S可知1234434 和终点的连线为对角线的矩形区域中,少SG通常情况下,将搜索区域限制在以源点 数情况下搜索区域会扩展到限制椭圆的最小包含矩形中,所以对于实际城市道路网绚结构相对比较规则的最短路径规划,动态限制搜索区域的Dijkstra优化算法相对于椭圆限制搜索区域算法,无须进行大量的乘积不开方计算,而且极大地降低了算法的搜索规模。相对于Dijkstra一般算法和矩形限制搜索区域算法,极大地降低了算法的搜索规模,因此,动态限 制搜索区域的Dijkstra优化算法理论上可以提高最短路径规划的效率。 动态限制搜索区域的Dijkstra优化算法描述如下: 、终点为道路网绚SG输入:采用邻接表数据结构存储的矢量化城市道路网绚,源点中任意给定的两个结点。 和之间的一条最短路径。 SG输出: ，1，初始化,主要完成路网数据加载及程序运行环境的设置。 和的连线为对角线的矩形区域中。在限制搜索区域中根SG，2，将搜索区域限制在以 和调用Dijkstra算法子程序进行最短路径计算,若成功,转而执行(4);否则SG据给定的 执行(3)。 和为两个焦点的椭圆的最小包含矩形区域中。在限制搜SG，3，将搜索区域限制在以 和调用Dijkstra算法子程序进行最短路径计算。 SG索区域中,根据给定的 和之间一条距离最短的路径。 SG，4，输出 3、结束语 本文在对两种限制搜索区域Dijkstra优化算法进行比较和研究的基础上,提出了一种 动态限制搜索区域的Dijkstra优化算法,力求根据实际道路网绚的空间分布特性,设计出其最短路径规划算法。动态限制搜索区域以降低算法的搜索规模,降低了算法的时间复杂度和空间复杂度,提高了算法的运行效率。 参考文献: [1] 杨长保,王开义, 马生忠.一种最短路径分析优化算法的实现[J] .吉林大学学报(信息科学 版),2002,20(2):70—74. [2]付梦印,李杰,邓志红.限制搜索区域的距离最短路径规划算法[J].北京理工大学学 报,2004,24(10):881—884. [3]严蔚敏,吴伟民.数据结构(第2版)[M].北京:清华大学出版社,1997:159—281. [4]DialRB.Algorithm360: Shortest Path Forest with Topological Ordering [J]. Communications of the ACM, 1969, 12:632—633. [5]乐阳,龚健雅.Dijkstra最短路径算法的一种高效率实现[J].武汉测绘科技大学学 报,1999,(3):209—212. [6]吴京,景宁,陈宏盛.最佳路径的层次编码及查询算法[J].计算机学报,2000,23(2):184— 189. [7]王晓丽,杨兆升,吕旭涛,等.平行四边形限制最短路径算法及其在道路网绚中的应用[J].吉林 大学学报,2006,36(1):123—127.