基于动态极大元素覆盖值的极小碰集求解算法

邓召勇 欧阳丹彤 耿雪娜 刘 杰

(吉林大学计算机科学与技术学院 长春 130012) (符号计算与知识工程教育部重点实验室(吉林大学) 长春 130012) (dengzy19941019@163.com)

极小碰集的应用领域广泛，很多现实和理论中的问题都可以转化为求解极小碰集问题，例如基于模型诊断(model-based diagnosis, MBD)[1]中极小诊断问题、极小覆盖集问题以及规则冲突检测算法中位向量的碰集问题[2]等.基于模型诊断是人工智能领域里一个非常重要的研究分支，它的主要工作原理是根据系统的描述和观测进行逻辑推理得到冲突部件集合，再通过冲突部件集合计算极小碰集，即得到诊断结果.

迄今为止，国内外学者已对极小碰集求解算法进行了许多研究和优化.最经典的计算极小碰集的算法是1987年由人工智能专家Reiter[1]提出的HS-TREE算法，该算法在求解过程中加入了剪枝策略和关闭策略.HS-TREE算法的缺点是空间复杂度呈指数级增长、产生节点多、效率低，并且会因为剪枝策略导致求得的极小碰集不完备.为了保证极小碰集求解算法的完备性，Greiner等人[3]于1989年提出了HS-DAG算法.HS-DAG算法在HS-TREE算法的基础上优化了剪枝策略，避免了剪掉正确解的情况，但是HS-DAG算法的模型结构比较复杂，空间复杂度高，计算过程较为繁琐.针对这些缺点，姜云飞和林笠[4]于2002年提出了BHS-TREE算法，该算法无需剪枝，求解效率有明显提高，但由于是树形结构，导致该算法在编程实现时存在数据结构复杂、不易实现等缺点.近年来，国内学者陆续提出了一些串行极小碰集求解算法：2003年姜云飞和林笠[5]提出Boolean算法；2006年和2011年欧阳丹彤等人提出HSSE-TREE[6]和DMDSE-TREE[7]算法；2015年王艺源等人[8]提出CSP-MHS算法.此外，近年来也有一些并行及分布式[9-10]极小碰集求解算法被提出，并行及分布式极小碰集求解算法利用多核和多处理器的优势提高极小碰集求解效率.并行及分布式极小碰集求解算法相对串行极小碰集求解算法效率有了较大提高，但是串行算法经过相应修改可以转变为并行及分布式算法，因此本文主要关注串行极小碰集求解算法.串行极小碰集求解算法中效率较为突出的算法是Boolean算法，Boolean算法用布尔代数变量表示待诊断系统的部件，并用布尔代数知识计算极小碰集.目前来看，在布尔代数算法之后提出的串行算法虽然在某些集合簇上有较高的效率，但综合来看，仍是布尔代数算法占优.

布尔代数算法是目前求解极小碰集效率优良的算法，然而当系统很大时，碰集的极小化过程会花费较多时间，因此不适用于规模较大的系统.本文针对布尔代数算法的缺点，引入特定状态下元素的元素覆盖值作为启发式信息，提出了一种基于动态极大元素覆盖值求解极小碰集的新算法MHS-DMECV.本文中元素覆盖值的概念类似于2011年欧阳丹彤等人[7]提出的DMDSE-TREE算法中的度，且MHS-DMECV算法和DMDSE-TREE算法都优先选取覆盖集合簇中元素最多的元素作为碰集的1个元素，但是本文中的元素覆盖值简化了度的定义且MHS-DMECV算法在选取元素时添加了启发式策略和剪枝策略.MHS-DMECV算法的主要优点是：

1) 按照元素的元素覆盖值由大到小的顺序选取元素，选取的元素构成的集合S若能构成碰集，则S是最快构成碰集的元素集合，否则直接返回对当前元素的处理.

2) 求解过程中添加启发式策略和剪枝策略，使得搜索空间极大减少，且剪枝策略不会丢失极小碰集.

3) 使用邻接链表存储输入的集合簇，邻接链表结构能快速找到元素能够覆盖的集合簇中的元素.

4) MHS-DMECV算法只对邻接链表进行简单遍历，因此程序容易实现.

5) MHS-DMECV算法结束时能保证求得所有的极小碰集.

