基于動(dòng)態(tài)極大元素覆蓋值的極小碰集求解算法

鄧召勇 歐陽丹彤 耿雪娜 劉 杰

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

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

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

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

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

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

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

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

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

1 背景知識

本節(jié)介紹碰集(hitting set,HS) 的相關(guān)定義和概念，并給出一個(gè)實(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的勢，即集合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}的勢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；若對于集合簇CS中的所有元素，元素e能覆蓋的元素個(gè)數(shù)為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；此時(shí)再選擇元素2，由于集合{1,2}已被覆蓋，所以元素2只能覆蓋集合{2,3}，因此Cover(2)=1；對于元素3，由于集合{2,3}已被覆蓋，所以元素3只能覆蓋集合{3,4}，因此Cover(3)=1；對于元素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. 對于集合簇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ù).對于待處理序列Seq，Seq能覆蓋的集合簇CS中元素總數(shù)為CanCover，則稱CanCover為可覆蓋數(shù).

例4. 對于集合簇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. 對于當(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)成的集合，因此對于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ā)式策略.對于當(dāng)前狀態(tài)state，若已知已覆蓋數(shù)AlreadyCover和可覆蓋數(shù)CanCover，且AlreadyCover+CanCover

2) 剪枝策略.對于待處理序列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. 對于求解集合簇CS的極小碰集問題，剪枝策略不會(huì)導(dǎo)致丟解.

證明. 從前往后掃描待處理序列Seq的過程中，如果發(fā)現(xiàn)某個(gè)位置k使得該位置處元素ek的元素覆蓋值Cover(ek)=0，由于待處理序列Seq是按照元素覆蓋值Cover(e)從大到小的順序排列，且Cover(e)≥0，因此位置k及其之后位置對應(yīng)的元素et(t=k,k+1,…,j-1,j) 的元素覆蓋值Cover(et)=0.由元素覆蓋值的定義知，元素et對覆蓋集合簇CS中的元素不再有幫助，且極小碰集的定義要求極小碰集MHS中的任意1個(gè)元素e′∈MHS都是不可取代的.e′至少能覆蓋集合簇CS中的1個(gè)元素S∈CS，且極小碰集中的其他元素都不能覆蓋S，因此去除Seq中位置k及其之后位置對應(yīng)的元素對于計(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′都不滿足碰集定義，則說明碰集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. 對于集合簇CS={{1,2},{2,3},{3,4}}，由于Cap(CS)=3，U={1,2,3,4}，Car(U)=4，所以需要4個(gè)ListNode節(jié)點(diǎn)來表示集合U中的4個(gè)元素，這里用Head[4]數(shù)組表示(數(shù)組索引代表集合U中相應(yīng)元素).對于集合簇CS，用1代表第1個(gè)元素{1,2}，2代表第2個(gè)元素{2,3}，3代表第3個(gè)元素{3,4}，因此集合簇CS對應(yīng)的鄰接鏈表結(jié)構(gòu)如圖1所示：

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

有了對集合簇CS的鄰接鏈表表示形式，下面基于極小碰集判定規(guī)則給出極小碰集判定算法JudgeMHS.SetFlag數(shù)組(大小為集合簇CS的容量) 維護(hù)碰集HS能夠覆蓋的集合簇中的元素，SetFlag[i](i=1,2,…,Cap(CS)) 初始為0表示未覆蓋，大于等于1表示覆蓋(等于1表示HS中只有1個(gè)元素能覆蓋i對應(yīng)的集合簇中的元素，大于1表示HS中存在多個(gè)元素能覆蓋i對應(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，則說明去除碰集中的元素e后構(gòu)成的集合仍然滿足碰集定義，則HS不是極小碰集，返回false，否則執(zhí)行步⑥.

⑥ 利用Head[e]的鄰接指向獲取元素e能覆蓋的集合簇中的元素setNum，將SetFlag[setNum]+1，即恢復(fù)元素e對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對應(yīng)的鄰接鏈表Head數(shù)組、與Seq對應(yīng)的元素覆蓋值Cover數(shù)組、動(dòng)態(tài)保存碰集的容器HittingSet、集合簇CS的元素覆蓋標(biāo)志SetFlag數(shù)組(初始時(shí)每個(gè)元素的值都為0)、已覆蓋數(shù)AlreadyCover(初始為0)；

輸出：集合簇CS對應(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中對應(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′對應(yīng)的元素覆蓋值數(shù)組為Cover′；Head′數(shù)組構(gòu)建1個(gè)對應(yīng)Seq′的鄰接鏈表，即只有在Seq′中的元素在Head′數(shù)組中才會(huì)有鄰接指向，且Head′數(shù)組中元素的鄰接指向指向的SetNode節(jié)點(diǎn)集正是Seq′中相應(yīng)元素能覆蓋的集合簇CS中的元素集對應(yīng)的SetNode節(jié)點(diǎn)集.構(gòu)建可覆蓋數(shù)CanCover(初始為0)，CanCover表示在元素e已被選中的狀態(tài)下，Seq′可以覆蓋的集合簇CS中的元素?cái)?shù)，執(zhí)行步⑥.

⑥ 如果AlreadyCover+CanCover

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

MHS-DMECV算法結(jié)束時(shí)，MinHittingSet包含所有極小碰集，下面從理論上對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算法對于求解集合簇CS的極小碰集問題是完備的.

2) 復(fù)雜性.假設(shè)MHS-DMECV算法的總運(yùn)行時(shí)間用T表示(此時(shí)不考慮啟發(fā)式策略和剪枝策略)，由于初始時(shí)需要執(zhí)行m次循環(huán)(m表示集合U的勢)，因此T=T(1)+T(2)+…+T(m).在每一次循環(huán)中都遍歷一遍鄰接鏈表和對相應(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ù)級；由于需要存儲(chǔ)所有極小碰集，且在最壞情況時(shí)極小碰集數(shù)是指數(shù)級增長，因此算法的空間復(fù)雜度在最壞情況時(shí)是指數(shù)級.在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í)例對MHS-DMECV算法的執(zhí)行流程進(jìn)行分析.

例6. 對于集合簇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)對應(yīng)于表2和圖3.

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

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

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

