图的Steiner最小树的竞争决策算法

摘要

图的Steiner最小树问题是一个著名的NP难题,在通讯网络、VLSI等工程实践中有着重要的应用.在分析图的Steiner最小树问题数学性质的基础上,提出了图的Steiner最小树的竞争决策算法.为了验证算法的有效性,求解了OR-Library中的基准问题,测试结果表明了算法具有较好的求解效果.%The Steiner minimal tree problem in graphs(GSTP) is a well-known NP-hard problem. Its applications can be found in many areas, such as telecommunication network design,VLSI design,etc. A competitive decision algorithm was developed to solve the GSTP. The mathematical properties of GSTP were analysed, which can be used to scale down the size of original problem and accelerate the algorithm. To assess the efficiency of the proposed competitive decision algorithm,it was applied to a set of benchmark problems in the OR-Library. In terms of computation times,our algorithm clearly outperforms other heuristics for the Steiner problem in graphs, while obtaining better or comparable solutions.