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

Backtracking algorithm with reduction for node-weighted Steiner tree problem

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

The node-weighted Steiner tree problem is a classic NP-hard problem in the combinatorial optimization.The existing algorithms for studying the problem have the disadvantages of high time complexity and unavailability of the optimal solution.In view of the shortcomings of existing algorithms,this paper presented a backtracking algorithm based on reduced-order technique.Firstly,this paper studied the mathematical properties of the node-weighted Steiner tree problem and utilized its mathematical properties to reduce the scale of the problem.Then,it designed an upper bound sub-algorithm and a lower bound sub-algorithm and utilized such sub-algorithms to prune the solution space tree of the problem and improved the search efficiency.Finally,it designed a backtracking algorithm to solve the above-mentioned problem by utilizing the upper and lower bound sub-algorithms and mathematical properties.Example analysis and experimental results demonstrate that the algorithm is not only with lower time complexity,but also can obtain the optimal solution of the problem.