计算机工程与应用2024，Vol.60Issue(9)：19-29,11.DOI:10.3778/j.issn.1002-8331.2311-0016
Steiner树优化问题的算法研究综述
Review of Algorithmic Research on Steiner Tree Optimization Problems
摘要
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 approxima-tion 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 disadvan-tages 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.关键词
Steiner树问题(STP)/启发式算法/信息传播算法/智能优化算法/叶交叉(LC)Key words
Steiner tree problem(STP)/heuristics algorithms/belief propagation algorithms/intelligent optimization algo-rithms/leaf crossover(LC)分类
信息技术与安全科学引用本文复制引用
王军霞,王晓峰,彭庆媛,华盈盈,宋家欢..Steiner树优化问题的算法研究综述[J].计算机工程与应用,2024,60(9):19-29,11.基金项目
国家自然科学基金(62062001) （62062001）
宁夏青年拔尖人才项目(2021). （2021）
