Steiner森林問(wèn)題的一種同步增長(zhǎng)算法研究

李 ?！钭犹m　周華君

(云南大學(xué)旅游文化學(xué)院信息科學(xué)與技術(shù)系， 云南 麗江 674100)

?

Steiner森林問(wèn)題的一種同步增長(zhǎng)算法研究

李 睿楊子蘭周華君

(云南大學(xué)旅游文化學(xué)院信息科學(xué)與技術(shù)系， 云南 麗江 674100)

Steiner森林問(wèn)題是組合優(yōu)化理論中一個(gè)著名的NP-完備問(wèn)題。針對(duì)Steiner森林問(wèn)題設(shè)計(jì)了一種同步增長(zhǎng)算法。該算法利用同步增長(zhǎng)各連通片對(duì)偶值的方法，逐步求得可行解，在不影響可行性的前提下進(jìn)行調(diào)整，最后得到一個(gè)新的解。

Steiner森林； 同步增長(zhǎng)； 連通片

Steiner森林問(wèn)題是組合優(yōu)化理論中的一個(gè)經(jīng)典問(wèn)題。一般可描述如下[1]：給定一個(gè)無(wú)向圖G=(V,E;c)，其中c:E→Q+為定義在邊上的權(quán)重(邊權(quán)重，也稱費(fèi)用)，V1,V2,…,Vk為頂點(diǎn)V互不相交的k個(gè)子集，要找到圖G的某個(gè)子圖G′，使得在G′中各Vi內(nèi)部的頂點(diǎn)保持相互連通，使所得子圖的邊權(quán)重之和最小(簡(jiǎn)稱為SFP)。顯然，若Vi=V，則此問(wèn)題就是Steiner樹(shù)問(wèn)題，因此該問(wèn)題為NP-完備。Goemans證明了即便圖G滿足三角不等式，SFP仍為NP-完備[2]。K?nemann給出了SFP問(wèn)題的一個(gè)2-近似算法，該算法可同時(shí)用來(lái)解決Steiner樹(shù)和Steiner森林問(wèn)題[1]。Feldman設(shè)計(jì)的一種近似算法解決了有向的Steiner森林問(wèn)題，該算法近似度與頂點(diǎn)子集的個(gè)數(shù)k有關(guān)[3]。Bateni等人將該問(wèn)題限制在平面圖上，給出了問(wèn)題的一個(gè)PTAS算法[4]。更多的學(xué)者將問(wèn)題限制在特殊圖上，并給出了相應(yīng)的算法[5-7]。

為了討論方便，首先作以下定義：

則SFP可描述為尋找圖G的一個(gè)邊子集E′，使得所有滿足r(u,v)=1的點(diǎn)u和v之間均存在u-v路。

本文中所用術(shù)語(yǔ)均與文獻(xiàn)[8]相同。

1　SFP的規(guī)劃形式

則可得到如下整數(shù)線性規(guī)劃：

xe∈{0,1}

式中δ(S)為S的割集，約束條件的含義為：若u和v屬于同一子集Vi，則應(yīng)在包含u或v的所有點(diǎn)子集S的割集δ(S)中至少選一條邊，進(jìn)而可得到其松弛線性規(guī)劃的對(duì)偶形式：

yS≥0,S?V

2　算法ASFP

在此首先給出幾個(gè)概念。若yS>0且e∈δ(S)，則稱邊e與對(duì)偶變量yS相關(guān)聯(lián)。進(jìn)而，若與某一邊e相關(guān)聯(lián)的所有對(duì)偶變量yS之和等于ce，則稱邊e是緊邊。

由原問(wèn)題與對(duì)偶問(wèn)題的松緊定理容易得到2項(xiàng)結(jié)論[9]：

上述結(jié)論Ⅰ表明，對(duì)選取的每條邊來(lái)說(shuō)，跟其相關(guān)聯(lián)的對(duì)偶變量之和等于此邊的費(fèi)用ce，即所選的邊應(yīng)為緊邊。結(jié)論Ⅱ的松弛條件說(shuō)明，對(duì)任何子集S，若yS>0，則在S的割集中最多只需選2條邊即可。

命題1集合S是有效集，當(dāng)且僅當(dāng)S是當(dāng)前森林的一個(gè)連通片，且f(S)=1。

若f(S)=1,且S是當(dāng)前森林的一個(gè)連通分片，則S是非確定集；若S不是極小，不妨設(shè)S-{v}為極小的非確定集，則eSv已被選。兩者矛盾。

至此可得到算法ASFP：

Step 1設(shè)F=φ，對(duì)所有頂點(diǎn)子集S?V，yS=0。

Step 2若存在非確定集S，則進(jìn)行如下循環(huán)：對(duì)所有有效集同步增加yS的值，直到某一邊e∈δ(S)先變?yōu)榫o邊，不妨設(shè)為e′，令F=F∪{e′}。