1 背景知识

本节介绍碰集(hitting set,HS) 的相关定义和概念，并给出一个实例说明碰集、极小碰集、容量、势以及频数的具体含义.

集合簇CS的一个碰集是极小碰集(MHS)当且仅当它的任意真子集都不是CS的碰集.

定义2. 容量.若集合簇CS中包含元素的个数为n，则称n为集合簇CS的容量，记为Cap(CS)=n.

设U是集合簇CS中所有元素的并集构成的集合，即U=∪Si={e1,e2,…,em}，用Car(U)表示集合U的势，即集合U中元素的个数.

定义3. 频数.若e∈S，则称集合S含有元素e，记Freq(CS,e) 表示集合簇CS中含有元素e的元素的个数，称为元素e在集合簇CS中的频数.

例1. 设集合簇CS={{1,2},{2,3},{3,4}}，则集合簇CS的容量Cap(CS)=3；集合U={1,2,3,4}的势Car(U)=4；容易看出集合{2,3}构成集合簇CS的一个碰集，并且它还是极小碰集.若选取元素e=2，则元素2在集合簇CS中的频数Freq(CS,2)=2，因为元素2出现在集合簇CS的元素{1,2}和{2,3}中.

2 极小碰集求解算法

本节首先给出元素覆盖值、已覆盖数和可覆盖数等概念，然后详细描述算法JudgeMHS和MHS-DMECV.

2.1 相关定义及定理

本节给出元素覆盖值、待处理序列、已覆盖数和可覆盖数的定义，并基于启发式策略、剪枝策略和极小碰集判定规则给出3个定理.

定义4. 元素覆盖值.若元素e在集合簇CS的某个元素Si(i=1,2,…,n)中出现，且在当前状态下Si中没有其他元素出现，则称元素e覆盖Si；若对于集合簇CS中的所有元素，元素e能覆盖的元素个数为C，则称C为元素e的元素覆盖值，记为Cover(e).显然 0≤Cover(e)≤Freq(CS,e) .

例2. 对于集合簇CS={{1,2},{2,3},{3,4}}，若首先选择元素1，则它能覆盖集合{1,2}，所以Cover(1)=1；此时再选择元素2，由于集合{1,2}已被覆盖，所以元素2只能覆盖集合{2,3}，因此Cover(2)=1；对于元素3，由于集合{2,3}已被覆盖，所以元素3只能覆盖集合{3,4}，因此Cover(3)=1；对于元素4，由于集合簇CS中的所有元素都已被覆盖，因此Cover(4)=0.

定义5. 待处理序列.在当前状态下，待处理的元素集合为Pend={ei,ei+1,…,ej-1,ej}，计算出Pend集合中所有元素的元素覆盖值Cover(ek)(k=i,i+1,…,j-1,j)，并按照元素覆盖值从大到小的顺序排列，此时得到的序列称为待处理序列，记为Seq.

例3. 对于集合簇CS={{1,2},{2,3},{3,4}}，初始时没有选中任何元素，则Cover(1)=1，此时恢复到初始状态，即没有选中元素1时的状态.此后每计算出一个元素e的元素覆盖值，都将元素e造成的影响进行恢复，所以Cover(2)=2，Cover(3)=2和Cover(4)=1，因此待处理序列Seq=[2,3,1,4](为了描述方便，假设具有相同元素覆盖值的元素按照元素本身的大小从小到大排序).

定义6. 已覆盖数和可覆盖数.在当前状态下，如果集合簇CS中已被覆盖的元素个数为AlreadyCover，则称AlreadyCover为已覆盖数.对于待处理序列Seq，Seq能覆盖的集合簇CS中元素总数为CanCover，则称CanCover为可覆盖数.

例4. 对于集合簇CS={{1,2},{2,3},{3,4}}，假设已经选取元素2作为碰集HS的一个元素，且HS中没有选取其他元素，即HS={2}.则在当前状态state下，集合簇CS中的元素{1,2}和{2,3}已被元素2覆盖，所以已覆盖数AlreadyCover=2；基于当前状态state，计算出待处理元素集合Pend={1,3,4}中每个元素的元素覆盖值为Cover(1)=0，Cover(3)=1和Cover(4)=1(在计算完某一个元素e的元素覆盖值后，都将该元素e造成的影响恢复，使其回到当前状态state).注意到在当前状态state下集合簇CS中只有一个元素{3,4}能被覆盖，且{3,4}可以被元素3或元素4覆盖，所以可覆盖数CanCover=1.此时新的待处理序列Seq′=[3,4,1].

