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

来源：计算机工程与应用杂志2024年第9期北京时间：

作者：王军霞, 王晓峰, 彭庆媛, 华盈盈, 宋家欢

单位：1.北方民族大学 计算机科学与工程学院，银川 750021；2.北方民族大学 图形图像智能处理国家民委重点实验室，银川 750021

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

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