基于节点压缩的寻径优化算法

廖志芳 陈亮名 彭志文 李严冰

(中南大学软件学院 湖南 长沙 410075)

基于节点压缩的寻径优化算法

廖志芳 陈亮名 彭志文 李严冰

(中南大学软件学院 湖南 长沙 410075)

最短路径问题是一个经典问题，而目前的研究大多是针对给定起点和终点，选择从起点到终点的最短路径，且取得了不少成果。而对于限定时间的最短路径问题的研究成果相对较少，这类问题在现实生活中却随处可见。针对这一问题提出几种限定时间的寻径优化算法，从对回溯法的改进到不同的节点压缩的方法，给出改进的回溯法以及三种基于节点压缩的寻径算法。算法实现在限定的时间内从起点出发经过给定的节点集合再到达终点的路径选择，并针对不同复杂度的网络图有相应合适的算法可以选择，从而有效地解决这类问题。

最短路径 限定时间 节点压缩 寻径

0 引 言

图论中单源最短路径问题[1-3]是一个经典问题，其在实际生活中应用广泛，如网络路由路径选择、车载导航、旅行路线等。解决这一问题的经典算法是Dijkstra EW.A于1959年提出的Dijkstra算法。但这一算法不能解决从起点开始必须经过指定的中间节点再到达终点的问题，然而这类问题实用性更强，比如：

(1) “邮递员问题”：邮递员从邮局出发为有信件的居民送完信件后回家，在给定的时间内为该邮递员选择一条行驶距离最短的路线；

(2) “旅行家问题”[4-6]：在指定的时间内为旅行者计算出一条旅行路线，从指定地点出发，到达指定旅游景点再到达指定目的地，要求路线的总行驶距离或者总行驶开销最短。

(3) “网络寻径问题”[7-9]：在指定的时间内为网络数据传输寻找一条有效路径，且这些数据必须经过某些网络站点，到达指定的站点，使得网络开销最小。

这些问题最终都可以归纳为同一个图论问题，即在一个带权有向图中，从起点经过指定的中间节点，到达终点，要求在指定时间内，寻找有效路径，并计算这些路径的权重，选择一条权重最低的路径作为结果路径。

对于这一类问题，可以采用对整个图进行遍历，寻找一条最短路径。虽然从理论上来说这种遍历算法最终能够得到最优解，但是其时间复杂度相当高。针对这一问题，本文提出了时间限制的节点压缩寻径算法。该算法通过采用节点压缩，将寻径过程中得到的有用信息使用到搜索条件、调整子节点顺序等方法，改善了传统算法时间复杂度太高的问题，为这类问题的解决给出了有效的办法。

1 问题描述

1.1 问题的数学模型

给定一个带权有向图G(V,E),其中:V={1,2,…,n}为顶点集，E={eij=(i,j)|i,j∈V,i≠j}为边集。dij(i,j∈V,i≠j)为顶点i到j的权重，其中:dij>0且dij≠∞，同时dij和dji可以不相等。V′={1′,2′,…,n′}∈V，给定起点s和终点t，s,t∈V且s，t不属于V′，要求在给定时间内求序列A={a1,a2,…,an},其中:a1=s,an=t，V′中的所有元素都必须在序列A中出现，并使得以按照序列A在图中形成的路径的所有边的权重之和尽可能小，且路径中不能出现环路。该问题的数学模型定义如下：

(1)

∑i≠jXij=1i∈V

(2)

∑i≠jXij=1j∈V

(3)

∑Xsj=1j∈Vj≠s

(4)

∑Xjs=0j∈Vj≠s

(5)

∑Xit=1i∈Vi≠t

(6)

∑Xti=1i∈Vi≠t

(7)

为了限制路径中不会出现无关的回路，作如下约束：

∑i,j∈VXij=|A|

(8)

为了方便后续描述，给出以下两个定义：

定义1关键节点：问题描述中给定的起始节点s和终点t以及必经节点的集合V′为关键节点。

