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

基于动态极大度的极小碰集求解方法基于动态极大度的极小碰集求解方法张立明欧阳丹彤曾海林(吉林大学计算机科学与技术学院长春130012)摘要在计算集合簇的碰集时,结合SE-Tree(setenumerationtree)形式化地表达计算过程,逐步生成所有的极小碰集.并在SE-Tree中添加了终止结点,避免了非极小碰集的产生,并且不会因剪枝而丢失正确的解.提出未扩展元素度的概念和结点度的概念,进而在扩展SE-Tree结点时按照未扩展元素度由大到小的顺序扩展,极早地生成集合簇的碰集,减少枚举树生成的结点个数,并且直接根据结点度得出结点对应的集合是否为集合簇的碰集,避免计算集合是否为集合簇的碰集.实验结果表明,该算法程序容易编制且效率较好.关键词基于模型的诊断;极小碰集;SE-Tree;动态极大度;向量交集中图法分类号;TP18现实和理论中的很多问题在某种程度上都可以转换成极小碰集问题.例如:基于模型诊断中极小诊断问题[1]、极小覆盖集问题、老师与课程(teacherandcourses)问题和规则冲突检测算法中位向量的碰集问题[2]等.这类问题都是求解与已知集合都相交的极小集合.在基于模型的诊断过程中[3],一般先根据系统的描述和观测,得到极小冲突集,然后再求解极小冲突集的极小碰集,即为系统的极小诊断.迄今为止,国内外学者已对计算碰集的方法进行了许多研究和改进.在模型诊断中最早计算碰集的方法是由著名人工智能专家Reiter在1987年提出的HS-Tree求解碰集的方法[1],在求解过程中加入剪枝策略和关闭策略,此种方法可能会丢失正确解.为了保证极小碰集求解方法的完备性,Greiner等人对此方法进行了改进,给出了结合非循环图的HS-DAG方法[4].此后,奥地利学者Wotawa也给出了基于Reiter碰集算法的改进方法[5];欧阳丹彤等人对Greiner给出的方法进行了改进,提出了NewHs-Tree[6]方法,此方法在计算碰集时比HS-DAG方法搜索的结点数大大减少.由于计算碰集的方法是一个NP-hard问题,如何提高求解极小碰集的效率成为研究人员追求的目标.赵相福等人给出了使用集合枚举树SE-Tree形式化表达计算碰集的方法[7];姜云飞等人分别给出了通过使用BHS-Tree[8]和布尔代数[9]求解碰集的方法;张楠等人给出了结合遗传算法的碰集求解方法[10];黄杰等人给出了结合模拟退火的遗传算法来求解碰集[11];这些方法主要缺点集中表现在:1)因剪枝策略或近似的计算可能丢失某些正确解[1,10-11];2)需要建立复杂的数据结构树或图,并且数据结构及算法实现比较烦琐[1,4-5];3)因为是递归计算碰集,其效率较差[1,4-7];4)以上算法计算效率不高,复杂度为NP完全的或是指数级的[1,4-8];5)一般先存储计算得到所有碰集,最后还需删除非极小碰集才能得出所有极小的碰集[9-11].本文在充分吸收国内外研究成果的基础上,分析求解碰集方法的优势与不足,提出基于动态极大度的求解极小碰集新方法,并使用带有终止结点的集合枚举树SE-Tree形式化地表达计算过程,逐步生成所有的极小碰集,这种方法主要优点是:1)按未扩展元素的度由大到小的顺序扩展结点,极早地生成集合簇的碰集,从而减少SE-Tree中计算的结点的个数;2)直接根据结点的度得出当前扩展的集合是否为碰集,从而避免了计算集合是否为集合簇的碰集的过程;3)在SE-Tree中添加了终止结点,从而避免了非极小碰集的产生,提高了搜索效率,并且不会因剪枝而丢失正确的解;4)虽然本方法使用树结构描述算法,但实现时并不需要使用树结构,仅使用简单的链表和数组数据结构即可实现,即程序容易实现;5)所求得的集合若为碰集一定是极小的,不必最终再删除非极小碰集,并且能保证求得所有的极小碰集.1预备知识首先介绍基于模型诊断的相关概念:定义1[1].一个系统定义为一个三元组(SD,COMPS,OBS),其中:1)SD是系统描述,是一阶谓词公式的集合;2)COMPS为系统的组成部件集合,是一个有限的常量集;3)OBS为一观测集,是一阶谓词公式的有限集.以下使用一元谓词AB(·)表示“abnormal”,AB(c)为真当且仅当c异常,其中c∈COMPS.定义2[1].冲突集(CS)是一个部件集{c1,c2,…,cn}COMPS,当且仅当SD∪OBS∪{AB(c1),AB(c2),…,AB(cn)}是不一致的.称某冲突集为极小冲突集(MCS),当且仅当该冲突集的任意真子集都不是冲突集.定义3[1].设F是集合簇,F={S1,S2,…,Sn},称H为F的一个碰集(HS),如果H满足:1)H∪S∈FF;2)对每一个S∈F,都有H∩S≠.称F的一个碰集是极小碰集(MHS)当且仅当它的任意真子集都不是F的碰集.例1.如图1为5个元件的poly-box系统,所有的极小冲突集为{M1,M2,A1},{M1,A1,A2,M3}.所有极小冲突集的极小碰集为{M1},{A1},{M2,A2},{M2,M3}.Fig.1Apoly-boxsystemwith5components(Miisamultiplier,Aiisan:I=A×B).图15个元件的poly-box系统(Mi表示乘法器,Ai表示加法器.如元件M1:I=A×B)以上部分介绍了模型诊断领域中碰集的相关背景知识,并给出了一个关于极小碰集的简单实例,下面部分将给出本文提出的基于动态极大度的碰集求解方法.2动态极大度的极小碰集求解方法在给出基于动态极大度的求解方法之前,下面先给出度的概念和相应的命题.度的概念及相关的命题定义4.若c∈S,则称元素c覆盖集合S.元素c覆盖集合簇F记为Cover(c,F)={S|c∈S,S∈F}.对于集合簇F={S1,S2,…,Sn},S1∪S2∪…∪Sn={c1,c2,…,cm},若nodes={ci,…,cj,…,ck},(1≤i≤j≤k≤m),则Cover(nodes,F)=Cover(ci,F)∪…∪Cover(cj,F)∪…∪Cover(ck,F).定义5.结点中元素覆盖集合簇F中集合的个数称为结点的度,记为Degree(Cover(nodes,F));当前结点对应的未扩展元素覆盖集合簇F-Cover(nodes)中集合的个数称为未扩展元素的度,记为Degree(Cover(cp,F-Cover(nodes,F))),其中cp为未扩展元素,且cpnodes.根据以上定义,下列命题成立.命题1.设结点对应的集合为nodes,将扩展的元素为cp,则子结点度为当前结点度与未扩展元素度的和.即Degree(Cover({nodes,cp},F))=Degree(Cover(nodes,F))+Degree(Cover(cp,F-Cover(nodes,F))).命题2.结点度不小于集合簇中集合个数时,结点对应的集合为集合簇的碰集,即Degree(Cover(nodes,F))≥n,则nodes为集合簇F的碰集.DMDSE-Tree方法基本思想使用SE-Tree按照集合长度由小到大的顺序逐步生成元素集合的子集,计算每个结点对应的未扩展元素的度,并按度由大到小的顺序对元素进行扩展.如果结点的度不小于集合簇中集合的个数,则为碰集,对枚举树剪枝.否则继续扩展,最后得到所有的极小碰集.SE-Tree由Rymon[12]提出:一个完全的SE-Tree可以按照预先设定的顺序(如字母、数字顺序等),系统地枚举出一个集合的幂集中所有元素集合.比如集合S={A,B,C,D},它的完全集合枚举树如图2所示:Fig.2TheSE-Treeof{A,B,C,D}.图2集合{A,B,C,D}的完全集合枚举树下面的子部分给出SE-Tree中当前结点要扩展元素的基于度的扩展顺序.基于未扩展元素度的扩展顺序在算法DMD中,用二维数组setCluster[m][n]表示冲突集合簇F,setCluster中每一列表示一个冲突集,每行表示一个元素,如冲突集中有此元素,则记为1,否则记为0;用nodes存储SE-Tree中当前结点对应的元素集合;用一维数组setFlag来标记集合簇中集合是否已覆盖,并且数组中所有元素初始为0,表示所有集合未被覆盖;用一维数组elementFlag来标记元素是否已扩展,并且数组中所有元素初始为0,表示所有元素未扩展;用一维数组unExtend存储按度由大到小对应的元素;用一维数组unExtWeight存储按度由大到小对应的元素的度.FUNCTIONDMD(nodes)①BEGIN211张立明等:基于动态极大度的极小碰集求解方法②For(nodes中每个元素sai)③BEGIN④elementFlag[sai]=1;⑤For(sai覆盖集合簇中的每个集合setj)⑥setFlag[setj]=1⑦END⑧degree=0;ueti=0;⑨For(集合簇中的每一个元素ej)○10BEGIN○11If(elementFlag[ej]==1)Continue;○12For(集合簇中每一个集合si)○13If(!(setCluster[ej][si]&&setFlag[si]))○14degree++;○15unExtend[ueti++]=ej;○16unExtWeight[ueti++]=degree;○17END○18Reorder(unExtend,unExtWeight);○19END在算法DMD中,首先将SE-Tree的当前结点中每一个元素sai对应的elementFlag标记为1,表示已经扩展,并且把此元素覆盖集合簇中的集合setFlag[setj]标记为1,表示已经覆盖.然后对degree和ueti初始化为0.并且对于集合簇中每一个元素,如果此元素为未扩展元素,则遍历此元素在集合簇中对应的集合,如果此元素覆盖集合,则degree++,进而存储此元素对应的度.随后对使用数组存储未扩展元素和及其相应的度.最后对未扩展元素和其相应的度按照度由大到小的顺序进行排序.在编程实现中,可以记录父结点集合相应的信息,以减少对已经扩展元素的重复计算.下面给出结合结点的动态扩展顺序生成的一个剪枝的DMDSE-Tree过程.DMDSE-Tree的生成使用SE-Tree按照集合长度由小到大的顺序生成元素集合的子集,FUCTIONDMD()给出了计算每个结点对应的未扩展元素度的过程.SE-Tree扩展结点时,按未扩展元素度由大到小顺序进行扩展.最大度的未扩展元素先扩展,因此较早地生成集合簇的碰集,有效地减少了扩展SE-Tree时生成结点个数.下面结合结点的动态扩展顺序生成一个剪枝的DMDSE-Tree,然后给出剪枝树的正确性、完备性和复杂性分析.DMDSE-Tree生成过程如下:FUNCTIONDMDSE-Tree()①BEGIN②For(对于每一个当前的结点nodes)③BEGIN④For(ishslist中每一个hs)⑤BEGIN⑥If(nodeshs)⑦终止集合nodes;/*不再继续扩展集合nodes*/⑧Break;⑨END○10END○11For(DMD(nodes)中每一个未扩展元素cp)○12BEGIN○13degree=Degree(Cover({nodes,cp},F));○14If(degree≥集合簇中集合的个数)○15标识{nodes,cp}为“√”,不再继续扩展○16ishslist·append({nodes,cp});/*用ishslist存储碰集*/○17END○18END最终,集合簇F的所有的极小碰集即为ishslist中的集合.下面对该方法从理论上作一个简单说明.1)两个修剪规则的正确性.一方面,对于在ishslist已产生的每一个极小碰集hs,若nodeshs,则该集合必为已产生的极小碰集的真超集,因此我们将不再判断集合nodes是否为碰集,从而避免产生某极小碰集的真超集的集合;另一方面,如果一个集合是碰集,那么所有它的孩子结点的集合必然都是它的真超集,因而需将它标识为“√“,不必再对其进行扩展.2)完备性