鄧召勇 歐陽(yáng)丹彤 耿雪娜 劉 杰

(吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 長(zhǎng)春 130012) (符號(hào)計(jì)算與知識(shí)工程教育部重點(diǎn)實(shí)驗(yàn)室(吉林大學(xué)) 長(zhǎng)春 130012) (dengzy19941019@163.com)

極小碰集的應(yīng)用領(lǐng)域廣泛，很多現(xiàn)實(shí)和理論中的問題都可以轉(zhuǎn)化為求解極小碰集問題，例如基于模型診斷(model-based diagnosis, MBD)[1]中極小診斷問題、極小覆蓋集問題以及規(guī)則沖突檢測(cè)算法中位向量的碰集問題[2]等.基于模型診斷是人工智能領(lǐng)域里一個(gè)非常重要的研究分支，它的主要工作原理是根據(jù)系統(tǒng)的描述和觀測(cè)進(jìn)行邏輯推理得到?jīng)_突部件集合，再通過沖突部件集合計(jì)算極小碰集，即得到診斷結(jié)果.

迄今為止，國(guó)內(nèi)外學(xué)者已對(duì)極小碰集求解算法進(jìn)行了許多研究和優(yōu)化.最經(jīng)典的計(jì)算極小碰集的算法是1987年由人工智能專家Reiter[1]提出的HS-TREE算法，該算法在求解過程中加入了剪枝策略和關(guān)閉策略.HS-TREE算法的缺點(diǎn)是空間復(fù)雜度呈指數(shù)級(jí)增長(zhǎng)、產(chǎn)生節(jié)點(diǎn)多、效率低，并且會(huì)因?yàn)榧糁Σ呗詫?dǎo)致求得的極小碰集不完備.為了保證極小碰集求解算法的完備性，Greiner等人[3]于1989年提出了HS-DAG算法.HS-DAG算法在HS-TREE算法的基礎(chǔ)上優(yōu)化了剪枝策略，避免了剪掉正確解的情況，但是HS-DAG算法的模型結(jié)構(gòu)比較復(fù)雜，空間復(fù)雜度高，計(jì)算過程較為繁瑣.針對(duì)這些缺點(diǎn)，姜云飛和林笠[4]于2002年提出了BHS-TREE算法，該算法無(wú)需剪枝，求解效率有明顯提高，但由于是樹形結(jié)構(gòu)，導(dǎo)致該算法在編程實(shí)現(xiàn)時(shí)存在數(shù)據(jù)結(jié)構(gòu)復(fù)雜、不易實(shí)現(xiàn)等缺點(diǎn).近年來(lái)，國(guó)內(nèi)學(xué)者陸續(xù)提出了一些串行極小碰集求解算法：2003年姜云飛和林笠[5]提出Boolean算法；2006年和2011年歐陽(yáng)丹彤等人提出HSSE-TREE[6]和DMDSE-TREE[7]算法；2015年王藝源等人[8]提出CSP-MHS算法.此外，近年來(lái)也有一些并行及分布式[9-10]極小碰集求解算法被提出，并行及分布式極小碰集求解算法利用多核和多處理器的優(yōu)勢(shì)提高極小碰集求解效率.并行及分布式極小碰集求解算法相對(duì)串行極小碰集求解算法效率有了較大提高，但是串行算法經(jīng)過相應(yīng)修改可以轉(zhuǎn)變?yōu)椴⑿屑胺植际剿惴?，因此本文主要關(guān)注串行極小碰集求解算法.串行極小碰集求解算法中效率較為突出的算法是Boolean算法，Boolean算法用布爾代數(shù)變量表示待診斷系統(tǒng)的部件，并用布爾代數(shù)知識(shí)計(jì)算極小碰集.目前來(lái)看，在布爾代數(shù)算法之后提出的串行算法雖然在某些集合簇上有較高的效率，但綜合來(lái)看，仍是布爾代數(shù)算法占優(yōu).

布爾代數(shù)算法是目前求解極小碰集效率優(yōu)良的算法，然而當(dāng)系統(tǒng)很大時(shí)，碰集的極小化過程會(huì)花費(fèi)較多時(shí)間，因此不適用于規(guī)模較大的系統(tǒng).本文針對(duì)布爾代數(shù)算法的缺點(diǎn)，引入特定狀態(tài)下元素的元素覆蓋值作為啟發(fā)式信息，提出了一種基于動(dòng)態(tài)極大元素覆蓋值求解極小碰集的新算法MHS-DMECV.本文中元素覆蓋值的概念類似于2011年歐陽(yáng)丹彤等人[7]提出的DMDSE-TREE算法中的度，且MHS-DMECV算法和DMDSE-TREE算法都優(yōu)先選取覆蓋集合簇中元素最多的元素作為碰集的1個(gè)元素，但是本文中的元素覆蓋值簡(jiǎn)化了度的定義且MHS-DMECV算法在選取元素時(shí)添加了啟發(fā)式策略和剪枝策略.MHS-DMECV算法的主要優(yōu)點(diǎn)是：

1) 按照元素的元素覆蓋值由大到小的順序選取元素，選取的元素構(gòu)成的集合S若能構(gòu)成碰集，則S是最快構(gòu)成碰集的元素集合，否則直接返回對(duì)當(dāng)前元素的處理.