定义2自由节点：除关键节点以外的所有节点都是自由节点。

1.2 简单样例

如图1所示的带权有向图G，分别有0、1、2、3共四个节点，即C={0,1,2,3}，图中有0、1、2、3、4、5、6七条边，即E={0,1,2,3,4,5,6}，边的权重为{d01=1,d02=2,d03=1,d21=3,d31=1,d23=1,d32=1},如果此时需要寻找从0到1的路径，且必须经过顶点2和3，则V′={2,3}。对于该问题，可以从图中找到如下两条可用路径：0->2->3->1和0->3->2->1。由于第一条路径各条边的权重和为4，第二条路径各条边的权重和为5，所以此时最优解应该为0->2->3->1。

图1 问题的简单样例

2 改进的回溯法(IBA)

使用回溯法求解该问题时，理论上可以得到最优解，且可以得到所有解，但是回溯法没有有效地利用在搜索过程中构造的信息以及已求得的可行解，使其作为下一步搜索的优化条件。本节通过对回溯法进行改进，提出改进的回溯法，在算法每次搜索完上一节点后，并在搜索下一节点之前，利用已有的信息和已求出的可行解来添加搜索规则，从而对搜索方式进行改进，使得算法在运行过程中，利用已有的信息和已求出的可行解来提高搜索效率。

改进回溯法中的添加规则表示如下：

规则1如果下一节点是终点，而当前路径没有经过必经节点集合中的所有节点，则回溯，继续搜索下一节点。这一规则可以避免许多无效解的生成，以期提高算法效率。

规则2如果当前路径权重加上到达下一节点的那条边的权重大于等于当前已求得的权重最小的可行解的路径，则回溯，继续搜索下一节点。由于当前已经搜索到可行的路径，如果当前路径权重加上下一节点的权重不小于已有路径权重，那么接下来继续搜索就没有任何意义，因为问题是求解权重尽量小的路径。

规则3对于不是终点而且没有子节点的节点，要避免进入搜索。如果某节点不是终点，又没有子节点，到达该节点后无法继续下去，因此这种节点是没有必要搜索的，甚至可以在图中直接删除。

改进回溯法算法的关键伪代码如下：

Improved-Backtrack(G)

1 node=start

2 while usedtime

3 nodes.add(node)

4 record information include route and weigths

5 for i=1 to children.length

6 add search rule

7 Improvedacktrack(children[i])

8 if result ！=null-B

9 return result and weight

10 else

11 return NA

3 节点压缩的搜索算法

虽然改进的回溯算法在一定程度上可以提高搜索效率，但是随着图规模的增大，解空间的增长，改进的回溯法的复杂度也随之提高。为降低算法复杂度，本文提出了新算法—基于节点压缩的搜索算法NCSA(Node Compression based Search Algorithm)。

随着图规模的增大，图中的路径也随之扩大，而所求路径是从起点到终点且经过中间节点的路径，因此可以先将图进行预处理，对图的总节点数进行压缩，去掉无关的节点和价值较低的路径片段，尽量只保留需要的路径，从而达到简化整个图、缩小解空间、提高搜索效率的目的。

3.1 节点压缩算法(NCA)

本算法要解决的问题具有如下情况：如有节点比较偏僻，只能到达一个其他节点(即只有一个子节点)，当算法搜索过程中到达这样的节点时，只会往它唯一的子节点往下走。每经过该节点一次就要这样走一次，这样简单而又重复的计算是可以避免的。

解决办法就是采用节点压缩的方法，将经过该类型节点的唯一路径在搜索算法第一次经过时就记录下来，并将这一节点移除，只保留这一路径信息。当下次搜索到达该节点时，直接使用已存在的路径信息，避免重复搜索计算。移除节点之后的图总节点数目减少，因此经过压缩之后的图将更容易搜索出更好的解。

过程如图2所示。

图2 压缩搜索算法的基本思想

