文永松 朱淑娟 龐一成

摘 ?要： 在賦權(quán)連通網(wǎng)絡(luò)下，給定多種材料及每種材料的費用和拼接費用，以便尋找賦權(quán)網(wǎng)絡(luò)中的一棵Terminal Steiner樹，并用給定材料連接此樹，使得總費用及材料根數(shù)達(dá)到最小，記此問題為多材料Terminal Steiner樹拼接問題。為了解決Terminal Steiner樹拼接問題，首先分析Terminal Steiner 樹拼接問題是NP問題，不存在多項式時間算法;然后基于Steiner 樹問題和變尺寸裝箱問題的近似算法及算法復(fù)雜度，給出多材料的Terminal Steiner樹拼接問題的一個近似算法;最后證明算法的近似值及近似算法的時間復(fù)雜度。

關(guān)鍵詞： Terminal Steiner樹; 拼接問題; 變尺寸裝箱; 近似算法; 絕對近似比; 時間復(fù)雜度

中圖分類號： TN911?34; TP301.6 ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識碼： A ? ? ? ? ? ? ? ? ? ?文章編號： 1004?373X（2018）10?0028?03

Abstract： In the weighted and connected network， a variety of materials， cost of each material， and the splicing cost are given to look for a Terminal Steiner tree in the weighted network. The given materials are used to connect the Terminal Steiner tree， so as to minimize the total cost and the number of materials. This can be called the multi?material Terminal Steiner tree splicing problem. The Terminal Steiner tree splicing problem is analyzed and determined to be the NP problem， in which the polynomial time algorithm does not exist， and then an approximation algorithm of the multi?material Terminal Steiner tree splicing problem is presented based on the approximation algorithm of Steiner tree problem and variable?sized bin packing problem as well as the complexity of the algorithm， so as to resolve the Terminal Steiner tree splicing problem. The approximate value of the algorithm and the time complexity of the approximation algorithm are demonstrated.

Keywords： Terminal Steiner tree; splicing problem; variable?sized bin packing; approximation algorithm; absolute approximate ratio; time complexity

考慮這樣一個實際問題：假設(shè)某一軍事地區(qū)有多個信號站點，這些站點可以分為兩大類，一類為必需的信號站點，另一類是輔助信號站點，且必需的信號站點作為葉子節(jié)點與某幾個輔助信號站點終端相連接。為了保證信號的聯(lián)通性，需要一些不同特殊的材料把必需的信號站點與輔助信號站點拼接起來，費用包括拼接費用和材料費用兩部分。由于選取的輔助信號站點的不同，從而使連接信號站點之間的方式有許多種，每種方式的拼接費用和所需的材料費用可能不同，因此，最終所產(chǎn)生的總費用也不盡相同，在拼接時，人們總是希望費用及材料數(shù)目盡可能的少一些。為了解決該問題，把各信號站點看成網(wǎng)絡(luò)中的頂點，線路看成網(wǎng)絡(luò)中的，從而將該問題抽象成為一個組合最優(yōu)化問題。文中用Terminal Steiner 樹問題及裝箱問題來解決該優(yōu)化問題。

Terminal Steiner樹問題源于Steiner樹問題，文獻(xiàn)[1]證明了Terminal Steiner 樹問題是NP?難，給出了絕對近似比為2+k的近似算法，k為Steiner樹問題的最好的絕對近似比;文獻(xiàn)[2?5]討論了Terminal Steiner樹問題的其他較好的近似算法;變尺寸裝箱問題是一維裝箱問題的推廣，文獻(xiàn)[6]證明了變尺寸裝箱問題是NP?難，給出了最壞情況下2，[32]，[43]的漸近近似算法;文獻(xiàn)[6?9]給出了變尺寸裝箱問題其他漸進(jìn)近似算法的結(jié)果;文獻(xiàn)[10?11]分別討論了單個材料在樹形結(jié)構(gòu)網(wǎng)絡(luò)構(gòu)建問題及有向圖中滿足某種結(jié)構(gòu)的構(gòu)建問題，本文基于Terminal Steiner樹問題算法及變尺寸裝箱問題算法的基礎(chǔ)上，設(shè)計了多材料Terminal Steiner樹拼接問題的一個近似算法。

3 ?結(jié) ?論

Terminal Steiner樹問題在通信工程以及超規(guī)模集成電路設(shè)計（VLSI）上有著普遍的應(yīng)用[12]。本文基于Terminal Steiner樹問題和變尺寸裝箱問題的相關(guān)算法，提出網(wǎng)絡(luò)中多材料Terminal Steiner樹的拼接問題。本文設(shè)計了該問題[2ρ]?絕對近似算法，算法使用材料的方案是由變尺寸裝箱問題所決定的，材料的多少依賴于變尺寸裝箱問題的近似比。取文獻(xiàn)[13]中Steiner樹的絕對近似比[m=1.55]，文獻(xiàn)[2]中Terminal Steiner樹的絕對近似比[ρ=2m]，則多材料Terminal Steiner Tree 拼接問題的絕對近似比為6.1。算法精度的提高很大程度上依賴于Terminal Steiner 樹問題的近似值，因此，要提高算法的精度只需要改進(jìn)Terminal Steiner 樹算法的精度。

參考文獻(xiàn)

[1] LIN G， XUE G. On the Terminal Steiner tree problem [J]. Information processing letters， 2002， 84（2）： 103?107.

[2] DRAKE D E， HOUGARDY S. On approximation algorithms for the Terminal Steiner tree problem [J]. Information processing letters， 2004， 89（1）： 15?18.

[3] MARTINEZ F V， PINA J C D， SOARES J. Algorithms for Terminal Steiner tree [C]// Proceedings of International Computing and Combinatorics Conference. Berlin： Springer， 2005： 369?379.

[4] CHEN Y H. An improved approximation algorithm for the Terminal Steiner tree problem [C]// Proceedings of International Conference on Computational Science and Its Applications. Berlin： Springer， 2011： 141?151.

[5] LEE C W， HUANG C W， PI W H， et al. An improved approximation ratio to the partial?Terminal Steiner tree problem [J]. IEEE transactions on computers， 2014， 64（1）： 274?279.

[6] FRIESEN D K， LANGSTON M A. Variable sized bin packing [J]. SIAM journal on computing， 1986， 15（1）： 222?230.

[7] KANG J， PARK S. Algorithms for the variable sized bin packing problem [J]. European journal of operational research， 2003， 147（2）： 365?372.

[8] EPSTEIN L， LEVIN A. An APTAS for generalized cost variable?sized bin packing [J]. SIAM journal on computing， 2008， 38（1）： 411?428.

[9] JANSEN K， KRAFT S. An improved approximation scheme for variable?sized bin packing [J]. Theory of computing systems， 2016， 59（2）： 262?322.

[10] LI J， GE Y， HE S， et al. Approximation algorithms for constructing some required structures in digraphs [J]. European journal of operational research， 2014， 232（2）： 307?314.

[11] LI J， Guan L， DING H， et al. Approximations for constructing tree?form structures using specific material with fixed length [J]. Optimization letters， 2016， 10（6）： 1?9.

[12] VAZIRANI V V. Approximation algorithm [M]. Berlin： Springer， 2010.

[13] ZELIKOVSKY A Z. A faster approximation algorithm for the Steiner tree problem in graphs [J]. Information processing letters， 1993， 46（2）： 79?83.

[14] KOU L， MARKOWSKY G， BERMAN L. A fast algorithm for Steiner trees [J]. Acta informatica， 1981， 15（2）： 141?145.