An Exact Algorithm for Prize-Collecting Steiner Tree Problem
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.
prize-collection Steiner treeupper and lower bound sub algorithmreduced order sub algorithmbacktracking sub algorithm
国家科技期刊平台
NSTL
万方数据
