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

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

2、内，后续的CPU开销数据也说明此类启发式算法的资源消耗远小于整数线性规划ILP算法。 弹性路由 最短途径问题 必经点作为社会关键根底设施，通信网络的可伸缩性和生命力是非常重要的。参见通信网络中的弹性和生命力构造性框架。根据路由途径约束的等级，其通过约束途径来寻找节点或边不重复的路由，在某些情况下所寻求的途径必须满足经过指定的必经点点集的约束，这些必经点可能是基于某种特性比方高可靠性被选出的，也可能是根据基于运营商之间协议所产生的参数来决定的，或者是由于其他网络管理的约束条件所制定的。针对诸如此类从某一源点经过一系列给定的必经点到达另一终点的最短途径计算问题的算法少之又少，的最早的算法是由Sak

3、sena和Kumar提出的，他们尝试运用最正确性原理开发出一种准确算法来计算经过指定点集的最短途径问题途径可能有环。考虑到时间复杂度，Dreyfus在中指出，从某一源点经过必经点点集到目的节点的最短途径算法可能有环路的时间复杂度并不亚于k维旅行商问题TSP，这里k-2代表必经点的个数。Andrade也提出，假如必经点点集是由有向图中除源点和终点外的所有节点构成的，此类问题相当于寻找最短权重的汉密尔顿通路，属于NP-困难问题。文章的其余部分构造如下。第一部分介绍了该问题模型的数学公式和数学方法。第二部分着重表达了计算经过必经点的最短无环途径的启发式算法，包括最早的SK66算法，以及SK66算法的

4、修正版算法。第三部分描绘了针对此类最短途径问题的三种变体型启发式算法。第四部分为实验数据结果。第五部分为总结。一、数学模型对该问题的数学建模旨在寻找经过给定必经点点集的无环最短途径，并且满足要求途径上没有交点。一条无环途径上每个节点只能经过一次，因此所有的途径都必须是不存在环路的。一数学符号在本文第二及第三部分用了如下数学定义。定义有向图G=V，A，其中点集V=v1，.，vn，有向边集A=a1，am。定义假如vi，vjV，并且vi=vj，ak=vi，vjA，那么vi为边尾vj为边头。边vi，vj定义为从点vi到vj的途径。边vi，vj和边vj，vi为对称边。一条途径定义为从源点s开场的到终点t

5、的一个不同点组成的连续序列，s，tV，将其定义为p=，其中vi，vi+1A，？坌i1，k-1，k为该途径中节点的个数。由Vp代表途径p中所有点的点集，Ap代表途径上所有边的边集合，Ap=？坌i1，.，k-1vi，vi+1。经过一条边vi，vjA的花费权重定义为wvi，vj，假设为大于0的正数。一条途径的权重为途径上所有边权重的代数和，Dp=vi，vjAp wvi，vj。假如两点之间不存在通路，那么定义其权重为无穷。二、过指定必经点的最短途径最初的SK66算法，虽然不能保证计算出最优途径，但是其时间复杂度与必经点点集|Vs|的规模成正比；在初始化阶段首先计算|Vs|+2|Vs|个最短途径；在之后

6、的每一步需要|Vs|2次计算，该步骤中大部分的时间开销花费在节点计算过程中，其最差时间复杂度为|V|log2|V|；因此，SK66算法的最差时间复杂度为O|Vs+2|2|A|log2|V|+|Vs|2|V|log2|V|，其中假设最短子途径计算是基于二叉堆的Dijkstra算法。一Saksena和Kumar提出的算法SK66SK66算法通过在每一次子途径的选择中找出当前最短途径，计算出从某一源点到另一终点并且经过制定必经点点集的最终最短途径可能存环路。算法的初始化步骤为：1计算出必经点点集|Vs|中任意两点的最短间隔 没有任何限制，和源点s到点集中每一点的最短间隔 ；2计算出必经点点集Vs中每

7、一点到终点的最短间隔 。假定Dvi，vl代表从点vi到vl的最短途径花费，其中viVs s并且vlVs，f0vi代表从一点viVs到终点t的最短途径花费。二SK66算法改良版此部分算法为SK66算法的改良版本，它可以保证所获得的途径是不含环路的，并且进步了原始算法的性能。此改良版本的算法牺牲了一定空间来同时存储更多的中间子途径，来换取时间上的充裕，这种算法暂命名为SK。为了保证获得的途径是无环的，每一次迭代12和11进展时必须严格保证迭代获得的子途径不含环路。根据上述公式，在SK66算法的每一次迭代中，对于每一个必经点集Vs中的点vi都要选出一个新的中间点vlvlVs放到途径中。SK66的这个

