多材料Terminal Steiner樹拼接問題的近似算法研究

文永松 朱淑娟 龐一成

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

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

中圖分類號： TN911?34; TP301.6 ? ? ? ? ? ? ? 文獻標識碼： 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

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

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

3 ?結 ?論

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

參考文獻

[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.