TST問題的降階回溯算法

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

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

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

中圖分類號：TP301.6? ? ? ? ? 文獻(xiàn)標(biāo)識碼：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é)點(diǎn)均為葉子結(jié)點(diǎn)[1]。在應(yīng)用方面，劉林峰等[2]基于TST問題設(shè)計(jì)出一種近似的拓?fù)溆纤惴ǎ档土藗鬏數(shù)臅r(shí)間延遲和能量損耗，進(jìn)而有效延長了水下傳感器網(wǎng)絡(luò)的生命周期；文永松等[3]基于TST問題模型和裝箱問題模型設(shè)計(jì)近似算法用于求解多材料拼接問題；Wassila等[4]提出BIND方法解決分區(qū)網(wǎng)絡(luò)拓?fù)渲腥绾尾渴鹱钌俚慕Y(jié)點(diǎn)來恢復(fù)網(wǎng)絡(luò)連接的問題。

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

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

1 定義及其性質(zhì)

1.1 問題定義與符號說明

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

3.2 算法復(fù)雜度對比與分析

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

4 結(jié)束語

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

參考文獻(xiàn)（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ò)拓?fù)溆纤惴ㄑ芯縖J].通信學(xué)報(bào)，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] 鄒佰翰，張吉懿，苑曉兵.最短路徑算法在計(jì)算機(jī)網(wǎng)絡(luò)路由選擇中的應(yīng)用研究[J].電聲技術(shù)，2020，44（2）：59-60，70

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

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

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

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

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

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