Steiner树优化问题的算法研究综述

doi:10.3778/j.issn.1002-8331.2311-0016

摘要/Abstract

摘要： 最优Steiner树问题（Steiner tree problem，STP）是一个经典的组合优化问题，许多工程问题都可以归结为最优Steiner树问题。STP被广泛应用于通信网络、电路设计、VLSI设计等领域。然而，STP是典型的NP难问题，还没有多项式时间的精确算法求解该问题。目前，求解该问题的算法主要集中在基于启发式的近似算法、智能优化算法、信息传播算法等，并取得了很好的效果。在不同规模的网络中，基于传统遗传算法给出一种叶交叉机制（leaf crossover，LC），使用该机制的算法性能表现更好。通过对这些算法的原理、性能、精度等方面进行梳理，归纳出算法的优缺点，并指出STP的研究方向和算法设计路径，对于相关问题的研究有指导意义。

关键词: Steiner树问题（STP）, 启发式算法, 信息传播算法, 智能优化算法, 叶交叉（LC）

Abstract: The optimal Steiner tree problem (STP) is a classical combinatorial optimization problem, and many engineering problems can be summed up as optimal Steiner tree problems. STP is widely used in communication networks, circuit design, VLSI design, and other fields. However, the STP is a typical NP hard problem, and there is no precise polynomial time algorithm to solve it. Currently, the algorithms for solving this problem mainly focus on heuristic based approximation algorithms, intelligent optimization algorithms, and belief propagation algorithms, and have achieved good results. By sorting out the principles, performance, accuracy, and other aspects of these algorithms, the advantages and disadvantages of the algorithms are summarized, and the research direction and algorithm design path for STP are pointed out, which has guiding significance for the research of related issues.

Key words: Steiner tree problem (STP), heuristics algorithms, belief propagation algorithms, intelligent optimization algorithms, leaf crossover (LC)

王军霞, 王晓峰, 彭庆媛, 华盈盈, 宋家欢. Steiner树优化问题的算法研究综述[J]. 计算机工程与应用, 2024, 60(9): 19-29.

WANG Junxia, WANG Xiaofeng, PENG Qingyuan, HUA Yingying, SONG Jiahuan. Review of Algorithmic Research on Steiner Tree Optimization Problems[J]. Computer Engineering and Applications, 2024, 60(9): 19-29.

参考文献

