集合覆盖问题的模型与算法

2013，49（17）1引言集合覆盖问题是组合最优化和理论计算机科学中的一类典型问题，它要求以最小代价将某一集合利用其若干子集加以覆盖。在现实生产生活中，集合覆盖问题有着众多应用场合，如物流配送、道路定向、工程调度、设施选址、VLSI设计、网络安全等[1-2]。遗憾的是，集合覆盖问题在算法复杂性上属于NP-困难问题[3]，即它不存在多项式时间精确算法，除非P=NP。因此，近似算法成为求解集合覆盖问题的一个有效途径，其中以Chvátal的贪心算法[4-5]最为简洁。后来，学者们又陆续提出过一些近似程度更好的近似算法[6]。近似算法固然是多项式时间算法，但返回的往往不是最优解，这在许多实际领域当然是不能令人满意的。事实上，在实际计算中，如果问题的规模相对较小，那么利用一般的线性规划或整数规划方法还是可以较为快速地得到其最优解的。随着计算机科技的迅猛发展，特别是LINGO、MATLAB[7-9]等高性能计算软件的成功研发与广泛应用，即便在问题的规模相当大时，人们也仍然能够迅速地求得其最优解。2问题与模型设基集S={e1e2en}，S1S2Sm是S的一族子集，若JÍ{12m}，且jÎJSj=S，则称{}SjjÎJ为S的一个集合覆盖。问题：求S的一个基数最小的集合覆盖，其中基数定义为集合中元素的数目。事实上，{}SjjÎJ为S的一个集合覆盖，意指S中的每一元素都至少含于某一集合Sj(jÎJ)中，即被Sj“覆盖”住。对每一子集Sj(j=12m)，引入决策变量：xj={1jÎJ0否则则可建立如下集合覆盖问题的0-1规划模型IP：minåj=1mxjs.t.åj:eiÎSjxj1i=12nxj=01j=12m其中约束条件“åj:eiÎSjxj1i=12n”确保S中的每一元素ei都至少被集合覆盖Sj(jÎJ)中的某一集合覆盖住。为便利后续讨论，将IP中变量的整数性要求加以放松，得其松弛线性规划问题LP：minåj=1mxj集合覆盖问题的模型与算法王继强WANGJiqiang山东财经大学数学与数量经济学院，济南250014SchoolofMathematicsandQuantitativeEconomics,ShandongUniversityofFinanceandEconomics,Jinan250014,ChinaWANGJiqiang.Modelandalgorithmforsetcoverproblem.ComputerEngineeringandApplications,2013,49（17）：15-17.Abstract：Thesetcoverproblemhasfavourableapplicationsinareasofnetworkdesign,butitisNP-hardincomputationalcom-plexity.A0-1programmodelisformulatedforthesetcoverproblem.Anapproximationalgorithmderivingfromgreedyideaisputforward,andisprovedfromtheangleofprimal-dualprogram.AcasestudyofsensornetworkoptimaldesignbasedonLINGOsoftwaredemonstratescorrectnessofthemodelandeffectivenessofthealgorithm.Keywords：setcover;approximationalgorithm;0-1program;dualprogram;LinearInteractiveandGeneralOptimizer（LINGO）摘要：集合覆盖问题在网络设计领域中有着良好的应用背景，但它在算法复杂性上却是NP-困难问题。建立了集合覆盖问题的0-1规划模型，给出了源于贪心思想的近似算法，并从原始-对偶规划的角度进行了证明，基于LINGO软件的传感器网络最优设计案例验证了模型的正确性和算法的有效性。关键词：集合覆盖；近似算法；0-1规划；对偶规划；线性交互式通用优化器（LINGO）文献标志码：A中图分类号：Q784；TP301.6doi：10.3778/j.issn.1002-8331.1303-0383基金项目：国家自然科学基金（No.10901093）。作者简介：王继强（1976—），男，博士，副教授，研究领域为算法分析与设计。E-mail：[e-mail]收稿日期：2013-03-25修回日期：2013-05-27文章编号：1002-8331（2013）17-0015-03ComputerEngineeringandApplications计算机工程与应用15ComputerEngineeringandApplications计算机工程与应用2013，49（17）s.t.åj:eiÎSjxj1i=12nxj0j=12m显然，由IP和LP之间的松弛关系知，OPTLPOPTIP，其中OPTLPOPTIP分别为LPIP的最优值。再由线性规划的对偶理论[10-11]知，LP的对偶问题为DP：maxåi=1nyis.t.åi:eiÎSjyi1j=12myi0i=12n下面，将分别给出集合覆盖问题的基于上述模型的两种解法。3近似算法借鉴Chvátal的贪心算法思想[4-5]，为集合覆盖问题设计如下算法：步骤1令J:=Φ，S͂j:=Sj(j=12m)。步骤2若jÎJSj¹S则令|S͂j*|=max1jm{|S͂j|}，J:=J{j*}，S͂j:=S͂j-S͂j*(j=12m)；否则，转步骤3。步骤3输出集合覆盖Sj(jÎJ)。定理1对每一eiÎS͂j*，令y͂i=1H(g)|S͂j*|，其中H(x)=åk=1x1k，g=max1jm{|Sj|}，则y͂i(i=12n)为DP的可行解。证明任取一子集Sj={e1e2ek}不妨设e1e2ek是依序被覆盖的，则当ei被覆盖时，e1e2ei-1已被S͂j*覆盖，故|S͂j*|i-1，从而|S͂j|k-(i-1)=k-i+1。由S͂j*的选取及y͂i的定义知：y͂i=1H(g)|S͂j*|1H(g)|S͂j|1H(g)(k-i+1)于是：åi:eiÎSjy͂i=åi=1ky͂iåi=1k1H(g)(k-i+1)=1H(g)åi=1k1k-i+1=1H(g)åi=1k1i=1H(g)H(k)1得证。定理2设算法输出的集合覆盖为Sj(jÎJ)，则|J|H(g)OPTIP。证明由y͂i的定义知：1=H(g)y͂i|S͂j*|=H(g)åi:eiÎS͂j*y͂i一般地，对每一jÎJ，有1=H(g)åi:eiÎS͂jy͂i。对其两边求和，得：|J|=åjÎJ1=åjÎJH(g)åi:eiÎS͂jy͂i=H(g)åjÎJåi:eiÎS͂jy͂i=H(g)åi=1ny͂i再由线性规划的弱对偶性知，åi=1ny͂iOPTLP，又OPTLPOPTIP，故|J|H(g)OPTIP，得证。据微积分知识知，H(g)=åk=1g1k»lng，因此算法的近似比为lng。4LINGO解法LINGO全称为LinearInteractiveandGeneralOpti-mizer（线性交互式通用优化器），是美国芝加哥大学学者L.Scharge在年研制开发的最优化计算软件，适用于线性规划、非线性优化、整数规划、二次规划等最优化问题的求解[7-9]。模型IP是一个0-1规划，当然可以利用LINGO来解决。5案例在Ad-hoc传感器网络中，信号覆盖范围或覆盖率是衡量网络服务质量的主要度量指标。因此，如何在保证信号覆盖质量的前提下，尽可能地节省网络建设成本就显得格外重要[1]。如图1所示，四个平面上的圆形区域是同种型号的传感器S1~S4的信号覆盖范围，e1~e9是九个服务客户，问：设置传感器的最佳方案是什么?不妨将九个服务客户视为“元素”，而各传感器的信号覆盖范围内的元素（客户）分别构成集合：S1={e1e2e3e4e5}S2={e3e4e5e6e7e8}S3={e2e4e5e7e8e9}S4={e1e2e3e4e8e9}则传感器的最佳设置方案应为集合S={e1~e9}的一个基数最小的集合覆盖。5.1近似算法求解根据算法的步骤，计算过程如下：（1）J:=ΦS͂1:=S1={e1e2e3e4e5}S͂2:=S2={e3e4e5e6e7e8}e8e5e4e2e3e1e6e7e9S3S2S1S4图1传感器网络162013，49（17）S͂3:=S3={e2e4e5e7e8e9}S͂4:=S4={e1e2e3e4e8e9}（2）j*=2，J:={2}S͂1:=S͂1-S͂j*={e1e2}S͂2:=S͂2-S͂j*=ΦS͂3:=S͂3-S͂j*={e2e9}S͂4:=S͂4-S͂j*={e1e2e9}（3）j*=4，J:={24}S͂1:=S͂1-S͂j*=ΦS͂2:=S͂2-S͂j*=ΦS͂3:=S͂3-S͂j*=ΦS͂4:=S͂4-S͂j*=Φ（4）因S2S4=S，故基数最小的集合覆盖为S2、S4。从而，最佳方案为设置传感器S2和S4。5.2LINGO求解根据模型IP建立如下0-1规划：minz=x1+x2+x3+x4s.t.x1+x41x1+x3+x41x1+x2+x41x1+x2+x3+x41x1+x2+x31x21x2+x31x2+x3+x41x3+x41x1x2x3x4=01编写如下LINGO程序：model：sets：variable/1..4/：c，x；constraint/1..9/：b；matrix（constraint，variable）：A；endsetsdata：c=1，1，1，1；b=1，1，1，1，1，1，1，1，1；A=100110111101111111100100011001110011；enddatamin=@sum（variable：c*x）；@for（constraint（i）：@sum（variable（j）：A（i，j）*x（j））=b（i））；@for（variable：@bin（x））；end在LINGO11.0上运行上述程序，返回如下结果：（限于篇幅，仅给出主要部分）Globaloptimalsolutionfound.Objectivevalue：2.000000Objectivebound：2.000000Infeasibilities：0.000000Extendedsolversteps：0Totalsolveriterations：0VariableValueReducedCostC（1）1.0000000.000000C（2）1.0000000.000000C（3）1.0000000.000000C（4）1.0000000.000000X（1）0.0000001.000000X（2）1.0000001.000000X（3）0.0000001.000000X（4）1.0000001.000000据此，最优解为x1=0x2=1x3=0x4=1，即基数最小的集合覆盖为S2、S4。从而，最佳方案为设置传感器S2和S4。案例表明两种方法得到的结果是一致的，因此模型科学合理，算法可行有效。6相关问题顶点覆盖问题是一个经典的图最优化问题，在算法复杂性上也属于NP-困难问题。设G=(VE)是一个无向图，其中VE分别为顶点集和边集，若存在CÍV，使ijÎE，都有iÎC或jÎC（即每一条边都至少有一个顶点含于C中），则称C为G的一个顶点覆盖。问题：求G的一个基数最小的顶点覆盖。顶点覆盖问题可等价地