Fig. 3 The corresponding adjacency list about Seq in table 2圖3 表2中Seq對應(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)對應(yīng)于表3和圖4.

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

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

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

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

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

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

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

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

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

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

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

圖6描述了在測試用例為M15N200時(shí)布爾代數(shù)算法與MHS-DMECV算法的性能對比圖，表5是與圖6對應(yīng)的實(shí)驗(yàn)統(tǒng)計(jì)結(jié)果.圖6中橫軸表示元素在1個(gè)集合簇元素中出現(xiàn)的概率p；右側(cè)縱軸表示對應(yīng)實(shí)例的極小碰集數(shù)量.表5中Number ofMHSs表示在10組測試用例中對應(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算法需要遍歷鄰接鏈表以及對待處理序列中的元素排序，這兩個(gè)操作的時(shí)間占比在極小碰集個(gè)數(shù)較少時(shí)會(huì)相對突出.但隨著極小碰集個(gè)數(shù)的增長，MHS-DMECV算法優(yōu)勢逐漸顯現(xiàn)出來，在元素出現(xiàn)概率p=0.5時(shí)，MHS-DMECV算法平均比布爾代數(shù)算法快5～6倍.

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

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

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

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性能對比圖

Table7ExperimentalStatisticalResultsofBooleanandMHS-DMECVUnderM25N200

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

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

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

在M30N200類數(shù)據(jù)對比中，容易看出在極小碰集個(gè)數(shù)達(dá)到幾十萬的規(guī)模時(shí)，布爾代數(shù)算法在可容忍時(shí)間內(nèi)已經(jīng)失效；反觀MHS-DMECV算法，即使極小碰集個(gè)數(shù)達(dá)到幾十萬的規(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ù)對比中得出，雖然在某些小數(shù)據(jù)上布爾代數(shù)算法占有優(yōu)勢，但隨著數(shù)據(jù)規(guī)模的增大，MHS-DMECV算法具有非常優(yōu)良的性能開銷.綜合來看，MHS-DMECV算法較布爾代數(shù)算法更具有實(shí)用價(jià)值.下面給出近年來的一些極小碰集求解算法與MHS-DMECV算法的比較.

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

5 結(jié)束語

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

1) 使用鄰接鏈表存儲(chǔ)特定狀態(tài)下的元素覆蓋信息，對鄰接鏈表只做簡單遍歷操作，因此算法效率較高，程序易于實(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)良，對于極小碰集求解問題有較高的求解效率.

本文提出的MHS-DMECV算法除了應(yīng)用在基于模型的診斷領(lǐng)域外，還可以將其應(yīng)用到極小覆蓋集問題、智能規(guī)劃和軟件調(diào)試中.針對具體問題的特點(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ī)則沖突檢測算法[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)(姜云飛, 林笠. 用對分-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)(張立明, 歐陽丹彤, 曾海林. 基于動(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)(王藝源, 歐陽丹彤, 張立明, 等. 利用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.