定理1. 对于当前状态state，若已知已覆盖数AlreadyCover和可覆盖数CanCover，且Already-Cover+CanCover

证明.

1) 必要性.

假设NewPend表示新的待处理序列Seq′中所有元素构成的集合，S=Before∪NewPend.由于已覆盖数AlreadyCover和可覆盖数CanCover的和小于集合簇CS的容量，因此∃S′∈CS，Before∩S′=∅ 且NewPend∩S′=∅，从而S∩S′=∅，由碰集定义可知S不构成碰集.又因为NewPend表示新的待处理序列Seq′中所有元素构成的集合，因此对于NewPend的任意子集Su⊆NewPend，S=Before∪Su也一定不能构成碰集，必要性得证.

2) 充分性.

假设NewPend表示新的待处理序列Seq′中所有元素构成的集合，S=Before∪NewPend.由于S不构成碰集，因此 ∃S′∈CS，S∩S′=∅.将S=Before∪NewPend代入得(Before∩S′)∪(NewPend∩S′)=∅，即在预先选择的元素集合Before以及新的待处理序列Seq′中不存在元素e使得e能够覆盖集合S′，所以已覆盖数AlreadyCover与可覆盖数CanCover的和一定小于集合簇CS的容量，即AlreadyCover+CanCover

证毕.

基于定理1和相关定义给出启发式策略和剪枝策略.

1) 启发式策略.对于当前状态state，若已知已覆盖数AlreadyCover和可覆盖数CanCover，且AlreadyCover+CanCover

2) 剪枝策略.对于待处理序列Seq=[ei,ei+1,…,ej-1,ej]，从前往后扫描Seq时发现位置k处元素ek的元素覆盖值Cover(ek)=0，则只需考虑位置k之前的序列Seq1=[ei,ei+1, …,ek-1](如果Seq中不存在位置k使得Cover(ek)=0，那么Seq1就指Seq).

定理2. 对于求解集合簇CS的极小碰集问题，剪枝策略不会导致丢解.

证明. 从前往后扫描待处理序列Seq的过程中，如果发现某个位置k使得该位置处元素ek的元素覆盖值Cover(ek)=0，由于待处理序列Seq是按照元素覆盖值Cover(e)从大到小的顺序排列，且Cover(e)≥0，因此位置k及其之后位置对应的元素et(t=k,k+1,…,j-1,j) 的元素覆盖值Cover(et)=0.由元素覆盖值的定义知，元素et对覆盖集合簇CS中的元素不再有帮助，且极小碰集的定义要求极小碰集MHS中的任意1个元素e′∈MHS都是不可取代的.e′至少能覆盖集合簇CS中的1个元素S∈CS，且极小碰集中的其他元素都不能覆盖S，因此去除Seq中位置k及其之后位置对应的元素对于计算极小碰集并不会导致丢解，也即可以用Seq1代替Seq参与运算.如果Seq1=Seq，显然可以用Seq1代替Seq.

证毕.

极小碰集判定规则.假设碰集HS={ex,ex+1,…,ey}，若依次去除元素ei∈HS(i=x,x+1,…,y)的过程中，发现得到的集合HS′ 满足碰集定义，则判定HS不是极小碰集，否则恢复ei造成的影响，继续处理去除ei+1的情况.若在去除碰集HS最后1个元素ey时HS′ 仍不满足碰集定义，则判定HS是极小碰集.

定理3. 极小碰集判定规则正确有效.

证明. 假设碰集HS={ex,ex+1,…,ey}，若去除HS中任意1个元素ei(i=x,x+1,…,y)之后得到的集合HS′ 满足碰集定义，则由极小碰集的定义知碰集HS一定不是极小碰集，否则HS存在是极小碰集的可能性.若去除碰集HS中任意1个元素ei(i=x,x+1,…,y)后得到的集合HS′都不满足碰集定义，则说明碰集HS中每个元素都不可取代，因此判定HS是极小碰集.