2) 求解過程中添加啟發(fā)式策略和剪枝策略，使得搜索空間極大減少，且剪枝策略不會(huì)丟失極小碰集.

3) 使用鄰接鏈表存儲(chǔ)輸入的集合簇，鄰接鏈表結(jié)構(gòu)能快速找到元素能夠覆蓋的集合簇中的元素.

4) MHS-DMECV算法只對(duì)鄰接鏈表進(jìn)行簡(jiǎn)單遍歷，因此程序容易實(shí)現(xiàn).

5) MHS-DMECV算法結(jié)束時(shí)能保證求得所有的極小碰集.

1 背景知識(shí)

本節(jié)介紹碰集(hitting set,HS) 的相關(guān)定義和概念，并給出一個(gè)實(shí)例說(shuō)明碰集、極小碰集、容量、勢(shì)以及頻數(shù)的具體含義.

集合簇CS的一個(gè)碰集是極小碰集(MHS)當(dāng)且僅當(dāng)它的任意真子集都不是CS的碰集.

定義2. 容量.若集合簇CS中包含元素的個(gè)數(shù)為n，則稱n為集合簇CS的容量，記為Cap(CS)=n.

設(shè)U是集合簇CS中所有元素的并集構(gòu)成的集合，即U=∪Si={e1,e2,…,em}，用Car(U)表示集合U的勢(shì)，即集合U中元素的個(gè)數(shù).

定義3. 頻數(shù).若e∈S，則稱集合S含有元素e，記Freq(CS,e) 表示集合簇CS中含有元素e的元素的個(gè)數(shù)，稱為元素e在集合簇CS中的頻數(shù).

例1. 設(shè)集合簇CS={{1,2},{2,3},{3,4}}，則集合簇CS的容量Cap(CS)=3；集合U={1,2,3,4}的勢(shì)Car(U)=4；容易看出集合{2,3}構(gòu)成集合簇CS的一個(gè)碰集，并且它還是極小碰集.若選取元素e=2，則元素2在集合簇CS中的頻數(shù)Freq(CS,2)=2，因?yàn)樵?出現(xiàn)在集合簇CS的元素{1,2}和{2,3}中.

2 極小碰集求解算法

本節(jié)首先給出元素覆蓋值、已覆蓋數(shù)和可覆蓋數(shù)等概念，然后詳細(xì)描述算法JudgeMHS和MHS-DMECV.

2.1 相關(guān)定義及定理

本節(jié)給出元素覆蓋值、待處理序列、已覆蓋數(shù)和可覆蓋數(shù)的定義，并基于啟發(fā)式策略、剪枝策略和極小碰集判定規(guī)則給出3個(gè)定理.

定義4. 元素覆蓋值.若元素e在集合簇CS的某個(gè)元素Si(i=1,2,…,n)中出現(xiàn)，且在當(dāng)前狀態(tài)下Si中沒有其他元素出現(xiàn)，則稱元素e覆蓋Si；若對(duì)于集合簇CS中的所有元素，元素e能覆蓋的元素個(gè)數(shù)為C，則稱C為元素e的元素覆蓋值，記為Cover(e).顯然 0≤Cover(e)≤Freq(CS,e) .

例2. 對(duì)于集合簇CS={{1,2},{2,3},{3,4}}，若首先選擇元素1，則它能覆蓋集合{1,2}，所以Cover(1)=1；此時(shí)再選擇元素2，由于集合{1,2}已被覆蓋，所以元素2只能覆蓋集合{2,3}，因此Cover(2)=1；對(duì)于元素3，由于集合{2,3}已被覆蓋，所以元素3只能覆蓋集合{3,4}，因此Cover(3)=1；對(duì)于元素4，由于集合簇CS中的所有元素都已被覆蓋，因此Cover(4)=0.

定義5. 待處理序列.在當(dāng)前狀態(tài)下，待處理的元素集合為Pend={ei,ei+1,…,ej-1,ej}，計(jì)算出Pend集合中所有元素的元素覆蓋值Cover(ek)(k=i,i+1,…,j-1,j)，并按照元素覆蓋值從大到小的順序排列，此時(shí)得到的序列稱為待處理序列，記為Seq.

例3. 對(duì)于集合簇CS={{1,2},{2,3},{3,4}}，初始時(shí)沒有選中任何元素，則Cover(1)=1，此時(shí)恢復(fù)到初始狀態(tài)，即沒有選中元素1時(shí)的狀態(tài).此后每計(jì)算出一個(gè)元素e的元素覆蓋值，都將元素e造成的影響進(jìn)行恢復(fù)，所以Cover(2)=2，Cover(3)=2和Cover(4)=1，因此待處理序列Seq=[2,3,1,4](為了描述方便，假設(shè)具有相同元素覆蓋值的元素按照元素本身的大小從小到大排序).

定義6. 已覆蓋數(shù)和可覆蓋數(shù).在當(dāng)前狀態(tài)下，如果集合簇CS中已被覆蓋的元素個(gè)數(shù)為AlreadyCover，則稱AlreadyCover為已覆蓋數(shù).對(duì)于待處理序列Seq，Seq能覆蓋的集合簇CS中元素總數(shù)為CanCover，則稱CanCover為可覆蓋數(shù).

