基于深度优先反向搜索算法确定有效路径集合

张建旭，蒋 燕, 刘兴国

(重庆交通大学 交通运输学院，重庆 400074)



基于深度优先反向搜索算法确定有效路径集合

张建旭，蒋 燕, 刘兴国

(重庆交通大学 交通运输学院，重庆 400074)

基于最短路径中任意路段因发生交通事件而失效时的替代路径搜索，合理界定了有效路径的阻抗值范围。参考深度优先算法和有效路径Dail算法离终点越来越近的思想，提出了一种从终点出发，反向搜索前置节点的多条有效路径搜索算法。算例结果表明：该算法能自动识别与路网结构相关的有效路径阻抗值范围，且能快速找到阻抗范围内的有效路径集合。

交通工程；图论；有效路径；深度优先算法；Floyd算法

0 引 言

在城市交通网络中，为防止起讫点间的理想路径因交通事件而拥挤或中断，交通管理者需要快速识别备选分流路径，将瓶颈段的车流快速分流到理想路径外的其他合理路径当中。备选分流路径选择的实质就是有效路径集合的确定。

现有最典型的有效路径确定方法为Dail算法[1-2]及K路径算法，但这两种算法都存在一定的缺陷。Dail算法以路网中路段所在位置与起讫点位置关系来确定该路段是否为有效路段，而忽略了路阻的权重。这样可能会造成所选出的有效路径所包含路段的路阻和很大，而路阻较小的路径却没能被选中[3]。K路径算法[4]避免了Dail算法的这一问题，但也存在搜索次数多，计算量大的问题。每次均以最短路径搜索算法为基础，计算多条路径阻抗值并比较，得出第K条有效路径。K路径算法对路径阻抗值排序的思想，需人为判断有效路径条数K。

通过对传统Dail算法和K路径算法的分析可知，这两种算法无法准确地找到路径阻抗值在一个合理范围内的有效路径集合。笔者以交通出行拥堵常发状况为基础，合理地界定了有效路径阻抗值范围。根据有效路径定义，自动识别不同路网结构下OD对间有效路径阻抗值的范围。结合深度优先算法与Dail算法离终点越来越近的思想，从终点出发，以中间节点的临界阻抗值是否不小于起点至该中间节点最短路径阻抗值为判断条件，能够快速找到OD对间阻抗值合理范围内的有效路径集合。

1 有效路径阻抗值的范围界定

如何判定某一路径是否为有效路径，其关键在于判断这一路径的阻抗值是否在一个合理的阻抗值范围内。何胜学，等[5]认为，路径K为有效路径，则其阻抗值应不大于最短路径阻抗值(1+Hrs)倍。一般情况下，伸展系数Hrs的值对于城际间的研究可取0.6，对于城市内的研究可在区间[0.3,0.5]内取值[6]。F.Leurent[6]明确了有效路径的阻抗范围，其不足之处在于其伸展系数为一个经验值，这对于不同形式的路网结构，误差往往较大。例如，对于棋盘式路网路段普遍较短的情况，根据这一值找出的有效路径数较多；但对于组团式城市，这样的经验值则较为合理。李景，等[7]在进行多路径交通流分配时认为：若所选路径的路权与最短路径的路权的相对差小于或等于临界相对差，则该条路径即为有效路径，其中，临界相对差是指出行者在出行过程中所能容忍的比最短路径多走的路程或多用的时间与最短路径路权的比值。

考虑到在城市交通网络中，起讫点间最短路径一般不会出现多条路段同时中断的情况，而是汇、分流交通量大的一条路段出现交通中断或几条路段在不同时段发生交通拥堵，为此，笔者对有效路径的阻抗值范围重新定义。为方便叙述，先定义以下变量：

G=(V,A,D)表示一个有向交通网络；

V={vi|i=1,2,…,n}表示节点的集合；

A={aij|i,j=1,2,…,n}表示所有有向路段的集合，∃aij∈A表示从vi至vj存在有向路段，称vj与vi相连，vi与vj反向相连；

D={dij|i,j=1,2,…,n}表示有向路段阻抗值的集合，dij表示有向路段aij的阻抗值大小；

