TST问题的降阶回溯算法

付振星 宁爱兵 曾宾 程志浩 张惠珍

摘  要： 考虑Terminal Steiner Tree（TST）问题中特殊结点及其关联边之间的关系、结点之间的权值比较、可行解的连通性等几个方面，提出该问题的相关数学性质，判断问题中结点与边是否一定在或一定不在最优解中；利用上下界子算法对降阶回溯算法的解空间进行剪枝，加快了算法求解问题的速率，最后通过算法复杂度分析证明算法的有效性。

关键词： TST问题； 数学性质； 降阶； 回溯

中图分类号：TP301.6          文献标识码：A     文章编号：1006-8228（2023）04-39-05

Abstract： Considering several aspects of the Terminal Steiner Tree （TST） problem， such as the relationship between special nodes and their associated edges， the comparison of weights between nodes， and the connectivity of feasible solutions， the relevant mathematical properties of the problem are proposed to determine whether the nodes and edges in the problem must be in or must not be in the optimal solution. The solution space of the reduced-order backtracking algorithm is pruned by using the upper and lower bound sub-algorithms to speed up the problem solving. The algorithm complexity analysis proves the effectiveness of the algorithm.

Key words： TST problem; mathematical properties; reduction; backtracking

0 引言

Terminal Steiner Tree（TST）問题是经典NP-难题斯坦纳树问题的一个衍生问题，即要求求得的最小斯坦纳树中所有正则结点均为叶子结点[1]。在应用方面，刘林峰等[2]基于TST问题设计出一种近似的拓扑愈合算法，降低了传输的时间延迟和能量损耗，进而有效延长了水下传感器网络的生命周期；文永松等[3]基于TST问题模型和装箱问题模型设计近似算法用于求解多材料拼接问题；Wassila等[4]提出BIND方法解决分区网络拓扑中如何部署最少的结点来恢复网络连接的问题。

不仅如此，在算法研究领域，Ding等[5]证明了最小直径终端斯坦纳树问题的最优解的极性问题，并给出了时间复杂度为[O（|S|*|V（G）＼S|2）]的精确算法；Karim[6]给出时间复杂度为[O（（n+m）log2m）]的精确算法用于求解瓶颈完全斯坦纳树问题；Biniaz等[7]表明一般图中的完整斯坦纳树问题在对任给的[ε>0]时不能在[O（log2-ε|R|）]复杂度内近似，并给出推广的斯坦纳树组的多项式时间近似算法；Chen[8]利用进化树重构方法改进了该问题的逼近算法，提出了性能比为[2ρ-（ρα2-αρ）/[（α+α2）（ρ-1）+2（α-1）2]]的近似算法。

本文对于TST问题首先从正则结点与斯坦纳结点之间的连接关系出发，以结点的度为突破口，提出关于TST问题的相关数学性质。在数学性质的基础上，设计降阶回溯算法，批量的判断图中部分结点与边是否一定在或一定不在最优解中。该算法在保证求得最优解的基础上降低问题的规模，进而降低算法的时间复杂度。相较于近似算法与启发式算法，该算法一定可以求得问题的最优解，并且在数学性质的基础上对原问题进行了降阶，利用上下界子算法加快问题求解速度，较经典的精确算法可以更快的求得问题的最优解。

1 定义及其性质

1.1 问题定义与符号说明

为了方便问题的描述与表达，本文定义下列数学符号。

3.2 算法复杂度对比与分析

规模n=|S|的TST问题经过文中降阶子算法处理后，规模降低为l，l=|V5|，示例分析中为例，即将原问题算法复杂度由O（219）降低至O（23）。本文中所使用的算法除回溯算法外均为多项式时间算法，在回溯算法中复杂度最高为O（2l），而后经过上界子算法与下界子算法在解空间中进行剪枝，可进一步降低算法的时间复杂度。该算法在处理SteinLib数据库中改进的较大的规模的问题时，对于稀疏图上的TST问题能够有较高的求解效率，而对于稠密图上的TST问题速度较慢，但仍能够在较短时间内求得问题的精确解。

4 结束语

现阶段对于TST问题的求解方案主要有近似算法，启发式算法以及精确算法三大类，近似算法与启发式算法能够在较短时间内求得问题的可行解，但是往往会陷入局部最优，对于某些特殊的问题，还可能导致可行解与最优解相去甚远；精确算法虽然能求得问题的最优解，但是并未使用数学性质等方法进行合理降阶，求解速度较慢。本文提出的关于TST问题的相关数学性质，不仅可以应用在精确算法中，也可与其他近似算法相结合进一步加快求解效率。

参考文献（References）：

[1] Lin G， Xue G. On the terminal Steiner tree problem[J]. Information Processing Letters，2002，84（2）：103-107

[2] 刘林峰，刘业.基于满 Steiner 树问题的水下无线传感器网络拓扑愈合算法研究[J].通信学报，2010（9）：9-37

[3] 文永松，朱淑娟，庞一成.多材料 Terminal Steiner 树拼接问题的近似算法研究[J].现代电子技术，2018，41（10）：28-30

[4] Lalouani W， Younis M， Badache N. Optimized repair of a partitioned network topology[J]. Computer Networks，2017（128）：63-77

[5] Ding W， Qiu K. Algorithms for the minimum diameter terminal steiner tree problem[J]. Journal of Combinatorial Optimization，2014，28（4）：837-853

[6] Abu-Affash A K. On the Euclidean bottleneck full Steiner tree problem[C]//Proceedings of the Twenty-Seventh Annual Symposium on Computational Geometry，2011：433-439

[7] Biniaz A， Maheshwari A， Smid M. On the hardness of full Steiner tree problems[J].Journal of Discrete Algorithms，2015（34）：118-127

[8] Chen Y H. An improved approximation algorithm for the terminal Steiner tree problem[C]//International Conference on Computational Science and Its Applications. Springer， Berlin， Heidelberg，2011：141-151

[9] 邹佰翰，张吉懿，苑晓兵.最短路径算法在计算机网络路由选择中的应用研究[J].电声技术，2020，44（2）：59-60，70

[10] 孙佳宁，马海龙，张立臣，等.求解0-1背包问题的融合贪心策略的回溯算法[J].计算机技术与发展，2022，32（2）：190-195

[11] 黄小利，高岳林，谢金宵，等.一种新的二次约束二次规划问题的分支定界算法[J].应用数学，2021，34（1）：240-252

[12] 王晓东.计算机算法设计与分析[M].北京：电子工业出版社，2012

*基金项目：国家自然科学基金（71401106）； 上海市“管理科學与工程”高原学科建设项目

作者简介：付振星（1995-），男，河南安阳人，硕士研究生，主要研究方向：算法、系统工程。

通讯作者：宁爱兵（1972-），男，湖南邵东人，博士，副教授，主要研究方向：算法设计、系统工程。