例4. 對(duì)于集合簇CS={{1,2},{2,3},{3,4}}，假設(shè)已經(jīng)選取元素2作為碰集HS的一個(gè)元素，且HS中沒有選取其他元素，即HS={2}.則在當(dāng)前狀態(tài)state下，集合簇CS中的元素{1,2}和{2,3}已被元素2覆蓋，所以已覆蓋數(shù)AlreadyCover=2；基于當(dāng)前狀態(tài)state，計(jì)算出待處理元素集合Pend={1,3,4}中每個(gè)元素的元素覆蓋值為Cover(1)=0，Cover(3)=1和Cover(4)=1(在計(jì)算完某一個(gè)元素e的元素覆蓋值后，都將該元素e造成的影響恢復(fù)，使其回到當(dāng)前狀態(tài)state).注意到在當(dāng)前狀態(tài)state下集合簇CS中只有一個(gè)元素{3,4}能被覆蓋，且{3,4}可以被元素3或元素4覆蓋，所以可覆蓋數(shù)CanCover=1.此時(shí)新的待處理序列Seq′=[3,4,1].

定理1. 對(duì)于當(dāng)前狀態(tài)state，若已知已覆蓋數(shù)AlreadyCover和可覆蓋數(shù)CanCover，且Already-Cover+CanCover

證明.

1) 必要性.

假設(shè)NewPend表示新的待處理序列Seq′中所有元素構(gòu)成的集合，S=Before∪NewPend.由于已覆蓋數(shù)AlreadyCover和可覆蓋數(shù)CanCover的和小于集合簇CS的容量，因此?S′∈CS，Before∩S′=? 且NewPend∩S′=?，從而S∩S′=?，由碰集定義可知S不構(gòu)成碰集.又因?yàn)镹ewPend表示新的待處理序列Seq′中所有元素構(gòu)成的集合，因此對(duì)于NewPend的任意子集Su?NewPend，S=Before∪Su也一定不能構(gòu)成碰集，必要性得證.

2) 充分性.

假設(shè)NewPend表示新的待處理序列Seq′中所有元素構(gòu)成的集合，S=Before∪NewPend.由于S不構(gòu)成碰集，因此 ?S′∈CS，S∩S′=?.將S=Before∪NewPend代入得(Before∩S′)∪(NewPend∩S′)=?，即在預(yù)先選擇的元素集合Before以及新的待處理序列Seq′中不存在元素e使得e能夠覆蓋集合S′，所以已覆蓋數(shù)AlreadyCover與可覆蓋數(shù)CanCover的和一定小于集合簇CS的容量，即AlreadyCover+CanCover

證畢.

基于定理1和相關(guān)定義給出啟發(fā)式策略和剪枝策略.

1) 啟發(fā)式策略.對(duì)于當(dāng)前狀態(tài)state，若已知已覆蓋數(shù)AlreadyCover和可覆蓋數(shù)CanCover，且AlreadyCover+CanCover

2) 剪枝策略.對(duì)于待處理序列Seq=[ei,ei+1,…,ej-1,ej]，從前往后掃描Seq時(shí)發(fā)現(xiàn)位置k處元素ek的元素覆蓋值Cover(ek)=0，則只需考慮位置k之前的序列Seq1=[ei,ei+1, …,ek-1](如果Seq中不存在位置k使得Cover(ek)=0，那么Seq1就指Seq).

定理2. 對(duì)于求解集合簇CS的極小碰集問題，剪枝策略不會(huì)導(dǎo)致丟解.

證明. 從前往后掃描待處理序列Seq的過程中，如果發(fā)現(xiàn)某個(gè)位置k使得該位置處元素ek的元素覆蓋值Cover(ek)=0，由于待處理序列Seq是按照元素覆蓋值Cover(e)從大到小的順序排列，且Cover(e)≥0，因此位置k及其之后位置對(duì)應(yīng)的元素et(t=k,k+1,…,j-1,j) 的元素覆蓋值Cover(et)=0.由元素覆蓋值的定義知，元素et對(duì)覆蓋集合簇CS中的元素不再有幫助，且極小碰集的定義要求極小碰集MHS中的任意1個(gè)元素e′∈MHS都是不可取代的.e′至少能覆蓋集合簇CS中的1個(gè)元素S∈CS，且極小碰集中的其他元素都不能覆蓋S，因此去除Seq中位置k及其之后位置對(duì)應(yīng)的元素對(duì)于計(jì)算極小碰集并不會(huì)導(dǎo)致丟解，也即可以用Seq1代替Seq參與運(yùn)算.如果Seq1=Seq，顯然可以用Seq1代替Seq.

證畢.

極小碰集判定規(guī)則.假設(shè)碰集HS={ex,ex+1,…,ey}，若依次去除元素ei∈HS(i=x,x+1,…,y)的過程中，發(fā)現(xiàn)得到的集合HS′ 滿足碰集定義，則判定HS不是極小碰集，否則恢復(fù)ei造成的影響，繼續(xù)處理去除ei+1的情況.若在去除碰集HS最后1個(gè)元素ey時(shí)HS′ 仍不滿足碰集定義，則判定HS是極小碰集.

