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-），男，湖南邵東人，博士，副教授，主要研究方向：算法設計、系統工程。