时间约束下最优时变后向超路近似算法设计  

Approximate Algorithm Design of Optimal Time-varying Backward Hyperpaths with Time Constraints

作　　者：邢治乐 张淑蓉 XING Zhile;ZHANG Shurong(School of Mathematics,Taiyuan University of Technology,Taiyuan 030000,China)

机构地区：[1]太原理工大学数学学院,山西太原030000

出　　处：《山西大学学报（自然科学版）》2024年第1期112-121,共10页Journal of Shanxi University(Natural Science Edition)

基　　金：山西省自然科学基金(202103021224058)。

摘　　要：时变最短路径设计是网络优化的一类重要问题。特别是针对结构复杂的网络,通常采用时变超图作为网络拓扑结构,所以在时变超图中研究路径优化问题受到广泛关注。时变后向超图(TVBH)是一类特殊的时变超图。文章主要是研究了在TVBH中构建满足时间约束的给定源点与所有网络节点间的最优时变后向超路(TV-B超路)问题。由于该类问题是NP(Non-deterministic Polynomial)完全的,文章利用时间离散的方法设计了伪多项式时间算法,并进一步提出了有效近似算法得到了(1+ε)近似解。最后通过实例仿真表明了利用近似算法能够显著降低运算复杂性。Time-varying shortest path design is an important problem in network optimization.Especially for networks with complex structures,time-varying hypergraph is usually used as the network topology,so the research of path optimization in time-varying hypergraph has received wide attention.Time-varying backward hypergraph(TVBH)is a special kind of time-varying hypergraph.In this paper,we mainly studies the problem of constructing the optimal time-varying backward hyperpath(TV-B hyperpath)between a given source node and all network nodes satisfying time constraints in TVBH.Because this kind of problem is NP(Non-deterministic Polynomial)complete,we design a pseudopolynomial time algorithm using the method of time discretization,and further propose an effective approximation algorithm to obtain the(1+e)approximate solution.Finally,an example simulation shows that using the approximation algorithm can significantly reduce the computational complexity.

关 键 词：时变后向超图 时间约束下的最优超路 近似算法 伪多项式时间算法 时间离散 

分 类 号：O157[理学—数学]