基于动态极大度的极小碰集求解方法

1、精选优质文档-倾情为你奉上基于动态极大度的极小碰集求解方法            基于动态极大度的极小碰集求解方法张立明欧阳丹彤曾海林(吉林大学计算机科学与技术学院长春)摘要在计算集合簇的碰集时,结合SE-Tree(set enumeration tree)形式化地表达计算过程,逐步生成所有的极小碰集.并在SE-Tree中添加了终止结点,避免了非极小碰集的产生,并且不会因剪枝而丢失正确的解.提出未扩展元素度的概念和结点度的概念,进而在扩展SE-Tree结点

2、时按照未扩展元素度由大到小的顺序扩展,极早地生成集合簇的碰集,减少枚举树生成的结点个数,并且直接根据结点度得出结点对应的集合是否为集合簇的碰集,避免计算集合是否为集合簇的碰集.实验结果表明,该算法程序容易编制且效率较好.关键词基于模型的诊断;极小碰集; SE-Tree;动态极大度;向量交集中图法分类号; TP18现实和理论中的很多问题在某种程度上都可以转换成极小碰集问题.例如:基于模型诊断中极小诊断问题1、极小覆盖集问题、老师与课程(teacherand courses)问题和规则冲突检测算法中位向量的碰集问题2等.这类问题都是求解与已知集合都相交的极小集合.在基

3、于模型的诊断过程中3,一般先根据系统的描述和观测,得到极小冲突集,然后再求解极小冲突集的极小碰集,即为系统的极小诊断.迄今为止,国内外学者已对计算碰集的方法进行了许多研究和改进.在模型诊断中最早计算碰集的方法是由著名人工智能专家Reiter在1987年提出的HS-Tree求解碰集的方法1,在求解过程中加入剪枝策略和关闭策略,此种方法可能会丢失正确解.为了保证极小碰集求解方法的完备性,Greiner等人对此方法进行了改进,给出了结合非循环图的HS-DAG方法4.此后,奥地利学者Wotawa也给出了基于Reiter碰集算法的改进方法5;欧阳丹彤等人对Greiner给出的方法进行了改进,提出了New

4、Hs-Tree6方法,此方法在计算碰集时比HS-DAG方法搜索的结点数大大减少.由于计算碰集的方法是一个NP-hard问题,如何提高求解极小碰集的效率成为研究人员追求的目标.赵相福等人给出了使用集合枚举树SE-Tree形式化表达计算碰集的方法7;姜云飞等人分别给出了通过使用BHS-Tree8和布尔代数9求解碰集的方法;张楠等人给出了结合遗传算法的碰集求解方法10;黄杰等人给出了结合模拟退火的遗传算法来求解碰集11;这些方法主要缺点集中表现在:1)因剪枝策略或近似的计算可能丢失某些正确解1,10-11;2)需要建立复杂的数据结构树或图,并且数据结构及算法实现比较烦琐1,4-5;3)因为是递归计算

5、碰集,其效率较差1,4-7;4)以上算法计算效率不高,复杂度为NP完全的或是指数级的1,4-8;5)一般先存储计算得到所有碰集,最后还需删除非极小碰集才能得出所有极小的碰集9-11.本文在充分吸收国内外研究成果的基础上,分析求解碰集方法的优势与不足,提出基于动态极大度的求解极小碰集新方法,并使用带有终止结点的集合枚举树SE-Tree形式化地表达计算过程,逐步生成所有的极小碰集,这种方法主要优点是:1)按未扩展元素的度由大到小的顺序扩展结点,极早地生成集合簇的碰集,从而减少SE-Tree中计算的结点的个数;2)直接根据结点的度得出当前扩展的集合是否为碰集,从而避免了计算集合是否为集合簇的碰集的过

