图的Steiner最小树问题的降阶回溯算法  

Reduced-order backtracking algorithm for Graphical Steiner Minimum Tree Problem

作　　者：刘艳芳[1] 宁爱兵[1] 王英磊[1] 

机构地区：[1]上海理工大学管理学院,上海200093

出　　处：《计算机工程与应用》2014年第7期67-70,169,共5页Computer Engineering and Applications

基　　金：国家自然科学基金(No.70871081);上海市重点学科建设资助项目(No.S30504)

摘　　要：图的Steiner最小树问题是经典的组合优化问题,是一个NP难题,在不同的领域有着广泛的应用。研究该问题的部分数学性质,在此基础上给出了该问题的初步降阶方法和下界子方法,形成一个新的回溯算法。该算法具有较低的时间复杂度,还给出了应用实例及其分析。Graphical Steiner Minimum Tree Problem（GSMTP）is a well-known optimization problem, which is a NP-hard problem and has many applications in various fields. This paper gives some mathematical properties of GSMTP, then proposes a reduction method and a method to calculate the lower bound of the GSMTP. The paper presents a backtracking algorithm for GSMTP which includes the lower bound method. It is proved to be efficient and can decrease the time complexity. In addition, series of examples and instances are solved and analyzed.

关 键 词：图的Steiner最小树 最小生成树 回溯法 降阶算法 

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