0 引言

实现城市的繁荣、有序和快速发展，一个基本条件是良好的城市交通系统。但随着各城市机动车保有量的不断增加，导致对交通需求的急剧增加，紧接而来的一系列如交通拥堵、交通事故频发、环境污染严重及能源短缺等问题，给人们生产、生活等带来了诸多不便，这些都制约着一个城市的进一步、可持续的发展。出行者在交通出行中，一个经常关心的问题是如何迅速选择一条最优的路径。因此，出行最优路径选择算法问题的研究已迫在眉睫。

求解两点间的最短路径问题，已经有很多学者做了研究，给出了很多的算法，其中以Dijkstra算法^[1]最为经典。该算法可以在O(n²)(n为节点数)时间复杂度情况下，求出某初始点到其他与其有路径相通的点之间的最短路径。当节点个数较少时，O(n²)级别的时间复杂度是可以接受的，实际系统中，节点个数往往较多，该级别的复杂度就显得效率低下，因此，直接使用Dijkstra算法的情况不多。

文献[2-3]针对堆排序算法做了分析；文献[2]给出了一种基于左倾树的堆排序改进算法，在输入数据排列任意的情况下，该算法实现排序的时间复杂性为O(nlogn)；通过只对最短路径上节点的临界点处理，在不涉及其他节点的情况下，文献[4]对Dijkstra算法进行优化，使得计算的节点数大幅减少，从而提高了算法的速度；文献[5]讨论了启发式算法在路径规划问题中的一些改进策略，该方法考虑到了一些计算机硬件因素；文献[6]采用预先计算存储的方法，程序运行时，根据初始节点和目标节点，直接调用数据库查询语句，查询出事先计算好的两点间的距离，如果图中节点数目较多，额外存储空间开销就较大。

因此，路径搜索在交通网络中是一个比较复杂的问题，设计算法时，需要考虑多种方面的因素，然后给出最终解决方案。本文将启发式的思想引入Dijkstra算法中，并对搜索区域加以限制，提出限制搜索区域的启发式最短路径算法(Restricted Searching Area Heuristic Shortest Path Algorithm, RSAHSPA)，该算法能够有效缩短路径搜索时间，为使用者提供出行依据。

1 路径搜索算法描述 1.1 寻径问题网络模型

寻径问题是在图论中研究的热点之一，目标是设计一个算法，寻找图中从初始节点到目标节点的一条通路。城市路网除具有一般路网的特点之外，还有其特殊之处：数据量大和结构复杂。这都使得城市路网的结构变得非常复杂，现实中的城市路网实体只有抽象化为图论中的网络图后，才能做最佳路径分析，一般的方法是采用GIS技术生成其对应的电子地图。本文的研究在已生成的电子地图上进行，以此讨论最短路径算法的实现过程。

1.2 Dijkstra寻径算法

定义1  图是由1个顶点集V和1个弧集VR构成的数据结构，Graph=(V, VR)，其中，VR={ < v, w>|v, w∈V∧P(v, w)}， < v, w>表示从v到w的1条弧，P(v, w)定义了弧的意义或信息，一般设置为该弧的权重^[7]。

Dijkstra算法采用贪婪策略，描述如下。

算法1：

(1) 初始，从节点集合V′={v_s|v_s∈V}出发，v_s为路径初始节点。

(2) 在V′关于V的补集V′中，选择与V′中某节点v_i直接相连的节点v_j，令其组成节点集合M。

(3) 在所有满足v_i∈V′∧v_j∈M的弧 < v_i, v_j>中，选择权重最小的边，设该边在M中依附的节点为v_j，若v_j=v_e(v_e为路径目标节点)，则算法结束。

(4) 将节点v_j从M中删除，添加到集合V′中，并根据该节点来更新V′中节点的相关信息。

(5) 返回(2)。

理论上Dijkstra算法能够保证得到最优解，但其时间复杂度较高，为O(n²)。主要在于对每个V中的节点，扩大V′的过程采用的是同等的对待策略。对于离最终路径P=(v_s, …, v_e)较远或与该路径方向相背离的节点，应该考虑不选择，或最后再选择。

当图中节点个数很多的时候，Dijkstra算法的性能就显得有些低。此时，为了提高搜索的效率，可以在牺牲一定精确性的情况下达到提高查找速度的目的。启发式算法就是这样一种策略。在每次扩展过程中，尽量选择离最终路径近的那些节点。

1.3 启发式方法

定义2  设评价函数f(v_j)=g(v_s, v_j)+h(v_j, v_e)^[8]，式中，g (v_s, v_j)为从初始节点v_s经过寻径算法到达节点v_j的权值之和，且g(v_s, v_s)=0；h(v_j, v_e)为节点v_j的代价函数，h(v_e, v_e)=0，它预测从v_j到终点v_e的代价。一个点是否能被优先选用进行搜索，主要由评价函数f(v_j)的值来决定。

引入代价函数h(v_j, v_e)后，每次对节点的扩散不再是盲目的，而是有方向性的。其值越大，算法的解也就越偏离最优解，但同时时间耗费也越小；其值越小，搜索所花费的时间越大，算法的解也就越逼近最佳解。基于启发式的路径搜索算法如下。

集合V^*={v^*|v_i^*∈V, ∀v_i^*≠v_j^*(i≠j)}，V^*为V^*关于V的补集，初始时，V^*中只有1个初始节点v_s；V_c^*={v_ci^*|v_ci^*∈V, ∀v_ci^*≠v^*_cj(i≠j)}表示V^*中所有与V^*中的节点直接连接的节点集合。算法步骤如下。

算法2：

(1) 在V_c^*中查找v^*_cj，使v_ci^*∈V_c^*。

(2) 将v^*_cj从V_c^*中删除，并添加到V^*中。

(3) 在集合中查找与v_cj^*直接相连的节点，将其移到V_c^*中去，如果该步骤中添加的节点有终点v_e，则算法结束。

(4) 返回(1)。

定理1  设有序序列V′={v_s, v₁, v₂, …, v_j, …, v_n, v_e}，j=1, …, n，为使用启发式方法求出的从初始点v_s到目标点v_e的路径上的点，该路径P′=(v_s, v₁, v₂, …, v_j, …, v_n, v_e)，j=1, …, n，dist_min(v_k, v_l)用来记录节点v_k到节点v_l最小权值之和，若满足(∀v_j)[h(v_j, v_e)≤dist_min(v_j, v_e)∧(v_j∈V′)]，则P′为最短路径。

证明  设V″={v_s, v′₁, v′₂, …, v′_i-1}为求得的最短路径上前i个节点的集合，v′_i为该路径上下一个节点。从v′_i-1到目标点v_e可有m条路径，不失一般性，设其中1条为P_q=(v′_i-1, v′_q1, v′_q2, …, v′_qr, v_e)，1≤q≤m。

令v′_pi≠v′_i，P_q中的节点满足∀v′_pi[f(v′_pi) < f(v′_i)∧(v′_pi∈V″)]，则按照启发式算法，必然会优先顺着P_q方向按深度优先搜索下去。当到达终点v_e时，

引入记号d(v_k, v_l)来表示边 < v_k, v_l>的权，则：

而

又因为最短路径上的下一节点为v′_i，则有：

即：

根据该不等式，此时启发式算法会放弃路径P_q，从而最终会将节点v′_i添加到集合V″中，证毕。

由算法1和算法2的相似性，容易看出，Dijkstra算法为该启发式算法的特例[h(v_ci^*, v_e)=0]，即不需要任何启发信息。引入h(v_ci^*, v_e)可以使得原来向四周漫无目的搜索，变为有方向性的，这样也就提高了寻径效率。

由于在交通网络图中，对每个节点v^*_cj，在集合中与之直接相连的节点数目是有限的, 因此图中所有弧的权值都大于某个整数ε, 对图中的所有节点v_j，代价函数h(v_j, v_e)的预测值不会超过其实际值。同时，由于交通网络图是连通图，即存在1条从初始点v_s到目标点v_e的路径，因此，算法2能够保证找到1条从初始点v_s到目标点v_e的最小代价路径^[9]。

2 算法的改进 2.1 评价函数

评价函数f(v_j)的任务主要是用来估计搜索路径上某节点v_j的重要性。理论上讲，它可以是任意的函数，具体应用中采用什么样的形式，主要由应用而定。一个节点的价值一般从两方面考虑：搜索到该节点时算法已经付出的代价g(v_s, v_j); 如果选择从该节点出发到达目标节点v_e，算法将要付出的代价h(v_j, v_e)。一般来说，已经付出的代价g(v_s, v_j)的值是一定的，而最关键的就是根据具体应用来选择合适的h(v_j, v_e)。

在网络地图中，设两点v_j和v_e的坐标分别为(x_j，y_j)与(x_e，y_e)，常用的启发式函数主要有：

曼哈顿距离：h(v_j, v_e)=(|x_j-x_e|+|y_j-y_e|)；

欧氏距离：

切比雪夫距离：h(v_j, v_e)=max{|x_j-x_e|, |y_j-y_e|}。

