劉　麗，張　安，陳　永，陳光亭

(杭州電子科技大學(xué)理學(xué)院，浙江 杭州，310018)

?

一類新型網(wǎng)絡(luò)構(gòu)建問(wèn)題的算法設(shè)計(jì)與分析

劉麗，張安，陳永，陳光亭

(杭州電子科技大學(xué)理學(xué)院，浙江 杭州，310018)

摘要：研究了一類新型網(wǎng)絡(luò)構(gòu)建問(wèn)題，使有向網(wǎng)絡(luò)中子網(wǎng)絡(luò)的弧在切割成權(quán)值為L(zhǎng)的分段時(shí)所產(chǎn)生的總分段數(shù)盡可能小。針對(duì)問(wèn)題，假設(shè)有向網(wǎng)絡(luò)每條弧的權(quán)值不小于L，給出子網(wǎng)絡(luò)結(jié)構(gòu)為有向路或強(qiáng)連通支撐子網(wǎng)絡(luò)兩種情形時(shí)的近似算法，并證明算法的最壞情況界分別為和3。

關(guān)鍵詞：網(wǎng)絡(luò)構(gòu)建；近似算法；最壞情況界；裝箱問(wèn)題

0引言

1近似算法設(shè)計(jì)與分析

1.1　CDP問(wèn)題

首先考慮CDP問(wèn)題，即在有向圖D中尋找一條s-t有向路，使構(gòu)建該有向路所用的資源盡可能少。在算法中調(diào)用裝箱問(wèn)題[3]的經(jīng)典算法——FFD作為子過(guò)程。對(duì)FFD算法，文獻(xiàn)[4]給出了如下性質(zhì)。

針對(duì)CDP問(wèn)題，設(shè)計(jì)了算法A1，算法A1的具體描述如下：

1)利用Dijkstra算法[5]在網(wǎng)絡(luò)D中找到一條總權(quán)重最小的s-t有向路Pst，記其弧集為A(Pst)={e1,e2,…,ek}；

3)對(duì)全部剩余弧段(權(quán)重為w′(ei)，i=1,2,…,k)，調(diào)用裝箱問(wèn)題的FFD算法將他們裝入大小為L(zhǎng)的箱子中，記b2為所用的箱子數(shù)，即此階段所產(chǎn)生的分段數(shù)；

4)輸出總共所需的分段數(shù)OUT=b1+b2。

1.2　CSCSS問(wèn)題

本小節(jié)考慮CSCSS問(wèn)題，即在有向網(wǎng)絡(luò)D中找到一個(gè)強(qiáng)連通支撐子網(wǎng)絡(luò)，使得構(gòu)建該子網(wǎng)絡(luò)所用的資源盡可能少。采用類似于算法A1的方法，得到算法A2，算法A2的計(jì)算步驟如下：

3)對(duì)全部剩余弧段(權(quán)重為w′(ei)，i=1,2,…,k)，調(diào)用裝箱問(wèn)題的FFD算法將他們裝入大小為L(zhǎng)的箱子中，記b2為所用的箱子數(shù)，即此階段所產(chǎn)生的分段數(shù)；

4)輸出總共所需的分段數(shù)OUT=b1+b2。

定理2算法A2的最壞情況界是3。

證明最小權(quán)強(qiáng)連通支撐子網(wǎng)絡(luò)問(wèn)題是NP-難的，SCA算法給出的是一個(gè)近似算法，最壞情況界為2[6]。設(shè)OPT是CSCSS問(wèn)題最優(yōu)解所用的分段數(shù)，則有w(A1)≤2w(A*)且w(A*)≤L×OPT，即w(A1)≤2w(A*)≤2L×OPT。與定理1證明類似，分兩種情況討論。

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

參考文獻(xiàn)

[1]Schrijver A.Combinatorial optimization:Polyhedra and efficiency[M].Berlin:Springer-Verlag Berlin Heidelberg,2003:1002-1035.

[2]Li J P,Ge Y,He S,et al.Approximation algorithms for constructing some required structures in digraphs[J].European Journal of Operational Reaearch,2014,232(2):307-314.

[3]Kantorovich L V.Mathematical methods of organizing and planning production[J].Management Science,1960,6(4):366-422.

[4]Simchi-Levi D.New worst-case results for the bin-packing problem[J].Naval Research Logistics,1994,41(4):579-585.

[5]Dijkstra E W.A note on two problems in connexion with graphs[J].Numerische Mathematik,1959,1(1):269-271.

[6]Frederckson G N,Jaja J.Approximation algorithms for several graph augmentation problems[J].SIAM Journal on computing,1981,10(2):270-283.

Design and Analysis of Algorithms for a New Class of Network Construction Problems

Liu Li，Zhang An，Chen Yong，Chen Guangting

(SchoolofScience，HangzhouDianziUniversity，HangzhouZhejiang310018，China)

Abstract：This paper considers a new class of network construction problems.Given a directed network，it aims to find a subnetwork with specific structure in which arcs are cut into pieces of length at most L.The objective is to minimize the total number of pieces. and 3 respectively.

Key words：network construction；approximation algorithm；worst case ratio；bin packing problem

中圖分類號(hào)：O221.7

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1001-9146(2015)06-0090-03

通信作者：

作者簡(jiǎn)介：劉麗(1991-)，女，安徽馬鞍山人，在讀研究生，組合優(yōu)化與網(wǎng)絡(luò)優(yōu)化.張安副教授，E-mail：anzhang@hdu.edu.cn.

基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目(11201105；11401149)

收稿日期：2015-02-05

DOI：10.13954/j.cnki.hdu.2015.06.019