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

《关于过必经点的最短无环路径算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、关于过必经点的最短无环路径算法导读：现在请大家鉴赏的文章是路径和算法方面的毕业论文题目。本篇文章有利于同专业方向的大学硕士研究生和本科生在写作毕业论文范文前写作和查找资料有清晰思路。（辽金融职业学院，辽沈阳110122）【摘要】通过启发式算法解决带权有向图中从某一源点经过指定的必经点集到达目标终点且节点不重复的最短无环路径问题.随着复杂X络优化问题的不断凸显，对X络分析算法的性能要求也日渐升高.经过必经点的最短无环路径问题的复杂度不亚于旅行商问题（TSP），但没有获得广泛的关注.近些年来出现了一种高效的整数线性规划公式（ILP）来解决此类问题

2、，这种ILP算法适用于有节点不相交约束的最短路径问题，但是实验表明大型复杂X络中这种算法的时间开销过高.此有了本论文的三种启发式算法，大量的实验表明这些算法大多数情况下都能接受的时间范围内找出合理解，这些解与最优解的误差都接受的范围内，后续的CPU开销数据也表明此类启发式算法的资源消耗远于整数线性规划（ILP）算法.【关键词】弹性路由最短路径问题必经点作为社会关键基础设施，通信X络的伸缩性和生命力是十分重要的.参见通信X络中的弹性和生命力结构性框架.根据路由路径约束的等级，其通过约束路径来寻找节点（或边）不重复的路由，某些情况下寻求的路径必须

3、满足经过指定的必经点点集的约束，这些必经点能是基于某种特性（比高靠性）被选出的，也能是根据基于运营商间协议产生的参数来决定的，或者是由于其他X络管理的约束条件制定的.针对诸此类从某一源点经过一系列给定的必经点到达另一终点的最短路径计算问题的算法少又少，知的最早的算法是由Saksena和Kumar提出的，他们尝试运用最佳性原理开发出一种精确算法来计算经过指定点集的最短路径问题（路径能有环）.考虑到时间复杂度，Dreyfus中指出，从某一源点经过必经点点集到目标节点的最短路径算法（能有环路）的时间复杂度不亚于k维旅行商问题（TSP），这里k2代表

4、必经点的个数.Andrade也提出，果必经点点集是由有向图中除源点和终点外的有节点构成的，此类问题相当于寻找最短权重的汉密顿通路，属于NP困难问题.文章的其余部分结构下.第一部分介绍了该问题模型的数学公式和数学方法.第二部分着重叙述了计算经过必经点的最短无环路径的启发式算法，包括最早的SK66算法，以及SK66算法的修正版算法.第三部分描述了针对此类最短路径问题的三种变体型启发式算法.第四部分为实验数据结果.第五部分为总结.一、数学模型对该问题的数学建模旨寻找经过给定必经点点集的无环最短路径，且满足要求路径上没有交点.一条无环路径上每个节点只

5、能经过一次，此有的路径都必须是不存环路的.(一)数学符号二、过指定必经点的最短路径最初的SK66算法，虽然不能保证计算出最优路径，但是其时间复杂度与必经点点集（

6、Vs

7、）的规模成正比初始化阶段首先计算(

8、Vs

9、+2)

10、Vs

11、个最短路径后的每一步需要

12、Vs

13、2次计算，该步骤中大部分的时间开销花费节点计算过程中，其最差时间复杂度为

14、V

15、log2

16、V

17、;此，SK66算法的最差时间复杂度为O(

18、Vs+2

19、2

20、A

21、log2

22、V

23、+

24、Vs

25、2

26、V

27、log2

28、V

29、)，其中假设最短子路径计算是基于二叉堆的Dijkstra算法.(一)Saksena和Kumar

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

31、Vs

32、中任意两点的最短距离（没有任何限制），和源点s到点集中每一点的最短距离（2）计算出必经点点集Vs中每一点到终点的最短距离.假定D(vi，vl)代表从点vi到vl的最短路径花费，其中vi∈Vs∪{s}且vl∈Vs，f0vi代表从一点vi∈Vs到终点t的最短路径花费.于是该算法以迭代地表示为：其中η=1，2，…，

33、本篇关于过必经点的最短无环路径算法论

34、文范文综合参考评定下度:优质题目Vs

35、1，每一次迭代经寻得的路径上新加入指定点集中距离当前vi路径最近的一点，且算法中每一次从点vi经过新的一点vl到终点t的路径（能包含环路）的寻找过程中必须保证剩余必经点点集中不包含经经过的节点vi.(二)SK66算法改进版此部分算法为SK66算法的改进版本，以保证获得的路径是不含环路的，且提高了原始算法的性能.此改进版本的算法牺牲了一定空间来时存储更多的中间子路径，来换取时间上的充裕，这种算法暂命名为SK.为了保证获得的路径是无环的，每一次迭代（12）和（11）进行时必须严格保证迭代获得的子路径不含环路.

36、根据上述公式，SK66算法的每一次迭代中，对于每一个必经点集Vs中的点vi都要选出一个新的中间点vl（vl∈Vs）放到路径中.SK66的这个步骤寻找局部最优路径时也