图的Steiner最小树问题的降阶回溯算法

计算机工程与应用 ›› 2014, Vol. 50 ›› Issue (7): 67-70.

图的Steiner最小树问题的降阶回溯算法

刘艳芳，宁爱兵，王英磊

上海理工大学管理学院，上海 200093

出版日期:2014-04-01 发布日期:2014-04-25

Reduced-order backtracking algorithm for Graphical Steiner Minimum Tree Problem

LIU Yanfang, NING Aibing, WANG Yinglei

School of Management, University of Shanghai for Science and Technology, Shanghai 200093, China

Online:2014-04-01 Published:2014-04-25

摘要/Abstract

摘要： 图的Steiner最小树问题是经典的组合优化问题，是一个NP难题，在不同的领域有着广泛的应用。研究该问题的部分数学性质，在此基础上给出了该问题的初步降阶方法和下界子方法，形成一个新的回溯算法。该算法具有较低的时间复杂度，还给出了应用实例及其分析。

关键词: 图的Steiner最小树, 最小生成树, 回溯法, 降阶算法

Abstract: Graphical Steiner Minimum Tree Problem（GSMTP） is a well-known optimization problem, which is a NP-hard problem and has many applications in various fields. This paper gives some mathematical properties of GSMTP, then proposes a reduction method and a method to calculate the lower bound of the GSMTP. The paper presents a backtracking algorithm for GSMTP which includes the lower bound method. It is proved to be efficient and can decrease the time complexity. In addition, series of examples and instances are solved and analyzed.

Key words: graphical Steiner minimum tree, minimum spanning tree, backtracking algorithm, reduction algorithm

刘艳芳，宁爱兵，王英磊. 图的Steiner最小树问题的降阶回溯算法[J]. 计算机工程与应用, 2014, 50(7): 67-70.

LIU Yanfang, NING Aibing, WANG Yinglei. Reduced-order backtracking algorithm for Graphical Steiner Minimum Tree Problem[J]. Computer Engineering and Applications, 2014, 50(7): 67-70.

[1]	邓宇，谌贵辉，李忠兵，张军豪，亢宇欣，夏旭洪. 基于颜色与边缘融合的非局部立体匹配算法[J]. 计算机工程与应用, 2020, 56(10): 199-204.
[2]	宋森森1，贾振红1，杨杰2，Nikola KASABOV3. 结合Ostu阈值法的最小生成树图像分割算法[J]. 计算机工程与应用, 2019, 55(9): 178-183.
[3]	曹戴，陈丽芳. 基于杰卡德度量的智能拼图改进算法[J]. 计算机工程与应用, 2018, 54(2): 188-192.
[4]	陈卉，胡立坤，黄钰雯. 采用高斯混合模型及树结构的立体匹配算法[J]. 计算机工程与应用, 2017, 53(20): 195-200.
[5]	贺靖卿，岳春生，胡泽明. 考虑综合性约束的软件无线电应用部署算法[J]. 计算机工程与应用, 2017, 53(15): 239-243.
[6]	郑淼1，郑成增2. 粒子寻优和最小生成树聚类下的WSN能量优化[J]. 计算机工程与应用, 2017, 53(15): 106-110.
[7]	邵　　超，万春红，李洁颖. 用于多流形分类的核等距映射算法[J]. 计算机工程与应用, 2016, 52(4): 121-128.
[8]	徐晨凯，高茂庭. 改进的最小生成树自适应分层聚类算法[J]. 计算机工程与应用, 2014, 50(22): 149-153.
[9]	黎莹，戴芳，郝勇，左涛. 基于最小生成树的图像分割[J]. 计算机工程与应用, 2013, 49(13): 149-151.
[10]	欧阳浩，陈波. 求解最小生成树的一种小生境遗传禁忌算法[J]. 计算机工程与应用, 2013, 49(1): 59-61.
[11]	刘维群，李元臣. 基于局部信息的时延和时延差约束的组播路由[J]. 计算机工程与应用, 2012, 48(34): 76-80.
[12]	孙宁1，肖国强1，杨恒2，邱开金1. 压缩域中基于自动标记的图像分割[J]. 计算机工程与应用, 2012, 48(23): 168-172.
[13]	彭煜，张华忠，魏晓镇. WSN中一种基于最小能耗树的路由协议[J]. 计算机工程与应用, 2011, 47(6): 109-112.
[14]	刘军立，孙劲光. 基于高维仿生覆盖的人脸识别方法[J]. 计算机工程与应用, 2011, 47(17): 178-180.
[15]	杜丽娟1，2，余镇危1. 分布式超级节点选举算法[J]. 计算机工程与应用, 2011, 47(14): 4-6.