其他形式的代价函数也可以选择，只要满足最优解条件即可。欧氏距离代表了两点间的直线距离，是一般情况的首选。在此，考虑到计算机做乘方和开方运算，耗时比加减大很多，故选择曼哈顿距离作为启发函数。

2.2 搜索区域

Dijkstra算法的搜索区域，可近似地看成以初始节点V_s为圆心所构成的一系列同心圆，各个节点依离初始节点的距离远近而先后被搜索到。整个过程没有涉及终点V_e所在的方向或位置，因此，其被搜索到的概率与其他节点V_j是相同的。若图中顶点数目较多，或初始节点V_s与终点V_e间距离较大，算法实际运行效率将大大降低^[10-11]。

启发式的搜索方法能够改变这种状况。文献[12]提出了一种矩形限制搜索区域，缩小了搜索的范围，提高了效率。在此基础上，本文将搜索区域进一步缩小，限制在一个条状范围内，如图 1所示。以初始节点V_s和终点V_e分别画半径为r(r为搜索半径，该值可调整)的圆，与两圆相切的直线分别为L₁和L₂，则两直线与两圆围成的条状区域即为搜索区域。

已知V_s和V_e的坐标分别为(x_s, y_s)，(x_e, y_e)，由解析几何知识可得平行线L₁，L₂的方程为：(y_e-y_s)x+(x_s-x_e)y+(y_sx_e-y_ex_s)±r·=0。

实际算法实现时，为了进一步简化计算，可以将搜索区域的横坐标值进一步简化为(x_s-r, x_e+r)，而纵坐标轴限定在两平行线L₁，L₂间不变。

初始时，根据经验，设置r值，运行算法，进行搜索，如果搜索到终点，则算法结束，否则，按预设增量增大r值，在一个更大的搜索区域上进行搜索，直至搜索到终点。最坏的情况即是搜索扩展到了整个区域。实际算法中，搜索半径r值设定为一个递增序列r_i，形如r_i={1, 1.5, 2, 2.5, 3, …}，如果根据前一个半径序列的值没有在搜索区域内找到终点，则选择半径序列中的下一个值来进行搜索。

由于程序首先考虑的是位于条状区域内的点，而不是所有的点，这样就减少了对无用节点的考察，加速了程序的运行。

2.3 排序方法

对算法2的分析可知，相对于算法1，无目的的宽度搜索改进成了有方向的启发搜索，加上对搜索区域的限制，被搜索的节点数目大大减少。在节点数目不大的情况下，算法2是可以接受的。但如果节点个数很多，在V_c^*中找到具有最小f(v^*_cj)值的节点v_ci^*(v_ci^*∈V_c^*)的时间耗费也不容忽视。该问题实质上是在一个动态集合中寻找最小值，为了缩短算法2的搜索时间，本文将使用二叉堆来对集合V_c^*进行查找。

定义3  堆是满足下列性质的数列{k₁, k₂, …, k_n}：

前者称为小顶堆，后者称为大顶堆^[7]。在此主要关注前者，并且采用一种改进的堆结构来进行排序。

如果集合F={f|f_i=f(v_ci^*, v_e)∧∀v_ci^*(v_ci^*∈V_c^*)}满足定义3，则，v_ci^*∈V_c^*成立。此时查找最小f值时，只需将其该集合中第1个元素取出即可，不用在V_c^*中查找。

左倾树排序方法是众多排序方法中较快的一种。在原始输入数据任意排列的情况下，该算法的时间复杂度可以达到O(nlog₂n)^[2]。左倾树实际上就是经典堆结构的一个改进。

定义4  左倾树T是1棵具有特殊性质的二叉树, 其中每个结点满足下列性质。

(1) 给树中每个节点k赋予1个Ek值：如果该节点具有不多于1个孩子，则Ek=1；如果该节点有两个孩子k₁和k₂，则Ek=min{Ek₁, Ek₂}+1。

(2) 根节点的值小于(仅考虑小顶堆)以该节点为根的子树上所有节点的值；如果节点k无左孩子，则它必然无右孩子；如果k同时具有两个孩子(分别为k₁和k₂)，则左孩子节点的Ek值Ek₁大于等于右孩子节点的Ek值Ek₂。

用左倾树实现排序的过程和普通的堆排序相似，也分为构造和排序两个阶段：第1阶段执行构造过程，输入含有n个节点的待排序序列，经过n-1次左倾树的合并过程，构造1棵新的左倾树；第2阶段执行排序过程，再经过n-1次左倾树的合并过程，从而最终实现排序。

合并过程描述如下(仅考虑两棵树的情况)：

