Reduced-order backtracking algorithm for Graphical Steiner Minimum Tree Problem

Abstract

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

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

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.

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

[1]	GOU Haiwen, NING Aibing, HU Qin, ZHANG Huizhen. Reduction Backtracking Algorithm for Uncapacitated Facility Location Problem With Penalties [J]. Computer Engineering and Applications, 2020, 56(24): 43-49.
[2]	MOU En, ZHANG Xianyong, YAO Yuesong, DENG Qie. Class-Specific Attribute Reduct and Its Heuristic Algorithm of Neighborhood Approximation Condition-Entropy [J]. Computer Engineering and Applications, 2020, 56(24): 175-180.
[3]	DENG Yu, CHEN Guihui, LI Zhongbing, ZHANG Junhao, KANG Yuxin, XIA Xuhong. Non-local Stereo Matching Algorithm Based on Image Color and Edge [J]. Computer Engineering and Applications, 2020, 56(10): 199-204.
[4]	SONG Sensen1, JIA Zhenhong1, YANG Jie2, Nikola KASABOV3. Image Segmentation Algorithm of Minimum Spanning Tree Combined with Ostu Threshold Method [J]. Computer Engineering and Applications, 2019, 55(9): 178-183.
[5]	CHEN Hui, HU Likun, HUANG Yuwen. Stereo matching algorithm based on Gaussian mixture model and tree structure [J]. Computer Engineering and Applications, 2017, 53(20): 195-200.
[6]	ZHENG Miao1, ZHENG Chengzeng2. Approach to WSN energy optimization based on particle optimization and MST clustering [J]. Computer Engineering and Applications, 2017, 53(15): 106-110.
[7]	WANG Qian, LIU Shenghui. Application research of improved K-means algorithm in intrusion detection [J]. Computer Engineering and Applications, 2015, 51(17): 124-127.
[8]	XU Chenkai, GAO Maoting. Improved adaptive hierarchical clustering algorithm based on minimum spanning tree [J]. Computer Engineering and Applications, 2014, 50(22): 149-153.
[9]	LI Ying, DAI Fang, HAO Yong, ZUO Tao. Image segmentation based on minimum spanning tree [J]. Computer Engineering and Applications, 2013, 49(13): 149-151.
[10]	OUYANG Hao, CHEN Bo. Solution of minimum spanning tree based on niche genetic algorithm Importing Tabu Search [J]. Computer Engineering and Applications, 2013, 49(1): 59-61.
[11]	SUN Ning1, XIAO Guoqiang1, YANG Heng2, QIU Kaijin1. Image segmentation based on automatic markers in compressed domain [J]. Computer Engineering and Applications, 2012, 48(23): 168-172.
[12]	CHENG Senlin, ZENG Wei. Application of multilevel reduction algorithm to PCB path optimization [J]. Computer Engineering and Applications, 2012, 48(16): 212-215.
[13]	PENG Yu，ZHANG Huazhong，WEI Xiaozhen. Routing protocol based on minimum energy consumption tree for Wireless Sensor Networks [J]. Computer Engineering and Applications, 2011, 47(6): 109-112.
[14]	CHANG Yuhui，QIAN Jin，GUO Qingjun. Hybrid attribute reduction method and its application in power load forecasting [J]. Computer Engineering and Applications, 2011, 47(30): 234-236.
[15]	LIU Junli，SUN Jinguang. Face recognition on high-dimensional bionic coverage [J]. Computer Engineering and Applications, 2011, 47(17): 178-180.

Reduced-order backtracking algorithm for Graphical Steiner Minimum Tree Problem

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics