过必经点的最短无环路径算法

余英瀚

【摘要】通过启发式算法解决在带权有向图中从某一源点经过指定的必经点集到达目标终点且节点不重复的最短无环路径问题。随着复杂网络优化问题的不断凸显，对网络分析算法的性能要求也日渐升高。经过必经点的最短无环路径问题的复杂度不亚于旅行商问题（TSP），但并没有获得广泛的关注。近些年来出现了一种高效的整数线性规划公式（ILP）来解决此类问题，这种ILP算法适用于有节点不相交约束的最短路径问题，但是实验表明在大型复杂网络中这种算法的时间开销过高。因此有了本论文的三种启发式算法，大量的实验表明这些算法在大多数情况下都能在可接受的时间范围内找出合理解，这些解与最优解的误差都在可接受的范围内，后续的CPU开销数据也表明此类启发式算法的资源消耗远小于整数线性规划（ILP）算法。

【关键词】弹性路由 最短路径问题 必经点

作为社会关键基础设施，通信网络的可伸缩性和生命力是十分重要的。参见通信网络中的弹性和生命力结构性框架。根据路由路径约束的等级，其通过约束路径来寻找节点（或边）不重复的路由，在某些情况下所寻求的路径必须满足经过指定的必经点点集的约束，这些必经点可能是基于某种特性（比如高可靠性）被选出的，也可能是根据基于运营商之间协议所产生的参数来决定的，或者是由于其他网络管理的约束条件所制定的。针对诸如此类从某一源点经过一系列给定的必经点到达另一终点的最短路径计算问题的算法少之又少，已知的最早的算法是由Saksena和Kumar提出的，他们尝试运用最佳性原理开发出一种精确算法来计算经过指定点集的最短路径问题（路径可能有环）。

考虑到时间复杂度，Dreyfus在中指出，从某一源点经过必经点点集到目标节点的最短路径算法（可能有环路）的时间复杂度并不亚于k维旅行商问题（TSP），这里k-2代表必经点的个数。Andrade也提出，如果必经点点集是由有向图中除源点和终点外的所有节点构成的，此类问题相当于寻找最短权重的汉密尔顿通路，属于NP-困难问题。

文章的其余部分结构如下。第一部分介绍了该问题模型的数学公式和数学方法。第二部分着重叙述了计算经过必经点的最短无环路径的启发式算法，包括最早的SK66算法，以及SK66算法的修正版算法。第三部分描述了针对此类最短路径问题的三种变体型启发式算法。第四部分为实验数据结果。第五部分为总结。

一、数学模型

对该问题的数学建模旨在寻找经过给定必经点点集的无环最短路径，并且满足要求路径上没有交点。一条无环路径上每个节点只能经过一次，因此所有的路径都必须是不存在环路的。

（一）数学符号

在本文第二及第三部分用了如下数学定义。定义有向图G=（V，A），其中点集V={v1，...，vn}，有向边集A={a1，…，am}。定义如果vi，vj∈V，并且vi=vj，ak=（vi，vj）∈A，则vi为边尾vj为边头。边（vi，vj）定义为从点vi到vj的路径。边（vi，vj）和边（vj，vi）为对称边。

一条路径定义为从源点s开始的到终点t的一个不同点组成的连续序列，（s，t∈V），将其定义为p=，其中（vi，vi+1）∈A，？坌i∈{1，…，k-1}，k为该路径中节点的个数。由Vp代表路径p中所有点的点集，Ap代表路径上所有边的边集合，Ap=∪？坌i∈{1，...，k-1}（vi，vi+1）。经过一条边（vi，vj）∈A的花费（权重）定义为w（vi，vj），假设为大于0的正数。一条路径的权重为路径上所有边权重的代数和，Dp=（vi，vj）∈Ap w（vi，vj）。如果两点之间不存在通路，则定义其权重为无穷。

二、过指定必经点的最短路径