定理3. 極小碰集判定規(guī)則正確有效.

證明. 假設(shè)碰集HS={ex,ex+1,…,ey}，若去除HS中任意1個(gè)元素ei(i=x,x+1,…,y)之后得到的集合HS′ 滿足碰集定義，則由極小碰集的定義知碰集HS一定不是極小碰集，否則HS存在是極小碰集的可能性.若去除碰集HS中任意1個(gè)元素ei(i=x,x+1,…,y)后得到的集合HS′都不滿足碰集定義，則說(shuō)明碰集HS中每個(gè)元素都不可取代，因此判定HS是極小碰集.

證畢.

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

2.2 JudgeMHS算法

本節(jié)給出極小碰集判定算法JudgeMHS的算法描述.

本文用鄰接鏈表存儲(chǔ)輸入的集合簇CS，目的是快速找到集合U中特定元素具體能覆蓋集合簇CS中的哪些元素.引入2個(gè)結(jié)構(gòu)SetNode和ListNode，其中SetNode包含屬性setNum(setNum表示U中特定元素能覆蓋集合簇CS中的第setNum個(gè)元素)和next(next指向下一個(gè)SetNode節(jié)點(diǎn))；ListNode包含屬性adjacent(adjacent表示U中特定元素具體能覆蓋的集合簇CS中元素的鄰接指向).

例5. 對(duì)于集合簇CS={{1,2},{2,3},{3,4}}，由于Cap(CS)=3，U={1,2,3,4}，Car(U)=4，所以需要4個(gè)ListNode節(jié)點(diǎn)來(lái)表示集合U中的4個(gè)元素，這里用Head[4]數(shù)組表示(數(shù)組索引代表集合U中相應(yīng)元素).對(duì)于集合簇CS，用1代表第1個(gè)元素{1,2}，2代表第2個(gè)元素{2,3}，3代表第3個(gè)元素{3,4}，因此集合簇CS對(duì)應(yīng)的鄰接鏈表結(jié)構(gòu)如圖1所示：

Fig. 1 The adjacency list of the set cluster CS圖1 集合簇CS對(duì)應(yīng)的鄰接鏈表

有了對(duì)集合簇CS的鄰接鏈表表示形式，下面基于極小碰集判定規(guī)則給出極小碰集判定算法JudgeMHS.SetFlag數(shù)組(大小為集合簇CS的容量) 維護(hù)碰集HS能夠覆蓋的集合簇中的元素，SetFlag[i](i=1,2,…,Cap(CS)) 初始為0表示未覆蓋，大于等于1表示覆蓋(等于1表示HS中只有1個(gè)元素能覆蓋i對(duì)應(yīng)的集合簇中的元素，大于1表示HS中存在多個(gè)元素能覆蓋i對(duì)應(yīng)的集合簇中的元素)；邏輯變量Flag標(biāo)志HS是否是極小碰集，false表示HS不是極小碰集，true表示HS是極小碰集.

算法1. JudgeMHS.

輸入：碰集HS、集合簇CS的鄰接鏈表Head數(shù)組；

輸出：碰集HS是否是極小碰集，若是返回true，否則返回false.

① 將SetFlag數(shù)組中每個(gè)元素的值初始化為0，執(zhí)行步②.

② 循環(huán)處理HS中的元素e，循環(huán)未結(jié)束時(shí)利用Head[e]的鄰接指向獲取元素e能覆蓋的集合簇中的元素setNum，將SetFlag[setNum]+1，返回步②，否則執(zhí)行步③.

③ 循環(huán)處理HS中的元素e，循環(huán)未結(jié)束時(shí)利用Head[e]的鄰接指向獲取元素e能覆蓋的集合簇中的元素setNum，將SetFlag[setNum]-1，即去除元素e，執(zhí)行步④，否則返回true.

④ 置Flag=false，循環(huán)處理SetFlag數(shù)組中的元素SetFlag[i]，循環(huán)未結(jié)束時(shí)如果SetFlag[i]=0，則置Flag=true，退出當(dāng)前循環(huán)并執(zhí)行步⑤，否則繼續(xù)執(zhí)行循環(huán)；循環(huán)結(jié)束時(shí)執(zhí)行步⑤.

⑤ 如果Flag=false，則說(shuō)明去除碰集中的元素e后構(gòu)成的集合仍然滿足碰集定義，則HS不是極小碰集，返回false，否則執(zhí)行步⑥.

⑥ 利用Head[e]的鄰接指向獲取元素e能覆蓋的集合簇中的元素setNum，將SetFlag[setNum]+1，即恢復(fù)元素e對(duì)SetFlag數(shù)組造成的影響，執(zhí)行步③.

2.3 MHS-DMECV算法

本節(jié)給出MHS-DMECV算法的算法描述并分析其完備性和復(fù)雜性.

MHS-DMECV算法中HittingSet用于在算法執(zhí)行過程中動(dòng)態(tài)生成碰集，MinHittingSet用于存儲(chǔ)所有的極小碰集.