L=[lij]n×n为该网络最短路径阻抗矩阵，lij表示从vi至vj最短路径的阻抗值。假定初始阻抗矩阵也为邻接矩阵，即L(0)=[dij]n×n；

对有效路径新定义有以下说明：

说明1：有效路径条数与最短路径所包含的路段数无绝对函数关系。这是由以下两种情况引起的。

1)一般情况下，OD对间最短路径所包含路段失效时，其替代路径可能是同一条。如图1中，v2至v4间最短路径为v2→v3→v4，路段a23、a34分别失效时，其最短替代路径均是v2→A→v4。

图1 定义1说明简单路网

2)此外，有些路径不是某路段失效时的替代路径，但其阻抗值介于有效路径阻抗值范围内，这样的路径也是有效路径。图1中v1至v4间，v1→v2→B→v4不是最短路径路段a23或a24失效时的替代路径。但其阻抗值小于路段a12失效时，最短替代路径的阻抗值为5，所以该路径也是有效路径。

说明2：对于不同起讫点的有效路径存在相对性。即OD对间，一条路径在小网络结构中不是有效路径，但在一个较大的网络中，这条路径可能变成其他OD对有效路径的组成部分。

例如图1中，根据定义1，v2至v4间，v2→B→v4不是节点对(v2,v4)的有效路径。但对于节点对(v1,v4)间，v1→v2→B→v4是有效路径。这与起终点距离越大，出行者可接受的相对距离也越大的出行心理相符，也是因为阻抗范围随路网结构变大而增大的结果。

定义3：在节点对(r,s)有效路径搜索时，除终点vs外，其他中间节点均存在临界阻抗值u。对于某路径i，某路段akg∈A位于该路径i中，则中间节点vk的临界阻抗值(urk)i，等于后置节点vg的临界阻抗值减去路段akg的阻抗值，即(urk)i=(urg)i-dkg。在计算时，假定终点vs临界阻抗值urs=Crrs。

从定义3可知，从中间节点到终点vs存在j条路径，那么节点vk的临界阻抗值需要计算j次。例如图2中，对于节点对(1,10)寻找有效路径，可能需要分别从路径v10→v9→v6和v10→v7→v6计算节点v6的临界阻抗值。根据定义3，假定终点v10的临界阻抗值u1,10=Cr1,10=21，从路径1：v10→v9→v6计算时，(u19)1=21-5=16，则(u16)1=(u19)1-d69=11。从路径2：v10→v7→v6计算时，(u17)2=21-4=17，(u16)2=(u17)2-d67=17-5=12。此时对于从v6至v10的上述2条路径，中间节点v6的临界阻抗值需要计算2次，结果分别为11和12。

图2 定义3示例说明

推论1：节点对(r,s)有效路径搜索时，对中间节点临界阻抗值判断，如果urk≥lrk，此时沿着vk继续向起点vr搜索，必定能找到1条及以上的阻抗值介于(lrs,lrs′)的有效路径。则称vk、akg为OD对(r,s)间1条有效路径所包含的有效节点、有效路段。

证明：对于某路径i，在计算中间节点vk的临界阻抗值(urk)i时，令节点vk至终点vs在路径i上所有路段阻抗值之和为(sks)i。

(urk)i≥lrk⟹(urk)i+(sks)i≥lrk+(sks)i⟹urs≥lrk+(sks)i

不等式表示的是从vr至vs的一条路径的阻抗值在(r,s)有效路径阻抗最大容许值范围内。这条路径由vr至vk最短路径及在计算中间节点vk的临界阻抗值(urk)i时，节点vk至终点vs在路径i上所有路段组成。

如图2中，从路径2：v10→v7→v6出发计算得(u16)2=12>l16=10，路径v10→v7→v6的阻抗值(s6,10)2=9，则u16+(s6,10)2=21>l16+(s6,10)2=19。已知，对于起点1而言，终点v10的阻抗最大容许值Cr1,10=21，这说明路径v1→v6→v7→v10是一条有效路径，其路径阻抗为19。事实上从v6向前搜索还可以找到另外一条有效路径v1→v2→v4→v6→v7→v10，其阻抗值正好为21。