图中节点1只有1个子节点2，节点1到节点2的权重为2，路径为“1”，压缩过程就是将节点1的信息合并到节点2上，节点2成为节点0的直接子节点，压缩之后，节点0到节点2的权重就变为3，节点0到节点2的路径变为“0|1”。这样就有效地将节点1移除了，并将节点1到2的路径保留在节点2的信息中。当下次搜索算法到达节点0时，可以直接使用节点2中保留的信息，而无需再次搜索节点1。

3.2 完全压缩算法(CCA)

由于节点压缩算法(NCA)的目标是针对只有一个子节点的自由节点，如果图中这样的节点个数较多，那么算法的效率提高就比较明显。但是如果图中这样的节点很少甚至没有，那么基本压缩策略的效果就不明显，甚至会没有任何效果，因而利用压缩方法的搜索算法在这种情况下并没有效果。

针对NCA算法的这一问题，本文提出了更有效的压缩策略，针对所有的自由节点进行压缩，从而有效地对图中节点进行压缩，降低图的复杂度，提高搜索效率。

该问题集中在寻找从起点到终点并经过中间节点集合的不成环的路径，使得路径上各条边的权重尽可能小。当图中节点互相之间的可达关系比较复杂时，从一个节点到达另一个节点的可行路径会很多，由于问题要求必须经过中间节点集合V′,且中间节点集合中的各个节点之间的可达路径也会有多条。而最终解只会从这些路径中选择一条作为它的一个片段，因此，找出所有可达路径，并尽可能保存权重最小的一条路径，当搜索算法到达相应的节点时可以直接使用这些保存好的路径。而原路径上的自由节点则可以从图中移除，从而减少了图中的节点。使用这种压缩方法压缩后的图中，仅存在起点、终点、中间节点集合以及它们之间互通的路径信息，这样就在很大程度上简化了整个图，更加有效地进行了压缩。

3.3 改进的完全压缩算法(ICCA)

为进一步改善压缩效果，本文继续进行节点压缩的调整和改进。

1) 调整子节点顺序使之按照权重大小顺序排序

由于在搜索过程中，可以当前可行解的权重为基础进行搜索(参照基本搜索算法的改进规则2)，将子节点的顺序按照权重大小从小到大排序，搜索时先搜索权重小的子节点，则权重较小的路径就有可能先得到。根据搜索策略就可以跳过一些权重较大的路径，减少不必要的搜索过程，提高效率。

2) 调整子节点顺序，使之按照经过的节点的个数从小到大的顺序排序

从概率的角度来讲，如果经过的节点个数越多，那么新加入一个节点时产生重复路径的可能性就越大。因此，在权重相同的基础上，优先选择那些经过节点个数较少的子节点，在后续选择路径时寻找没有重复节点的过程就越简单，从而更容易寻找符合条件的路径。

3) 去掉子节点中权重较大的子节点

该条件是针对复杂程度很高的图，压缩之后剩下的节点基本可以两两形成路径。针对这样的情况，为了降低图的复杂度，对于图中某些子节点，因其权重比较大，虽然经过该节点有能够到达终点的有效路径，但由于其权重过大，该路径可能是结果不太好的路径。去掉这些权重较高的异常关系，可以降低图的复杂度，提高搜索效率，另一方面，也避免了搜索这些点耗费的时间，从而更快地搜索权重较低的路径。

经过分析，IBA的空间复杂度为O(n)，NCA、CCA及ICCA的空间复杂度为O(n2),其中n为图中总节点个数。

4 实验验证

4.1 数据说明及分析

为了不失一般性，实验数据采取“2016年华为软件精英大赛”的多个用例，这些用例来自华为公司在建设网络时的路由器交换机等网络元素构成的网络拓扑图。

1) 问题描述

给定一个带权重的有向图G=(V,E)，V为顶点集，E为有向边集，每一条有向边均包含权重。对于给定的顶点s、t，以及V的子集V′，在给定的时间内，寻找从s到t的不成环有向路径P，使得P经过V′中所有的顶点(对经过V′中节点的顺序不做要求)，并使得路径P上的所有有向边的权重之和尽可能小。