证毕.

由于本文的算法只能极大限度地缩小搜索的碰集空间，它并不保证求得的碰集一定是极小碰集，因此在给出求解极小碰集的算法MHS-DMECV之前，首先给出极小碰集判定算法JudgeMHS.

2.2 JudgeMHS算法

本节给出极小碰集判定算法JudgeMHS的算法描述.

本文用邻接链表存储输入的集合簇CS，目的是快速找到集合U中特定元素具体能覆盖集合簇CS中的哪些元素.引入2个结构SetNode和ListNode，其中SetNode包含属性setNum(setNum表示U中特定元素能覆盖集合簇CS中的第setNum个元素)和next(next指向下一个SetNode节点)；ListNode包含属性adjacent(adjacent表示U中特定元素具体能覆盖的集合簇CS中元素的邻接指向).

例5. 对于集合簇CS={{1,2},{2,3},{3,4}}，由于Cap(CS)=3，U={1,2,3,4}，Car(U)=4，所以需要4个ListNode节点来表示集合U中的4个元素，这里用Head[4]数组表示(数组索引代表集合U中相应元素).对于集合簇CS，用1代表第1个元素{1,2}，2代表第2个元素{2,3}，3代表第3个元素{3,4}，因此集合簇CS对应的邻接链表结构如图1所示：

Fig. 1 The adjacency list of the set cluster CS图1 集合簇CS对应的邻接链表

有了对集合簇CS的邻接链表表示形式，下面基于极小碰集判定规则给出极小碰集判定算法JudgeMHS.SetFlag数组(大小为集合簇CS的容量) 维护碰集HS能够覆盖的集合簇中的元素，SetFlag[i](i=1,2,…,Cap(CS)) 初始为0表示未覆盖，大于等于1表示覆盖(等于1表示HS中只有1个元素能覆盖i对应的集合簇中的元素，大于1表示HS中存在多个元素能覆盖i对应的集合簇中的元素)；逻辑变量Flag标志HS是否是极小碰集，false表示HS不是极小碰集，true表示HS是极小碰集.

算法1. JudgeMHS.

输入：碰集HS、集合簇CS的邻接链表Head数组；

输出：碰集HS是否是极小碰集，若是返回true，否则返回false.

① 将SetFlag数组中每个元素的值初始化为0，执行步②.

② 循环处理HS中的元素e，循环未结束时利用Head[e]的邻接指向获取元素e能覆盖的集合簇中的元素setNum，将SetFlag[setNum]+1，返回步②，否则执行步③.

③ 循环处理HS中的元素e，循环未结束时利用Head[e]的邻接指向获取元素e能覆盖的集合簇中的元素setNum，将SetFlag[setNum]-1，即去除元素e，执行步④，否则返回true.

④ 置Flag=false，循环处理SetFlag数组中的元素SetFlag[i]，循环未结束时如果SetFlag[i]=0，则置Flag=true，退出当前循环并执行步⑤，否则继续执行循环；循环结束时执行步⑤.

⑤ 如果Flag=false，则说明去除碰集中的元素e后构成的集合仍然满足碰集定义，则HS不是极小碰集，返回false，否则执行步⑥.

⑥ 利用Head[e]的邻接指向获取元素e能覆盖的集合簇中的元素setNum，将SetFlag[setNum]+1，即恢复元素e对SetFlag数组造成的影响，执行步③.

2.3 MHS-DMECV算法

本节给出MHS-DMECV算法的算法描述并分析其完备性和复杂性.

MHS-DMECV算法中HittingSet用于在算法执行过程中动态生成碰集，MinHittingSet用于存储所有的极小碰集.

算法2. MHS-DMECV.

输入：待处理序列Seq、与Seq对应的邻接链表Head数组、与Seq对应的元素覆盖值Cover数组、动态保存碰集的容器HittingSet、集合簇CS的元素覆盖标志SetFlag数组(初始时每个元素的值都为0)、已覆盖数AlreadyCover(初始为0)；

输出：集合簇CS对应的所有极小碰集容器MinHittingSet.

① 循环处理Seq中的元素e，执行步②，循环结束则返回.

② 如果e是Seq中最后一个元素，且Cover[e]+AlreadyCover