6、程;3)在SE-Tree中添加了终止结点,从而避免了非极小碰集的产生,提高了搜索效率,并且不会因剪枝而丢失正确的解;4)虽然本方法使用树结构描述算法,但实现时并不需要使用树结构,仅使用简单的链表和数组数据结构即可实现,即程序容易实现;5)所求得的集合若为碰集一定是极小的,不必最终再删除非极小碰集,并且能保证求得所有的极小碰集.1预备知识首先介绍基于模型诊断的相关概念:定义11.一个系统定义为一个三元组(SD,COMPS,OBS),其中:1) SD是系统描述,是一阶谓词公式的集合;2) COMPS为系统的组成部件集合,是一个有限的常量集;3) OBS为一观测集,是一

7、阶谓词公式的有限集.以下使用一元谓词AB(·)表示“abnormal”,AB(c)为真当且仅当c异常,其中cCOMPS.定义21.冲突集(CS)是一个部件集c1,c2,cn COMPS,当且仅当SDOBS AB(c1), AB(c2), AB(cn)是不一致的.称某冲突集为极小冲突集(MCS),当且仅当该冲突集的任意真子集都不是冲突集.定义31.设F是集合簇,F=S1,S2,Sn,称H为F的一个碰集(HS),如果H满足:1) H SFF;2)对每一个SF,都有HS .称F的一个碰集是极小碰集(MHS)当且仅当它的任

8、意真子集都不是F的碰集.例1.如图1为5个元件的poly-box系统,所有的极小冲突集为M1,M2, A1,M1, A1, A2,M3.所有极小冲突集的极小碰集为M1,A1,M2,A2,M2,M3.Fig. 1A poly-box system with 5 components(Miis amultiplier,Aiis an :I=A×B).图15个元件的poly-box系统(Mi表示乘法器,Ai表示加法器.如元件M1:I=A×B)以上部分介绍了模型诊

9、断领域中碰集的相关背景知识,并给出了一个关于极小碰集的简单实例,下面部分将给出本文提出的基于动态极大度的碰集求解方法.2动态极大度的极小碰集求解方法在给出基于动态极大度的求解方法之前,下面先给出度的概念和相应的命题.度的概念及相关的命题定义4.若cS,则称元素c覆盖集合S.元素c覆盖集合簇F记为Cover(c,F)=S|cS,SF.对于集合簇F=S1,S2,Sn,S1S2Sn=c1,c2,cm,若nodes=ci,cj,ck,(1ijkm),则Cover(nodes,F)=Cover(ci,F)Cover(cj,F)Cover(ck,F).定义5.结点中元素覆盖集合簇F中集合的个数称为结点的度

