软件学报  2018, Vol. 29 Issue (12): 3733-3746   PDF    
极小碰集求解中候选解极小性判定方法
刘思光1,2, 欧阳丹彤1,2, 张立明1,2     
1. 吉林大学 计算机科学与技术学院, 吉林 长春 130012;
2. 符号计算与知识工程教育部重点实验室(吉林大学), 吉林 长春 130012
摘要: 极小碰集问题是人工智能中的重要问题,应用广泛.碰集极小性判定,作为极小碰集求解过程中的关键步骤,效率的高低会对极小碰集求解算法的耗时产生直接影响.现有的极小碰集求解算法主要使用子集检测方法进行碰集极小性判定.针对子集检测方法在极小碰集簇规模较大时效率较低的问题,提出了基于元素独立覆盖度检测的碰集极小性判定方法——ICC方法,剥离了碰集极小性判定耗时与极小碰集簇大小的相关性;通过深入分析增量求解过程中非极小碰集的产生原因,给出了ICC方法的增量判定形式ⅡCC方法,使其可以尽早发现并丢弃非极小候选解,为使用其增量极小碰集求解算法带来额外的剪枝效果,进一步提升算法的效率.实验结果表明:该方法易于实现,可扩展性强,对于当前效率较高的Boolean算法,使用ⅡCC方法后,算法可求解问题的规模和整体效率均有明显提升,效率提升最高达4个数量级以上.
关键词: 基于模型诊断     极小碰集     碰集极小性判定     预剪枝     增量方法    
Method of Minimality-Checking of Candidate Solution for Minimal Hitting Set Algorithm
LIU Si-Guang1,2, OUYANG Dan-Tong1,2, ZHANG Li-Ming1,2     
1. College of Computer Science and Technology, Jilin University, Changchun 130012, China;
2. Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education(Jilin University), Changchun 130012, China
Foundation item: National Natural Science Foundation of China (61133011, 61402196, 61272208, 61003101, 61170092); China Postdoctoral Science Foundation (2013M541302); Jilin Province Science and Technology Development Plan (20140520067JH); Provincial Key Disciplines Foundation of Computer Software and Theory of Zhejiang Normal University (ZSDZZZZXK12)
Abstract: Minimal hitting set (MHS) problem is an important problem with widely applications in artificial intelligence. During computing all minimal hitting set, how to check the minimality of hitting sets is a key issue. Most of exhaustive MHS algorithms ensure the minimality of results by using subset checking method where its effectiveness is mainly relevant to the scale of minimal hitting sets, i.e., the larger the scale of the MHSs is, the lower the effectiveness of this method has. Consequently, when coming to solve the massive cases, the effectiveness of these algorithms is not high. To overcome this problem, this paper proposes independent coverage checking (ICC) and then develops it into an incremental method named ⅡCC. The effectiveness of this method is irrelevant to the scale of minimal hitting sets. Moreover, when computing all MHS by the incremental MHS algorithm with ⅡCC, it can incrementally test the minimality of candidate solutions, resulting in cutting down many unnecessary non-minimal hitting sets. ⅡCC is used to optimize the Boolean algorithm which is an incremental MHS algorithm using subset checking. The results show that ⅡCC method significantly outperforms the subset checking methods in terms of running time.
Key words: model-based diagnosis     minimal hitting set     minimality-checking of hitting set     pre-pruning     incremental method    

极小碰集问题一直是人工智能领域的热点问题, 在许多理论和实际问题中有着广泛应用.如:基于模型诊断中, 候选产生阶段是通过计算所有极小冲突集的极小碰集得到极小诊断解[1]; 溯因推理问题、老师与课程问题, 以及智能规划、软件调试中的核心问题, 都可以通过转换为极小碰集问题后使用成熟的极小碰集求解算法来提高求解效率[2-4]; 极小顶点覆盖、极小集合覆盖等极小覆盖问题, 也可以视为极小碰集问题的特殊形式.

迄今为止, 国内外众多研究人员都对极小碰集的求解方法进行了研究和改进.1987年, 著名的人工智能专家Reiter完成了该领域的开创性工作, 提出了最早的极小碰集计算方法HS-Tree方法[1], 并将其应用在基于模型的诊断中.但此方法存在一些缺陷, 可能会因剪枝而丢失正确解.针对此问题, 1989年, Greiner等人对此方法进行改进后提出了HS-DAG方法[5].2001年, Wotawa提出了HS-Tree的改进算法——HST-Tree方法[6], 理论上, 很大程度地降低了极小碰集求解过程中子集检测的数量.2002年和2003年, 姜云飞等人提出了BHS-Tree[7]和布尔代数方法[8], 前者在解决了HS-Tree方法可能因剪枝而丢解问题的同时, 有效减少了生成节点的数量; 后者将问题集合簇编码为布尔表达式, 通过布尔代数计算来求解所有极小碰集, 不仅提高了求解的效率, 而且简化了数据结构. 2004年, 欧阳丹彤等人对HS-DAG方法进行了改进, 提出了New HS-Tree方法[9], 相对于HS-DAG方法, 大幅减少了搜索节点的数量.2006年, 赵相福等人提出了HSSE-Tree方法[10], 使用带有终止节点的集合枚举树, 形式化地表示了极小碰集的求解过程.近年来, 随着对极小碰集问题的深入研究, 一些新的求解方法及改进算法不断被提出[11-15].除了以上这些完备求解方法, 随着近似求解策略的不断发展, 学者们提出了许多非完备极小碰集求解方法[16-20].这些方法大多使用随机搜索策略, 对比传统的完备方法求解, 效率大幅提升, 即使对于规模很大的问题, 也能够在可接受的时间内进行求解, 但同时, 这也是以牺牲解的完备性为代价的.此外, 也有一些并行及分布式极小碰集求解算法被提出[21, 22].

