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

Review of Algorithmic Research on Steiner Tree Optimization Problems

作　　者：王军霞 王晓峰[1,2] 彭庆媛 华盈盈 宋家欢 WANG Junxia;WANG Xiaofeng;PENG Qingyuan;HUA Yingying;SONG Jiahuan(School of Computer Science and Engineering,North Minzu University,Yinchuan 750021,China 2.Laboratory of Image&Graphics Intelligent Processing of State Ethnic Affairs Commission,North Minzu University,Yinchuan 750021,China)

机构地区：[1]北方民族大学计算机科学与工程学院,银川750021 [2]北方民族大学图形图像智能处理国家民委重点实验室,银川750021

出　　处：《计算机工程与应用》2024年第9期19-29,共11页Computer Engineering and Applications

基　　金：国家自然科学基金(62062001);宁夏青年拔尖人才项目(2021)。

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]