③ 如果Cover[e]+AlreadyCover=Cap(CS)，将HittingSet中元素存储到一个新的容器container里并将元素e也加入container.以container作为输入调用JudgeMHS，若返回true，则将container加入MinHittingSet，返回步①处理Seq中下一个元素.若Cover[e]+AlreadyCover

④ 将元素e加入HittingSet，遍历Head[e]的邻接指向，若集合簇CS中存在元素setNum的覆盖标志SetFlag[setNum]=0且e能覆盖setNum，则将AlreadyCover+1；将Head[e]能遍历到的集合簇CS中对应元素的覆盖标志+1，执行步⑤.

⑤ 构建2个数据结构Seq′和Head′，其中Seq′表示在元素e已被选中的状态下Seq中在e之后的序列里元素覆盖值不为0的元素集合，此时Seq′对应的元素覆盖值数组为Cover′；Head′数组构建1个对应Seq′的邻接链表，即只有在Seq′中的元素在Head′数组中才会有邻接指向，且Head′数组中元素的邻接指向指向的SetNode节点集正是Seq′中相应元素能覆盖的集合簇CS中的元素集对应的SetNode节点集.构建可覆盖数CanCover(初始为0)，CanCover表示在元素e已被选中的状态下，Seq′可以覆盖的集合簇CS中的元素数，执行步⑥.

⑥ 如果AlreadyCover+CanCover

⑦ 按照元素覆盖值从大到小对Seq′进行排序，得到新的待处理序列Seq′；将Seq′、Seq′对应的邻接链表Head′数组、Cover′数组、HittingSet、SetFlag数组以及AlreadyCover作为输入递归调用MHS-DMECV.递归返回时从HittingSet中移除元素e，遍历Head[e]的邻接指向，将Head[e]能遍历到的集合簇CS中对应元素的覆盖标志减1，若集合簇CS中存在元素setNum的覆盖标志SetFlag[setNum]=0且e能覆盖setNum，则将AlreadyCover-1，返回步①继续处理Seq中下一个元素.

MHS-DMECV算法结束时，MinHittingSet包含所有极小碰集，下面从理论上对MHS-DMECV算法的完备性和复杂性进行分析.

1) 完备性.在循环处理待处理序列Seq中的元素e时(不考虑启发式策略和剪枝策略)，由于是递归处理，因此它总能枚举出所有可能的集合.加入启发式策略会得到最先能够构成碰集的碰集集合HSS，且HSS是极小碰集集合的超集，因此能保证在算法结束时得到所有的极小碰集.又因为剪枝策略并不会导致丢失极小碰集，所以MHS-DMECV算法对于求解集合簇CS的极小碰集问题是完备的.

2) 复杂性.假设MHS-DMECV算法的总运行时间用T表示(此时不考虑启发式策略和剪枝策略)，由于初始时需要执行m次循环(m表示集合U的势)，因此T=T(1)+T(2)+…+T(m).在每一次循环中都遍历一遍邻接链表和对相应元素排序，这个子过程的时间复杂度可以用Tsub=O(mn+mlbm)表示，其中n表示集合簇CS的容量；又T(1)=Tsub+T(2)+T(3)+…+T(m)，T(2)=Tsub+T(3)+T(4)+…+T(m)，…，T(m-1)=Tsub+T(m)，T(m)=O(1)，所以T=O(Tsub2m)，即算法最坏时间复杂度是指数级；由于需要存储所有极小碰集，且在最坏情况时极小碰集数是指数级增长，因此算法的空间复杂度在最坏情况时是指数级.在MHS-DMECV算法中，因为每次处理的元素ei的元素覆盖值都是待处理序列Seq中最大的，这种策略能规避掉很多不必要的处理.例如元素e1能覆盖集合簇CS中的所有元素，元素e2只能覆盖集合簇CS中的1个元素.如果首先处理e1，则不需要再递归处理e2，否则由于处理到e2时，发现单独由e2构成的集合{e2}并不足以构成碰集，且在e2之后的序列中存在元素构成的集合并上{e2}能构成碰集，则会继续递归处理.考虑启发式策略，如果选择元素ei放入动态碰集容器HittingSet后，发现AlreadyCover+CanCover

3 实例分析