2 有效路径搜索算法

通过笔者的定义可知，找出OD对(r,s)间有效路径，需找出有效路径阻抗值范围。笔者以floyd最短路径算法[8-11]基础计算得到两个结果，供有效路径搜索使用：①没有路段失效时，任意节点间最短路径阻抗矩阵L；②初始最短路中任意路段失效时，OD对(r,s)间有效路径阻抗值范围。

现有对于阻抗值范围内的有效路径搜索算法研究中，赖树坤，等[12]通过图的遍历方法进行搜索，需找出起点出发所有路径，当其终点为目标节点，且阻抗值在预先给定的范围内时，此时判断该路径为有效路径。该方法必需遍历全部路径，造成大量的冗余计算。为防止这种算法在求解有效路径时的“组合爆炸”问题，何胜学，等[5]利用节点坐标划分有效搜索区域，根据已求出的节点位势，以节点估价函数确定下一步搜索邻接节点。该方法能有效缩小搜索范围，但是在搜索过程中，需对每一个节点定位，这样使得计算复杂，并且在山地城市中高差较大必然引起节点位势及搜索半径的不准确，导致计算结果产生较大差异。

笔者探索一种基于深度优先算法的反向搜索算法，该算法能够自动判断有效路径阻抗值范围，并从终点节点出发，不重复筛选地一次性找出满足阻抗范围条件的全部有效路径。

深度优先算法基本思想[13-14]是：为了求得问题的解，先选择某一种可能情况向前(子节点)探索，在探索过程中，一旦发现原来的选择不符合要求，就回溯至父亲节点重新选择另一节点，继续向前探索，如此反复进行，直至求得最优解。深度优先算法在最优解搜索过程中，往往存在不满足条件要求的“死路”或已访问节点，为避免下次继续朝这个方向走，对这些“死路”或已访问节点进行标记，可以得到更高的效率。

笔者基于深度优先原理，设计出可实现多条有效路径搜索的算法，具体思路如下：对于OD对(r,s)间有向路径搜索，主要从终点vs出发向起点vr搜索；首先计算与vs反向相连的一个节点vg的临界阻抗值，判断该值与vr至该节点的最短路径阻抗值的关系，若urg≥lrg满足，则寻找与节点vg反向相连且满足判断条件urk≥lrk的子节点vk；如果不满足条件，则寻找其他满足条件的节点；这样一直向下搜索，直到当前访问节点为起点vr时，则找到了第1条有效路径。根据第1条有效路径，从节点vr反溯至其父亲节点，从其父亲节点寻找与其反向相连且能满足判断条件的其他未访问节点。如果有，继续向前搜索，则寻找到另一条有效路径；如果没有，则回溯至当前节点的父亲节点。一直这样回溯，直到回溯至终点vs，且不再存在满足条件且没有访问过的节点，算法结束。

本算法说明：①对于从任意中间节点vk判断是否继续沿此节点继续向前搜索的判断条件均为urk≥lrk，如果满足此条件则继续搜索，如果不满足则回溯至其父亲节点；②算法在一条有效路径搜索节点标记时，对搜索过的当前节点的兄弟节点及父亲节点进行标记，防止搜索时回到父亲节点或已访问过的兄弟节点，对子节点进行临时标记，当回溯至当前节点的父亲节点时，清除对当前节点的子节点的标记；③中间节点的临界阻抗值随不同路径变化而变化，在存储中间节点临界阻抗值时，需实时更新。

多条有效路径搜索的具体算法步骤如下：

2.1 有效路径阻抗值范围确定

Step1：将实际路网抽象成简单路网图，根据floyd算法找到OD对(r,s)间最短路径及阻抗值。floyd算法调用如下。

1)输入初始权矩阵L(0)=(lij(0))n×n，其中：

2)：计算L(k)=(lij(k))n×n，(k=1,2,…,n)，其中：lij(k)=min[lij(k-1),lik(k-1)+lkj(k-1)]。

2.2 深度优先反向搜索算法寻求有效路径

进行下一步前先定义几个存储空间。