10、,记为Degree(Cover(nodes,F);当前结点对应的未扩展元素覆盖集合簇F-Cover(nodes)中集合的个数称为未扩展元素的度,记为Degree(Cover(cp,F-Cover(nodes,F),其中cp为未扩展元素,且cp nodes.根据以上定义,下列命题成立.命题1.设结点对应的集合为nodes,将扩展的元素为cp,则子结点度为当前结点度与未扩展元素度的和.即Degree(Cover(nodes,cp,F)=Degree(Cover(nodes, F)+Degree(Cover(cp, F-Cover(nodes,F).命题2.结点度不小于

11、集合簇中集合个数时,结点对应的集合为集合簇的碰集,即Degree(Cover(nodes,F)n,则nodes为集合簇F的碰集.DMDSE-Tree方法基本思想使用SE-Tree按照集合长度由小到大的顺序逐步生成元素集合的子集,计算每个结点对应的未扩展元素的度,并按度由大到小的顺序对元素进行扩展.如果结点的度不小于集合簇中集合的个数,则为碰集,对枚举树剪枝.否则继续扩展,最后得到所有的极小碰集.SE-Tree由Rymon12提出:一个完全的SE-Tree可以按照预先设定的顺序(如字母、数字顺序等),系统地枚举出一个集合的幂集中所有元素集合.比如集合S=A,B,C,D,它的完全集合枚举树如图2所

12、示:Fig. 2The SE-Tree ofA,B,C,D.图2集合A,B,C,D的完全集合枚举树下面的子部分给出SE-Tree中当前结点要扩展元素的基于度的扩展顺序.基于未扩展元素度的扩展顺序在算法DMD中,用二维数组setClustermn表示冲突集合簇F,setCluster中每一列表示一个冲突集,每行表示一个元素,如冲突集中有此元素,则记为1,否则记为0;用nodes存储SE-Tree中当前结点对应的元素集合;用一维数组setFlag来标记集合簇中集合是否已覆盖,并且数组中所有元素初始为0,表示所有集合未被覆盖;用一维数组elementFlag来标记元素是

13、否已扩展,并且数组中所有元素初始为0,表示所有元素未扩展;用一维数组unExtend存储按度由大到小对应的元素;用一维数组unExtWeight存储按度由大到小对应的元素的度.FUNCTION DMD(nodes)BEGIN211张立明等:基于动态极大度的极小碰集求解方法For(nodes中每个元素sai)BEGINelementFlagsai=1;For(sai覆盖集合簇中的每个集合setj)setFlagsetj=1ENDdegree=0;ueti=0;For(集合簇中的每一个元素ej)10BEGIN11If(elementFlagej=1)Continue;12For(集合簇中

14、每一个集合si)13If(!(setClusterejsi&&setFlagsi)14degree+;15unExtendueti+=ej;16unExtWeightueti+=degree;17END18Reorder(unExtend,unExtWeight);19END在算法DMD中,首先将SE-Tree的当前结点中每一个元素sai对应的elementFlag标记为1,表示已经扩展,并且把此元素覆盖集合簇中的集合setFlagsetj标记为1,表示已经覆盖.然后对degree和ueti初始化为0.并且对于集合簇中每一个元素,如果此元素为未扩展元素,则遍历此元素在集合簇中对

15、应的集合,如果此元素覆盖集合,则degree+,进而存储此元素对应的度.随后对使用数组存储未扩展元素和及其相应的度.最后对未扩展元素和其相应的度按照度由大到小的顺序进行排序.在编程实现中,可以记录父结点集合相应的信息,以减少对已经扩展元素的重复计算.下面给出结合结点的动态扩展顺序生成的一个剪枝的DMDSE-Tree过程.DMDSE-Tree的生成使用SE-Tree按照集合长度由小到大的顺序生成元素集合的子集,FUCTION DMD()给出了计算每个结点对应的未扩展元素度的过程.SE-Tree扩展结点时,按未扩展元素度由大到小顺序进行扩展.最大度的未扩展元素先扩展,因此较早地生成集合簇

16、的碰集,有效地减少了扩展SE-Tree时生成结点个数.下面结合结点的动态扩展顺序生成一个剪枝的DMDSE-Tree,然后给出剪枝树的正确性、完备性和复杂性分析.DMDSE-Tree生成过程如下:FUNCTION DMDSE-Tree()BEGINFor(对于每一个当前的结点nodes)BEGINFor(ishslist中每一个hs)BEGINIf(nodes hs)终止集合nodes;/*不再继续扩展集合nodes*/Break;END10END11For(DMD(nodes)中每一个未扩展元素cp)12BEGIN13degree=Degree(Cover(nodes,cp

17、,F);14If(degree集合簇中集合的个数)15标识nodes,cp为“”,不再继续扩展16ishslist·append (nodes, cp);/*用ishslist存储碰集*/17END18END最终,集合簇F的所有的极小碰集即为ishslist中的集合.下面对该方法从理论上作一个简单说明.1)两个修剪规则的正确性.一方面,对于在ishslist已产生的每一个极小碰集hs,若nodes hs,则该集合必为已产生的极小碰集的真超集,因此我们将不再判断集合nodes是否为碰集,从而避免产生某极小碰集的真超集的集合;另一方面,如果一个集合是碰集,那

18、么所有它的孩子结点的集合必然都是它的真超集,因而需将它标识为“,不必再对其进行扩展.2)完备性.由于一个完全SE-Tree能够按照某种预定的顺序枚举出一个集合的所有子集,因而除了已产生的极小碰集的真超集,系统部件集合的所有其他可能的子集都将产生;所有的极小碰集也将最终全部产生.212计算机研究与发展2011, 48(2)3)本方法的时间复杂度及空间复杂度主要与产生集合的个数相关,在最坏的情形为O(2n);但由于使用动态极大度生成结点和剪枝的存在,一般情况下复杂度总是小于O(2n)的.以上部分给出了本文提出的基于动态极大度的碰集求解方法,并描述了相应的主要算法;下面给出结合本文所提出的

19、方法来求解极小碰集的实例.3实例分析对于冲突集合簇F=1,3,4,3,4,5,2,5,图3为DMDSE-Tree方法的计算过程和结果.Fig. 3The DMDSE-Tree of 1,3,4,3,4,5,2,5.图3集合簇为1,3,4,3,4,5,2,5的DMDSE-Tree生成一个DMDSE-TreeT,过程如下:结点对应的未扩展元素为1,2,3,4,5.未扩展元素的度分别为1,1,2,2,2.则将扩展的元素顺序为3,4,5,1,2.集合3:degree=2集合4:degree=2集合5:degree=2集合1:degree=1集合2:degree=

20、1结点3对应的未扩展元素为1,2,4,5.未扩展元素的度分别为0,1,0,1.则将扩展的元素顺序为2,5,1,4.集合3,2:degree=3n,是碰集.集合3,5:degree=3n,是碰集.集合3,1:degree=2集合3,4:degree=2结点3,1对应的未扩展元素为4.未扩展元素的度为0.则将扩展的元素顺序为4.集合3,1,4:degree=2最后得到所有的极小碰集为3,2,3,5,4,5,4,2,5,1.4实验结果分析本文算法已经在VC+ 环境(Dell DimensionC521,Windows XP,MD Athlon(tm) 

21、;64 X2 DualCore Processor 3600+,1022MB RAM)下编程实现.仿照文献9,各冲突集分别为1,2,l,2,3,l+1,n,n+1,n+l-1,并增大冲突集个数,其中每个用例测试10次取平均值作为最后结果.运行结果如图4和表1所示.Fig. 4The comparison of time cost in DMDSE-Tree,BHS-Tree, and Boolean methods.图4DMDSE-Tree,BH

22、S-Tree,Boolean方法运行时间对比图Table 1The Comparison of Time Cost in DMDSE-Tree,BHS-Tree, and Boolean Methods表1DMDSE-Tree,BHS-Tree,Boolean方法运行时间对比表msSet Number DMDSE-Tree Boolean BHS-Tree2        &#

23、160;               从结果可以看出:1)计算出所有的极小碰集耗费时间较小,复杂度远远小于O(2n).2)随着冲突集个数的增加,极小碰集的计算时间增长平缓.3)本方法的效率比目前较快的文献9中方法至少提高1倍.复杂性分析:对于一个由m个元素、n个集合组成的集合簇求解碰集来说,因每次先扩展的元素的度(ndi)较大,进而每次计算未扩展元素的度的复杂度为(n-ndi)×(m-i).然后,变成求解由m-i个213张立明等:基于动态极大度的极小碰集求解方法素、n-ndi个集合组成的集合簇的碰集,此时,每次计算未扩展元素的度的复杂度为(n-ndi-ndi+1)×(m-i-1),ndi+1为此次先扩展的元素的度.而传统的方法每次计算碰集的复杂度都为n×m.本文的方法使每个碰集的计算复杂度由原来的n×m减少到(ni-ndi)×(m-i),其中ni为组成当前集合簇中集合的个数,ndi为此次先扩展元素对应的度.因而本文方法有较好的效率.5相关工作和展望许多学者对碰集的求解方法进行