算法2. MHS-DMECV.

輸入：待處理序列Seq、與Seq對(duì)應(yīng)的鄰接鏈表Head數(shù)組、與Seq對(duì)應(yīng)的元素覆蓋值Cover數(shù)組、動(dòng)態(tài)保存碰集的容器HittingSet、集合簇CS的元素覆蓋標(biāo)志SetFlag數(shù)組(初始時(shí)每個(gè)元素的值都為0)、已覆蓋數(shù)AlreadyCover(初始為0)；

輸出：集合簇CS對(duì)應(yīng)的所有極小碰集容器MinHittingSet.

① 循環(huán)處理Seq中的元素e，執(zhí)行步②，循環(huán)結(jié)束則返回.

② 如果e是Seq中最后一個(gè)元素，且Cover[e]+AlreadyCover

③ 如果Cover[e]+AlreadyCover=Cap(CS)，將HittingSet中元素存儲(chǔ)到一個(gè)新的容器container里并將元素e也加入container.以container作為輸入調(diào)用JudgeMHS，若返回true，則將container加入MinHittingSet，返回步①處理Seq中下一個(gè)元素.若Cover[e]+AlreadyCover

④ 將元素e加入HittingSet，遍歷Head[e]的鄰接指向，若集合簇CS中存在元素setNum的覆蓋標(biāo)志SetFlag[setNum]=0且e能覆蓋setNum，則將AlreadyCover+1；將Head[e]能遍歷到的集合簇CS中對(duì)應(yīng)元素的覆蓋標(biāo)志+1，執(zhí)行步⑤.

⑤ 構(gòu)建2個(gè)數(shù)據(jù)結(jié)構(gòu)Seq′和Head′，其中Seq′表示在元素e已被選中的狀態(tài)下Seq中在e之后的序列里元素覆蓋值不為0的元素集合，此時(shí)Seq′對(duì)應(yīng)的元素覆蓋值數(shù)組為Cover′；Head′數(shù)組構(gòu)建1個(gè)對(duì)應(yīng)Seq′的鄰接鏈表，即只有在Seq′中的元素在Head′數(shù)組中才會(huì)有鄰接指向，且Head′數(shù)組中元素的鄰接指向指向的SetNode節(jié)點(diǎn)集正是Seq′中相應(yīng)元素能覆蓋的集合簇CS中的元素集對(duì)應(yīng)的SetNode節(jié)點(diǎn)集.構(gòu)建可覆蓋數(shù)CanCover(初始為0)，CanCover表示在元素e已被選中的狀態(tài)下，Seq′可以覆蓋的集合簇CS中的元素?cái)?shù)，執(zhí)行步⑥.

⑥ 如果AlreadyCover+CanCover

⑦ 按照元素覆蓋值從大到小對(duì)Seq′進(jìn)行排序，得到新的待處理序列Seq′；將Seq′、Seq′對(duì)應(yīng)的鄰接鏈表Head′數(shù)組、Cover′數(shù)組、HittingSet、SetFlag數(shù)組以及AlreadyCover作為輸入遞歸調(diào)用MHS-DMECV.遞歸返回時(shí)從HittingSet中移除元素e，遍歷Head[e]的鄰接指向，將Head[e]能遍歷到的集合簇CS中對(duì)應(yīng)元素的覆蓋標(biāo)志減1，若集合簇CS中存在元素setNum的覆蓋標(biāo)志SetFlag[setNum]=0且e能覆蓋setNum，則將AlreadyCover-1，返回步①繼續(xù)處理Seq中下一個(gè)元素.

MHS-DMECV算法結(jié)束時(shí)，MinHittingSet包含所有極小碰集，下面從理論上對(duì)MHS-DMECV算法的完備性和復(fù)雜性進(jìn)行分析.

1) 完備性.在循環(huán)處理待處理序列Seq中的元素e時(shí)(不考慮啟發(fā)式策略和剪枝策略)，由于是遞歸處理，因此它總能枚舉出所有可能的集合.加入啟發(fā)式策略會(huì)得到最先能夠構(gòu)成碰集的碰集集合HSS，且HSS是極小碰集集合的超集，因此能保證在算法結(jié)束時(shí)得到所有的極小碰集.又因?yàn)榧糁Σ呗圆⒉粫?huì)導(dǎo)致丟失極小碰集，所以MHS-DMECV算法對(duì)于求解集合簇CS的極小碰集問題是完備的.

