文永松 朱淑娟 龐一成

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

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

中圖分類(lèi)號(hào)： TN911?34; TP301.6 ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼： A ? ? ? ? ? ? ? ? ? ?文章編號(hào)： 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

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

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

3 ?結(jié) ?論

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

參考文獻(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.