建立数据栈S，数值p表示S的第p个元素，S(p)表示当前访问节点，初始化时第一个访问元素S(p=1)=s。S主要记录当前搜索的节点及被标记的当前节点的所有父亲节点。当S(p=1)=0时搜索结束，此时，终点节点vs的所有反向相连子节点全都被访问过，不存在满足判断条件的子节点。

建立游历标记矩阵o为n×n的零矩阵，主要记录子节点的临时访问情况。元素o(i,j)=1表示从vi出发至vj已经被访问过，只做临时标记。

建立临时路径存储矩阵q,令q(1,1)=s。该矩阵记录每一次搜索访问过的所有节点编号。当该矩阵当前行最后一个元素为vr时(或urS(p)-dhS(p)

建立永久路径存储矩阵y，当临时路径存储矩阵q的最后一个元素为节点vr时，记录此路径。即永久路径存储矩阵y的当前行等于临时路径存储矩阵q的当前行。记录完成后换行。

Step4：如果栈的第一个元素不为0时，执行以下程序。

1)如果当前访问节点S(p)为出发地vr，转至step4.4进入回溯。

2)找到与节点S(p)反向相连的节点vh，判断节点vh是否满足游历矩阵元素o(S(p),h)=0且urs(p)-dhs(p)≥lrh，满足则转至step4.5。

3)不满足条件则继续寻找满足条件的节点vh，如果与节点p反向相连的节点全被访问过，没有满足条件的节点vh。转至step4.4进入回溯。

4)①将当前访问节点的子节点全部标记为未访问，即o(S(p),:)=0；②让临时路径存储矩阵q换行(换行后的行元素与前一行除最后一个元素外的元素一致，下一次记录临时路径时则从此行的最后一个元素开始)；③如果当前访问节点为vr，则将临时路径存储矩阵q的当前行存储至永久路径存储矩阵y当前行中，换行；④让无后继点的或以达到目标点的节点元素出栈，即：S(p)=0。访问上一个父亲节点，即栈的前一个元素。

5)①标记从节点S(p)至节点vh已经访问过，即游历矩o(S(p),h)=1；②让节点vh入栈，并作为下一个访问节点；③节点vh的临界阻抗值等于当前访问节点临界阻抗值减去这两个节点间的路段阻抗值；④将节点vh存入临时路径存储矩阵q当前行后一个列元素当中。

Step5：当栈的第一个元素为0时，搜索结束，输出永久存储矩阵y。

具体使用MATLAB编程，流程如图3。

图3 深度优先反向搜索算法流程

3 算例说明

对于图4所示简化交通网络，存在v1，v2，…，v10共计10个节点和14条路段，每条路段的行驶阻抗为固定值，已标注在对应的路段中，将使用深度优先反向搜索算法找出OD对(1,10)间的有效路径。

图4 算例简化路网

根据有效路径定义，先找到OD对(1,10)的最短路径：v1→v2→v7→v9→v10。当最短路径所包含路段分别失效时，找到OD对(1,10)有效路径的阻抗值范围为(19,22)。

根据深度优先反向搜索算法搜索有效路径过程如图5。

<>—节点v1至该节点的最短路径阻抗值；[ ]—节点的临界阻抗值

图5中，有效路径搜索时，每次节点向前搜索均需计算节点临界阻抗值，只有当该节点的临界阻抗值大于或等于起点vs至该节点的最短路径阻抗值时，继续往下搜索。具体步骤如下：

搜索1：从终点v10出发找到第1条满足阻抗条件的有效路径1：v10→v6→v3→v2→v1。

搜索2：从起点v1开始回溯，每回溯至上一父亲节点vk均判断该节点是否存在没有访问过且满足判断条件urk≥lrk的其他子节点，满足则继续沿该子节点向前搜索，不存在这样的节点则继续回溯至上一父亲节点。本次搜索直到回溯至v6时，存在与其反向相连的节点v5，满足u15≥l15。继续向前搜索找到有效路径2：v10→v6→v5→v3→v2→v1。

搜索3：从有效路径2回溯至v5，找到与之反向相连的节点v4，且满足判断条件u14≥l14。从节点v4继续向前搜索找到有效路径3：v10→v6→v5→v4→v2→v1。

