付振星 寧愛(ài)兵 曾賓 程志浩 張惠珍

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

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

中圖分類(lèi)號(hào)：TP301.6? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A? ? ?文章編號(hào)：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）問(wèn)題是經(jīng)典N(xiāo)P-難題斯坦納樹(shù)問(wèn)題的一個(gè)衍生問(wèn)題，即要求求得的最小斯坦納樹(shù)中所有正則結(jié)點(diǎn)均為葉子結(jié)點(diǎn)[1]。在應(yīng)用方面，劉林峰等[2]基于TST問(wèn)題設(shè)計(jì)出一種近似的拓?fù)溆纤惴?，降低了傳輸?shù)臅r(shí)間延遲和能量損耗，進(jìn)而有效延長(zhǎng)了水下傳感器網(wǎng)絡(luò)的生命周期；文永松等[3]基于TST問(wèn)題模型和裝箱問(wèn)題模型設(shè)計(jì)近似算法用于求解多材料拼接問(wèn)題；Wassila等[4]提出BIND方法解決分區(qū)網(wǎng)絡(luò)拓?fù)渲腥绾尾渴鹱钌俚慕Y(jié)點(diǎn)來(lái)恢復(fù)網(wǎng)絡(luò)連接的問(wèn)題。

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

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

1 定義及其性質(zhì)

1.1 問(wèn)題定義與符號(hào)說(shuō)明

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

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

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

4 結(jié)束語(yǔ)

現(xiàn)階段對(duì)于TST問(wèn)題的求解方案主要有近似算法，啟發(fā)式算法以及精確算法三大類(lèi)，近似算法與啟發(fā)式算法能夠在較短時(shí)間內(nèi)求得問(wèn)題的可行解，但是往往會(huì)陷入局部最優(yōu)，對(duì)于某些特殊的問(wèn)題，還可能導(dǎo)致可行解與最優(yōu)解相去甚遠(yuǎn)；精確算法雖然能求得問(wèn)題的最優(yōu)解，但是并未使用數(shù)學(xué)性質(zhì)等方法進(jìn)行合理降階，求解速度較慢。本文提出的關(guān)于TST問(wèn)題的相關(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 樹(shù)問(wèn)題的水下無(wú)線傳感器網(wǎng)絡(luò)拓?fù)溆纤惴ㄑ芯縖J].通信學(xué)報(bào)，2010（9）：9-37

[3] 文永松，朱淑娟，龐一成.多材料 Terminal Steiner 樹(shù)拼接問(wèn)題的近似算法研究[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背包問(wèn)題的融合貪心策略的回溯算法[J].計(jì)算機(jī)技術(shù)與發(fā)展，2022，32（2）：190-195

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

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

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

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

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