2) 復(fù)雜性.假設(shè)MHS-DMECV算法的總運(yùn)行時(shí)間用T表示(此時(shí)不考慮啟發(fā)式策略和剪枝策略)，由于初始時(shí)需要執(zhí)行m次循環(huán)(m表示集合U的勢(shì))，因此T=T(1)+T(2)+…+T(m).在每一次循環(huán)中都遍歷一遍鄰接鏈表和對(duì)相應(yīng)元素排序，這個(gè)子過程的時(shí)間復(fù)雜度可以用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)，即算法最壞時(shí)間復(fù)雜度是指數(shù)級(jí)；由于需要存儲(chǔ)所有極小碰集，且在最壞情況時(shí)極小碰集數(shù)是指數(shù)級(jí)增長(zhǎng)，因此算法的空間復(fù)雜度在最壞情況時(shí)是指數(shù)級(jí).在MHS-DMECV算法中，因?yàn)槊看翁幚淼脑豦i的元素覆蓋值都是待處理序列Seq中最大的，這種策略能規(guī)避掉很多不必要的處理.例如元素e1能覆蓋集合簇CS中的所有元素，元素e2只能覆蓋集合簇CS中的1個(gè)元素.如果首先處理e1，則不需要再遞歸處理e2，否則由于處理到e2時(shí)，發(fā)現(xiàn)單獨(dú)由e2構(gòu)成的集合{e2}并不足以構(gòu)成碰集，且在e2之后的序列中存在元素構(gòu)成的集合并上{e2}能構(gòu)成碰集，則會(huì)繼續(xù)遞歸處理.考慮啟發(fā)式策略，如果選擇元素ei放入動(dòng)態(tài)碰集容器HittingSet后，發(fā)現(xiàn)AlreadyCover+CanCover

3 實(shí)例分析

本節(jié)基于一個(gè)實(shí)例對(duì)MHS-DMECV算法的執(zhí)行流程進(jìn)行分析.

例6. 對(duì)于集合簇CS={{1,2},{2,3},{3,4}}，利用MHS-DMECV算法求CS的所有極小碰集.

由例3知初始時(shí)待處理序列Seq=[2,3,1,4]，鄰接鏈表Head數(shù)組如圖2所示，元素覆蓋值數(shù)組Cover=[2,2,1,1],HittingSet和MinHittingSet為空，集合簇CS的元素覆蓋標(biāo)志SetFlag=[0,0,0]，已覆蓋數(shù)AlreadyCover=0.此時(shí)的狀態(tài)如表1和圖2所示，將元素2添加到HittingSet之后，此時(shí)的狀態(tài)對(duì)應(yīng)于表2和圖3.

Fig. 2 The corresponding adjacency list about Seq in table 1圖2 表1中Seq對(duì)應(yīng)的鄰接鏈表

Table 1 Value of Each Variable at the Beginning表1 初始時(shí)各變量對(duì)應(yīng)的值

Table 2 Value of Each Variable When Adding 2 into HittingSet表2 將元素2加入HittingSet時(shí)各變量對(duì)應(yīng)的值

Fig. 3 The corresponding adjacency list about Seq in table 2圖3 表2中Seq對(duì)應(yīng)的鄰接鏈表

處理本層元素3時(shí)，發(fā)現(xiàn)AlreadyCover+Cover[3]=3=Cap(CS)，因此新建1個(gè)容器container存儲(chǔ)HittingSet中的元素2，并將元素3也添加到container中，以container作為輸入調(diào)用JudgeMHS，容易看出JudgeMHS返回true，因此將container加入MinHittingSet.元素4與元素3處理類似，所以當(dāng)本層循環(huán)處理完畢時(shí)MinHittingSet中包含極小碰集{2,3}和{2,4}.回到上一層處理元素3，此時(shí)的狀態(tài)對(duì)應(yīng)于表3和圖4.

Table 3 Value of Each Variable When Processing 3表3 處理元素3時(shí)各變量對(duì)應(yīng)的值

Fig. 4 The corresponding adjacency list about Seq in table 3 圖4 表3中 Seq對(duì)應(yīng)的鄰接鏈表

處理本層元素1與前面處理元素3和4類似，所以本層循環(huán)結(jié)束時(shí)MinHittingSet中包含極小碰集{2,3}，{2,4}和{3,1}.回到上一層處理元素1，此時(shí)的狀態(tài)對(duì)應(yīng)于表4和圖5.

Fig. 5 The corresponding adjacency list about Seq in table 4圖5 表4中Seq對(duì)應(yīng)的鄰接鏈表

處理本層元素1時(shí)發(fā)現(xiàn)AlreadyCover+CanCover

Table 4 Value of Each Variable When Processing 1表4 處理元素1時(shí)各變量對(duì)應(yīng)的值

4 實(shí)驗(yàn)分析

本節(jié)對(duì)MHS-DMECV算法的性能進(jìn)行實(shí)驗(yàn)分析.在實(shí)驗(yàn)對(duì)比部分，選取目前效率優(yōu)良的布爾代數(shù)算法[5]作為比較對(duì)象.實(shí)驗(yàn)平臺(tái)如下：Windows 7操作系統(tǒng)，CPU Intel Core i7-3770 3.4 GHz，8.00 GB RAM，Java.

本文測(cè)試用例由偽隨機(jī)集合簇生成器產(chǎn)生，偽隨機(jī)集合簇生成器輸入?yún)?shù)包括元素個(gè)數(shù)m(m表示集合U的勢(shì))、集合簇容量n以及元素在一個(gè)集合簇元素中出現(xiàn)的概率p.在同一個(gè)測(cè)試用例中，所有元素的p值均相等，因此集合簇中每個(gè)元素包含元素的期望個(gè)數(shù)等于mp.對(duì)于元素個(gè)數(shù)為4、集合簇容量為3的測(cè)試用例用M4N3表示.

