| 图的Steiner最小树问题的降阶回溯算法 |
| |
| 引用本文： | 刘艳芳,宁爱兵,王英磊.图的Steiner最小树问题的降阶回溯算法[J].计算机工程与应用,2014(7):67-70,169. |
| |
| 作者姓名： | 刘艳芳 宁爱兵 王英磊 |
| |
| 作者单位： | 上海理工大学管理学院 |
| |
| 基金项目： | 国家自然科学基金(No.70871081);上海市重点学科建设资助项目(No.S30504) |
| |
| 摘 要： | 图的Steiner最小树问题是经典的组合优化问题，是一个NP难题，在不同的领域有着广泛的应用。研究该问题的部分数学性质，在此基础上给出了该问题的初步降阶方法和下界子方法，形成一个新的回溯算法。该算法具有较低的时间复杂度，还给出了应用实例及其分析。
|
| 关 键 词： | 图的Steiner最小树 最小生成树 回溯法 降阶算法 |
Reduced-order backtracking algorithm for Graphical Steiner Minimum Tree Problem |
| |
| LIU Yanfang;NING Aibing;WANG Yinglei.Reduced-order backtracking algorithm for Graphical Steiner Minimum Tree Problem[J].Computer Engineering and Applications,2014(7):67-70,169. |
| |
| Authors: | LIU Yanfang;NING Aibing;WANG Yinglei |
| |
| Affiliation: | LIU Yanfang;NING Aibing;WANG Yinglei;School of Management, University of Shanghai for Science and Technology; |
| |
| Abstract: | 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. |
| |
| Keywords: | graphical Steiner minimum tree minimum spanning tree backtracking algorithm reduction algorithm |
| 本文献已被 CNKI 维普 等数据库收录！ |