本节基于一个实例对MHS-DMECV算法的执行流程进行分析.

例6. 对于集合簇CS={{1,2},{2,3},{3,4}}，利用MHS-DMECV算法求CS的所有极小碰集.

由例3知初始时待处理序列Seq=[2,3,1,4]，邻接链表Head数组如图2所示，元素覆盖值数组Cover=[2,2,1,1],HittingSet和MinHittingSet为空，集合簇CS的元素覆盖标志SetFlag=[0,0,0]，已覆盖数AlreadyCover=0.此时的状态如表1和图2所示，将元素2添加到HittingSet之后，此时的状态对应于表2和图3.

Fig. 2 The corresponding adjacency list about Seq in table 1图2 表1中Seq对应的邻接链表

Table 1 Value of Each Variable at the Beginning表1 初始时各变量对应的值

Table 2 Value of Each Variable When Adding 2 into HittingSet表2 将元素2加入HittingSet时各变量对应的值

Fig. 3 The corresponding adjacency list about Seq in table 2图3 表2中Seq对应的邻接链表

处理本层元素3时，发现AlreadyCover+Cover[3]=3=Cap(CS)，因此新建1个容器container存储HittingSet中的元素2，并将元素3也添加到container中，以container作为输入调用JudgeMHS，容易看出JudgeMHS返回true，因此将container加入MinHittingSet.元素4与元素3处理类似，所以当本层循环处理完毕时MinHittingSet中包含极小碰集{2,3}和{2,4}.回到上一层处理元素3，此时的状态对应于表3和图4.

Table 3 Value of Each Variable When Processing 3表3 处理元素3时各变量对应的值

Fig. 4 The corresponding adjacency list about Seq in table 3 图4 表3中 Seq对应的邻接链表

处理本层元素1与前面处理元素3和4类似，所以本层循环结束时MinHittingSet中包含极小碰集{2,3}，{2,4}和{3,1}.回到上一层处理元素1，此时的状态对应于表4和图5.

Fig. 5 The corresponding adjacency list about Seq in table 4图5 表4中Seq对应的邻接链表

处理本层元素1时发现AlreadyCover+CanCover

Table 4 Value of Each Variable When Processing 1表4 处理元素1时各变量对应的值

4 实验分析

本节对MHS-DMECV算法的性能进行实验分析.在实验对比部分，选取目前效率优良的布尔代数算法[5]作为比较对象.实验平台如下：Windows 7操作系统，CPU Intel Core i7-3770 3.4 GHz，8.00 GB RAM，Java.

本文测试用例由伪随机集合簇生成器产生，伪随机集合簇生成器输入参数包括元素个数m(m表示集合U的势)、集合簇容量n以及元素在一个集合簇元素中出现的概率p.在同一个测试用例中，所有元素的p值均相等，因此集合簇中每个元素包含元素的期望个数等于mp.对于元素个数为4、集合簇容量为3的测试用例用M4N3表示.

Fig. 6 Performance comparison of Boolean and MHS-DMECV under M15N200图6 M15N200下Boolean与MHS-DMECV性能对比图

本文用伪随机集合簇生成器生成了4类测试用例，分别为M15N200，M20N200，M25N200以及M30N200.其中每类测试用例包含10×17个用例，即每类测试用例又细分为10组，各小组均包含p取值0.15～0.94的17个测试用例.所有测试用例中集合簇容量均为200.在10组测试用例中对取相同概率p的10个测试用例进行实验，取其平均执行时间作为实验结果.

图6描述了在测试用例为M15N200时布尔代数算法与MHS-DMECV算法的性能对比图，表5是与图6对应的实验统计结果.图6中横轴表示元素在1个集合簇元素中出现的概率p；右侧纵轴表示对应实例的极小碰集数量.表5中Number ofMHSs表示在10组测试用例中对应p取值0.15～0.94时的平均极小碰集个数；Speedup Ratio是布尔代数算法与MHS-DMECV算法平均运行时间(精确到微秒)的比值，即加速比.

Table5ExperimentalStatisticalResultsofBooleanandMHS-DMECVUnderM15N200

表5 M15N200下Boolean与MHS-DMECV实验统计结果