Fig. 6 Performance comparison of Boolean and MHS-DMECV under M15N200圖6 M15N200下Boolean與MHS-DMECV性能對(duì)比圖

本文用偽隨機(jī)集合簇生成器生成了4類測(cè)試用例，分別為M15N200，M20N200，M25N200以及M30N200.其中每類測(cè)試用例包含10×17個(gè)用例，即每類測(cè)試用例又細(xì)分為10組，各小組均包含p取值0.15～0.94的17個(gè)測(cè)試用例.所有測(cè)試用例中集合簇容量均為200.在10組測(cè)試用例中對(duì)取相同概率p的10個(gè)測(cè)試用例進(jìn)行實(shí)驗(yàn)，取其平均執(zhí)行時(shí)間作為實(shí)驗(yàn)結(jié)果.

圖6描述了在測(cè)試用例為M15N200時(shí)布爾代數(shù)算法與MHS-DMECV算法的性能對(duì)比圖，表5是與圖6對(duì)應(yīng)的實(shí)驗(yàn)統(tǒng)計(jì)結(jié)果.圖6中橫軸表示元素在1個(gè)集合簇元素中出現(xiàn)的概率p；右側(cè)縱軸表示對(duì)應(yīng)實(shí)例的極小碰集數(shù)量.表5中Number ofMHSs表示在10組測(cè)試用例中對(duì)應(yīng)p取值0.15～0.94時(shí)的平均極小碰集個(gè)數(shù)；Speedup Ratio是布爾代數(shù)算法與MHS-DMECV算法平均運(yùn)行時(shí)間(精確到微秒)的比值，即加速比.

Table5ExperimentalStatisticalResultsofBooleanandMHS-DMECVUnderM15N200

表5 M15N200下Boolean與MHS-DMECV實(shí)驗(yàn)統(tǒng)計(jì)結(jié)果

由圖6和表5可知，在極小碰集個(gè)數(shù)較少時(shí)布爾代數(shù)算法效率優(yōu)于MHS-DMECV算法，這是因?yàn)镸HS-DMECV算法需要遍歷鄰接鏈表以及對(duì)待處理序列中的元素排序，這兩個(gè)操作的時(shí)間占比在極小碰集個(gè)數(shù)較少時(shí)會(huì)相對(duì)突出.但隨著極小碰集個(gè)數(shù)的增長(zhǎng)，MHS-DMECV算法優(yōu)勢(shì)逐漸顯現(xiàn)出來(lái)，在元素出現(xiàn)概率p=0.5時(shí)，MHS-DMECV算法平均比布爾代數(shù)算法快5～6倍.

圖7和表6對(duì)應(yīng)測(cè)試用例為M20N200的情況.

由圖7和表6可知，在極小碰集個(gè)數(shù)達(dá)到上千個(gè)時(shí)，MHS-DMECV算法執(zhí)行時(shí)間較布爾代數(shù)算法明顯降低.對(duì)比M15N200的實(shí)驗(yàn)結(jié)果可以看出，在隨機(jī)情況下極小碰集個(gè)數(shù)與元素?cái)?shù)m是正相關(guān)的.為了對(duì)比數(shù)據(jù)規(guī)模較大時(shí)2種算法的性能差異，圖8和表7給出M25N200情況下的性能對(duì)比圖和實(shí)驗(yàn)統(tǒng)計(jì)結(jié)果.

Fig. 7 Performance comparison of Boolean and MHS-DMECV under M20N200圖7 M20N200下Boolean與MHS-DMECV性能對(duì)比圖

Table6ExperimentalStatisticalResultsofBooleanandMHS-DMECVUnderM20N200

表6 M20N200下Boolean與MHS-DMECV實(shí)驗(yàn)統(tǒng)計(jì)結(jié)果

Fig. 8 Performance comparison of Boolean and MHS-DMECV under M25N200圖8 M25N200下Boolean與MHS-DMECV性能對(duì)比圖

Table7ExperimentalStatisticalResultsofBooleanandMHS-DMECVUnderM25N200

表7 M25N200下Boolean與MHS-DMECV實(shí)驗(yàn)統(tǒng)計(jì)結(jié)果

從圖8和表7可知，在極小碰集個(gè)數(shù)達(dá)到上萬(wàn)級(jí)別時(shí)，布爾代數(shù)算法需要幾十甚至上百秒才能計(jì)算出所有極小碰集，而MHS-DMECV算法在零點(diǎn)幾秒內(nèi)就得到了結(jié)果.在概率p=0.5時(shí)，MHS-DMECV算法比布爾代數(shù)算法快200倍左右.最后對(duì)比1組數(shù)據(jù)規(guī)模更大的數(shù)據(jù)，即M30N200這類測(cè)試用例，圖9和表8給出M30N200情況下的性能對(duì)比圖和實(shí)驗(yàn)統(tǒng)計(jì)結(jié)果.

Fig. 9 Performance comparison of Boolean and MHS-DMECV under M30N200圖9 M30N200下Boolean與MHS-DMECV性能對(duì)比圖

