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

摘要：

图的Steiner最小树问题是经典的组合优化问题，是一个NP难题，在不同的领域有着广泛的应用。研究该问题的部分数学性质，在此基础上给出了该问题的初步降阶方法和下界子方法，形成一个新的回溯算法。该算法具有较低的时间复杂度，还给出了应用实例及其分析。

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

分类号：TP301.6(计算技术、计算机技术)

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

在线出版日期：2014-04-11（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：67-70,169