[1] SADEGHI A, FR?HLICH H. Steiner tree methods for optimal sub-network identification: an empirical study[J]. BMC Bioinformatics, 2013, 14(1): 1-19.
[2] MIN M, DU H, JIA X, et al. Improving construction for connected dominating set with Steiner tree in wireless sensor networks[J]. Journal of Global Optimization, 2006, 35: 111-119.
[3] 王辛, 王晓峰, 许道云, 等. 一种求解双目标最小生成树的警示传播算法[J]. 中国科学: 信息科学, 2020, 50(10): 1501-1510.
WANG X, WANG X F, XU D Y, et al. A warning propagation algorithm for solving dual objective minimum spanning tree[J]. Chinese Science: Information Science, 2020, 50(10): 1501-1510.
[4] BEZEN?EK M, ROBI? B. A survey of parallel and distributed algorithms for the Steiner tree problem[J]. International Journal of Parallel Programming, 2014, 42: 287-319.
[5] HAN L, WANG C, XU D, et al. Algorithms for the prize-collecting k-Steiner tree problem[J]. Tsinghua Science and Technology, 2022, 27(5): 785-792.
[6] GENDREAU M, LAROCHELLE J F, SANSO B. A tabu search heuristic for the Steiner tree problem[J]. Networks: an International Journal, 1999, 34(2): 162-172.
[7] KOU L, MARKOWSKY G, BERMAN L. A fast algorithm for Steiner trees[J]. Acta Informatica, 1981, 15: 141-145.
[8] TAKAHASHI H, MATSUYAMA A. An approximate solution for the Steiner problem in graphs[J]. Math Japonica, 1980, 24: 573-577.
[9] HWANG F K, RICHARDS D S. Steiner tree problems[J]. Networks, 1992, 22(1): 55-89.
[10] CALEFFI M, AKYILDIZ I F, PAURA L. On the solution of the Steiner tree NP-hard problem via physarum bionetwork[J]. IEEE/ACM Transactions on Networking, 2014, 23(4): 1092-1106.
[11] BRAUNSTEIN A, MUNTONI A. Practical optimization of Steiner trees via the cavity method[J]. Journal of Statistical Mechanics: Theory and Experiment, 2016(7): 073302.
[12] ESBENSEN H. Computing near‐optimal solutions to the Steiner problem in a graph using a genetic algorithm[J]. Networks, 1995, 26(4): 173-185.
[13] LIU G, HUANG X, GUO W, et al. Multilayer obstacle-avoiding X-architecture Steiner minimal tree construction based on particle swarm optimization[J]. IEEE Transactions on Cybernetics, 2014, 45(5): 1003-1016.
[14] CAMACHO-VALLEJO J F, GARCIA-REYES C. Co-evolutionary algorithms to solve hierarchized Steiner tree problems in telecommunication networks[J]. Applied Soft Computing, 2019, 84: 105718.
[15] 吕其诚. 图的Steiner树问题的快速算法[J]. 黑龙江大学自然科学学报, 1991(2): 61-64.
LYU Q C. A fast algorithm for the Steiner tree problem of graphs[J]. Journal of Natural Sciences of Heilongjiang University, 1991(2): 61-64.
[16] BIAZZO I, BRAUNSTEIN A, ZECCHINA R. Performance of a cavity-method-based algorithm for the prize-collecting Steiner tree problem on graphs[J]. Physical Review E, 2012, 86(2): 026706.
[17] LAI X, ZHOU Y, XIA X, et al. Performance analysis of evolutionary algorithms for Steiner tree problems[J]. Evolutionary Computation, 2017, 25(4): 707-723.
[18] BRAUNSTEIN A, MUNTONI A P. The cavity approach for Steiner trees packing problems[J]. Journal of Statistical Mechanics: Theory and Experiment, 2018 (12): 123401.
[19] LI J, LIU S, LICHEN J, et al. Approximation algorithms for solving the 1-line Euclidean minimum Steiner tree problem[J]. Journal of Combinatorial Optimization, 2019, 39(2): 492-508.
[20] SIEBERT M, AHMED S, NEMHAUSER G. A simulated annealing algorithm for the directed Steiner tree problem[J]. arXiv:2002.03055, 2020.
[21] REHFELDT D, KOCH T. On the exact solution of prize-collecting Steiner tree problems[J]. INFORMS Journal on Computing, 2021, 34(2): 872-889.
[22] C?LINESCU G, WANG X. Combination algorithms for Steiner tree variants[J]. Algorithmica, 2022, 85(1): 153-169.
[23] LI H, LIU H, LIU J, et al. Edge-disjoint Steiner trees and connectors in graphs[J]. Graphs and Combinatorics, 2023, 39(2): 23.
[24] 赵礼峰, 王小龙. 基于加权节点的Steiner树启发式算法[J]. 计算机应用, 2014, 34(12): 3414-3416.
ZHAO L F, WANG X L. Steiner tree heuristic algorithm based on weighted node[J]. Journal of Computer Applications, 2014, 34(12): 3414-3416.
[25] 余燕平, 仇佩亮. 一种改进的Steiner树启发式算法[J]. 通信学报, 2002(11): 35-40.
YU P Y, QIU P L. An improved Steiner tree heuristic algorithm[J]. Journal of Communications, 2002(11): 35-40.
[26] 王小龙. 图的Steiner最小树问题的算法与应用研究[D]. 南京: 南京邮电大学, 2015.
WANG X L. Algorithm and application research on the Steiner minimum tree problem of graphs[D]. Nanjing: Nanjing University of Posts And Telecommunications, 2015.
[27] AWAD A, PANG W, LUSSEAU D, et al. A survey on Physarum polycephalum intelligent foraging behaviour and bio-inspired applications[J]. Artificial Intelligence Review, 2023, 56(1): 1-26.
[28] HSU S, MASSOLO F I S, SCHAPOSNIK L P. A Physarum-inspired approach to the Euclidean Steiner tree problem[J]. Scientific Reports, 2022, 12(1): 14536.
[29] LIU L, SONG Y, ZHANG H, et al. Physarum optimization: a biology-inspired algorithm for the Steiner tree problem in networks[J]. IEEE Transactions on Computers, 2013, 64(3): 818-831.
[30] SUN Y. Solving the Steiner tree problem in graphs using physarum-inspired algorithms[J]. arXiv:1903.08926, 2019.
[31] BRAUNSTEIN A, MéZARD M, ZECCHINA R. Survey propagation: an algorithm for satisfiability[J]. Random Structures & Algorithms, 2010, 27(2): 201-226.
[32] HOàNG N D, KOCH T. Steiner tree packing revisited[J]. Mathematical Methods of Operations Research, 2012, 76: 95-123.
[33] PARK S, SHIN J. Convergence and correctness of max-product belief propagation for linear programming[J]. Siam Journal on Discrete Mathematics, 2017, 31(3): 2228-2246.
[34] 王晓峰, 许道云, 姜久雷, 等. 调查传播算法收敛的一个充分条件[J]. 中国科学: 信息科学, 2017, 47(12): 1646-1661.
WANG X F, XU D Y, JIANG J L, et al. A sufficient condition for the convergence of survey propagation algorithms[J]. Chinese Science: Information Science, 2017, 47(12): 1646-1661.
[35] DEHOUCHE N. Devolutionary genetic algorithms with application to the minimum labeling Steiner tree problem[J]. Evolving Systems, 2018, 9(2): 157-168.
[36] 刘耿耿, 黄逸飞, 王鑫, 等. 基于混合离散粒子群优化的Slew约束下X结构Steiner最小树算法[J]. 计算机学报, 2021, 44(12): 2542-2559.
LIU G G, HUANG Y F, WANG X, et al. Hybrid discrete particle swarm optimization algorithm for X-architecture Steiner minimal tree construction with Slew constraints[J]. Journal of Computer Science, 2021, 44 (12): 2542-2559.
[37] 刘庆, 李星, 王洋, 等. 求解最优Steiner树的前驱编码粒子群算法[J]. 西安理工大学学报, 2020, 36(2): 221-229.
LIU Q, LI X, WANG Y, et al. A predecessor-encoding-based particle swarm optimizer for least-cost Steiner tree problem [J]. Journal of Xi’an University of Technology, 2020, 36(2): 221-229.
[38] HAOUARI M, SIALA J C. A hybrid Lagrangian genetic algorithm for the prize collecting Steiner tree problem[J]. Computers & Operations Research, 2006, 33(5): 1274-1288.
[39] DIVEEV A I. Small variations of basic solution method for non-numerical optimization[J]. IFAC Papers OnLine, 2015, 48(25): 28-33.
[40] DABHI V K, CHAUDHARY S. Empirical modeling using genetic programming: a survey of issues and approaches[J]. Natural Computing, 2015, 14: 303-330.
[41] MEHBOOB U, QADIR J, ALI S, et al. Genetic algorithms in wireless networking: techniques, applications, and issues[J]. Soft Computing, 2016, 20: 2467-2501.
[42] PRIM R C. Shortest connection networks and some generalizations[J]. The Bell System Technical Journal, 2013, 36(6): 1389-1401.
[43] POP P C, MATEI O, SABO C, et al. A two-level solution approach for solving the generalized minimum spanning tree problem[J]. European Journal of Operational Research, 2018, 265(2): 478-487.
[44] HUY N V, NGHIA N D. Solving graphical Steiner tree problem using parallel genetic algorithm[C]//2008 IEEE International Conference on Research, Innovation and Vision for the Future in Computing and Communication Technologies, 2008: 29-35.
[45] ZHANG Q, YANG S, LIU M, et al. A new crossover mechanism for genetic algorithms for Steiner tree optimization[J]. IEEE Transactions on Cybernetics, 2020, 52(5): 3147-3158.
[46] LU T, ZHU J. Genetic algorithm for energy-efficient QoS multicast routing[J]. IEEE Communications Letters, 2012, 17(1): 31-34.
[47] ZHOU J, YI X, WANG K, et al. Uncertain distribution-minimum spanning tree problem[J]. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 2016, 24(4): 537-560.
[48] LU T, ZHU J, CHANG S, et al. Maximizing multicast lifetime in unreliable wireless ad hoc network[J]. Wireless Networks, 2018, 24: 1175-1185.
[49] GAO X, JIA L. Degree-constrained minimum spanning tree problem with uncertain edge weights[J]. Applied Soft Computing, 2017, 56: 580-588.
[50] YEN Y S, CHAN Y K, CHAO H C, et al. A genetic algorithm for energy-efficient based multicast routing on MANETs[J]. Computer Communications, 2008, 31(10): 2632-2641.
[51] PAPANNA N, REDDY A R M, SEETHA M. EELAM: energy efficient lifetime aware multicast route selection for mobile ad hoc networks[J]. Applied Computing and Informatics, 2019, 15(2): 120-128.
[52] 陈智豪, 侯为根, 杨天明. 遗传算法在最小Steiner树问题中的应用[J]. 安庆师范学院学报 (自然科学版), 2016, 22(2): 30-32.
CHEN Z H, HOU W G, YANG T M. Application of genetic algorithm in the problem of minimum Steiner tree[J]. Journal of Anqing Normal University (Natural Science Edition), 2016, 22 (2): 30-32.