计算机工程与应用 ›› 2024, Vol. 60 ›› Issue (9): 19-29.DOI: 10.3778/j.issn.1002-8331.2311-0016

• 热点与综述 • 上一篇    下一篇

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

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

  1. 1.北方民族大学 计算机科学与工程学院,银川 750021
    2.北方民族大学 图形图像智能处理国家民委重点实验室,银川 750021
  • 出版日期:2024-05-01 发布日期:2024-04-29

Review of Algorithmic Research on Steiner Tree Optimization Problems

WANG Junxia, WANG Xiaofeng, PENG Qingyuan, HUA Yingying, SONG Jiahuan   

  1. 1.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
  • Online:2024-05-01 Published:2024-04-29

摘要: 最优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)