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

基于动态限制搜索区域的Dijkstra优化算法研究李卫民，彭认灿，陈惠荣（海军大连舰艇学院海测工程系，辽宁大连116018）摘要:本文在比较两种Dijkstra优化算法的基础上，提出了一种动态限制搜索区域的优化算法。它是根据实际道路网络的空间分布特性，动态限制搜索区域，以降低算法的搜索规模、时间复杂度和空间复杂度，提高算法的运算效率。实验证明，对于实际城市道路网络结构相对比较规则的最短路径规划，此算法具有更高的效率。关键词:Dijkstra优化算法；最短路径；动态限制搜索区域；道路网络StudyofAnOptimizedDijkstraAlgorithmBasedonDynamicRestrictedSearchingAreaLiwei-min,Pengren-can,Chenhui-rong(DepartmentofHydrographyandCartography,DalianNavalAcademy,Dalian,Liaoning,116018)Abstract:AnoptimizedalgorithmwithinadynamicrestrictedsearchingareahasbeenproposedonthebasisofthecomparisonbetweentwokindsofoptimizedalgorithmsofDijkstra.Inordertoreducethesearchingsize，thetimecomplexityandspatialcomplexity，enhancetheefficiency，thisalgorithmtakesthemeasureofrestrictingthesearchingareaaccordingtothespatialdistributionfeatureoftherealroadnetworkdynamically.Theexperimentindicatesthealgorithmenhancestheefficiencyoftheshortest-routeplanninginthecitywhichhasarelativelyregularrealroadnetworkgreatly.Keywords:optimizedalgorithmofDijkstra；shortestroute；dynamicrestrictedsearchingarea；roadnetwork在GIS中，网络分析是其赖以生存的基础，它在电子导航、交通旅游、城市规划以及电力、通讯等各种管网、管线的布局设计都有极其广泛的应用，而其最基本、最关键的问题是最短路径问题。由于最短路径问题在实际中常用于汽车导航系统以及各种应急系统，这些系统对实时性的要求较高，即对于一个给定了起始点和目标点的特定路径规划问题，要在尽可能短的时间内给出规划后的路径。最短路径算法设计与实现的基础是具有拓扑结构的道路网络。目前世面上流行的各种最短路径算法中，核心思想都只有一个，即Dijkstra算法。该算法是目前所有系统解决最短路径问题采取的理论基础。为了能更清楚地阐述本文的优化算法，首先对Dijkstra一般算法进行简单说明。1、Dijkstra一般算法1.1算法的主要思想基本思路可描述为：将网络结点分成3部分：未标记结点、临时标记结点和永久标记点。网络中所有结点从首先初始化为未标记结点，在搜索过程中和最短路径中的结点相连通的结点为临时标记结点，每次循环都是从临时标记结点中搜索距源点路径长度最短的结点作为永久标记结点，直至找到目标结点或者所有的结点都成为永久标记结点来结束算法。在此主要讨论在一个赋权的简单连通无向图WEVG,,中，求一结点a(称为源点)到其他结点x的最短路径的长度，通常称它为单源问题。下面介绍1959年E.W.Dijkstra提出的单源问题的算法。其要点如下：（1）把V分成两个子集S和T，初始时，SVTaS},{；（2）对T中每一元素t计算)(tD，()(tD表示从a到t的不包含T中其他结点的最短路径的长度)，根据)(tD值找出T中距a最短的结点x，写出a到x的最短路径的长度)(xD；（3）置S为}{xS，置T为}{xT，若T，则停止，否则再重复（2）。1.2存在的不足近年来，由于图论与数据结构的有效结合，使得各种新的优化Dijkstra算法不断涌现。但由于这些算法主要诞生于计算机科学及运筹学领域，大多数算法均存在一个问题：在设计过程中只考虑了抽象网络的拓扑特性，力求通过各种新型的计算机数据结构和运筹学方法，从理论上减少算法的时间、复杂度而忽略了具体网络可能具有的空间分布特性。而要利用于GIS网络分析中，又不能不考虑具体应用网络中的相关空间分布特性，所以必须解决这个问题。另一方面，在Dijkstra一般算法中，临时标记结点无序地存储在无序表中，这无疑成为Dijkstra算法的瓶颈。因为Dijkstra算法是按结点距起始点距离递增顺序来产生最短路径，也就是说，由于临时标记结点是无序地存储在无序表，所以每次在临时标记点中搜索路径最短的结点时都要遍历所有的临时标记结点，因此该算法在最短路径的搜索过程中具有很大的盲目性，随时都准备向其四面八方展开这样，最终扫过的搜索点区域基本上是以起始点为原点、起始点与目标点的欧氏距离为半径的一个圆。鉴于以上两方面降低算法效率的问题，笔者认为有必要对Dijkstra一般算法进行改进。1.3改进思想针对上述不足，新算法主要从存取方面和算法本身来进行改进。前者要解决的是采用哪种存储方法来更好地表现Dijkstra算法的空间分布特征，而当前描述实际城市道路网络的拓扑图通常用邻接矩阵、邻接表、十字链表、邻接多重表等来表示。这几种图的存储结构比较如表1所示。表1几种图的存储结构比较名称实现方法优点缺点时间复杂度邻接矩阵二维数组易判断两点间的关系，容易求得顶点的出度占用空间大邻接表链表节省空间，易得到顶点的出度不易判断两点间的关系，不易得到顶点的入度)(2mnn)()(mnnm或十字链表链表空间要求较小，易求得顶点的出度和入度结构较复杂邻接多重表链表节省空间，易判断两点间的关系结构较复杂综合对比，采用邻接表来存储图是相对较好的选择。而对后者，一般的解决办法就是将临时标记结点按照最短路径排序，每个搜索过程不必全部遍历或者较少地遍历临时标记点。这也是目前各种基于Dijkstra一般算法的各种优化算法的重要出发点之一，但是经过大量的实验，效果都不是很好。另外一个优化途径是尽量减少最短路径分析过程中搜索的临时结点数量，从而尽快到达目标结点。基于此，本文提出了一种以椭圆为限制搜索区域的Dijkstra优化算法。2、Dijsktra算法的优化2.1椭圆限制搜索区域算法2.1.1算法基本思想在所研究的网络可以看成平面网络的条件下，将临时标记结点到源点的最短距离与本临时标记结点到目标结点的直线距离之和作为此临时标记结点的一个属性值，这个属性值将作为从临时标记结店中选取永久标记结点的依据，即选取此属性值最小的临时结点作为永久标记结点，暂时称这种优化方法为椭圆限制搜索区域算法。用数学模型来表示可描述为：设网络中的一个点N到起始点S和目标点G的直线距离分别为|GN|||、SN，限制条件可以写成。M|GN||SN|显然，这正好形成了一个以S和G为焦点、以M为长轴的椭圆如图1中的椭圆在进行路径规划时，算法只考虑位于椭圆之内的结点，对位于椭圆之外的结点不予考虑。此方法使得Dijkstra算法的搜索方向明显地趋向于目标结点，减少了算法中遍历的结点个数，从而提高了搜索速度。图1示意了椭圆限制搜索区域算法永久标记结点选取的原则。1L为临时标记结点1P距源点的最短路径长度，2L为临时标记结点nP距源点的最短路径长度，1D为结点1P到终点的直线距离，nD为结点nP到终点的直线距离，1P和nP的连线为C。Dijkstra一般算法永久标记结点的选取原则是：如果nLL1，则选取nP为永久标记结点，如果nLL1，则选取1P为永久标记结点。椭圆限制搜索区域算法永久标记点的选取原则是：如果nnDLDL11，则选取nP为永久标记结点，如果nnDLDL11，则选取1P为永久标记结点。通过以上描述，可以看出：椭圆限制搜索区域算法永久标记结点选取原则的一个前提条件是1L为1P到源点的最短距离，即1P的最短路径值不会再被修改。故必须解决以下问题。图1椭圆限制搜索区域算法永久标记结点选取的原则)()(mnnm或)()(mnnm或已知nnDLDL11，证明：1LCLn。因为11DLDLnn，所以11LDDLnn；又因为1DDCn，所以1LCLn。证毕。这种算法非常适合于网络中弧的权值为弧长度或以弧长度为基础的值，并且可以认为整个网络在同一平面内。在GIS的较小地理范围内的研究中，可以用平面代替地球表面。网络中两结点间的直线距离最短，是此优化算法的另外一个前提条件。Dijkstra一般算法的搜索过程(见图2a)，是以源点为圆心的一系列同心圆，搜索过程没有考虑终点所在的方向或位置，在从源点出发的搜索过程中，其他结点与终点被搜索到的概率是相同的。椭圆限制搜索区域算法的搜索过程(见图2b)，是以源点和终点为焦点的一系列“同心椭圆”。永久标记点的选取原则为：当前结点距源点的最短距离与此结点到终点的直线距离之和最小者被选取为永久标记点。所以搜索过程趋向于终点，搜索过程到达终点的速度明显快于Dijkstra一般算法，搜索到的结点也少于Dijkstra一般算法。aDijkstra一般算法b椭圆限制搜索区域算法图2两种算法结点搜索过程示意图椭圆限制搜索区域算法优于Dijkstra一般算法的关键在于其最大搜索范围得到了明显地减小，从而使搜索速度得到提高。通过图2，可以很清楚的看出，这里的椭圆限制搜索区域算法实际上就是一种椭圆限制搜索区域的优化算法。2.1.2构造合适的椭圆限制搜索区域在椭圆限制搜索区域算法中，关键是求解合适的椭圆长轴M以结合源点、终点的坐标构造限制椭圆。通常采用统计分析方法求解椭圆限制算法中的长轴M。其方法是：选定一块能够反映城市道路状况的区域，从这个区域中随机取点，分别放入集合A和B，将它们的笛卡尔乘积记为C，即)},()(|),{(BbAabaBAC所有在C中的元素都可以看成是待求最短路径的源点和终点，其直线距离为e，两点间的最短路径为，它们的比值er/构成采样点的集合R。对这个集合进行统计分析就可以得出一个特定的系数，使得R中总数为满足%95置信水平的元素，其值不大于。然后利用这个系数作为乘系数即可以通过起止点之间的距离得出椭圆的长轴长度||SGM[7]。以大连市电子地图为例，从6313个点中分别随机各抽取30个点放入集合A、B中，经过笛卡尔乘积，C中就含有900对点；分别求取r，并对这900对点求算术平均值，可以得到352.1，则。||352.1||SGSGM在椭圆限制算法中，一般给出的置信水平为95%，这表明在椭圆内找不到全局最短路径的可能性不大于5%，但即使是剩下的5%不是全局最短路径，也至少是局部最短路径，所以一般认为这5%是完全可以忽略的[7]。2.1.3算法的优缺点椭圆限制搜索区域算法的最大搜索范围与源点在网络中的位置有关。当源点位置靠近网络边界或处在网络边界上时，其搜索的结点数目可能不会明显地少于Dijkstra一般算法。总之，此改进算法搜索的结点数目要比Dijkstra一般算法少，具体的数量根据网络的具体情况不同而有所差异。另外，当源点和终点不连通时，如果网络是全连通的，两种算法的搜索范围是相同的，它们的搜索终止条件都是搜索到整个网络所有与源点连通的结点而未找到终点。这样两种算法搜索的结点数相同，椭圆限制搜索区域算法的开销要高于Dijkstra一般算法，因为椭圆限制搜索区域算法要处理两结点间的最短距离计算。椭圆限制搜索区域算法是在平面条件下进行的优化，在算法的速度、资源消耗和稳定