8、步骤在寻找部分最优途径时也许会提早因为更高的权重而排除掉本身最优途径解的子途径，因为部分最优并不是全局最优解，并且可能造成之后的必经节点无法到达的窘境。此算法主要的改良在于，在每一次迭代寻找vi到终点t的中间节点vl时，同时保存所有可能的中间点vl，而不是像SK66中一样寻找间隔 最近的中间节点vl，因此在此改良版本的算法中每一步的迭代需要保存|Vs|-1条途径。 三、保证途径上没有节点相交的变体型启发式算法此部分着重介绍用于寻找经过指定必经点点集并且满足约束条件途径上节点互不相交的最短途径的两种不同的算法。一主动子途径选取算法在此部分着重介绍一种基于2.2章节SK算法的新算法，它在执行SK算

9、法每一步的迭代过程中，每一次寻找子途径时都参加了严格的限制来确保所获得的子途径与将来的最终途径之间是没有相交节点的。然而这个过程并不能保证最终当所寻找的子途径联结起来时能形成一条从s到t的最短途径。此算法的初始步骤为：1运用算法8和9，最多可以得到条其中=|A|/|V|2 |VS|该有向图中的最短途径vi，vj，其中viVS s，vjVS；假设寻找到第k条最短途径Pijk=1，时，在图中移除掉点集VpijVss之后仍能使源点s到终点t连通，此时寻找过程停顿并保存途径Pij。2运用算法8和9，最多可以得到从节点vi到终点t的条其中=|A|/|V|2|Vs|该有向图中的最短途径vi，t，其中viV

10、s；假设寻找到第k条最短途径Pitk=1，时，在图中移除掉点集VpitVst之后仍能使源点s到终点t连通，此时寻找过程停顿并保存途径Pit。然后运用SK算法并在每一次迭代中另参加限制，保证去掉子途径的节点VsVPitt时源点s到终点t始终可以保持连通；类似的，在最后一步中，只有每一段无环子途径之间互相节点不相交才能保证最终从s到t途径的存在。算法的最后一步选择中首先使用了13，并且参加限制途径必须是无环并且互相之间节点不相交的。假如一段子途径p，可以使从源点s到某一点vl的子途径与从vl到终点t的子途径结合并且不存在环路，接下来需要验证这条结合途径是否有从s到t的备用节点不相交途径。需要注意的

11、是，虽然保证了每一段子途径都是从s到t的节点不相交途径，但这并不代表最终途径的存在。因此，此子途径主动选取算法仍然有待优化并辅以其他算法相配合。二备用途径优先选取算法在一切特定的网络环境中，3.1中的主动子途径选取算法选出的子途径也许并不能构成一条完好的途径。因此产生了与之相对的另一种算法来优先寻找备用途径，然后通过备用途径来找到对应的途径。这种算法的原理是尝试在移除了所有必经点及其相关途径的有向图中寻找备用途径。首先根据已有的班得瑞算法11生成具有最短权重和的尽量包含最多节点并且节点之间互不相交的途径。然后对于每一条备用途径用q代表其所包含的节点，在有向图中移除该备用途径的中间节点得到网络V

12、Vqs，t，A，而后在该网络中运用SK算法得出其子途径。假如之前的步骤出现问题不能找出子途径，此时需要重新运用公式8和9来计算在移除了必经点点集Vs中的所有点后的有向图中的最短备用子途径，然后针对每一条备用最短子途径使用SK算法计算出其子途径，重复此过程途径被找到。三启发式算法的结合命名3.1中的主动子途径选取算法为ASK，3.2中的备用途径优先选取为BSK；对于此类问题首先运用ASK算法，当网络环境特殊使用ASK没有适宜解时在其中参加BSK算法，将此混合算法命名为ABSK。四、结果考虑到不同的网络环境做了两个不同的实验测试。第一组网络模型来自SNDlib12，反映的是真实世界中的网络，分别用

13、了newyork，norway，india35，pioro40和germany50的网络模型；第二组网络使用了Georgia Tech Internetwork Topology Models软件GT-ITM生成模型，包含了5组平均出度为7的500节点网络模型。指定的必经节点数量定为2个4个或6个，完全随机分配。在每个网络中对于每一组必经点点集Vs，随机生成100对点集，产生20组样例，并以95%的置信区间为误差线标注在之后的图表上。实验结果的衡量是根据解决问题数量的占比百分数来决定并标注的，以CPLEX求解器计算出的结果予以比照，来评价本文中启发式算法的效率。五、结论在某网络中从某一源点经过

14、指定的必经点点集到达目的节点的途径的计算需求随着网络管理约束的丰富而日益增多。整数线性规划ILP8适用于解决此类问题并且满足限制子途径之间互相节点不相交，但时间本钱过高。根据本文的实验结果不难看出，基于启发式算法的主动途径选择和备用途径优先选择算法可以广泛应用于各种复杂的网络环境中，并且在可承受的误差范围内计算出可行解。相比于整数线性规划算法ILP，该算法在CPU时间开销方面具有明显的优势，可以在网络拓扑环境日益复杂的今天被广泛应用。参考文献1J.P.Sterbenz，D.Hutchison，E.K.C？etinkaya，A.Jabbar，J.P.Rohrer， M.Scholler，and P.Smith，“Resilience and survivability in muni- cation networks：Strategies，principles，and survey of disciplines，p