系统管理学报

系统管理学报 ›› 2024, Vol. 33 ›› Issue (5): 1242-1250.DOI: 10.3969/j.issn.2097-4558.2024.05.009

• 工业工程与工程管理 • 上一篇    下一篇

奖励-收集Steiner树问题的精确算法

曾宾，宁爱兵，付振星，付馨懿，张惠珍   

  1. 上海理工大学管理学院，上海 200093
  • 收稿日期:2022-08-16 修回日期:2023-02-03 出版日期:2024-09-28 发布日期:2024-09-27
  • 基金资助:

    国家自然科学基金资助项目（71401106）；上海市“管理科学与工程”高原学科建设项目

An Exact Algorithm for Prize-Collecting Steiner Tree Problem

ZENG Bin，NING Aibing，FU Zhenxing，FU Xinyi，ZHANG Huizhen   

  1. Business School, University of Shanghai for Science and Technology, Shanghai 200093, China
  • Received:2022-08-16 Revised:2023-02-03 Online:2024-09-28 Published:2024-09-27

PDF

摘要：

奖励-收集Steiner树问题是图的Steiner最小树问题的衍生，同时也是组合优化中的NP-hard问题。首先，提出该问题的数学性质并给出证明，利用数学性质能降低该问题的规模；其次，基于该问题的数学性质设计出上下界子算法、降阶子算法和回溯子算法，通过上下界子算法和降阶子算法可以降低该问题解空间的规模，从而缩短回溯子算法的搜索时间，进而降低求解该问题最优解的时间；最后，应用案例分析、算例分析以及算法分析与对比表明，所设计的算法不仅可以求出该问题的最优解，而且比没有考虑该问题数学性质的一般回溯算法的时间复杂度更低。

关键词:

奖励-收集Steiner树, 上下界子算法, 降阶子算法, 回溯子算法

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.

Key words:

prize-collection Steiner tree, upper and lower bound sub algorithm, reduced order sub algorithm, backtracking sub algorithm

中图分类号: