TST問題的降階回溯算法

付振星 寧愛兵 曾賓 程志浩 張惠珍

摘? 要： 考慮Terminal Steiner Tree（TST）問題中特殊結(jié)點及其關(guān)聯(lián)邊之間的關(guān)系、結(jié)點之間的權(quán)值比較、可行解的連通性等幾個方面，提出該問題的相關(guān)數(shù)學性質(zhì)，判斷問題中結(jié)點與邊是否一定在或一定不在最優(yōu)解中；利用上下界子算法對降階回溯算法的解空間進行剪枝，加快了算法求解問題的速率，最后通過算法復雜度分析證明算法的有效性。

關(guān)鍵詞： TST問題； 數(shù)學性質(zhì)； 降階； 回溯

中圖分類號：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）問題是經(jīng)典NP-難題斯坦納樹問題的一個衍生問題，即要求求得的最小斯坦納樹中所有正則結(jié)點均為葉子結(jié)點[1]。在應用方面，劉林峰等[2]基于TST問題設(shè)計出一種近似的拓撲愈合算法，降低了傳輸?shù)臅r間延遲和能量損耗，進而有效延長了水下傳感器網(wǎng)絡(luò)的生命周期；文永松等[3]基于TST問題模型和裝箱問題模型設(shè)計近似算法用于求解多材料拼接問題；Wassila等[4]提出BIND方法解決分區(qū)網(wǎng)絡(luò)拓撲中如何部署最少的結(jié)點來恢復網(wǎng)絡(luò)連接的問題。

不僅如此，在算法研究領(lǐng)域，Ding等[5]證明了最小直徑終端斯坦納樹問題的最優(yōu)解的極性問題，并給出了時間復雜度為[O（|S|*|V（G）＼S|2）]的精確算法；Karim[6]給出時間復雜度為[O（（n+m）log2m）]的精確算法用于求解瓶頸完全斯坦納樹問題；Biniaz等[7]表明一般圖中的完整斯坦納樹問題在對任給的[ε>0]時不能在[O（log2-ε|R|）]復雜度內(nèi)近似，并給出推廣的斯坦納樹組的多項式時間近似算法；Chen[8]利用進化樹重構(gòu)方法改進了該問題的逼近算法，提出了性能比為[2ρ-（ρα2-αρ）/[（α+α2）（ρ-1）+2（α-1）2]]的近似算法。

本文對于TST問題首先從正則結(jié)點與斯坦納結(jié)點之間的連接關(guān)系出發(fā)，以結(jié)點的度為突破口，提出關(guān)于TST問題的相關(guān)數(shù)學性質(zhì)。在數(shù)學性質(zhì)的基礎(chǔ)上，設(shè)計降階回溯算法，批量的判斷圖中部分結(jié)點與邊是否一定在或一定不在最優(yōu)解中。該算法在保證求得最優(yōu)解的基礎(chǔ)上降低問題的規(guī)模，進而降低算法的時間復雜度。相較于近似算法與啟發(fā)式算法，該算法一定可以求得問題的最優(yōu)解，并且在數(shù)學性質(zhì)的基礎(chǔ)上對原問題進行了降階，利用上下界子算法加快問題求解速度，較經(jīng)典的精確算法可以更快的求得問題的最優(yōu)解。

1 定義及其性質(zhì)

1.1 問題定義與符號說明

為了方便問題的描述與表達，本文定義下列數(shù)學符號。

3.2 算法復雜度對比與分析

規(guī)模n=|S|的TST問題經(jīng)過文中降階子算法處理后，規(guī)模降低為l，l=|V5|，示例分析中為例，即將原問題算法復雜度由O（219）降低至O（23）。本文中所使用的算法除回溯算法外均為多項式時間算法，在回溯算法中復雜度最高為O（2l），而后經(jīng)過上界子算法與下界子算法在解空間中進行剪枝，可進一步降低算法的時間復雜度。該算法在處理SteinLib數(shù)據(jù)庫中改進的較大的規(guī)模的問題時，對于稀疏圖上的TST問題能夠有較高的求解效率，而對于稠密圖上的TST問題速度較慢，但仍能夠在較短時間內(nèi)求得問題的精確解。

4 結(jié)束語

現(xiàn)階段對于TST問題的求解方案主要有近似算法，啟發(fā)式算法以及精確算法三大類，近似算法與啟發(fā)式算法能夠在較短時間內(nèi)求得問題的可行解，但是往往會陷入局部最優(yōu)，對于某些特殊的問題，還可能導致可行解與最優(yōu)解相去甚遠；精確算法雖然能求得問題的最優(yōu)解，但是并未使用數(shù)學性質(zhì)等方法進行合理降階，求解速度較慢。本文提出的關(guān)于TST問題的相關(guān)數(shù)學性質(zhì)，不僅可以應用在精確算法中，也可與其他近似算法相結(jié)合進一步加快求解效率。

參考文獻（References）：

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

[2] 劉林峰，劉業(yè).基于滿 Steiner 樹問題的水下無線傳感器網(wǎng)絡(luò)拓撲愈合算法研究[J].通信學報，2010（9）：9-37

[3] 文永松，朱淑娟，龐一成.多材料 Terminal Steiner 樹拼接問題的近似算法研究[J].現(xiàn)代電子技術(shù)，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] 鄒佰翰，張吉懿，苑曉兵.最短路徑算法在計算機網(wǎng)絡(luò)路由選擇中的應用研究[J].電聲技術(shù)，2020，44（2）：59-60，70

[10] 孫佳寧，馬海龍，張立臣，等.求解0-1背包問題的融合貪心策略的回溯算法[J].計算機技術(shù)與發(fā)展，2022，32（2）：190-195

[11] 黃小利，高岳林，謝金宵，等.一種新的二次約束二次規(guī)劃問題的分支定界算法[J].應用數(shù)學，2021，34（1）：240-252

[12] 王曉東.計算機算法設(shè)計與分析[M].北京：電子工業(yè)出版社，2012

*基金項目：國家自然科學基金（71401106）； 上海市“管理科學與工程”高原學科建設(shè)項目

作者簡介：付振星（1995-），男，河南安陽人，碩士研究生，主要研究方向：算法、系統(tǒng)工程。

通訊作者：寧愛兵（1972-），男，湖南邵東人，博士，副教授，主要研究方向：算法設(shè)計、系統(tǒng)工程。