搜索4：按照前述方法，从有效路径3回溯至终点节点v10，找到与v10反向相连没有访问过的节点v9，计算得u19≥l19。此时沿着v9继续向前搜索找到有效路径4：v10→v9→v4→v2→v1。

搜索5：从有效路径4回溯至v9，找到与v9反向相连没有访问过的节点v8，计算得u18≥l18。此时沿着v8继续向前搜索找到有效路径5：v10→v9→v8→v4→v2→v1。

搜索6：从有效路径5回溯至v8，回溯至v8找到与v8反向相连没有访问过的节点v7，计算得u17≥l17。此时沿着v7继续向前搜索找到有效路径6：v10→v9→v8→v7→v1。

搜索7：从有效路径6回溯，直至终点节点v10，没能找到与v10反向相连且没有访问过的节点。此时搜索结束。

根据笔者算法，使用MATLAB编程搜索出算例路网图中，OD对(1,10)间的有效路径如表1。

表1 OD对(1,10)间有效路径集合

表1中，本搜索算法找出OD对(1,10)间的有效路径阻抗值均介于(19,22)之间，共6条。从本算例来看，笔者提出的算法自动识别了有效路径阻抗值范围，从而避免了K路径算法人为判断有效路径条数K的情况。也没有出现Dail算法搜索时，相对较近的有效路径未被选中的情况。

本算例使用广度优先算法搜索过程如图6。在有效路径搜索过程中，广度优先搜索算法和深度优先反向搜索算法，均需完成图的遍历，故这两种算法具有相同的时间复杂度。在搜索过程中，深度优先反向算法每一次搜索得到的是一条完整的有效路径，完成每一次搜索后即可清除临时存储空间；而广度优先算法每一次搜索得到的是组成有效路径的零散路段、节点集合，需完成最后一次搜索后才能清除所有临时存储数据。相比之下，对于大型路网中有效路径搜索，广度优先搜索算法会占据更大的存储空间。

图6 广度优先搜索算法有效路径搜索过程

简而言之，对于大型网络中有效路径搜索，深度优先反向搜索算法具有和广度优先搜索算法相同的时间复杂度和更小的空间复杂度，且搜索过程具有系统性和连续性。故深度优先反向搜索算法更适合于大型网络中有效路径的搜索。

4 结 语

考虑现有多条有效路径算法无法客观界定OD对间阻抗值范围，可能出现有效路径漏选的情况，笔者对有效路径重新定义，找到了OD对间合理的阻抗范围的确定方法。使用深度优先反向搜索有效路径，有效的避免了大量的冗余计算。另外该算法可以迅速求解实际交通网络中节点间其他有效阻抗值范围内的多条有效路径集合，为路网交通分流路径识别、交通流诱导等提供了方法。

笔者所提出的多条有效路径搜索算法，找出的有效路径集合随路网规模的大小、路网的结构形式变化而变化，但没有考虑到路网的流量变化情况。在以后的研究中，若能结合路网流量的变化建立一种动态有效路径搜索系统，必然更能适用于交通诱导、组织、导航等实际管理任务。

[1] Soo-young J,Chae Y L.Multipath selection and channel assignment in wirelessmesh networks[J].Wireless Netw,2011,17(4):1001-1014.

[2] 王英杰,程琳,王炜.基于有效路径集合的节点间连通度估计方法研究[J].武汉理工大学学报:交通工程与科学版,2009,33(5):960-963. Wang Yingjie,Cheng Lin,Wang Wei.Researches on estimations of connectivity reliability of an OD pair based on the effective path sets[J].Journal of Wuhan University of Technology:Transportation Science & Engineering,2009,33(5):960-963.

[3] 杨信丰,刘兰芬.基于影响度的有效路径集合的确定[J].交通运输系统工程与信息,2011,11(6):104-110. Yang Xinfeng,Liu Lanfen.Determining the efficient paths based on effect degree[J].Journal of Transportation Systems Engineering and Information Technology,2011,11(6):104-110.