Step 3設(shè)已有F={e1,e2,…,ek}，對(duì)所有當(dāng)前在F中的邊e，檢驗(yàn)F-{e}是否為原問(wèn)題的可行解；若可行，則令F=F-{e}。

Step 4輸出最終的F。

命題2算法ASFP最后輸出的F及yS分別是原問(wèn)題及其松弛對(duì)偶問(wèn)題的可行解。

命題3設(shè)τ為SFP的一個(gè)實(shí)例，OUT(τ)為用算法ASFP解決實(shí)例τ得到的目標(biāo)函數(shù)值，OPT(τ)是實(shí)例τ的最優(yōu)值，則有OUT(τ)≤2OPT(τ)。

證：設(shè)算法最終得到的解為F，由于算法中所選取的邊都是緊邊，且滿足DEG(S)≤2，因此有

≤2OPT(τ)

命題得證。

3　結(jié)　語(yǔ)

Steiner森林問(wèn)題是組合優(yōu)化理論中的一個(gè)經(jīng)典問(wèn)題。本次研究以割集的方式描述了Steiner森林問(wèn)題的整數(shù)規(guī)劃及其松弛的對(duì)偶線性規(guī)劃形式，并提出應(yīng)在保持對(duì)偶可行解的同時(shí)，同步增加對(duì)偶解，進(jìn)而向原始可行解靠近。算法中需考慮的子集僅為當(dāng)前森林的各個(gè)連通分支，因此算法的復(fù)雜度較??；但近似度為2，相對(duì)來(lái)說(shuō)偏大。對(duì)松弛條件中的“選邊最多為2”作進(jìn)一步改進(jìn)， 是降低近似度的一個(gè)重要方法 。

[1]K?NEMANNJ,LEONARDIS,SCHFERG,etal.FromPrimal-DualtoCostSharesandBack:AStrongerLPRelaxationfortheSteinerForestProblem[C]∥Automata,LanguagesandProgramming.SpringerBerlinHeidelberg:[s.n.]，2005: 930-942.

[2]GOEMANSMX,WILLIAMSOMDP.AGenralApproximationTechniqueforConstrainedForestProblems[J].SIAMJournalonComputing, 1995,24:296-317.

[3]FELDMANM,KORTSARZG,NUTOVZ.ImprovedApproximatingAlgorithmsforDirectedSteinerForest[C]∥ProceedingsoftheTwentiethAnnualACM-SIAMSymposiumonDiscreteAlgorithms.SocietyforIndustrialandAppliedMathematics, 2009: 922-931.

[4]BATENIMH,HAJIAGHAYIMT,MARXD.ApproximationSchemesforSteinerForestonPlanarGraphsandGraphsofBoundedTreewidth[J].JournaloftheACM, 2011, 58(5): 21.

[5]GAREYMR,JOHNSONDS.ComputersandIntractability:AGuidetotheTheoryofNP-Completeness[M].SanFrancisco: [s.n.], 1979:30-32.

[6]BORRADAILEG,KLEINPN,MATHIEUC.APolynomial-timeApproximationSchemeforEuclideanSteinerForest[J].ACMTransactionsonAlgorithms, 2015, 11(3): 19.

[7]GUPTAA,KUMARA.AConstant-factorApproximationforStochasticSteinerForest[C]∥ProceedingsoftheForty-FirstAnnualACMSymposiumonTheoryofComputing. 2009: 659-668.

[8] 《運(yùn)籌學(xué)》教材編寫(xiě)組. 運(yùn)籌學(xué)[M]. 北京: 清華大學(xué)出版社, 1990：30-35.

[9] 常相全, 李同寧. 管理運(yùn)籌學(xué)[M]. 北京: 北京大學(xué)出版社, 2013：30-35.

ASynchronousApproximationAlgorithmforSteinerForestProblem

LI RuiYANG ZilanZHOU Huajun

(Tourism and Culture College of Yunnan University, Lijiang Yunnan 674100, China)

Steinerforestproblemisawell-knownNPCproblemincombinatorialoptimization,sointhispaperweadvocateanalgorithmtosolvetheSteinerforestproblem.Thealgorithmincreasesthedualvalueofeachconnectedcomponentsynchronously,andgetsafeasiblesolutiongradually.Thenweadjustthesolutionconstantlyandfinallyprovethecorrectnessandvalidityofthealgorithm.

Steinerforest;increasesynchronously;connectedcomponent

2016-04-16

云南省教育廳科學(xué)研究基金項(xiàng)目“視頻監(jiān)控中的全景攝像機(jī)自標(biāo)定技術(shù)”(2013Y167)

李睿(1983 — )，男，云南麗江人，碩士，云南大學(xué)旅游文化學(xué)院信息科學(xué)與技術(shù)系教師，研究方向?yàn)榻M合最優(yōu)化。

O157

A

1673-1980(2016)04-0122-03