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

• 作者: 宁爱兵 张惠珍 胡沁 苟海雯
• 来源期刊: 计算机应用研究
• 关键词: 节点加权的Steiner树 上界 下界 回溯算法
• 年，卷（期）: 2020,（11）
• 所属期刊栏目: 算法研究探讨
• 页码范围: 3307-3311
• 页数: 5页
• 分类号: TP301.6
• 语种: 中文
• DOI: 10.19734/j.issn.1001-3695.2019.07.0262

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	宁爱兵		59	341	11.0	15.0
2	张惠珍		86	662	16.0	23.0
3	苟海雯		3	0	0.0	0.0
4	胡沁		3	0	0.0	0.0