系统管理学报2024，Vol.33Issue(5)：1242-1250,9.DOI:10.3969/j.issn2097-4558.2024.05.009
奖励-收集Steiner树问题的精确算法
An Exact Algorithm for Prize-Collecting Steiner Tree Problem
摘要
Abstract
The prize-collecting Steiner tree problem is derived from the Steiner minimum tree problem of graphs,which is also a NP-hard problem in combinatorial optimization.In this paper,the mathematical properties of the problem are proposed and proved that the scale of the problem can be reduced by using the mathematical properties.In addition,based on the mathematical properties of the problem,the upper and lower bound sub algorithm,the reduced order sub algorithm,and the backtracking sub algorithm are designed.By using the upper and lower bound sub algorithm and the lower order sub algorithm,the size of the solution space of the problem can be reduced,to shorten the search time of backtracking sub algorithm,and then reduce the time to solve the optimal solution of the problem.Moreover,the application case,the numerical example analysis,the algorithm analysis,and the comparison show that the algorithm designed in this paper can not only find the optimal solution of the problem,but also has a lower time complexity than the general backtracking algorithm that does not consider the mathematical properties of the problem.关键词
奖励-收集Steiner树/上下界子算法/降阶子算法/回溯子算法Key words
prize-collection Steiner tree/upper and lower bound sub algorithm/reduced order sub algorithm/backtracking sub algorithm分类
数理科学引用本文复制引用
曾宾,宁爱兵,付振星,付馨懿,张惠珍..奖励-收集Steiner树问题的精确算法[J].系统管理学报,2024,33(5):1242-1250,9.基金项目
国家自然科学基金资助项目(71401106) （71401106）
上海市"管理科学与工程"高原学科建设项目 （）