在M30N200類數(shù)據(jù)對(duì)比中，容易看出在極小碰集個(gè)數(shù)達(dá)到幾十萬(wàn)的規(guī)模時(shí)，布爾代數(shù)算法在可容忍時(shí)間內(nèi)已經(jīng)失效；反觀MHS-DMECV算法，即使極小碰集個(gè)數(shù)達(dá)到幾十萬(wàn)的規(guī)模，MHS-DMECV算法也能在幾秒之內(nèi)得出結(jié)果.在概率p=0.5時(shí)，MHS-DMECV算法比布爾代數(shù)算法快2 000倍左右.

Table8TheExperimentalStatisticalResultsofBooleanandMHS-DMECVUnderM30N200

表8 M30N200下Boolean與MHS-DMECV實(shí)驗(yàn)統(tǒng)計(jì)結(jié)果

從上面的4類數(shù)據(jù)對(duì)比中得出，雖然在某些小數(shù)據(jù)上布爾代數(shù)算法占有優(yōu)勢(shì)，但隨著數(shù)據(jù)規(guī)模的增大，MHS-DMECV算法具有非常優(yōu)良的性能開銷.綜合來(lái)看，MHS-DMECV算法較布爾代數(shù)算法更具有實(shí)用價(jià)值.下面給出近年來(lái)的一些極小碰集求解算法與MHS-DMECV算法的比較.

由于沖突集合簇的極小碰集求解問題是NP難問題，因此目前國(guó)內(nèi)外的算法都是試圖避開無(wú)用路徑的搜索.理想情況是，對(duì)于一個(gè)給定的沖突集合簇，算法搜索的每條路徑上元素構(gòu)成的集合直接形成一個(gè)極小碰集，即算法不需要做無(wú)用功.DMDSE-TREE算法[7]利用極大度來(lái)盡量避免非極小碰集路徑的搜索，但是DMDSE-TREE算法沒有引入其他較好的剪枝策略，因此效率沒有較大提高.MHS-DMECV算法除了使用動(dòng)態(tài)極大元素覆蓋值規(guī)避掉大量無(wú)用路徑的搜索之外，還引入了啟發(fā)式策略和剪枝策略進(jìn)一步縮小搜索空間.CSP-MHS[8]算法將極小碰集求解問題轉(zhuǎn)換為約束可滿足問題，并調(diào)用相應(yīng)的求解器求解極小碰集.該算法具有較好的創(chuàng)新性，但是在轉(zhuǎn)換的過程中會(huì)丟失一些可以加快極小碰集求解效率的信息，因此CSP-MHS算法能正確地解決問題，但是CSP-MHS算法在效率上有所欠缺.

5 結(jié)束語(yǔ)

本文提出基于動(dòng)態(tài)極大元素覆蓋值求取所有極小碰集的MHS-DMECV算法，求解效率較高.MHS-DMECV算法引入特定狀態(tài)下元素的元素覆蓋值作為啟發(fā)式信息，并通過鄰接鏈表存儲(chǔ)元素覆蓋信息完成極小碰集的求解.MHS-DMECV算法的主要優(yōu)點(diǎn)有4個(gè)方面：

1) 使用鄰接鏈表存儲(chǔ)特定狀態(tài)下的元素覆蓋信息，對(duì)鄰接鏈表只做簡(jiǎn)單遍歷操作，因此算法效率較高，程序易于實(shí)現(xiàn)；

2) 將特定狀態(tài)下的元素覆蓋值從高到低排序，并按照這個(gè)順序選擇元素，因此能減少不必要的搜索，提高求解效率；

3) MHS-DMECV算法添加了啟發(fā)式策略和剪枝策略，算法效率大幅提高；

4) 產(chǎn)生碰集HS時(shí)使用JudgeMHS算法判定HS是否是極小碰集，因此算法結(jié)束時(shí)能保證得到所有的極小碰集.

實(shí)驗(yàn)結(jié)果表明：MHS-DMECV算法性能優(yōu)良，對(duì)于極小碰集求解問題有較高的求解效率.

本文提出的MHS-DMECV算法除了應(yīng)用在基于模型的診斷領(lǐng)域外，還可以將其應(yīng)用到極小覆蓋集問題、智能規(guī)劃和軟件調(diào)試中.針對(duì)具體問題的特點(diǎn)，將本文方法設(shè)計(jì)為相適應(yīng)的算法，在特定問題上取得更理想的效果.

[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)(李林, 盧顯良. 一種基于位向量交集運(yùn)算的規(guī)則沖突檢測(cè)算法[J]. 計(jì)算機(jī)研究與發(fā)展, 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)(姜云飛, 林笠. 用對(duì)分-HS樹計(jì)算最小碰集[J]. 軟件學(xué)報(bào), 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)(姜云飛, 林笠. 用布爾代數(shù)方法計(jì)算最小碰集[J]. 計(jì)算機(jī)學(xué)報(bào), 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)(張立明, 歐陽(yáng)丹彤, 曾海林. 基于動(dòng)態(tài)極大度的極小碰集求解方法[J]. 計(jì)算機(jī)研究與發(fā)展, 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)(王藝源, 歐陽(yáng)丹彤, 張立明, 等. 利用CSP求解極小碰集的方法[J]. 計(jì)算機(jī)研究與發(fā)展, 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.