由图6和表5可知，在极小碰集个数较少时布尔代数算法效率优于MHS-DMECV算法，这是因为MHS-DMECV算法需要遍历邻接链表以及对待处理序列中的元素排序，这两个操作的时间占比在极小碰集个数较少时会相对突出.但随着极小碰集个数的增长，MHS-DMECV算法优势逐渐显现出来，在元素出现概率p=0.5时，MHS-DMECV算法平均比布尔代数算法快5～6倍.

图7和表6对应测试用例为M20N200的情况.

由图7和表6可知，在极小碰集个数达到上千个时，MHS-DMECV算法执行时间较布尔代数算法明显降低.对比M15N200的实验结果可以看出，在随机情况下极小碰集个数与元素数m是正相关的.为了对比数据规模较大时2种算法的性能差异，图8和表7给出M25N200情况下的性能对比图和实验统计结果.

Fig. 7 Performance comparison of Boolean and MHS-DMECV under M20N200图7 M20N200下Boolean与MHS-DMECV性能对比图

Table6ExperimentalStatisticalResultsofBooleanandMHS-DMECVUnderM20N200

表6 M20N200下Boolean与MHS-DMECV实验统计结果

Fig. 8 Performance comparison of Boolean and MHS-DMECV under M25N200图8 M25N200下Boolean与MHS-DMECV性能对比图

Table7ExperimentalStatisticalResultsofBooleanandMHS-DMECVUnderM25N200

表7 M25N200下Boolean与MHS-DMECV实验统计结果

从图8和表7可知，在极小碰集个数达到上万级别时，布尔代数算法需要几十甚至上百秒才能计算出所有极小碰集，而MHS-DMECV算法在零点几秒内就得到了结果.在概率p=0.5时，MHS-DMECV算法比布尔代数算法快200倍左右.最后对比1组数据规模更大的数据，即M30N200这类测试用例，图9和表8给出M30N200情况下的性能对比图和实验统计结果.

Fig. 9 Performance comparison of Boolean and MHS-DMECV under M30N200图9 M30N200下Boolean与MHS-DMECV性能对比图

在M30N200类数据对比中，容易看出在极小碰集个数达到几十万的规模时，布尔代数算法在可容忍时间内已经失效；反观MHS-DMECV算法，即使极小碰集个数达到几十万的规模，MHS-DMECV算法也能在几秒之内得出结果.在概率p=0.5时，MHS-DMECV算法比布尔代数算法快2 000倍左右.

Table8TheExperimentalStatisticalResultsofBooleanandMHS-DMECVUnderM30N200

表8 M30N200下Boolean与MHS-DMECV实验统计结果

从上面的4类数据对比中得出，虽然在某些小数据上布尔代数算法占有优势，但随着数据规模的增大，MHS-DMECV算法具有非常优良的性能开销.综合来看，MHS-DMECV算法较布尔代数算法更具有实用价值.下面给出近年来的一些极小碰集求解算法与MHS-DMECV算法的比较.

由于冲突集合簇的极小碰集求解问题是NP难问题，因此目前国内外的算法都是试图避开无用路径的搜索.理想情况是，对于一个给定的冲突集合簇，算法搜索的每条路径上元素构成的集合直接形成一个极小碰集，即算法不需要做无用功.DMDSE-TREE算法[7]利用极大度来尽量避免非极小碰集路径的搜索，但是DMDSE-TREE算法没有引入其他较好的剪枝策略，因此效率没有较大提高.MHS-DMECV算法除了使用动态极大元素覆盖值规避掉大量无用路径的搜索之外，还引入了启发式策略和剪枝策略进一步缩小搜索空间.CSP-MHS[8]算法将极小碰集求解问题转换为约束可满足问题，并调用相应的求解器求解极小碰集.该算法具有较好的创新性，但是在转换的过程中会丢失一些可以加快极小碰集求解效率的信息，因此CSP-MHS算法能正确地解决问题，但是CSP-MHS算法在效率上有所欠缺.

5 结束语

本文提出基于动态极大元素覆盖值求取所有极小碰集的MHS-DMECV算法，求解效率较高.MHS-DMECV算法引入特定状态下元素的元素覆盖值作为启发式信息，并通过邻接链表存储元素覆盖信息完成极小碰集的求解.MHS-DMECV算法的主要优点有4个方面：

