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

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