节点加权的Steiner树问题的降阶回溯算法

来源：计算机应用研究杂志2020年第11期北京时间：

作者：胡沁,宁爱兵,苟海雯,张惠珍,

单位：上海理工大学管理学院,上海200093；

摘要：节点加权的Steiner树问题是组合优化中一个经典的NP-hard问题，现有算法研究该问题时存在时间复杂性高或无法得到最优解的缺点。针对现有算法的不足，提出了一个基于降阶技术的回溯算法。首先研究该问题的数学性质，利用数学性质对该问题进行降阶以缩小问题的规模；接着提出上界子算法和下界子算法，利用上下界子算法对该问题的解空间树进行剪枝，提高搜索效率；最后利用上下界子算法和数学性质设计了一个回溯算法求解该问题。示例分析以及实验的结果表明，该算法不仅时间复杂性较低而且可以得到问题的最优解。

关键词：节点加权的Steiner树,上界,下界,回溯算法,

基金资助：国家自然科学基金资助项目(71401106)；上海市一流学科建设项目(S1201YLXK)；；