碰集极小性判定作为极小碰集求解过程中的关键步骤, 其任务是保证算法最终求得问题解的极小性, 重要性不言而喻.同时, 所用判定方法效率的高低也会对极小碰集求解算法效率产生直接影响.但是, 当前对于极小碰集求解算法的研究主要集中在搜索过程的改进上, 未见专门针对碰集极小性判定方法进行优化的相关工作.

现有的极小碰集求解算法普遍采用子集检测方法来进行碰集极小性判定, 每次调用该方法, 都需要将新得到的碰集与极小碰集簇中部分甚至全部碰集进行比较.这使得一般情况下, 该方法的调用耗时往往与极小碰集簇中碰集的个数正相关.随着问题难度的增加, 算法调用子集检测方法进行碰集极小性判定的耗时会很快超过搜索耗时, 在算法总耗时中占据较大比例.若能对此进行优化改进, 降低碰集极小性判定耗时, 将会大幅提高现有算法的求解效率.针对此问题, 本文提出了一种基于元素独立覆盖度检测的碰集极小性判定方法, 剥离了碰集极小性判定耗时与极小碰集簇大小的相关性.并根据增量求解过程中非极小碰集的产生原因, 对所提方法进行优化, 使其能够快速对新产生候选解的极小性给出判定结果, 通过尽早发现并丢弃非极小候选解, 为使用其的极小碰集增量求解算法带来额外的剪枝收益.

本文将应用所提方法对当前完备求解算法中效率较高[23]的Boolean算法进行优化.通过优化前后算法对相同实例求解效率的对比实验, 对优化效果进行说明.

1 预备知识 1.1 基于模型诊断及极小碰集的相关概念

定义1[1]. 系统可定义为一个三元组(SD, COMPS, OBS), 其中,

1) SD为系统描述, 是一阶谓词公式集合;

2) COMPS是系统组成部件的集合, 是一个有限常量集;

3) OBS为观测集, 是一阶谓词公式的有限集.

定义2[1]. 称一个部件集{c1, c2, …, cn}⊆COMPS是冲突集, 当且仅当SDOBS∪{AB(c1), AB(c2), …, AB(cn)}是不一致的.其中, AB为一元谓词, 表示abnormal.AB(c)为真, 当且仅当c异常, 且cCOMPS.

称冲突集是极小冲突集(MCS)[24], 当且仅当该冲突集的任意真子集都不是冲突集.

定义3[1].F是一个集合簇, F={S1, S2, …, Sn}, 称HF的一个碰集HS, 如果H满足以下条件:

1) $H \subseteq \bigcup\limits_{{S_i} \in F} {{S_i}} $;

2) 对于任意一个SiF, 都有HSi≠∅.

F的一个碰集H为极小碰集(MHS), 当且仅当H的任意真子集都不是F的碰集.若去掉定义3中条件2的约束, 则称HF的候选解.

下面, 我们通过例1对以上提到的概念进行说明.

例1:对于集合簇F={{1, 2, 8}, {1, 2, 9}, {1, 3, 10}, {1, 3, 11}, {1, 4, 12}, {2, 13}, {2, 14}, {3, 15}, {3, 16}, {4, 17}, {4, 18}, {5, 19}, {6, 20}, {7, 21}}.{1, 2, 3, 4, 5, 6, 7}, {2, 3, 4, 5, 6, 7}及{1, 2, 3, 4}都是该集合簇的候选解, 其中, {1, 2, 3, 4, 5, 6, 7}与{2, 3, 4, 5, 6, 7}是碰集, 并且{2, 3, 4, 5, 6, 7}为极小碰集.

碰集的极小性判定, 即是对F的一个碰集H是否为该集合簇的极小碰集给出验证结果.现有的极小碰集求解算法一般是先求出碰集, 再对其极小性进行判定.对这类算法来说, 候选解的极小性判定等价于碰集的极小性验证.但就于一般情况而言, 两者存在一定差别, 极小候选解和极小碰集也是不同的概念, 具体定义将在第2.1节中给出.

1.2 基于子集检测的碰集极小性判定方法

根据定义3, 我们可以得到以下推论.

推论1.H是集合簇F的一个碰集, 若F存在碰集LLH的真子集, 则H不是F的极小碰集.

基于子集检测的碰集极小性判定方法就是根据推论1, 当极小碰集求解算法得到一个新碰集时, 将其与极小碰集簇中的碰集进行比较, 根据比较结果对极小碰集簇进行一些操作.具体过程见算法1:

算法1. Subset_Checking.

Function: Subset_Checking(H, allMHS)

Input:碰集H, 极小碰集簇allMHS={MHS1, MHS2, …, MHSn};

Output:极小碰集簇allMHS.

Begin

1. for (i=1; in; i++)

2. {

3.     if (HMHSi)

4.         allMHS.Remove(MHSi);

5.     else if (MHSiH)

6.         return;

7. }

8. allMHSallMHS∪{H};

End

在这一过程中, 若发现新得到碰集的真超集, 则说明该超级必不为集合簇的极小碰集, 将其从极小碰集簇中删去(第3行); 若发现新得到碰集的子集, 则将新得到碰集丢弃, 结束比较过程(第5行); 若比较过程结束时都未发现新得到碰集的子集, 则将该碰集暂时加入极小碰集簇中(第8行).

当极小碰集求解算法结束时, 极小碰集簇中保留的碰集即是问题集合簇的所有极小碰集.需要注意的是:在极小碰集算法运行的过程中, 极小碰集簇中保留的碰集并不一定是极小的.

