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

(吉林大學計算機科學與技術學院 長春 130012) (符號計算與知識工程教育部重點實驗室(吉林大學) 長春 130012) (dengzy19941019@163.com)

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

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

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

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

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

3) 使用鄰接鏈表存儲輸入的集合簇，鄰接鏈表結構能快速找到元素能夠覆蓋的集合簇中的元素.

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

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

1 背景知識

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

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

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

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

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

例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中的頻數(shù)Freq(CS,2)=2，因為元素2出現(xiàn)在集合簇CS的元素{1,2}和{2,3}中.

2 極小碰集求解算法

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

2.1 相關定義及定理

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

定義4. 元素覆蓋值.若元素e在集合簇CS的某個元素Si(i=1,2,…,n)中出現(xiàn)，且在當前狀態(tài)下Si中沒有其他元素出現(xiàn)，則稱元素e覆蓋Si；若對于集合簇CS中的所有元素，元素e能覆蓋的元素個數(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；此時再選擇元素2，由于集合{1,2}已被覆蓋，所以元素2只能覆蓋集合{2,3}，因此Cover(2)=1；對于元素3，由于集合{2,3}已被覆蓋，所以元素3只能覆蓋集合{3,4}，因此Cover(3)=1；對于元素4，由于集合簇CS中的所有元素都已被覆蓋，因此Cover(4)=0.

定義5. 待處理序列.在當前狀態(tài)下，待處理的元素集合為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，此時恢復到初始狀態(tài)，即沒有選中元素1時的狀態(tài).此后每計算出一個元素e的元素覆蓋值，都將元素e造成的影響進行恢復，所以Cover(2)=2，Cover(3)=2和Cover(4)=1，因此待處理序列Seq=[2,3,1,4](為了描述方便，假設具有相同元素覆蓋值的元素按照元素本身的大小從小到大排序).

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

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

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

證明.

1) 必要性.

假設NewPend表示新的待處理序列Seq′中所有元素構成的集合，S=Before∪NewPend.由于已覆蓋數(shù)AlreadyCover和可覆蓋數(shù)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′，所以已覆蓋數(shù)AlreadyCover與可覆蓋數(shù)CanCover的和一定小于集合簇CS的容量，即AlreadyCover+CanCover

證畢.

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

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

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

定理2. 對于求解集合簇CS的極小碰集問題，剪枝策略不會導致丟解.

證明. 從前往后掃描待處理序列Seq的過程中，如果發(fā)現(xiàn)某個位置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.

證畢.

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

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

證明. 假設碰集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算法

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

本文用鄰接鏈表存儲輸入的集合簇CS，目的是快速找到集合U中特定元素具體能覆蓋集合簇CS中的哪些元素.引入2個結構SetNode和ListNode，其中SetNode包含屬性setNum(setNum表示U中特定元素能覆蓋集合簇CS中的第setNum個元素)和next(next指向下一個SetNode節(jié)點)；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節(jié)點來表示集合U中的4個元素，這里用Head[4]數(shù)組表示(數(shù)組索引代表集合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的鄰接鏈表表示形式，下面基于極小碰集判定規(guī)則給出極小碰集判定算法JudgeMHS.SetFlag數(shù)組(大小為集合簇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數(shù)組；

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

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

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

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

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

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

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

2.3 MHS-DMECV算法

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

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

算法2. MHS-DMECV.

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

輸出：集合簇CS對應的所有極小碰集容器MinHittingSet.

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

② 如果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，執(zhí)行步⑤.

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

⑥ 如果AlreadyCover+CanCover

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

MHS-DMECV算法結束時，MinHittingSet包含所有極小碰集，下面從理論上對MHS-DMECV算法的完備性和復雜性進行分析.

1) 完備性.在循環(huán)處理待處理序列Seq中的元素e時(不考慮啟發(fā)式策略和剪枝策略)，由于是遞歸處理，因此它總能枚舉出所有可能的集合.加入啟發(fā)式策略會得到最先能夠構成碰集的碰集集合HSS，且HSS是極小碰集集合的超集，因此能保證在算法結束時得到所有的極小碰集.又因為剪枝策略并不會導致丟失極小碰集，所以MHS-DMECV算法對于求解集合簇CS的極小碰集問題是完備的.

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

3 實例分析

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

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

由例3知初始時待處理序列Seq=[2,3,1,4]，鄰接鏈表Head數(shù)組如圖2所示，元素覆蓋值數(shù)組Cover=[2,2,1,1],HittingSet和MinHittingSet為空，集合簇CS的元素覆蓋標志SetFlag=[0,0,0]，已覆蓋數(shù)AlreadyCover=0.此時的狀態(tài)如表1和圖2所示，將元素2添加到HittingSet之后，此時的狀態(tài)對應于表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時，發(fā)現(xiàn)AlreadyCover+Cover[3]=3=Cap(CS)，因此新建1個容器container存儲HittingSet中的元素2，并將元素3也添加到container中，以container作為輸入調用JudgeMHS，容易看出JudgeMHS返回true，因此將container加入MinHittingSet.元素4與元素3處理類似，所以當本層循環(huán)處理完畢時MinHittingSet中包含極小碰集{2,3}和{2,4}.回到上一層處理元素3，此時的狀態(tài)對應于表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類似，所以本層循環(huán)結束時MinHittingSet中包含極小碰集{2,3}，{2,4}和{3,1}.回到上一層處理元素1，此時的狀態(tài)對應于表4和圖5.

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

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

Table 4 Value of Each Variable When Processing 1表4 處理元素1時各變量對應的值

4 實驗分析

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

本文測試用例由偽隨機集合簇生成器產(chǎn)生，偽隨機集合簇生成器輸入?yún)?shù)包括元素個數(shù)m(m表示集合U的勢)、集合簇容量n以及元素在一個集合簇元素中出現(xiàn)的概率p.在同一個測試用例中，所有元素的p值均相等，因此集合簇中每個元素包含元素的期望個數(shù)等于mp.對于元素個數(shù)為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個測試用例進行實驗，取其平均執(zhí)行時間作為實驗結果.

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

Table5ExperimentalStatisticalResultsofBooleanandMHS-DMECVUnderM15N200

表5 M15N200下Boolean與MHS-DMECV實驗統(tǒng)計結果

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

圖7和表6對應測試用例為M20N200的情況.

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

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

Table6ExperimentalStatisticalResultsofBooleanandMHS-DMECVUnderM20N200

表6 M20N200下Boolean與MHS-DMECV實驗統(tǒng)計結果

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

Table7ExperimentalStatisticalResultsofBooleanandMHS-DMECVUnderM25N200

表7 M25N200下Boolean與MHS-DMECV實驗統(tǒng)計結果

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

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

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

Table8TheExperimentalStatisticalResultsofBooleanandMHS-DMECVUnderM30N200

表8 M30N200下Boolean與MHS-DMECV實驗統(tǒng)計結果

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

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

5 結束語

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

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

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

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

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

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

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

[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)(李林, 盧顯良. 一種基于位向量交集運算的規(guī)則沖突檢測算法[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]. 軟件學報, 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]. 計算機學報, 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)(張立明, 歐陽丹彤, 曾海林. 基于動態(tài)極大度的極小碰集求解方法[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]. 計算機研究與發(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.