《计算机应用研究》|Application Research of Computers

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

Backtracking algorithm with reduction for node-weighted steiner tree problem

免费全文下载 (已被下载 次)  
获取PDF全文
作者 胡沁,宁爱兵,苟海雯,张惠珍
机构 上海理工大学 管理学院
统计 摘要被查看 次,已被下载
摘要 节点加权的Steiner树问题是组合优化中一个经典的NP-Hard问题,现有算法研究该问题时存在时间复杂性高或无法得到最优解的缺点。针对现有算法的不足,提出了一个基于降阶技术的回溯算法。该算法首先研究该问题的数学性质,利用数学性质对该问题进行降阶以缩小问题的规模;接着提出上界子算法和下界子算法,利用上下界子算法对该问题的解空间树进行剪枝,提高搜索效率;最后利用上下界子算法和数学性质设计了一个回溯算法求解该问题。示例分析以及实验的结果表明,该算法不仅时间复杂性较低而且可以得到问题的最优解。
关键词 节点加权的Steiner树;上界;下界;回溯算法
基金项目 国家自然科学基金资助项目(71401106)
上海市一流学科建设项目(S1201YLXK)
本文URL http://www.arocmag.com/article/02-2020-11-011.html
收稿日期
修回日期
页码 -
中图分类号 TP301.6
文献标志码