最初的SK66算法，虽然不能保证计算出最优路径，但是其时间复杂度与必经点点集（|Vs|）的规模成正比；在初始化阶段首先计算（|Vs|+2）|Vs|个最短路径；在之后的每一步需要|Vs|2次计算，该步骤中大部分的时间开销花费在节点计算过程中，其最差时间复杂度为|V|log2|V|；因此，SK66算法的最差时间复杂度为O（|Vs+2|2|A|log2|V|+|Vs|2|V|log2|V|），其中假设最短子路径计算是基于二叉堆的Dijkstra算法。

（一）Saksena和Kumar提出的算法（SK66）

SK66算法通过在每一次子路径的选择中找出当前最短路径，计算出从某一源点到另一终点并且经过制定必经点点集的最终最短路径（可能存环路）。算法的初始化步骤为：

（1）计算出必经点点集|Vs|中任意两点的最短距离（没有任何限制），和源点s到点集中每一点的最短距离；

（2）计算出必经点点集Vs中每一点到终点的最短距离。

假定D（vi，vl）代表从点vi到vl的最短路径花费，其中vi∈Vs ∪{s}并且vl∈Vs，f0vi代表从一点vi∈Vs到终点t的最短路径花费。

（二）SK66算法改进版

此部分算法为SK66算法的改进版本，它可以保证所获得的路径是不含环路的，并且提高了原始算法的性能。此改进版本的算法牺牲了一定空间来同时存储更多的中间子路径，来换取时间上的充裕，这种算法暂命名为SK。

为了保证获得的路径是无环的，每一次迭代（12）和（11）进行时必须严格保证迭代获得的子路径不含环路。

根据上述公式，在SK66算法的每一次迭代中，对于每一个必经点集Vs中的点vi都要选出一个新的中间点vl（vl∈Vs）放到路径中。SK66的这个步骤在寻找局部最优路径时也许会提前因为更高的权重而排除掉本身最优路径解的子路径，因为局部最优并不是全局最优解，并且可能造成之后的必经节点无法到达的窘境。此算法主要的改进在于，在每一次迭代η寻找vi到终点t的中间节点vl时，同时保留所有可能的中间点vl，而不是像SK66中一样寻找距离最近的中间节点vl，因此在此改进版本的算法中每一步的迭代需要保留|Vs|-1条路径。

三、保证路径上没有节点相交的变体型启发式算法

此部分着重介绍用于寻找经过指定必经点点集并且满足约束条件路径上节点互不相交的最短路径的两种不同的算法。

（一）主动子路径选取算法

在此部分着重介绍一种基于2.2章节SK算法的新算法，它在执行SK算法每一步的迭代过程中，每一次寻找子路径时都加入了严格的限制来确保所获得的子路径与将来的最终路径之间是没有相交节点的。然而这个过程并不能保证最终当所寻找的子路径联结起来时能形成一条从s到t的最短路径。

此算法的初始步骤为：

（1）运用算法（8）和（9），最多可以得到τ条（其中τ=|A|/|V|2 |VS|）该有向图中的最短路径（vi，vj），其中vi∈VS ∪ {s}，vj∈VS；若寻找到第k条最短路径Pij（k=1，…，τ）时，在图中移除掉点集（Vpij∪Vs）＼{s}之后仍能使源点s到终点t连通，此时寻找过程停止并保存路径Pij。

（2）运用算法（8）和（9），最多可以得到从节点vi到终点t的τ条（其中τ=|A|/|V|2|Vs|）该有向图中的最短路径（vi，t），其中vi∈Vs；若寻找到第k条最短路径Pit（k=1，…，τ）时，在图中移除掉点集（Vpit∪Vs）＼{t}之后仍能使源点s到终点t连通，此时寻找过程停止并保存路径Pit。

然后运用SK算法并在每一次迭代η中另加入限制，保证去掉子路径的节点（Vs∪VPit＼{t}）时源点s到终点t始终可以保持连通；类似的，在最后一步中，只有每一段无环子路径之间互相节点不相交才能保证最终从s到t路径的存在。