[4] Lokshtanov D,Mnich M,Saurabh S.Planark-path in subexponential time and polynomial space[C]//Proceedings of the 37th International Workshop on Graph-Theoretic Concepts in Computer Science.Teplá-Klášter:Czech Republic,2011:262-270.

[5] 何胜学,范炳全.随机交通分配中有效路径的定向树搜索算法[J].交通与计算机,2005(5):38-41. He Shengxue,Fan Bingquan.Orientated tree algorithm of searching efficient paths in stochastic traffic assignment[J].Computer and Communications,2005(5):38-41.

[6] Leurent F.Curbing the computational difficulty of logit equilibrium assignment model[J].Transportation Research B:Methodological,1997,31(4):315-326.

[7] 李景,彭国雄,臧亦文.改进型多路径分配模型及算法设计[J].系统工程理论与实践,2001(9):130-134. Li Jing,Peng Guoxiong,Zang Yiwen.An improved multi-path assignment model and algorithms design [J].Systems Engineering-Theory & Practice,2001(9):130-134.

[8] 李洪波,王茂波.Floyd最短路径算法的动态优化[J].计算机工程与应用,2006(34):60-63. Li Hongbo,Wang Maobo.Dynamic optimum of shortest path’s algorithm devised by Floyd[J].Computer Engineering and Applications,2006(34):60-63.

[9] 严晓凤,陆济湘,唐双平.基于Floyd算法的校园最短路径问题分析与实现[J].武汉理工大学学报:信息与管理工程版,2012,34(6):695-703. Yan Xiaofeng,Lu Jixiang,Tang Shuangping.Analysis and implementation of campus shortest path based on Floyd algorithm[J].Journal of Wuhan University of Technology:Information & Management Engineering ,2012,34(6):695-703.

[10] 黄远春,胥耀方,潘海泽.城际公共交通系统最短路算法[J].重庆交通大学学报:自然科学版,2010,29(2):265-268. Huang Yuanchun,Xu Yaofang,Pan Haize.Algorithm for shortest path of intercity public transportation system[J].Journal of Chongqing Jiaotong University:Natural Science,2010,29(2):265-268.

[11] 黄美灵, 陆百川.考虑交叉口延误的城市道路最短路径[J].重庆交通大学学报:自然科学版,2009,28(6):1060-1063. Huang Meiling,Lu Baichuan.Determination of the shortest path considering delays at intersections[J].Journal of Chongqing Jiaotong University:Natural Science,2009,28(6):1060-1063.

[12] 赖树坤,姚宪辉,彭愚.交通网络中有效路径确定方法的探讨[J].交通标准化,2008(1):137-139. Lai Shukun,Yao Xianhui,Peng Yu.Determination of efficient path in traffic network[J].Communications Standardization,2008(1):137-139.

[13] Evangelista S,Laarman A,Petrucci L,et al.Improved multi-core nested depth-first search[C]∥Automated Technology for Verification and Analysis,Thiruvananthapuram.India:Springer Berlin Heidelberg,2012:269-283.

[14] Kozen D C.Depth-first and breadth-first search[M]//The Design and Analysis of Algorithms.New York:Springer Berlin Heidelberg,1992:19-24.

Determining Effective Paths Set Based on Reverse Depth-First Search Algorithm

Zhang Jianxu, Jiang Yan, Liu Xingguo

(School of Traffic & Transportation, Chongqing Jiaotong University, Chongqing 400074, China)

Based on the definition of alternative path, the range of effective path impedance values was identified. Adopting the depth-first algorithm and the idea of getting closer to the end from the effective path Dail algorithm, an effective paths search algorithm which starts from the end node to the front node was proposed. Numerical results show that, the effective path search algorithm not only identifies the impedance values range associated with the network structure automatically, but also finds the effective path sets quickly.

traffic engineering; graph theory; effective path; depth-first search algorithm; Floyd algorithm

10.3969/j.issn.1674-0696.2015.03.20

2013-12-11；

2014-02-22

国家自然科学基金项目(51308569)

张建旭(1978—)，男，河南许昌人，副教授，博士，主要从事综合交通规划与管理方面的研究。E-mail：jexu@qq.com。

U491.1+3

A

1674-0696(2015)03-093-06