2) 数据说明

(1) 图中所有权重均为[1，20]内的整数；

(2) 任一有向边的起点不等于终点；

(3) 连接顶点A至顶点B的有向边可能超过一条，其权重可能一样，也可能不一样；

(4) 有向图的顶点不会超过600个，每个顶点出度(以该点为起点的有向边数量)不超过8；

(5)V′中元素个数不超过50；

(6) 从s到t的不成环有向路径P是指，P为由一系列有向边组成的从s至t的有向连通路径，且不允许重复经过任一节点；

(7) 路径的权重是指所有组成该路径的所有有向边的权重之和。

3) 数据格式

(1) 图的数据中，每一行包含如下的信息：{LinkID,SourceID,DestinationID,Cost}，其中LinkID为该有向边的索引，SourceID为该有向边的起始顶点的索引，DestinationID为该有向边的终止顶点的索引，Cost为该有向边的权重。顶点与有向边的索引均从0开始 编号(不一定连续，但用例保证索引不重复)。

(2) 路径信息中，只有一行如下数据：SourceID,DestinationID,IncludingSet。其中，SourceID为该路径的起点，DestinationID为该路径的终点，IncludingSet表示必须经过的顶点集合V′，其中不同的顶点索引之间用“|”分割。

4) 实验环境

Windows7 64位操作系统，处理器为Intel core i5，jre1.6，32位Java虚拟机，可占用的最大内存为2 GB。

4.2 实验方法及结果分析

1) IBA、NCA、CCA的比较

为了验证回溯法，IBA、NCA以及CCA之间的效果，将进行四组实验，求解时间限定为10秒，从实验1到实验4将会逐渐增加图中的总节点个数和图中边的条数，而中间节点个数保持不变。实验将从最终结果路径的权重,找出最终结果的使用时间两个维度进行比较。

实验1总节点个数10,必经节点个数3，图的边数39，如图3所示。

图3 实验1实验结果

从实验1的实验结果可以看出，IBA比Backtrack的效率要高一些，基于节点压缩的NCA和CCA效果提高不明显，这是因为压缩节点的过程要耗费一些时间，当图的复杂度较低时，效率提高就不太明显了。

实验2总节点个数20,必经节点个数5，图的边数55，如图4所示。

图4 实验2实验结果

从实验2的实验结果可以看出，IBA、NCA、CCA相比Backtrack效果有明显提高，CCA效果则更加明显；IBA和NCA效果相似，这是因为图中较偏僻的节点较少。

实验3总节点个数30,必经节点个数10，图的边数135，如图5所示。

图5 实验3实验结果

从实验3的实验结果可以看出当图的复杂度逐渐提高时，CCA的优越性更加明显地体现出来了。

实验4总节点个数40,必经节点个数10，图的边数229，如图6所示。

图6 实验4实验结果

实验4的结果表明，当图的复杂度达到更高时，Backtrack的实用性就不那么好了，而CCA的效率依然很好。

从实验结果可以看出，IBA无论在得到的结果路径的权重还是搜索时间上，都比Backtrack要好；NCA比IBA有一定的进步，但效果不明显，主要原因是实验中所使用的图中，存在偏僻节点的情况不多；而CCA在各个维度上相比前三种算法，都大大地提高了搜索结果的质量和效率，可见CCA是一种很有效解决这一问题的算法。

2) CCA和ICCA的比较

从前4个实验结果来看，Backtrack、IBA、NCA的效率随着图中节点个数的增加急剧降低。因此，继续增加节点个数将变得没有意义，接下来将只针对CCA和ICCA之间的比较。

实验环境和实验1-实验4的相同，也将逐渐增加总节点个数和图中边的条数，另外还会逐渐增加中间节点集合的大小，将从以下5个实验进行比较。

实验5总节点个数60,必经节点个数10，图的边数285，如图7所示。

图7 实验5的实验结果

实验6总节点个数100,必经节点个数15，图的边数516，如图8所示。

图8 实验6的实验结果