算法的最后一步选择中首先使用了（13），并且加入限制路径必须是无环并且互相之间节点不相交的。如果一段子路径p，可以使从源点s到某一点vl的子路径与从vl到终点t的子路径联合并且不存在环路，接下来需要验证这条联合路径是否有从s到t的备用节点不相交路径。

需要注意的是，虽然保证了每一段子路径都是从s到t的节点不相交路径，但这并不代表最终路径的存在。因此，此子路径主动选取算法仍然有待优化并辅以其他算法相配合。

（二）备用路径优先选取算法

在一切特定的网络环境中，3.1中的主动子路径选取算法选出的子路径也许并不能构成一条完整的路径。因此产生了与之相对的另一种算法来优先寻找备用路径，然后通过备用路径来找到对应的路径。

这种算法的原理是尝试在移除了所有必经点及其相关路径的有向图中寻找备用路径。首先根据已有的班得瑞算法[11]生成具有最短权重和的尽量包含最多节点并且节点之间互不相交的路径。然后对于每一条备用路径（用q代表其所包含的节点），在有向图中移除该备用路径的中间节点得到网络（V＼（Vq＼{s，t}），A），而后在该网络中运用SK算法得出其子路径。

如果之前的步骤出现问题不能找出子路径，此时需要重新运用公式（8）和（9）来计算在移除了必经点点集Vs中的所有点后的有向图中的最短备用子路径，然后针对每一条备用最短子路径使用SK算法计算出其子路径，重复此过程路径被找到。

（三）启发式算法的结合

命名3.1中的主动子路径选取算法为ASK，3.2中的备用路径优先选取为BSK；对于此类问题首先运用ASK算法，当网络环境特殊使用ASK没有合适解时在其中加入BSK算法，将此混合算法命名为ABSK。

四、结果

考虑到不同的网络环境做了两个不同的实验测试。第一组网络模型来自SNDlib[12]，反映的是真实世界中的网络，分别用了newyork，norway，india35，pioro40和germany50的网络模型；第二组网络使用了Georgia Tech Internetwork Topology Models软件（GT-ITM）生成模型，包含了5组平均出度为7的500节点网络模型。指定的必经节点数量定为2个4个或6个，完全随机分配。在每个网络中对于每一组必经点点集Vs，随机生成100对点集，产生20组样例，并以95%的置信区间为误差线标注在之后的图表上。

实验结果的衡量是根据解决问题数量的占比百分数来决定并标注的，以CPLEX求解器计算出的结果予以对比，来评价本文中启发式算法的效率。

五、结论

在某网络中从某一源点经过指定的必经点点集到达目标节点的路径的计算需求随着网络管理约束的丰富而日益增多。整数线性规划（ILP）[8]适用于解决此类问题并且满足限制子路径之间互相节点不相交，但时间成本过高。

根据本文的实验结果不难看出，基于启发式算法的主动路径选择和备用路径优先选择算法可以广泛应用于各种复杂的网络环境中，并且在可接受的误差范围内计算出可行解。相比于整数线性规划算法（ILP），该算法在CPU时间开销方面具有明显的优势，可以在网络拓扑环境日益复杂的今天被广泛应用。

参考文献

[1]J.P.Sterbenz，D.Hutchison，E.K.C？etinkaya，A.Jabbar，J.P.Rohrer， M.Sch¨oller，and P.Smith，“Resilience and survivability in communi- cation networks：Strategies，principles，and survey of disciplines，”Computer Networks，vol.54，no.8，pp.1245-1265，2010.Resilient and Survivable networks.

[2]王实，高文.增强型朴索贝叶斯学习[J].计算机科学，2000，27（4）；46-49.

[3]林澜，闫春钢，等.基于稳定分支的变权网络最优路径算法[J].电子学报，2006，34（7）：1222-1225.

[4]曹政才，等.面向城市交通网络的一种新型动态路径寻优方法[J].电子学报，2012，40（10）：2043-2067.