(1) 如果有一棵左倾树为空树，合并后的结果为另一棵左倾树。

(2) 将根节点值小的左倾树的右子树与另一棵左倾树进行合并，使用合并后的结果代替该右子树。

(3) 如果合并后的结果不满足左倾树的条件，则可以通过交换该左倾树的左右子树，使之成为一棵左倾树。

假设一棵左倾树含有n个节点，由于“左倾”的性质，从该树根结点出发，一路沿着右子树向前走，最多走log₂(n+1)步(等于树的高度)。又因为左倾树的合并过程总是从右子树方向进行的，这样至多只需要O(log₂n)步就可以访问该树右边的子树，同时完成合并工作，这是最坏的情况。显然，左倾树树型最坏的情况是当它的左右子树较为平衡时；最佳树型是当它的所有节点的右指针为空时。

据此，对于含有n个节点的集合V_c^*，用左倾树实现对其节点排序的时间复杂性为O(nlog₂n)。显然，它是一种较快的排序方法。当集合V_c^*中元素较多时，使用上述改进的堆排序算法能够加快在其中查找具有最小f值元素的过程。

3 结果与分析

试验目的是为了证明改进算法在某市电子地图不同图层上寻径的有效性，并分析搜索半径r和两点间直线距离k对有效性的影响。仿真试验在处理器为Intel酷睿i5 4570(3.2 GHz)、内存4 GB、硬盘1 TB、操作系统为Microsoft Windows 7的微机环境下进行。

3.1 寻径时间

该市电子地图有多个不同的图层，分别含有508，1 033，2 013，3 998条边。选定固定的两个地理位置作为起点和终点，两点间直线距离为k=10 km，同时，搜索半径r设定为2 km，以寻径时间作为衡量算法效率的指标参数，分别从地理距离和拥堵时间两方面来设定边的权值，以对Dijkstra算法、RRSA算法和RSAHSPA算法的效率进行测试，其中RRSA指矩形限制搜索区域算法^[12]。

图 2描述了在地理距离最短权值下3种算法的寻径时间，在开始边数为508的条件下，Dijkstra、RRSA和RSAHSPA所花费的寻径时间分别为2 110，1 143，632 ms。随着边数的逐渐增加，3种算法花费的寻径时间都逐渐增加，但Dijkstra比RRSA和RSAHSPA增加得更快，同时，RRSA和RSAHSPA所花费的寻径时间增加变化缓慢，并且RSAHSPA算法一直低于RRSA算法。当图层边数增加为3 998条时，3种算法的寻径时间分别为34 412，6 617，3 216 ms。图 3描述了在拥堵时间最短权值下3种算法的寻径时间，因此，本文所提方法优于其他两种方法。

3.2 初始半径r的选择

保持上述试验运行环境不变，针对RSAHSPA算法修改k数值，以地理距离最短作为路径权重的情况为例，测试搜索半径r值对算法所花费寻径时间的影响。取k=10 km，初始半径r分别选择r=1, 1.5, 2, 2.5, 3 km，运行结果图 4所示。

另外，取k=5 km，初始半径r分别选择r=0.5, 0.7，1, 1.5, 2 km，运行结果图 5所示。

为了对照，再取k=20 km，初始半径r分别选择r=1, 2, 4, 6, 8 km，运行结果图 6所示。

试验结果表明，在不同数值k的条件下，随着图层中边数的增加，相同r值下，RSAHSPA算法的寻径时间都会逐渐增大；在同一个数值k的条件下，不同的初始r值对RSAHSPA算法的寻径时间影响显著。例如，在图 4的k=10 km条件下，初始r=2, 2.5, 3 km的运行曲线几乎在一起，说明在设置r=2 km的搜索区域内，已经能够找到一条起点到终点的最短路径，此时，增加r值，对寻径时间影响不大；r=1, 1.5 km需要更多的运行时间，说明在这样的搜索范围内没有找到最短路径，需要增加r值在一个更大的范围内进行搜索，因此时间花费更多。图 5和图 6中，当r分别增加至1 km和4 km后，再增大搜索半径，对寻径时间影响不大。根据图 4~图 6结果分析，r=k/5时算法运行效果最好，继续增加r值，效率提高不明显。

4 结论

本文将启发式方法应用到经典的最短路径算法之中，给出了网络地图中的一个新的路径搜索算法。同时，在启发式函数搜索范围和排序方法方面，讨论了算法的改进之处，并将其应用到实现的算法中。仿真试验结果证明了新的路径搜索算法的优越之处，与已有路径选择改进算法相比，能够有效缩短路径查找时间，从而更好地满足出行需要。