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

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