实验7总节点个数200,必经节点个数20，图的边数997，如图9所示。

图9 实验7的实验结果

实验8总节点个数400,必经节点个数28，图的边数2 178，如图10所示。

图10 实验8的实验结果

实验9总节点个数600,必经节点个数50，图的边数3 418，如图11所示。

图11 实验9的实验结果

从实验结果可以看出，ICCA相比CCA，其最终解都要好一些，因此，3.3节中的改进策略是行之有效的。

5 结 语

无论是“邮递员问题”、“旅行家问题”、公交车专线设计以及网络选路问题，还是其他生活中类似问题，都可以抽象为本文研究的寻径问题。本文提出的IBA和NCA适用于规模中等的问题。如果图中有很多相对偏僻的节点，则建议使用NCA；CCA和ICCA这两种算法适用于规模较大的问题，算法实现难度较大，如果问题可以通过调整字节点的排序规则来提高搜索效率，则使用ICCA。

由于当问题规模变得更加庞大时，CCA和ICCA在给定的时间内也无法将整个解空间搜索完全，得不到最优解。接下来将会把压缩思想融入到遗传算法、蚁群算法等启发式算法中，以期获得更高效的搜索算法，从而解决更大规模的寻径问题。

[1] 章登义,吴文李,欧阳黜霏.RDF图的Top-k最短路径查询[J].电子学报,2015,43(8):1531-1537.

[2] 王峰,曼媛,段俊洁.一种改进的求解前N条最短路径问题的多重标号算法[J].小型微型计算机系统,2016,37(7):1482-1487.

[3] 冯琳耀,袁林旺,罗文,等.节点约束型最短路径的几何代数算法[J].电子学报,2014,42(5):846-851.

[4] 戚远航,蔡延光,蔡颢,等.旅行商问题的混沌混合离散蝙蝠算法[J].电子学报,2016,44(10):2543-2547.

[5] 王勇臻,陈燕,张金松.求解TSP的学习记忆果蝇算法[J].小型微型计算机系统,2016,37(12):2722-2726.

[6] 吴新杰,王静文,黄国兴,等.一种求解旅行商问题的改进蛙跳算法[J].小型微型计算机系统,2015,36(5):1078-1081.

[7] 刘大伟,吕元娜,余智华.一种改进的复杂网络链路预测算法[J].小型微型计算机系统,2016,37(5):1071-1074.

[8] 安莹,黄家玮,罗熹,等.延迟容忍网络中一种基于节点介数的拥塞感知路由算法[J].小型微型计算机系统,2014,35(9):2062-2067.

[9] 李晓华,王士猛,杨晓春,等.基于Grid网格划分的改进路网最短路径查询[J].小型微型计算机系统,2014,35(9):1937-1942.

SEARCHPATHOPTIMIZATIONALGORITHMBASEDONNODECOMPRESSION

Liao Zhifang Chen Liangming Peng Zhiwen Li Yanbing

(SchoolofSoftware,CentralSouthUniversity,Changsha410075,Hunan,China)

The shortest path problem is a classic problem，while the current study is mostly for a given starting point and end point, choose the shortest path from the starting point to the end, and has achieved a lot of results. For the limit time of the research achievements of the shortest path problem is relatively less, this kind of problem is ubiquitous in real life. In this paper, we propose several optimization algorithms for time-dependent optimization of this problem, from the improvement of backtracking method to the method of different node compression, an improved backtracking method and three algorithms based on node compression are proposed. Implemented in a limited amount of time, starting from the starting point after a given node set to reach the destination path selection, and according to different complexity of network diagram, can choose the appropriate algorithm to deal with, which can effectively solve the problem.

Shortest path Time constrained Node compression Search path

2017-02-12。国家自然科学基金青年项目(61301136)。廖志芳，副教授，主研领域：数据挖掘，推荐系统。陈亮名，硕士。彭志文，硕士。李严冰，硕士。

TP393

A

10.3969/j.issn.1000-386x.2017.11.045