这种方法存在的主要问题是:极小碰集簇的规模会随着极小碰集求解算法的进行而不断变大, 新得到碰集的极小性判定时间也不断增加.这使得当问题难度较高时, 使用此种碰集极小性判定方法的极小碰集求解算法很难在可接受的时间内进行完备求解.而本文提出的基于元素独立覆盖度的碰集极小性判定方法则不存在这种问题.

Boolean算法正是使用了本节介绍的基于子集检测的碰集极小性判定方法.使用本文所提方法改进后的Boolean算法及两种算法的比较将在第2.3节中给出.

1.3 Boolean算法简介

Boolean方法是将问题集合簇编码为布尔表达式, 然后应用给定的规则对表达式进行计算, 得到碰集, 再应用布尔代数中的吸收律得到所有极小碰集(与子集检测原理一致).具体规则和布尔表达式计算原理见文献[8], 在此不做介绍.其算法实现可以递归表示为如下过程.

算法2. Boolean.

Function: Boolean(F', E, allMHS)

Input:集合簇F', 候选解E, 极小碰集簇allMHS, 其中, F'是问题集合簇F={S1, S2, …, Sn}的子集;

Output: allMHS.

Begin

1. if (F'==∅)

2. {

3.     Subset_Checking(E, allMHS);

4.     return;

5. }

6. if (∃e({e}∈F'))

7.     Boolean({Si|SiF'∧eSi}, E∪{e}, allMHS);

8. elseif (∃eSi(SiF'→eSi))

9. {

10.     Subset_Checking(E∪{e}, allMHS);

11.     Boolean({Si|SiF'∧eSi}∪{Si-{e}|SiF'∧eSi}, E, allMHS);

12. }

13. else

14. {

15.     $e \leftarrow Select\_element\left({\bigcup\limits_{{S_i} \in F'} {{S_i}} } \right)$;

16.     Boolean({Si|SiF'∧eSi}, E∪{e}, allMHS);

17.     Boolean({Si|SiF'∧eSi}∪{Si-{e}|SiF'∧eSi}, E, allMHS);

18. }

End

首次调用该算法前需对传入参数进行如下设置.

1. F'←F;

2.将EallMHS置为空;

为叙述清晰, 我们对原Boolean方法做了一些小的改动, 如将子集检测放入了递归过程中(第3行、第10行), 但算法整体原理是保持不变的.

F'为空, 则说明参数传入的候选解E已经是碰集, 对其进行检测并返回(第1行, 也是递归出口).否则, 就需要选择元素对候选解进行扩充:若F'中含有单元素构成的集合, 则将该元素加入E中, 同时从F'中删除包含该元素的集合, 继续递归计算(第6行); 否则, 若F'中所有集合都含有某一元素e, 则说明E∪{e}是碰集, 对其进行检测, 之后从F'包含的所有集合中删去元素e, 继续递归计算(第8行); 若前两个条件都不满足, 则从F'包含的所有集合的并集中挑选一个元素, 以此将F'表示的问题分解为2个解空间不重叠的子问题, 继续递归求解(第13行).其中, 第15行挑选元素所使用的规则可以自定义.最常使用的挑选规则是选择被F'中被最多集合包含的元素, 本文的算法2和算法5都依此对元素进行选择.

2 基于元素独立覆盖度的候选解极小性判定方法

本节将首先给出极小候选解的相关概念及定义, 并提出一种基于元素独立覆盖度检测的碰集极小性判定方法.在此基础上, 深入分析增量求解过程中非极小碰集的产生原因, 指出可将极小性判定提前到候选解产生阶段, 并给出相关方法.最后, 将所提方法与Boolean方法相结合.

2.1 相关定义

设有集合簇F={S1, S2, …, Sn}, E={e1, e2, …, em}为F的候选解, 其中, ${e_k} \in \bigcup\limits_{{S_i} \in F} {{S_i}} $(1≤km).现给出如下3个定义.

定义4.ESj={ek}(1≤jn, 1≤km), 则称在E中, 元素ek独立覆盖了集合Sj.ek独立覆盖F中集合的个数, 称为该元素在候选解E中的独立覆盖度.

定义5.TE={Si|SiFESi≠∅}, 称TEE对于F的覆盖集合簇.

定义6. 若{W|WETW=TE}=∅ ,则称E为极小候选解.

对于例1中给出的集合簇F, 候选解{1, 2, 3, 4}中, 元素2~元素4的独立覆盖度都为2, 元素1的独立覆盖度为0.T{1, 2, 3, 4}={1, 2, 8}, {1, 2, 9}, {1, 3, 10}, {1, 3, 11}, {1, 4, 12}, {2, 13}, {2, 14}, {3, 15}, {3, 16}, {4, 17}, {4, 18}}.同时有候选解{2, 3, 4}, 使得T{2, 3, 4}=T{1, 2, 3, 4}成立, 且{2, 3, 4}是{1, 2, 3, 4}的真子集, 所以{1, 2, 3, 4}不为极小候选解.

下面给出定理1, 对候选解是否极小的判定条件进行说明.

定理1.E是集合簇F的候选解, E不是极小候选解的充分必要条件为:E中含有独立覆盖度为0的元素.

证明:

● 充分性:假设eE中独立覆盖度为0, 则e覆盖的集合簇必被E中其他元素覆盖, 即T{e}TE-{e}, 因此存在W=E-{e}, 使得TW=TE成立, 根据定义6, E不为极小候选解.

● 必要性(反证法):假设E中不含有独立覆盖度为0的元素.由于E不为极小候选解, 其必有真子集W使得TW=TE成立, 设eE-W, 去掉e并未改变候选解的覆盖集合簇, 因此有T{e}TE-{e}, 即, e的独立覆盖度为0.与假设矛盾, 假设不成立.

证毕.

2.2 基于元素独立覆盖度检测的候选解极小性判定方法

本节将给出一种基于元素独立覆盖度检测的候选解极小性判定方法.为方便理解以及与第1.2节中介绍的子集检测方法进行比较, 首先给出这种方法对给定碰集极小性进行判定的过程, 然后通过分析增量求解过程中非极小碰集产生的原因, 对该过程进行优化, 使其在增量求解过程中保持较高效率.

2.2.1 基于元素独立覆盖度的碰集极小性判定方法

碰集显然也是候选解, 因此由定理1, 我们可以得到一种判别给定碰集极小性的新方法:对给定碰集中所有元素的独立覆盖度进行计算, 若其中含有独立覆盖度为0的元素, 则说明该碰集不是极小碰集.下面给出这种方法的伪码表示.

算法3. ICC (independent coverage checking).

Function: ICC(H, F, allMHS)

Input:碰集H={e1, e2, …, em}, 问题集合簇F={S1, S2, …, Sn}, 极小碰集簇allMHS;

Output: allMHS.

Begin

1. for (i=1; in; i++)

2.     configuration[i]←|HSi|; //统计SiH中多少个元素覆盖

3. for (i=1; im; i++)

4. {

5.     for (j=1; jn; j++)

6.     {

7.         if (eiSjconfiguration[j]==1) //说明ei独立覆盖Sj

8.             break;

9.         if (j==n) //说ei的明独立覆盖度为0

10.             return;

11.     }

12. }

13. allMHSallMHS∪{H};

End

算法中首先对集合簇F中各集合被H中元素覆盖情况进行统计, 结果记录在数组configuration中(第1行).然后对H中各元素的独立覆盖度进行检测:若H中某一元素至少独立覆盖集合簇F中的1个集合, 则说明该元素的独立覆盖度不为0(第5行); 反之, 则说明该元素独立覆盖度为0, H不是极小碰集(第7行).若H中所有元素的独立覆盖度都不为0, 则H为极小碰集, 将其加入到中allMHS.

我们可以发现:算法3的执行过程中无需对极小碰集簇进行遍历比较, 因此其效率与极小碰集簇的大小无关.下面, 本文将通过实例分析, 指出增量求解过程中非极小碰集产生的原因, 并以此对算法3进行优化, 提出一种增量的候选解极小性判定方法.

2.2.2 增量求解过程中非极小碰集的产生原因

现有的完备方法中普遍使用增量求解, 即是按照一定规则, 将候选解中不包含的元素加入其中, 直到候选解满足一定条件再对其进行下一步操作.

现有的极小碰集增量求解算法是将条件设置为候选解成为碰集, 之后再使用子集检测方法保证最终结果的极小性.在候选解成为碰集前, 一般不对其极小性进行检测.算法中所用的优化策略, 通常也都是以通过选择适当的扩充元素, 使候选解尽快成为碰集为目的.

对于例1中给出的集合簇F, 若使用算法2介绍的Boolean方法对其所有极小碰集进行求解, 便会在求解过程中首先得到碰集{1, 2, 3, 4, 5, 6, 7}, 并将其暂时保存在极小碰集簇中(此前极小碰集簇为空, 不包含该碰集的子集).通过第2.1节中给出的实例, 我们知道{1, 2, 3, 4}并不是极小候选解, 因此{1, 2, 3, 4, 5, 6, 7}也不是极小碰集.

定理2. 在增量求解过程中, 非极小候选解的产生不滞后于碰集的产生.

证明:反证法.假设存在问题集合簇F, 在使用增量方法对其进行求解的过程中, 可得到极小碰集MHS, 并会在得到MHS后继续向其中加入元素生成非极小候选解E, 即非极小候选解的产生滞后于碰集的产生.这与增量求解规则相矛盾, 增量求解方法不会在得到一个碰集后继续向其中加入元素, 假设不成立.证毕.

而非极小候选解通过加入元素生成的碰集显然也不是极小碰集.由此可见, 增量求解过程中非极小碰集的产生原因主要有两种:(1)最后加入的元素使得候选解的极小性发生了改变; (2)该碰集是某个已产生的非极小候选解的超集.若能在极小碰集增量求解算法运行过程中尽早地对非极小候选解进行丢弃, 防止其超级的生成, 必将减少很多不必要的计算.

一种简单的方法是:将configuration数组作为候选解的一个属性保存下来, 每当有新元素加入到候选解中, 便对数组进行相应的修改, 之后再使用算法3中的第3行~第9行对当前候选解的极小性进行判定, 对于非极小候选解直接丢弃.但通过进一步分析我们会发现:加入新元素后, 并不需要重新检测候选解中所有元素的独立覆盖度, 只需要对其中一部分元素的独立覆盖度进行操作, 即可对新生成候选解的极小性给出判定结果.

2.2.3 增量求解过程中候选解极小性的判定方法

定理3. 设问题集合簇F有极小候选解E, 将某元素e加入E后得到E', F'={Si|SiFSiE中元素独立覆盖}, P={ej|ejEejSiSiF'}.当且仅当存在属于P的元素在e加入候选解E后, 其独立覆盖度变为0时, E'为非极小候选解.

也就是说, 将元素e加入极小候选解E后, 只需对原候选解中独立覆盖的集合中包含e的元素进行独立覆盖度检测(对于不能保证新加入元素独立覆盖度非0的算法, 也需要对新加入元素的独立覆盖度进行检测), 便能够对新候选解的极小性进行判定.

证明:根据定理1, 若E'为非极小候选解, 则说明有元素的独立覆盖度由于元素e的加入变为了0.同时, 根据定义4, 若一个元素的独立覆盖度发生了变化, 则说明该元素在E中独立覆盖的部分或全部集合中包含元素e.而对于那些独立覆盖的全部集合中都不包含e的元素, 独立覆盖度不会发生变化.故, 只需对独立覆盖度发生变化元素进行检测的即可确定加入元素e后候选解E'的极小性.证毕.

对于例1中给出的集合簇F, {1, 2, 3}是F的一个极小候选解.其中:元素1独立覆盖的集合簇为{{1, 4, 12}}, 独立覆盖度为1;元素2独立覆盖的集合簇为{{2, 13}, {2, 14}}, 独立覆盖度为2;元素3独立覆盖的集合簇为{{3, 15}, {3, 16}}, 独立覆盖度为2.当元素4加入此候选解时, 由于元素2、元素3各自独立覆盖的集合内不包含元素4, 这2个元素的独立覆盖度自然不会发生变化; 而{1, 4, 12}内包含元素4, 其已不被元素1独立覆盖, 需对元素1的独立覆盖度减1, 得到新的独立覆盖度为0, 此时候选解非极小.可见, 元素4的加入使得元素1的独立覆盖度变为0, 进而导致了候选解极小性的改变.算法4给出了这种方法的伪码表示以及其中使用数据结构的说明.

算法4. IICC (incremental independent-coverage-checking).

Function: IICC(E, em+1, F, CS_attribute)

Input:极小候选解E={e1, e2, …, em}, 新加入元素em+1, 问题集合簇F={S1, S2, …, Sn}, 候选解属性CS_attribute, 其包含set_coverage, independently_covered_with, element_independent_coverage这3个一维数组;

Output: trueorfalse, CS_attribute.

Begin

1. for (i=1; in; i++)

2.     if (em+1Si)

3.         if (set_coverage[i]==0)

4.         {

5.             independently_covered_with[i]←m+1;

6.             set_coverage[i]←1;

7.             element_independent_coverage[m+1]++;

8.         }

9.         else if (set_coverage[i]==1)

10.         {

11.             set_coverage[i]←2;

12.             element_independent_coverage[independently_covered_with[i]]--;

13.             if (element_independent_coverage[independently_covered_with[i]]==0)

14.                 return false;

15.         }

16. return true;

End

首先对算法4中使用的一个新数据结构——候选解属性CS_attribute进行说明.其包含3个一维数组, 分别是set_coverage, independently_covered_with以及element_independent_coverage.set_coverage[i]用来记录集合Si被候选解E中的元素覆盖的情况, 为0表示未被覆盖, 为1表示被独立覆盖, 为2表示被多次覆盖.若set_ coverage[i]为1, 则independently_covered_with[i]记录了候选解E中哪个元素独立覆盖了Si, 比如:set_coverage[i]为1的同时independently_covered_with[i]的值为j, 表示Si被元素ej独立覆盖.element_independent_coverage[j]则表示在候选解E中, 元素ej独立覆盖集合簇F中集合的个数, 即ej的独立覆盖度.

算法4在运行过程中, 会根据set_coverage[i]中记录的不同分别进行如下操作:若此前Si未被E中的元素覆盖(第3行), 则将其记录为被em+1独立覆盖(第5行、第6行), 同时, 将em+1的独立覆盖度加1(第7行); 若SiE中元素ej独立覆盖(第9行), 则加入em+1后, Si不被E中任何元素独立覆盖(第11行), 需将ej的独立覆盖度减1(第12行), 此过程中如果发现ej的独立覆盖度变为0(第13行), 则说明在E中加入元素em+1形成的新候选解非极小, 直接返回.

在极小碰集增量求解过程中使用算法4给出的IICC方法, 会在每次对候选解进行扩充时, 都对其加入新元素后的极小性进行快速判定, 以期尽快发现并丢弃非极小候选解, 减少非极小碰集的生成.

从算法4中我们不难看出:IICC算法对一个极小碰集中某个元素进行独立覆盖度检测的上限为在其之后加入该候选解的元素个数, 对于包含n个元素的极小碰集就是(n-1)n/2.其只与自身有关, 与整个解集的结构无关.而对于子集检测方法而言, 当一个碰集产生时, 需要将其与当前解集中所有碰集进行比较, 最坏情况下的比较次数是整个解集的大小.通常情况下, 后者都要比前者高出数个数量级.

在随后的第2.3节中, 会给出结合IICC的Boolean方法, 并通过实例对比说明优化效果.

2.3 结合元素独立覆盖度检测的Boolean算法

算法5. BWIICC (Boolean with IICC).

Function: BWIICC(F, F', E, e', CS_attribute, allMHS)

Input: 原始问题集合簇F={S1, S2, …, Sn}, 中间过程集合簇F', 候选解E, 新加入元素e', 候选解属性CS_ attribute, 极小碰集簇allMHS, 其中, F'是F的子集;

Output: allMHS.

Begin

1. if (e'≠NULL)

2. {

3.     if (IICC(E, e', F, CS_attribute)==false)

4.         return;

5.     else

6.         EE∪{e'};

7. }

8. if (F==∅)

9. {

10.     allMHSallMHS∪{E};

11.     return;

12. }

13. if (∃e({e}∈F'))

14.     BWIICC(F, {Si|SiF'∧eSi}, E, e, CS_attribute, allMHS);

15. elseif (∃eSi(SiF'→eSi))

16. {

17.     BWIICC(F, {Si|SiF'∧eSi}∪{Si-{e}|SiF'∧eSi}, E, NULL, CS_attribute, allMHS);

18. if (IICC(E, e, F, CS_attribute)==false)

19.     return;

20.     else

21.     allMHSallMHS∪{E∪{e}};

22. }

23. else

24. {

25.     $e \leftarrow Select\_element\left({\bigcup\limits_{{S_i} \in F'} {{S_i}} } \right)$;

26.     BWIICC(F, {Si|SiF'∧eSi}, E, e, CS_attribute, allMHS);

27.     BWIICC(F, {Si|SiF'∧eSi}∪{Si-{e}|SiF'∧eSi}, E, NULL, CS_attribute, allMHS);

28. }

End

首次调用该算法前需对传入参数进行如下设置.

1. F'←F;

2.将EallMHS置为空;

3.将e'置为NULL;

4.将CS_attribute中各数组所有位都置为0;

该算法与算法2的主要不同在于:算法5每次对候选解E进行扩充前, 都会对扩充后新候选解的极小性进行检测(第2行、第16行), 以此保证算法执行过程中只生成极小候选解.这样做不仅剥离了碰集极小性判定耗时与极小碰集簇大小间的关系, 使得在极小碰集簇较大时算法仍能以较高的效率对候选解的极小性进行判定, 而且由于IICC方法能够及早地发现非极小候选解并将其丢弃, 也为算法5提供了额外的剪枝效果.

下面通过图 1给出在对例1集合簇F的极小碰集进行求解过程中, 算法2和算法5对部分候选解空间访问情况的对比.

Fig. 1 Visit-Situation-Comparison of the two methods forpart of candidate-solution-spaceinexample one 图 1 2种方法对例1部分候选解空间的访问情况比较

图 1中, 各节点表示会被访问到的候选解, 边表示自上而下新加入候选解的元素.图 1(a)为算法2访问的部分候选解空间, 图 1(b)是算法5对于相同空间的访问情况.算法5在发现{1, 2, 3, 4}不是极小候选解后, 会立将其丢弃, 停止对其超集的访问; 而算法2会继续向其中添加元素, 直到其成为碰集.但图 1所示的候选解空间实际上是没有极小碰集产生的, 对于类似情况, 算法5提前剪枝所带来的收益是显而易见的.

由于BWIICC方法在搜索阶段仍使用Boolean方法的规则对节点进行扩充, 只有在节点所代表的候选解非极小时才会停止对当前结点的继续扩充而返回上一层, 因此, BWIICC方法在整个求解过程中所遍历的全部节点是Boolean方法的子集, 其正确性由Boolean方法保证.同时, 由于非极小候选解的超集不可能是极小碰集, 因此对比Boolean方法, 使用IICC的BWIICC方法所剪枝掉的节点中不可能包含极小碰集, 即, 使用IICC后, Boolean方法的完备性不会被破坏.

在第3节中, 我们将会以多组实验数据对比的方式, 分析说明算法5相较于算法2的优势.

3 实验分析

首先, 将使用算法5给出的BWIICC方法与算法2介绍的Boolean方法进行比较, 给出两种方法在随机生成测试用例下的实验结果.然后, 会单独使用BWIICC方法对另外几组难度较高的测试用例进行求解, 以测试这种方法对较难问题的求解能力.

实验平台如下:Windows 10操作系统, CPU Intel Core i5-3470 3.2Ghz, 8.00GB RAM, C++.

实验所用测试用例为随机生成器产生, 输入参数有元素个数m, 集合簇中集合个数n, 以及元素在一个集合中出现的概率p.同一个用例中, 所有元素的p均相等, 每个集合包含元素的平均个数约等于mp.本文使用的实验用例共8小组, 分为对比组和较难问题组两部分.每小组元素个数固定, 对比组分别为15, 20, 25, 30, 较难问题组分别为35, 40, 45, 50, 各小组均包含p取值0.05~0.94的19个用例, 所有用例集合簇中集合个数均为200.本文所有实验数据均为使用相同参数下独立生成的10个用例进行实验, 所得结果的平均值.

图 2给出了两种方法对于对比组中所有实验用例运行时间的对比情况.

Fig. 2 Experimental comparisons of BWIICC and Boolean 图 2 BWIICC方法与Boolean方法实验结果比较

我们可以看出:对于耗时较少的用例, 两种方法所用时间十分接近, 用例点基本都落在1倍对比线附近; 但随着用例耗时的上升, BWIICC方法的优势逐步显现; 尤其对于那些Boolean方法耗时在1s以上的用例, 多数用例点已经处于102倍对比线上方, 部分耗时较高的用例点甚至位于104倍对比线之上.接下来, 我们将会通过实验数据的分组比较, 进一步分析产生这种现象的原因.

图 3是将两种方法的实验数据按用例元素数分组后得到的结果, 其中, 各子图的横坐标轴表示元素出现的概率p, MHS表示对应实例的极小碰集数量, 与右侧纵轴相关.从图中我们可以看出:各子图中, 对于大多数测试用例, 产生极小碰集的数量越多, 两种方法在时间效率上的差距也就越大; 而对于产生极小碰集较少的用例, 差距则并不明显.这主要是由于Boolean算法中使用的子集检测方法对极小碰集簇的大小较为敏感导致.同时, 产生极小碰集的数量越多, 一般也意味着用例的难度较高, 算法耗时也会相应增加, 这与图 2中体现的趋势是一致的.除此之外我们还可以发现, 各子图中Boolean与MHS两条折线图拟合的并不是很好.这说明对元素个数相同的一组用例, 出现概率p的不同会导致Boolean算法对于单一极小碰集的平均求解时间产生较大波动.

Fig. 3 Experimental comparisons of the two methods based on diverse number of elements 图 3 不同元素数实例分组下2种方法实验结果比较

图 4为两种方法对于各实例求解过程中访问总分支数情况的对比.分支数即是在形同图 1的树形表示下, 算法访问总节点对应的二叉树中所包含叶节点数量.其中, 各子图横坐标轴表示含义与图 3一致, 纵坐标轴表示算法对于各实例求解过程中访问总分支数与该实例解中实际包含的极小碰集数的比值.以此, 我们可以直观地看出使用IICC为BWIICC所带来的剪枝收益以及两种方法实际访问总分支数与理论下界(极小碰集数)的比较情况.同样是对于较难的实例, IICC所带来的剪枝效果更加明显.同时我们还能发现:虽然对于各组实例, BWIICC访问的总分支数都明显少于Boolean, 但两者间的差距并没有图 3中体现出的时间差那样巨大.这说明除去剪枝收益, IICC方法在候选解极小性判定上为使用其的BWIICC算法带来了更为巨大的时间效率收益.

Fig. 4 Experimental comparisons of the number of visited branches of the two methods 图 4 两种方法访问分支数对比

图 5给出了BWIICC方法对于较难问题组测试用例的实验结果, 其中, 各坐标轴表示含义与图 3中一致.

Fig. 5 Experimental data of BWIICC for the difficult problems based on diverse number of elements 图 5 BWIICC方法对于较难问题组实例的实验数据

图 5(a)中我们可以看到, 算法对其中难度较高的测试用例求得的极小碰集数已达到1.8×106个以上.而随着元素数的增加, 图 5(d)中难度最高测试用例产生的极小碰集数更是超过6×108个.但BWIICC方法仍可以将求解时间控制在3000s以内, 可见, BWIICC方法对于较高难度的问题也有着不错的求解效率.

同时, 对比图 3各子图中Boolean与MHS折线图的拟合情况, 图 5中BWIICC与MHS折线图的拟合度显然更高.这说明对于含有相同元素个数但出现概率p不同的一组用例, BWIICC方法的单一极小碰集平均求解时间较Boolean方法更为稳定, 随问题难度的波动幅度更小.

通过以上实验对比分析, 我们得到以下结论:使用IICC的BWIICC方法相较使用子集检测的Boolean方法, 求解效率有着显著的提升; 同时, 对于不同难度实例的单一极小碰集平均求解时间, BWIICC方法也更为稳定.

4 结束语

极小碰集问题在许多重要领域都有着广泛的应用, 现有的极小碰集算法主要通过使用子集检测方法来保证最终求得碰集的极小性, 但这种方法的效率会受到极小碰集簇大小影响, 极小碰集簇中碰集越多, 子集检测的耗时也就越高.对此, 本文首先提出了基于元素独立覆盖度检测的碰集极小性判定方法ICC, 剥离了碰集极小性判定效率与极小碰集簇大小的相关性.随后, 对增量求解过程中非极小碰集的产生原因进行了深入分析, 并以此对ICC方法进行优化, 得到IICC方法.该方法可以增量地对候选解的极小性给出判定结果, 在提升碰集极小性判定效率的同时, 还能够通过尽早发现并丢弃非极小候选解而获得额外的剪枝效果, 进一步提升了极小碰集求解算法整体的执行效率.最后, 将IICC方法与当前求解效率较高的Boolean算法相结合, 得到BWIICC算法, 并通过实验对比检测优化效果.实验结果表明:优化后的BWIICC算法相较于Boolean算法, 整体效率提升明显, 且优化效果有随问题难度上升而上升的趋势.对于对比组中难度最高的实例, 效率提升可达4个数量级以上.同时, 通过对较难问题组实例的测试, 显示出BWIICC算法在问题难度较高时, 依然可以保持不错的求解效率.此外, 对于单一极小碰集的平均求解时间, BWIICC算法也更为稳定.

致谢 本文作者对所有匿名审稿人的辛勤工作和宝贵意见表示真诚的感谢.
参考文献
[1]
Reiter R. A theory of diagnosis from first principles. Artificial Intelligence, 1987, 32(1): 57-95. http://d.old.wanfangdata.com.cn/NSTLQK/10.1016-0004-3702(94)90019-1/
[2]
Yu Q, Li CQ, Shen YM, Wang J. Method of solving abductive reasoning problem via hitting set. Ruan Jian Xue Bao/Journal of Software, 2015, 26(8): 1937-1945(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/4694.htm [doi:10.13328/j.cnki.jos.004694]
[3]
Bonet B, Helmert M. Strengthening landmark heuristics via hitting sets. In: Proc. of the 19th European Conf. on Artificial Intelligence. Amsterdam: IOS Press, 2010. 329-334.
[4]
Wotawa F. On the relationship between model-based debugging and program slicing. Artificial Intelligence, 2002, 135(1): 125-143. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=0913add187c7ac0289cf30974fa128b9
[5]
Greiner R, Smith BA, Wilkerson RW. A correction to the algorithm in Reiter's theory of diagnosis. Artificial Intelligence, 1989, 41(1): 79-88. http://dl.acm.org/citation.cfm?id=74707
[6]
Wotawa F. A variant of Reiter's hitting-set algorithm. Information Processing Letters, 2001, 79(1): 45-51. [doi:10.1016/S0020-0190(00)00166-6]
[7]
Jiang YF, Lin L. Computing the minimal hitting set with binary HS-tree. Ruan Jian Xue Bao/Journal of Software, 2002, 13(12): 2267-2274(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/13/2267.htm
[8]
Jiang YF, Lin L. The computation of hitting sets with Boolean formulas. Chinese Journal of Computers, 2003, 26(8): 919-924(in Chinese with English abstract). [doi:10.3321/j.issn:0254-4164.2003.08.004]
[9]
Ouyang DT, Ouyang JH, Cheng XC, Liu J. A method of computing hitting set in model-based diagnosis. Chinese Journal of Science Instrument, 2004, 25(4): 605-608(in Chinese with English abstract). http://d.old.wanfangdata.com.cn/Periodical/yqyb2004z3186
[10]
Zhao XF, Ouyang DT. A method of combing SE-tree to compute all minimal hitting sets. Progress in Natural Science, 2006, 16(2): 169-174. [doi:10.1080/10020070612331343209]
[11]
Chen XM, Meng XF, Qiao RX. Method of computing all minimal hitting set based on BNB-HSSE. Chinese Journal of Science Instrument, 2010, 31(1): 61-67(in Chinese with English abstract). http://d.old.wanfangdata.com.cn/Periodical/yqyb201001011
[12]
Zhang LM, Ouyang DT, Zeng HL. Computing the minimal hitting set based on dynamic maximum degree. Journal of Computer Reach and Development, 2011, 48(2): 209-215(in Chinese with English abstract). http://d.old.wanfangdata.com.cn/Periodical/jsjyjyfz201102005
[13]
Pill I, Quaritsch T. Optimizations for the Boolean approach to computing minimal hitting sets. In: Proc. of the 20th European Conf. on Artificial Intelligence. Amsterdam: IOS Press, 2012. 648-653. http://dl.acm.org/citation.cfm?id=3007451
[14]
Pill I, Quaritsch T. RC-Tree: A variant avoiding all the redundancy in Reiter's minimal hitting set algorithm. In: Proc. of the 2015 IEEE Int'l Symp. on Software Reliability Engineering Workshops. 2015. 78-84. http://dl.acm.org/citation.cfm?id=2922936
[15]
Wang YY, Ouyang DT, Zhang LM, Zhang YG. A method of computing minimal hitting sets using CSP. Journal of Computer Reach and Development, 2015, 52(3): 588-595(in Chinese with English abstract). http://d.old.wanfangdata.com.cn/Periodical/jsjyjyfz201503005
[16]
Lin L, Jiang YF. Computing minimal hitting sets with genetic algorithm. In: Proc. of the 13th Int'l Workshop on Principles of Diagnosis. 2002. 77-80.
[17]
Cincotti A, Cutello V, Pappalardo F. An ant-algorithm for the weighted minimum hitting set problem. In: Proc. of the 2003 IEEE Symp. on Swarm Intelligence. Piscataway: IEEE, 2003. 1-5.
[18]
Huang J, Chen L, Zou P. Computing minimal diagnosis by compounded genetic and simulated annealing algorithm. Ruan Jian Xue Bao/Journal of Software, 2004, 15(9): 1345-1350(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/15/1345.htm
[19]
Abreu R, Gemund AJCV. A low-cost approximate minimal hitting set algorithm and its application to model-based diagnosis. In: Proc. of the 8th Symp. on Abstraction, Reformulation, and Approximation, Vol.9. Menlo Park: AAAI, 2009. 2-9.
[20]
Zhou G, Feng WQ, Jiang BF, et al. Computing minimal hitting set based on immune genetic algorithm. Int'l Journal of Modelling, Identification and Control, 2014, 21(1): 93-100. [doi:10.1504/IJMIC.2014.059397]
[21]
Jannach D, Schmitz T, Shchekotykhin K. Parallelized hitting set computation for model-based diagnosis. In: Proc. of the 29th AAAI Conf. on Artificial Intelligence. Menlo Park: AAAI, 2015. 1503-1510. http://dl.acm.org/citation.cfm?id=2886529
[22]
Zhao XF, Ouyang DT. Deriving all minimal hitting sets based on join relation. IEEE Trans. on Systems, Man, and Cybernetics:Systems, 2015, 45(7): 1063-1076. [doi:10.1109/TSMC.2015.2400423]
[23]
Pill I, Quaritsch T, Wotawa F. From conflicts to diagnoses: An empirical evaluation of minimal hitting set algorithms. In: Proc. of the 22nd Int'l Workshop on the Principles of Diagnosis. 2011. 203-210.
[24]
Han B, Lee SJ. Deriving minimal conflict sets by CS-tree with mark set in diagnosis from first principles. IEEE Trans. on Systems, Man, and Cybernetics:Cybernetics, 1999, 29(2): 281-286. [doi:10.1109/3477.752801]
[2]
余泉, 李承乾, 申宇铭, 王驹. 溯因推理问题的碰集求解方法. 软件学报, 2015, 26(8): 1937-1945. http://www.jos.org.cn/1000-9825/4694.htm [doi:10.13328/j.cnki.jos.004694]
[7]
姜云飞, 林笠. 用对分HS-树计算最小碰集. 软件学报, 2002, 13(12): 2267-2274. http://www.jos.org.cn/1000-9825/13/2267.htm
[8]
姜云飞, 林笠. 用布尔代数方法计算最小碰集. 计算机学报, 2003, 26(8): 919-924. [doi:10.3321/j.issn:0254-4164.2003.08.004]
[9]
欧阳丹彤, 欧阳继红, 程晓春, 刘杰. 基于模型诊断中计算碰集的方法. 仪器仪表学报, 2004, 25(4): 605-608. http://d.old.wanfangdata.com.cn/Periodical/yqyb2004z3186
[11]
陈晓梅, 孟晓风, 乔仁晓. 基于BNB-HSSE计算全体碰集的方法. 仪器仪表学报, 2010, 31(1): 61-67. http://d.old.wanfangdata.com.cn/Periodical/yqyb201001011
[12]
张立明, 欧阳丹彤, 曾海林. 基于动态极大度的极小碰集求解方法. 计算机研究与发展, 2011, 48(2): 209-215. http://d.old.wanfangdata.com.cn/Periodical/jsjyjyfz201102005
[15]
王艺源, 欧阳丹彤, 张立明, 张永刚. 利用CSP求解极小碰集的方法. 计算机研究与发展, 2015, 52(3): 588-595. http://d.old.wanfangdata.com.cn/Periodical/jsjyjyfz201503005
[18]
黄杰, 陈琳, 邹鹏. 一种求解极小诊断的遗传模拟退火算法. 软件学报, 2004, 15(9): 1345-1350. http://www.jos.org.cn/1000-9825/15/1345.htm