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

邢治乐; 张淑蓉

doi:10.13451/j.sxu.ns.2023026

山西大学学报(自然科学版) ›› 2024, Vol. 47 ›› Issue (01) : 112 -121. DOI: 10.13451/j.sxu.ns.2023026

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

邢治乐, 张淑蓉

作者信息 +

Author information +

文章历史 +

PDF (1548K)

摘要

时变最短路径设计是网络优化的一类重要问题。特别是针对结构复杂的网络，通常采用时变超图作为网络拓扑结构，所以在时变超图中研究路径优化问题受到广泛关注。时变后向超图（TVBH）是一类特殊的时变超图。文章主要是研究了在TVBH中构建满足时间约束的给定源点与所有网络节点间的最优时变后向超路（TV-B超路）问题。由于该类问题是NP(Non-deterministic Polynomial)完全的，文章利用时间离散的方法设计了伪多项式时间算法，并进一步提出了有效近似算法得到了(1+ε)近似解。最后通过实例仿真表明了利用近似算法能够显著降低运算复杂性。