1) 使用邻接链表存储特定状态下的元素覆盖信息，对邻接链表只做简单遍历操作，因此算法效率较高，程序易于实现；

2) 将特定状态下的元素覆盖值从高到低排序，并按照这个顺序选择元素，因此能减少不必要的搜索，提高求解效率；

3) MHS-DMECV算法添加了启发式策略和剪枝策略，算法效率大幅提高；

4) 产生碰集HS时使用JudgeMHS算法判定HS是否是极小碰集，因此算法结束时能保证得到所有的极小碰集.

实验结果表明：MHS-DMECV算法性能优良，对于极小碰集求解问题有较高的求解效率.

本文提出的MHS-DMECV算法除了应用在基于模型的诊断领域外，还可以将其应用到极小覆盖集问题、智能规划和软件调试中.针对具体问题的特点，将本文方法设计为相适应的算法，在特定问题上取得更理想的效果.

[1]Reiter R. A theory of diagnosis from first principles[J]. Artificial Intelligence, 1987, 32(1): 57-96

[2]Li Lin, Lu Xianliang. An algorithm for detecting filters conflicts based on the intersection of bit vectors[J]. Journal of Computer Research and Development, 2008, 45(2): 237-245 (in Chinese)(李林, 卢显良. 一种基于位向量交集运算的规则冲突检测算法[J]. 计算机研究与发展, 2008, 45(2): 237-245)

[3]Greiner R, Smith B A, Wilkerson R W. A correction to the algorithm in Reiter’s theory of diagnosis[J]. Artificial Intelligence, 1989, 41(1): 79-88

[4]Jiang Yunfei, Lin Li. Computing the minimal hitting sets with BHS-tree[J]. Journal of Software, 2002, 13(12): 2267-2274 (in Chinese)(姜云飞, 林笠. 用对分-HS树计算最小碰集[J]. 软件学报, 2002, 13(12): 2267-2274)

[5]Jiang Yunfei, Lin Li. The computation of minimal hitting sets with Boolean formulas[J]. Chinese Journal of Computers, 2003, 26(8): 919-924 (in Chinese)(姜云飞, 林笠. 用布尔代数方法计算最小碰集[J]. 计算机学报, 2003, 26(8): 919-924 )

[6]Zhao Xiangfu, Ouyang Dantong. A method of combining SE-tree to compute all minimal hitting sets[J]. Progress in Natural Science, 2006, 16(2): 169-174

[7]Zhang Liming, Ouyang Dantong, Zeng Hailin. Computing the minimal hitting sets based on dynamic maximum degree[J]. Journal of Computer Research and Development, 2011, 48(2): 209-215 (in Chinese)(张立明, 欧阳丹彤, 曾海林. 基于动态极大度的极小碰集求解方法[J]. 计算机研究与发展, 2011, 48(2): 209-215)

[8]Wang Yiyuan, Ouyang Dantong, Zhang Liming, et al. A method of computing minimal hitting sets using CSP[J].

Journal of Computer Research and Development, 2015, 52(3): 588-595 (in Chinese)(王艺源, 欧阳丹彤, 张立明, 等. 利用CSP求解极小碰集的方法[J]. 计算机研究与发展, 2015, 52(3): 588-595)

[9]Jannach D, Schmitz T, Shchekotykhin K. Parallelized hitting set computation for model-based diagnosis[C]Proc of the 29th AAAI Conf on Artificial Intelligence. Menlo Park, CA: AAAI, 2015: 1503-1510

[10]Zhao Xiangfu, Ouyang Dantong. Deriving all minimal hitting sets based on join relation[J]. IEEE Trans on Systems, Man, and Cybernetics: Systems, 2015, 45(7): 1063-1076

DengZhaoyong, born in 1994. Master candidate at Jilin University. His main research interest is model-based diagnosis.

OuyangDantong, born in 1968. Professor and PhD supervisor of Jilin University. Senior member of CCF. Her main research interests include model-based diagnosis, model checking and automated reasoning (ouyangdantong@163.com).

GengXuena, born in 1988. PhD at Jilin University. Her main research interest is model-based diagnosis (183267037@qq.com).

LiuJie, born in 1973. Associate professor at Jilin University. Her main research interests include model-based diagnosis, model checking and Boolean satisfiability.