結(jié)合SE-Tree結(jié)構(gòu)特征的極小碰集求解算法

劉思光 歐陽(yáng)丹彤 王藝源 賈鳳雨 張立明

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

?

結(jié)合SE-Tree結(jié)構(gòu)特征的極小碰集求解算法

劉思光 歐陽(yáng)丹彤 王藝源 賈鳳雨 張立明

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

在結(jié)合SE-Tree計(jì)算集合簇極小碰集的過(guò)程中,現(xiàn)有算法會(huì)對(duì)大量不會(huì)產(chǎn)生碰集的冗余節(jié)點(diǎn)進(jìn)行訪問(wèn).這無(wú)疑將影響算法的效率,冗余節(jié)點(diǎn)比例越高,影響越大.通過(guò)對(duì)SE-Tree中葉節(jié)點(diǎn)的特殊性質(zhì)的分析,并結(jié)合現(xiàn)有碰集算法有解空間中冗余節(jié)點(diǎn)的特征,提出非解冗余節(jié)點(diǎn)概念.在對(duì)SE-Tree的結(jié)構(gòu)特征進(jìn)行深入分析基礎(chǔ)上,根據(jù)非碰集的子集也不是碰集的特點(diǎn),提出輔助剪枝的概念,通過(guò)在剪枝樹(shù)上設(shè)置剪枝判定節(jié)點(diǎn),減少對(duì)極小碰集求解過(guò)程中無(wú)解空間的訪問(wèn);針對(duì)較大規(guī)模問(wèn)題,還提出結(jié)合多級(jí)輔助剪枝樹(shù)的極小碰集求解算法,進(jìn)而較大程度地減少對(duì)非解冗余節(jié)點(diǎn)的訪問(wèn);根據(jù)多級(jí)輔助剪枝樹(shù)及SE-Tree的結(jié)構(gòu)特征,給出提前終止算法的判定條件,并證明了此算法的正確性.實(shí)驗(yàn)結(jié)果表明:與效率較高的Boolean算法相比,該算法高效且易于實(shí)現(xiàn),尤其是對(duì)規(guī)模較大的問(wèn)題,效率能提升1個(gè)數(shù)量級(jí).

基于模型診斷;極小碰集;集合枚舉樹(shù);輔助剪枝樹(shù);無(wú)解空間剪枝

極小碰集問(wèn)題是人工智能領(lǐng)域的研究熱點(diǎn)之一,許多實(shí)際和理論問(wèn)題都可以轉(zhuǎn)化為極小碰集問(wèn)題.例如：基于模型診斷(model-based diagnosis)[1]過(guò)程一般可以分為沖突識(shí)別和候選產(chǎn)生2個(gè)主要步驟,沖突識(shí)別為根據(jù)系統(tǒng)描述及觀測(cè)得到極小沖突集,候選產(chǎn)生則是利用得到的極小沖突集計(jì)算極小碰集；極小集合覆蓋和極小頂點(diǎn)覆蓋等極小覆蓋問(wèn)題可以看作是極小碰集問(wèn)題的特殊形式；智能規(guī)劃和軟件調(diào)試中的核心問(wèn)題也可以通過(guò)轉(zhuǎn)換為極小碰集問(wèn)題后使用相應(yīng)算法求解來(lái)提高效率[2-3].

迄今為止,國(guó)內(nèi)外許多學(xué)者都對(duì)極小碰集的求解算法進(jìn)行了研究和改進(jìn).最早的極小碰集計(jì)算算法是由Reiter[1]于1987年提出的HS-Tree算法,但此算法可能會(huì)因剪枝而丟失正確解;為解決此問(wèn)題,1989年Greiner等人[4]對(duì)此算法進(jìn)行改進(jìn),提出了HS-DAG算法;隨著對(duì)極小碰集問(wèn)題的深入研究,許多新的求解算法不斷被提出：2001年Wotawa[5]通過(guò)對(duì)HS-Tree算法的改進(jìn)提出了HST-Tree算法,有效降低了極小碰集求解過(guò)程中子集檢測(cè)的數(shù)量；2002和2003年,姜云飛等人提出了BHS-Tree[6]和Boolean算法[7],前者對(duì)比HS-Tree算法有效減少了節(jié)點(diǎn)生成的數(shù)量同時(shí)解決了HS-Tree算法可能會(huì)因剪枝而丟解的問(wèn)題,后者使用Boolean變量代表沖突集元素,通過(guò)Boolean表達(dá)式計(jì)算求解所有極小碰集,在提高求解效率的同時(shí)簡(jiǎn)化了數(shù)據(jù)結(jié)構(gòu)；2004年,歐陽(yáng)丹彤等人[8]在HS-DAG算法的基礎(chǔ)上提出了改進(jìn)后的New HS-Tree算法,對(duì)比HS-DAG算法,搜索節(jié)點(diǎn)大幅減少；2006年,趙相福等人[9]提出了HSSE-Tree算法,使用帶有終止節(jié)點(diǎn)的集合枚舉樹(shù)形式化地表示了極小碰集的求解過(guò)程；2010年,陳曉梅等人[10]提出了BNB-HSSE算法,通過(guò)使用分支定界法與集合枚舉法相結(jié)合將問(wèn)題不斷分解,降低求解規(guī)模、簡(jiǎn)化枚舉過(guò)程,進(jìn)而提高求解效率；2011年,張立明等人[11]提出了基于動(dòng)態(tài)極大度的DMDSE-Tree算法,該算法通過(guò)在擴(kuò)展集合枚舉樹(shù)(SE-Tree)節(jié)點(diǎn)的過(guò)程中使用自定義度對(duì)待擴(kuò)充元素進(jìn)行排序,有效降低了生成節(jié)點(diǎn)的數(shù)量；2012年,Pill等人[12]對(duì)Boolean算法進(jìn)行了改進(jìn),通過(guò)對(duì)部分規(guī)則進(jìn)行修改,有效提升了該算法對(duì)有界問(wèn)題的求解效率；2015年王藝源等人[13]提出了利用CSP求解極小碰集的CSP-MHS算法,通過(guò)將極小碰集問(wèn)題轉(zhuǎn)換為約束滿(mǎn)足問(wèn)題后調(diào)用CSP求解器進(jìn)行求解,并提出hard-沖突集與soft-沖突集概念,以此提高算法對(duì)于具有某些特征的極小碰集問(wèn)題的求解效率.除了這些完備求解算法,隨著近似求解策略的不斷發(fā)展,許多非完備極小碰集求解算法被提出[14-18].這些算法大多使用隨機(jī)搜索策略,即使對(duì)于規(guī)模很大的問(wèn)題,也能夠在較短時(shí)間內(nèi)完成求解,但同時(shí)這也是以犧牲解的完備性為代價(jià)的.此外,近年來(lái)也有許多并行及分布式極小碰集求解算法被提出[19-20].

以上極小碰集求解算法的缺點(diǎn)集中表現(xiàn)為：1)因剪枝或使用隨機(jī)策略可能丟失正確的解[1,14-18];2)需要建立結(jié)構(gòu)復(fù)雜的樹(shù)或圖,算法實(shí)現(xiàn)繁瑣[1,4-6];3)碰集計(jì)算由遞歸實(shí)現(xiàn),效率較差[1,4-5,8];4)先存儲(chǔ)計(jì)算所得的所有碰集,最后對(duì)非極小碰集進(jìn)行刪減,導(dǎo)致空間復(fù)雜度較高[7,16].

這些極小碰集求解算法中,大部分完備算法都顯式[1,4-6,8-11]或隱式[7,12]地使用了樹(shù)形結(jié)構(gòu)來(lái)進(jìn)行算法描述及問(wèn)題求解.這與樹(shù)形結(jié)構(gòu)表達(dá)清晰、易于根據(jù)實(shí)際問(wèn)題特征加入各種剪枝策略等特點(diǎn)密切相關(guān).其中基于SE-Tree的HSSE-Tree算法,所用樹(shù)結(jié)構(gòu)簡(jiǎn)單且有很強(qiáng)的規(guī)律性,算法實(shí)現(xiàn)也較容易.但由于其采用寬度優(yōu)先的策略對(duì)SE-Tree中節(jié)點(diǎn)進(jìn)行生成,使得在碰集計(jì)算過(guò)程中需對(duì)當(dāng)前層中生成的非碰集節(jié)點(diǎn)進(jìn)行存儲(chǔ),用于下一層需訪問(wèn)節(jié)點(diǎn)的生成,這就導(dǎo)致了算法運(yùn)行過(guò)程中較高的空間需求，并且無(wú)法對(duì)一些無(wú)需訪問(wèn)的非解冗余節(jié)點(diǎn)進(jìn)行剪枝,影響了算法效率.

本文通過(guò)對(duì)SE-Tree結(jié)構(gòu)進(jìn)行深度分析,指出SE-Tree在深度優(yōu)先遍歷過(guò)程中存在一種新型可剪枝節(jié)點(diǎn),給出相應(yīng)的剪枝算法,并在此基礎(chǔ)上提出結(jié)合SE-Tree結(jié)構(gòu)特征的極小碰集求解算法.這種算法的主要優(yōu)點(diǎn)是：1)采用深度優(yōu)先求解方式,相較于HSSE-Tree算法空間復(fù)雜度大幅降低;2)可以對(duì)無(wú)訪問(wèn)價(jià)值的非解冗余節(jié)點(diǎn)進(jìn)行大量剪枝,大幅提高算法效率;3)增加了提前終止條件的判定,進(jìn)一步提高算法效率;4)僅使用SE-Tree結(jié)構(gòu)進(jìn)行描述,實(shí)現(xiàn)過(guò)程中僅使用鏈表和數(shù)組,實(shí)現(xiàn)簡(jiǎn)單.

1 預(yù)備知識(shí)

首先介紹模型診斷中與碰集相關(guān)的背景知識(shí),以及集合枚舉樹(shù)SE-Tree的相關(guān)概念及性質(zhì).

1.1 基于模型診斷的相關(guān)概念

定義1[1].一個(gè)系統(tǒng)可定義為一個(gè)三元組(SD,COMPS,OBS),其中：

1)SD為系統(tǒng)描述,是一階謂詞公式集合;

2)COMPS是系統(tǒng)組成部件的集合,是一個(gè)有限常量集;

3)OBS為觀測(cè)集,是一階謂詞公式的有限集.

定義2[1].沖突集CS是一個(gè)部件集{c1,c2,…,cn}?COMPS,當(dāng)且僅當(dāng)SD∪OBS∪{AB(c1),AB(c2),…,AB(cn)}是不一致的.其中AB為一元謂詞,表示“abnormal”.AB(c)為真,當(dāng)且僅當(dāng)c異常,且c∈COMPS.

稱(chēng)沖突集是極小沖突集(minimal conflict set, MCS)[21],當(dāng)且僅當(dāng)該沖突集的任意真子集都不是沖突集.

定義3[1].設(shè)F是一個(gè)集合簇,F={S1,S2,…,Sn},稱(chēng)H為F的一個(gè)碰集HS,如果H滿(mǎn)足2個(gè)條件：

2) 對(duì)于任意一個(gè)Si∈F,都有H∩Si≠?；

稱(chēng)F的一個(gè)碰集H為極小碰集(minimal hitting set, MHS),當(dāng)且僅當(dāng)H的任意真子集都不是F的碰集.

1.2 SE-Tree的相關(guān)概念及性質(zhì)

SE-Tree由Rymon[22]提出：一個(gè)完全的SE-Tree是按照一定的順序(如數(shù)字或字母的順序等),系統(tǒng)地枚舉出一個(gè)集合的冪集中所有元素的集合.例如S={1,2,3,4}的完全集合枚舉樹(shù)如圖1所示:

Fig. 1 SE-Tree of S={1,2,3,4}.圖1 S={1,2,3,4}對(duì)應(yīng)的SE-Tree

按上述規(guī)則生成的SE-Tree具有2個(gè)性質(zhì)：

1) 對(duì)于所有非葉節(jié)點(diǎn),該節(jié)點(diǎn)是其所有子孫節(jié)點(diǎn)的真子集,特別地根節(jié)點(diǎn)是所有其他節(jié)點(diǎn)的真子集;

2) 對(duì)于所有非根節(jié)點(diǎn),該節(jié)點(diǎn)是其所有祖先節(jié)點(diǎn)的真超集,特別地葉節(jié)點(diǎn)是其所在分支上所有其他節(jié)點(diǎn)的真超集.

根據(jù)以上性質(zhì)和碰集的定義,我們可以得到以下推論：

推論1. 若一個(gè)非葉節(jié)點(diǎn)是碰集,則該節(jié)點(diǎn)的所有子孫節(jié)點(diǎn)都是碰集.

推論2. 若一個(gè)葉節(jié)點(diǎn)不是碰集,則該葉節(jié)點(diǎn)所在分支上的所有節(jié)點(diǎn)都不是碰集.

其中,推論2是本文核心算法的基礎(chǔ).

為方便討論,首先給出一些SE-Tree的相關(guān)定義：

定義4. 若一個(gè)節(jié)點(diǎn)內(nèi)所有元素都是連續(xù)的,則稱(chēng)此節(jié)點(diǎn)為純節(jié)點(diǎn)(只含有1個(gè)元素的節(jié)點(diǎn)是純節(jié)點(diǎn)).若一個(gè)葉節(jié)點(diǎn)是純節(jié)點(diǎn),則稱(chēng)該葉節(jié)點(diǎn)為純?nèi)~節(jié)點(diǎn).

例如圖1中,{2,4}不是純節(jié)點(diǎn),{2,3}是純節(jié)點(diǎn),{2,3,4}是純?nèi)~節(jié)點(diǎn).

定義5. 稱(chēng)SE-Tree中最左側(cè)的葉節(jié)點(diǎn)為頭葉節(jié)點(diǎn);最右側(cè)葉節(jié)點(diǎn)為尾葉節(jié)點(diǎn).

例如圖1中{1,2,3,4}為頭葉節(jié)點(diǎn),{4}為尾葉節(jié)點(diǎn).

顯然,頭葉節(jié)點(diǎn)和尾葉節(jié)點(diǎn)都是純?nèi)~節(jié)點(diǎn).并且,頭葉節(jié)點(diǎn)包含了該SE-Tree任意節(jié)點(diǎn)中可出現(xiàn)的全部元素.

本文集合中的元素在默認(rèn)情況下都為遞增排序.

2 基于SE-Tree的深度優(yōu)先碰集求解算法

首先給出一種基于SE-Tree的深度優(yōu)先極小碰集求解算法,隨后通過(guò)1個(gè)實(shí)例對(duì)其不足之處進(jìn)行說(shuō)明.

基于SE-Tree的深度優(yōu)先極小碰集求解算法,即是在SE-Tree上使用深度優(yōu)先算法求解極小碰集.其一般過(guò)程為：對(duì)問(wèn)題對(duì)應(yīng)的SE-Tree以左優(yōu)先進(jìn)行深度優(yōu)先遍歷.當(dāng)訪問(wèn)到的節(jié)點(diǎn)為碰集時(shí),對(duì)該節(jié)點(diǎn)的所有子孫節(jié)點(diǎn)進(jìn)行剪枝,對(duì)該碰集進(jìn)行檢測(cè)：若是極小碰集則加入結(jié)果中,否則不加入.繼續(xù)深度優(yōu)先遍歷,直到SE-Tree中所有未被剪枝掉的節(jié)點(diǎn)都已被訪問(wèn).

我們可以發(fā)現(xiàn),以上算法可以看作這樣一個(gè)過(guò)程：每次迭代是對(duì)一個(gè)葉節(jié)點(diǎn)所在分支中的一部分進(jìn)行遍歷.此處,一個(gè)分支由根節(jié)點(diǎn)到這個(gè)葉節(jié)點(diǎn)路徑上的所有節(jié)點(diǎn)構(gòu)成.迭代開(kāi)始于本分支與上次進(jìn)行迭代的分支的最后一個(gè)共有節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn).在沒(méi)有遇到碰集節(jié)點(diǎn)的情況下,結(jié)束于本分支的葉節(jié)點(diǎn);否則結(jié)束于第1個(gè)碰集節(jié)點(diǎn).下面給出基于SE-Tree的深度優(yōu)先極小碰集算法DF-SE(deep first-SE).

算法1. DF-SE(F={S1,S2,…,Sm})

Leaf=S；

② Begin

③ While(1)

④ While(1)

⑤Node=next(Node,Leaf)；

⑥ If (Node為碰集)

⑦ If (Node為極小碰集)

⑧MHS=MHS∪Node；

⑨ EndIf

⑩ Break；

其中,Leaf表示本次迭代需遍歷的分支上的葉節(jié)點(diǎn),Node為當(dāng)前遍歷節(jié)點(diǎn),函數(shù)next用于計(jì)算當(dāng)前分支上下一個(gè)需要遍歷的節(jié)點(diǎn),函數(shù)next_begin用于計(jì)算本次迭代遍歷分支與下次迭代需遍歷分支的最后一個(gè)共有節(jié)點(diǎn),函數(shù)next_end用于計(jì)算下次迭代需遍歷分支上的葉節(jié)點(diǎn).

下面給出1個(gè)結(jié)合SE-Tree求解極小碰集的深度優(yōu)先算法過(guò)程實(shí)例.

例1. 使用DF-SE算法求集合簇F={{1,4},{2},{3}}的極小碰集.

其SE-Tree同圖1給出的一樣.求解過(guò)程中,需要按順序遍歷{1},{1,2},{1,2,3},{1,2,4},{1,3},{1,3,4},{1,4},{2},{2,3},{2,3,4},{2,4},{3},{3,4},{4}總共14個(gè)節(jié)點(diǎn),其中{1,2,3},{2,3,4}為極小碰集節(jié)點(diǎn).通過(guò)觀察可以發(fā)現(xiàn)對(duì){1,2,4},{1,3},{1,3,4},{1,4},{2,4},{3},{3,4},{4}這8個(gè)節(jié)點(diǎn)對(duì)應(yīng)分支的遍歷沒(méi)有碰集產(chǎn)生,即這些節(jié)點(diǎn)是冗余節(jié)點(diǎn).

定義6. 在SE-Tree中,稱(chēng)非極小的碰集節(jié)點(diǎn)為有解冗余節(jié)點(diǎn),節(jié)點(diǎn)本身及其所有子孫節(jié)點(diǎn)都不為碰集的節(jié)點(diǎn)為非解冗余節(jié)點(diǎn).對(duì)于不是碰集的葉節(jié)點(diǎn),稱(chēng)之為冗余葉節(jié)點(diǎn).

顯然,在極小碰集計(jì)算過(guò)程中,對(duì)非解冗余節(jié)點(diǎn)進(jìn)行剪枝不會(huì)對(duì)解的正確性及完備性造成影響.接下來(lái)我們需要考慮的就是如何最大程度地對(duì)非解冗余節(jié)點(diǎn)進(jìn)行剪枝,從而提高算法的效率.

3 結(jié)合子集刪減的碰集求解算法

在給出具體的算法之前,我們先介紹SE-Tree中葉節(jié)點(diǎn)在一些結(jié)構(gòu)中的性質(zhì).

3.1 SE-Tree中葉節(jié)點(diǎn)的特殊性質(zhì)及輔助剪枝樹(shù)

3.1.1 SE-Tree中葉節(jié)點(diǎn)的特殊性質(zhì)

根據(jù)推論2,若一個(gè)葉節(jié)點(diǎn)為冗余葉節(jié)點(diǎn),則這個(gè)節(jié)點(diǎn)對(duì)應(yīng)的分支上不存在碰集,即這條分支沒(méi)有必要進(jìn)行遍歷.

一種簡(jiǎn)便的方法就是在對(duì)每個(gè)分支進(jìn)行遍歷前,先對(duì)分支的葉節(jié)點(diǎn)進(jìn)行檢測(cè),若葉節(jié)點(diǎn)對(duì)應(yīng)的集合是碰集,則對(duì)該分支進(jìn)行遍歷,否則將該分支剪掉.注意,此時(shí)并不能說(shuō)明這條分支上所有的節(jié)點(diǎn)都是非解冗余節(jié)點(diǎn),但在非冗余節(jié)點(diǎn)為根的子樹(shù)下必有不少于1個(gè)非冗余葉節(jié)點(diǎn).因此對(duì)冗余葉節(jié)點(diǎn)所在分支進(jìn)行剪枝并不會(huì)導(dǎo)致分支上的非冗余節(jié)點(diǎn)被剪枝,其必然會(huì)在對(duì)其他分支的遍歷中被訪問(wèn).但在一棵SE-Tree中,葉節(jié)點(diǎn)的數(shù)量占總節(jié)點(diǎn)數(shù)的一半,此方法顯然十分低效.

定理1. 設(shè)節(jié)點(diǎn)A為SE-Tree中的一個(gè)葉節(jié)點(diǎn).若節(jié)點(diǎn)A不是尾葉節(jié)點(diǎn),則SE-Tree中至少存在1個(gè)葉節(jié)點(diǎn)B,使得葉節(jié)點(diǎn)B為節(jié)點(diǎn)A的真子集;若節(jié)點(diǎn)A不是頭葉節(jié)點(diǎn),則SE-Tree中至少存在1個(gè)葉節(jié)點(diǎn)C,使得葉節(jié)點(diǎn)C為節(jié)點(diǎn)A的真超集.

顯然,對(duì)于一個(gè)葉節(jié)點(diǎn),若其不是頭葉節(jié)點(diǎn),則頭葉節(jié)點(diǎn)是其真超集;若其不是尾葉節(jié)點(diǎn),則尾葉節(jié)點(diǎn)是其真子集.

通過(guò)定理1我們知道,若節(jié)點(diǎn)A為冗余葉節(jié)點(diǎn),且節(jié)點(diǎn)A不是尾葉節(jié)點(diǎn),那么必存在至少1個(gè)葉節(jié)點(diǎn)B,使得葉節(jié)點(diǎn)B為節(jié)點(diǎn)A的真子集.因?yàn)楣?jié)點(diǎn)A為非解冗余節(jié)點(diǎn),不是碰集,則其真子集自然也不是碰集,即葉節(jié)點(diǎn)B同為冗余葉節(jié)點(diǎn).若能通過(guò)對(duì)節(jié)點(diǎn)A的判斷將節(jié)點(diǎn)B對(duì)應(yīng)的分支剪掉,必將極大地提高算法效率.此時(shí),我們就需要引入一種新的結(jié)構(gòu)來(lái)進(jìn)行輔助剪枝.

3.1.2 輔助剪枝樹(shù)

定義7. 將一棵SE-Tree中的尾葉節(jié)點(diǎn)作為樹(shù)根,以剩余葉節(jié)點(diǎn)去掉該尾葉節(jié)點(diǎn)中的元素后余下的元素作為度量標(biāo)準(zhǔn),應(yīng)用與該SE-Tree相同的排序規(guī)則生成一棵樹(shù),稱(chēng)這棵樹(shù)為該SE-Tree的輔助剪枝樹(shù).

如圖2就是圖1中 SE-Tree的輔助剪枝樹(shù).

Fig. 2 Assistant pruning tree of example 1.圖2 例1對(duì)應(yīng)的輔助剪枝樹(shù)

因?yàn)檩o助剪枝樹(shù)是應(yīng)用與SE-Tree相似的規(guī)則生成的,所以擁有許多與SE-Tree一樣的性質(zhì).如每個(gè)節(jié)點(diǎn)都是其祖先節(jié)點(diǎn)的真超集;若一個(gè)節(jié)點(diǎn)不是碰集,則其所有的祖先節(jié)點(diǎn)都不是碰集.因此,當(dāng)我們發(fā)現(xiàn)輔助剪枝樹(shù)中的一個(gè)節(jié)點(diǎn)不是碰集時(shí),其祖先節(jié)點(diǎn)在SE-Tree中必為冗余葉節(jié)點(diǎn),它們對(duì)應(yīng)的分支也就都不需要進(jìn)行訪問(wèn).

通過(guò)觀察我們還會(huì)發(fā)現(xiàn):在SE-Tree中進(jìn)行深度優(yōu)先算法過(guò)程中對(duì)葉節(jié)點(diǎn)的訪問(wèn)順序,與在其對(duì)應(yīng)的輔助剪枝樹(shù)中后序遍歷訪問(wèn)節(jié)點(diǎn)的順序是一致的.這樣就可以對(duì)一些非解冗余節(jié)點(diǎn)進(jìn)行剪枝,減少需訪問(wèn)分支的數(shù)量.如在例1中,當(dāng)發(fā)現(xiàn)節(jié)點(diǎn){1,3,4}為非解冗余節(jié)點(diǎn)后就沒(méi)有必要對(duì){1,4}節(jié)點(diǎn)所在的分支進(jìn)行遍歷,可直接跳轉(zhuǎn)到對(duì){2,3,4}節(jié)點(diǎn)所在的分支進(jìn)行遍歷.

下面給出SE-Tree中結(jié)合輔助剪枝樹(shù)的深度優(yōu)先求解算法DFI-SE(deep first with improvement-SE)：

算法2. DFI-SE(F={S1,S2,…,Sm})

① 初始化：MHS=?,Node=?,Prune_node=

② Begin

③ While(1)

④ If (!(Leaf?Prune_node) )

⑤ While(1)

⑥Node=next(Node,Leaf)；

⑦ If (Node為碰集)

⑧ If (Node為極小碰集)

⑨MHS=MHS∪Node；

⑩ EndIf

3.1.3 多級(jí)輔助剪枝樹(shù)

結(jié)合輔助剪枝樹(shù)的深度優(yōu)先算法已經(jīng)能對(duì)部分冗余葉節(jié)點(diǎn)所在分支進(jìn)行剪枝,但剪枝效果十分有限.為了能夠?qū)⒓糁ψ畲蠡?下面引入多級(jí)輔助剪枝樹(shù)的概念.

定義8. 稱(chēng)定義7中得到的輔助剪枝樹(shù)為1級(jí)輔助剪枝樹(shù),將1級(jí)輔助剪枝樹(shù)中的葉節(jié)點(diǎn)按照定義7中的規(guī)則生成的樹(shù)稱(chēng)為2級(jí)輔助剪枝樹(shù),以此類(lèi)推可生成級(jí)別更高的輔助剪枝樹(shù).i級(jí)輔助剪枝樹(shù)用Ψi表示.當(dāng)輔助剪枝樹(shù)中只包含1個(gè)節(jié)點(diǎn)時(shí),無(wú)法生成更高級(jí)別的輔助剪枝樹(shù).

圖3為例1中SE-Tree的各級(jí)輔助剪枝樹(shù).

Fig. 3 Multi-level assistant pruning tree of example 1.圖3 例1對(duì)應(yīng)的各級(jí)輔助剪枝樹(shù)

通過(guò)觀察圖3,我們可以發(fā)現(xiàn)：每個(gè)輔助剪枝樹(shù)的根節(jié)點(diǎn)包含的元素為S中最后m個(gè)連續(xù)元素,其中m為輔助剪枝樹(shù)的級(jí)別.n級(jí)輔助剪枝樹(shù)的根節(jié)點(diǎn)P中包含S中的全部元素,其無(wú)子孫節(jié)點(diǎn),即n級(jí)輔助剪枝樹(shù)中只包含1個(gè)節(jié)點(diǎn).根據(jù)定義8,此時(shí)無(wú)法繼續(xù)生成n+1級(jí)輔助剪枝樹(shù).

多級(jí)輔助剪枝樹(shù)的引入,使得原本在1級(jí)輔助剪枝樹(shù)中無(wú)法被剪枝的非解冗余節(jié)點(diǎn)在滿(mǎn)足一些條件的情況下,可以在更高級(jí)別的輔助剪枝樹(shù)中被剪掉.例如冗余葉節(jié)點(diǎn){3,4}在1級(jí)輔助剪枝樹(shù)中為葉節(jié)點(diǎn),因此根據(jù)算法DFI-SE無(wú)法被剪枝,但其在2級(jí)輔助剪枝樹(shù)中為{1,3,4}的父節(jié)點(diǎn).因此當(dāng)發(fā)現(xiàn){1,3,4}為非解冗余節(jié)點(diǎn)后,根據(jù)2級(jí)輔助剪枝樹(shù){3,4}必為非解冗余節(jié)點(diǎn),其所在分支沒(méi)有遍歷的必要.

因?yàn)樵诙嗉?jí)輔助剪枝樹(shù)中,i+1級(jí)輔助剪枝樹(shù)中的節(jié)點(diǎn)為i級(jí)輔助剪枝樹(shù)中的所有葉節(jié)點(diǎn),所以級(jí)別較高的輔助剪枝樹(shù)中的節(jié)點(diǎn)必然出現(xiàn)在比其級(jí)別低的輔助剪枝樹(shù)中.這就引出了首次出現(xiàn)的概念.

定義9. 稱(chēng)包含節(jié)點(diǎn)A的最高級(jí)輔助剪枝樹(shù)為節(jié)點(diǎn)A的首次出現(xiàn)輔助剪枝樹(shù),記為ΥA;該輔助剪枝樹(shù)的級(jí)別為A的首次出現(xiàn)級(jí),用ΩA表示.

如例1中Υ{1,3,4}為圖3中的Ψ2,Ω{1,3,4}=2.

定義10. 一個(gè)有序集合從前至后順序地刪除一些元素,直至剩余元素都為連續(xù)元素,稱(chēng)此時(shí)剩余元素為該集合的尾元素.

由多級(jí)輔助剪枝樹(shù)的形成規(guī)則我們可以得到以下推論：

推論3. 一棵SE-Tree中某個(gè)葉節(jié)點(diǎn)A的首次出現(xiàn)級(jí)即為該節(jié)點(diǎn)中最大的尾元素個(gè)數(shù).

在此,我們需要先簡(jiǎn)單闡述在多級(jí)輔助剪枝樹(shù)中發(fā)現(xiàn)當(dāng)前節(jié)點(diǎn)為非解冗余節(jié)點(diǎn)后,下次算法迭代需遍歷分支對(duì)應(yīng)葉節(jié)點(diǎn)的選取方法:

當(dāng)發(fā)現(xiàn)葉節(jié)點(diǎn)A為冗余葉節(jié)點(diǎn)后,若葉節(jié)點(diǎn)A不是ΥA中的根節(jié)點(diǎn),則選取ΥA中節(jié)點(diǎn)A右側(cè)第1個(gè)葉節(jié)點(diǎn)作為下次檢測(cè)的葉節(jié)點(diǎn)；若節(jié)點(diǎn)A為ΥA中的根節(jié)點(diǎn),此時(shí)為特殊情況,將在3.2節(jié)中進(jìn)行說(shuō)明.

多級(jí)輔助剪枝樹(shù)的結(jié)構(gòu)特點(diǎn)保證了通過(guò)此方法被剪枝的葉節(jié)點(diǎn)都是葉節(jié)點(diǎn)A的真子集,即保證了方法的正確性.

3.2 結(jié)合SE-Tree結(jié)構(gòu)特征的極小碰集求解算法

3.1節(jié)中介紹了如何在基于SE-Tree的深度優(yōu)先算法中結(jié)合多級(jí)輔助剪枝樹(shù)對(duì)非解冗余節(jié)點(diǎn)進(jìn)行最大化剪枝,其主要是基于非碰集的子集仍為非碰集的思想.下面給出結(jié)合SE-Tree結(jié)構(gòu)特征的極小碰集求解算法SPHS(subset-pruning hitting set algorithm)的終止條件及算法描述.

定義11. 稱(chēng)一棵SE-Tree中任意節(jié)點(diǎn)W及其所有子孫節(jié)點(diǎn)所組成的子樹(shù)為K級(jí)子樹(shù),K為W中元素的個(gè)數(shù).

定理3. 當(dāng)以左優(yōu)先深度優(yōu)先遍歷一棵SE-Tree時(shí),若發(fā)現(xiàn)一個(gè)冗余葉節(jié)點(diǎn)為純節(jié)點(diǎn),則算法可以終止,當(dāng)前求得的極小碰集即為全部極小碰集.

證明. 設(shè)純?nèi)~節(jié)點(diǎn)A為冗余葉節(jié)點(diǎn).若純?nèi)~節(jié)點(diǎn)A為SE-Tree中的尾葉節(jié)點(diǎn),則SE-Tree中已無(wú)未遍歷節(jié)點(diǎn),算法應(yīng)終止；否則純?nèi)~節(jié)點(diǎn)A所在1級(jí)子樹(shù)的右側(cè)必有其他1級(jí)子樹(shù).從SE-Tree的結(jié)構(gòu)可知:

1) SE-Tree中每棵1級(jí)子樹(shù)中有且只有1個(gè)純?nèi)~節(jié)點(diǎn),該節(jié)點(diǎn)會(huì)出現(xiàn)在該子樹(shù)的最左側(cè)分支上,其包含了該子樹(shù)節(jié)點(diǎn)中可能出現(xiàn)的全部元素,因此,這個(gè)純?nèi)~節(jié)點(diǎn)是該1級(jí)子樹(shù)中所有其他葉節(jié)點(diǎn)的真超級(jí),若該純?nèi)~節(jié)點(diǎn)為冗余葉節(jié)點(diǎn),則該1級(jí)子樹(shù)中所有的葉節(jié)點(diǎn)都是冗余葉節(jié)點(diǎn);

2) 純?nèi)~節(jié)點(diǎn)A所在1級(jí)子樹(shù)右側(cè)所有1級(jí)子樹(shù)的純?nèi)~節(jié)點(diǎn)都是純?nèi)~節(jié)點(diǎn)A的真子集,即若純?nèi)~節(jié)點(diǎn)A為冗余葉節(jié)點(diǎn),則純?nèi)~節(jié)點(diǎn)A右側(cè)的所有純?nèi)~節(jié)點(diǎn)皆為冗余葉節(jié)點(diǎn).

綜合1)和2),若純?nèi)~節(jié)點(diǎn)A不是SE-Tree中的尾葉節(jié)點(diǎn),則其右側(cè)的所有葉節(jié)點(diǎn)都為冗余葉節(jié)點(diǎn),即純?nèi)~節(jié)點(diǎn)A右側(cè)的所有分支均不包含碰集節(jié)點(diǎn),算法可終止. 證畢.

算法SPHS中需要用到一個(gè)名為輔助剪枝表的結(jié)構(gòu)，其主要用來(lái)存儲(chǔ)各級(jí)輔助剪枝樹(shù)中最新遍歷到的冗余葉節(jié)點(diǎn).輔助剪枝表結(jié)構(gòu)如圖4所示:

Fig. 4 Structure of assistant pruning table.圖4 輔助剪枝表結(jié)構(gòu)

圖4中的Last_layer用來(lái)記錄最近遍歷到的冗余葉節(jié)點(diǎn)的首次出現(xiàn)級(jí).在算法SPHS中,會(huì)用當(dāng)前需遍歷分支對(duì)應(yīng)葉節(jié)點(diǎn)的首次出現(xiàn)級(jí)與Last_layer進(jìn)行比較.若當(dāng)前葉節(jié)點(diǎn)的首次出現(xiàn)級(jí)大于或等于Last_layer,則使用與當(dāng)前葉節(jié)點(diǎn)首次出現(xiàn)級(jí)相對(duì)應(yīng)的表位置存儲(chǔ)的信息對(duì)該葉節(jié)點(diǎn)進(jìn)行檢測(cè);否則,使用與Last_layer相對(duì)應(yīng)的表位置存儲(chǔ)的信息進(jìn)行檢測(cè).這主要是因?yàn)槭状纬霈F(xiàn)級(jí)較低的節(jié)點(diǎn)可能是首次出現(xiàn)級(jí)較高的節(jié)點(diǎn)的子集,而相反的情況則不會(huì)出現(xiàn).

下面給出SPHS的算法描述.

算法3. SPHS(F={S1,S2,…,Sm})

① 初始化：MHS=?,Node=?,

Prune_List[n+1]=?,Last_layer=0,

② Begin

③ While(1)

④ If (!(Leaf?Prune_List[max(ΩLeaf,Last_layer)]) )

⑤ While(1)

⑥Node=next(Node,Leaf)；

⑦ If (Node為碰集)

⑧ If (Node為極小碰集)

⑨MHS=MHS∪Node；

⑩ EndIf

Node；

這些都有效地保證了算法效率.在第4節(jié)中,我們會(huì)以多組實(shí)驗(yàn)數(shù)據(jù)對(duì)比的方式,分析說(shuō)明SPHS算法相較于Boolean算法的優(yōu)勢(shì).

4 實(shí)驗(yàn)結(jié)果

本節(jié)將使用SPHS算法與當(dāng)前效率較高的Boolean算法進(jìn)行比較,并給出2種算法在隨機(jī)生成測(cè)試用例下的實(shí)驗(yàn)結(jié)果.實(shí)驗(yàn)平臺(tái)如下: Windows XP操作系統(tǒng)、CPU AMD AthlonTM64 X2 Dual Core Processor 3600+ 1.9 GHz、2.00 GB RAM.

實(shí)驗(yàn)用例使用隨機(jī)生成器產(chǎn)生,輸入?yún)?shù)有元素個(gè)數(shù)m、集合簇中集合個(gè)數(shù)n以及元素在一個(gè)集合中出現(xiàn)的概率p.同一個(gè)用例中,所有元素的p均相等,每個(gè)集合包含元素的平均個(gè)數(shù)約等于mp.本文使用的實(shí)驗(yàn)用例共分為4組,每組元素個(gè)數(shù)固定,分別為30,25,20,15,各組均包含p取值0.05～0.94的19個(gè)用例,所有用例集合個(gè)數(shù)均為200.本文所有實(shí)驗(yàn)數(shù)據(jù)均為使用相同參數(shù)下獨(dú)立生成的10個(gè)用例進(jìn)行實(shí)驗(yàn)所得結(jié)果的平均值.

Fig. 6 Experimental comparison of the two algorithms based on diverse number of elements.圖6 不同元素個(gè)數(shù)實(shí)例下2種算法實(shí)驗(yàn)結(jié)果比較

從圖5我們可以看出，對(duì)于耗時(shí)較少的用例(2種算法運(yùn)行時(shí)間均低于0.2 s),Boolean算法占優(yōu)較多；但對(duì)于絕大多數(shù)其他用例,SPHS算法擁有較大優(yōu)勢(shì).尤其對(duì)于耗時(shí)較長(zhǎng)的用例(2種算法運(yùn)行時(shí)間均高于20 s),多數(shù)點(diǎn)已經(jīng)處于5倍對(duì)比線(xiàn)甚至10倍對(duì)比線(xiàn)的上方.不難發(fā)現(xiàn),對(duì)比Boolean算法,SPHS算法在耗時(shí)越長(zhǎng)的用例中優(yōu)勢(shì)較為明顯.接下來(lái),我們將進(jìn)一步分析出現(xiàn)這種現(xiàn)象的原因.

Fig. 5 Experimental comparison of SPHS and Boolean.圖5 SPHS算法與Boolean算法實(shí)驗(yàn)結(jié)果比較

圖6中各坐標(biāo)系橫軸表示元素出現(xiàn)概率p,MHS表示對(duì)應(yīng)實(shí)例的極小碰集數(shù)量,與右側(cè)縱軸相關(guān).通過(guò)圖6我們可以發(fā)現(xiàn),相對(duì)于Boolean算法,SPHS算法對(duì)于實(shí)例對(duì)應(yīng)的極小碰集數(shù)量的敏感度并不高,尤其在圖6(c)與圖6(d)中更為明顯,一些極小碰集數(shù)量上升的同時(shí),算法運(yùn)行時(shí)間卻發(fā)生了下降.我們還可以發(fā)現(xiàn)圖6(d)是唯一一個(gè)SPHS算法效率要差于Boolean算法的情況.這說(shuō)明,相對(duì)于Boolean算法,SPHS算法的優(yōu)勢(shì)主要集中在規(guī)模相對(duì)較高的問(wèn)題上(元素較多).

Fig. 7 Visit-proportion of SPHS based on diverse number of elements.圖7 SPHS算法訪問(wèn)分支數(shù)占總分支數(shù)的比例

Fig. 8 Experimental comparison of visit-proportion of SPHS and DF-SE.圖8 SPHS與DF-SE訪問(wèn)分支數(shù)對(duì)比

圖7各個(gè)坐標(biāo)系中各包含2個(gè)折線(xiàn)圖.其中SPHS表示SPHS算法訪問(wèn)分支數(shù)占該實(shí)例對(duì)應(yīng)的總分支數(shù)的比例,與左側(cè)縱軸相關(guān)；TIME為此組用例SPHS算法的CPU運(yùn)行時(shí)間,與右側(cè)縱軸相關(guān).從圖7中我們可以發(fā)現(xiàn),各組數(shù)據(jù)對(duì)應(yīng)的2條折線(xiàn)擬合度很高,這說(shuō)明使用訪問(wèn)分支數(shù)與剪枝分支數(shù)來(lái)衡量此算法的效率是合理的.通過(guò)對(duì)比各組實(shí)驗(yàn)數(shù)據(jù)我們還能夠發(fā)現(xiàn),當(dāng)用例元素個(gè)數(shù)增多時(shí),SPHS算法訪問(wèn)分支數(shù)占總分支數(shù)的比例有逐漸下降的趨勢(shì).也就是說(shuō),對(duì)于元素?cái)?shù)較大的用例,SPHS算法的剪枝比例較高.如圖7(d)中的最高點(diǎn)已接近0.4,而圖7(a)中的最高點(diǎn)僅在0.2附近.這與實(shí)驗(yàn)結(jié)果中所表現(xiàn)出來(lái)的在較難實(shí)例中SPHS算法更占優(yōu)的趨勢(shì)是相符的.

圖8給出了SPHS與DF-SE算法在各組實(shí)例中訪問(wèn)分支占總分支數(shù)比例.通過(guò)對(duì)比,我們可以更直觀地看出SPHS算法中所加策略對(duì)其算法效率的提升.我們可以發(fā)現(xiàn),對(duì)于各組元素出現(xiàn)概率p較小的實(shí)例,DF-SE算法幾乎需要訪問(wèn)所有的分支.這主要是未加入提前終止策略所導(dǎo)致的結(jié)果.

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

本文首先給出了基于SE-Tree結(jié)構(gòu)的深度優(yōu)先極小碰集求解算法DF-SE,通過(guò)對(duì)SE-Tree中葉節(jié)點(diǎn)的特殊性質(zhì)和算法執(zhí)行過(guò)程的分析,并結(jié)合現(xiàn)有碰集算法中有解冗余節(jié)點(diǎn)的特征,提出非解冗余節(jié)點(diǎn)概念.若能在算法執(zhí)行過(guò)程中對(duì)此類(lèi)節(jié)點(diǎn)進(jìn)行剪枝,算法效率將得到提高且不會(huì)對(duì)算法的正確性及完備性造成影響.針對(duì)此問(wèn)題,本文給出一種新型的輔助剪枝結(jié)構(gòu)——輔助剪枝樹(shù).通過(guò)將此結(jié)構(gòu)與基于SE-Tree結(jié)構(gòu)的深度優(yōu)先極小碰集求解算法相結(jié)合得到的DFI-SE算法,能夠?qū)Σ糠址墙馊哂喙?jié)點(diǎn)進(jìn)行剪枝.為進(jìn)一步提高算法效率,本文還通過(guò)對(duì)輔助剪枝樹(shù)結(jié)構(gòu)的遞歸定義得到了多級(jí)輔助剪枝樹(shù),并且在保證解的完備性的前提下給出了算法的提前終止條件,最終得到SPHS算法.該算法容易理解且易于實(shí)現(xiàn),雖然使用了SE-Tree以及多級(jí)輔助剪枝樹(shù),但實(shí)現(xiàn)過(guò)程中并不需要構(gòu)造樹(shù)結(jié)構(gòu),保證了算法較低的空間復(fù)雜度和較高的執(zhí)行效率.實(shí)驗(yàn)結(jié)果表明,對(duì)比當(dāng)前效率較高的Boolean算法,SPHS算法對(duì)于規(guī)模較大的問(wèn)題具有明顯優(yōu)勢(shì),對(duì)于部分較難問(wèn)題的求解效率甚至提高了1個(gè)數(shù)量級(jí)以上.

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

[2] Bonet B, Helmert M. Strengthening landmark heuristics via hitting sets[C] //Proc of the 19th European Conf on Artificial Intelligence. Amsterdam: IOS Press, 2010: 329-334

[3] Wotawa F. On the relationship between model-based debugging and program slicing[J]. Artificial Intelligence, 2002, 135(1): 125-143

[4] 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

[5] Wotawa F. A variant of Reiter's hitting-set algorithm[J]. Information Processing Letters, 2001, 79(1): 45-51

[6] Jiang Yunfei, Lin Li. Computing the minimal hitting set with binary HS-tree[J]. Journal of Software, 2002, 13(12): 2267-2274 (in Chinese)

(姜云飛, 林笠. 用對(duì)分HS-樹(shù)計(jì)算最小碰集[J]. 軟件學(xué)報(bào), 2002, 13(12): 2267-2274)

[7] Jiang Yunfei, Lin Li. The computation of 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)

[8] Ouyang Dantong, Ouyang Jihong, Cheng Xiaochun, et al. A method of computing hitting set in model-based diagnosis[J]. Chinese Journal of Scientific Instrument, 2004, 25(4): 605-608 (in Chinese)

(歐陽(yáng)丹彤, 歐陽(yáng)繼紅, 程曉春, 等. 基于模型診斷中計(jì)算碰集的方法[J]. 儀器儀表學(xué)報(bào), 2004, 25(4): 605-608)

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

[10]Chen Xiaomei, Meng Xiaofeng, Qiao Renxiao. Method of computing all minimal hitting set based on BNB-HSSE[J]. Chinese Journal of Scientific Instrument, 2010, 31(1): 61-67 (in Chinese)

(陳曉梅, 孟曉風(fēng), 喬仁曉. 基于BNB-HSSE計(jì)算全體碰集的方法[J]. 儀器儀表學(xué)報(bào), 2010, 31(1): 61-67)

[11]Zhang Liming, Ouyang Dantong, Zeng Hailin. Computing the minimal hitting set 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)

[12]Pill I, Quaritsch T. Optimizations for the Boolean approach to computing minimal hitting Sets[C] //Proc of the 20th European Conf on Artificial Intelligence. Amsterdam: IOS Press, 2012: 648-653

[13]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)

[14]Lin Li, Jiang Yunfei. Computing minimal hitting sets with genetic algorithm[C/OL] //Proc of the 13th Int Workshop on Principles of Diagnosis. 2002[2015-01-12]. https://www.researchgate.net/publication/235118684_Thirteenth_International_Workshop_on_Principles_of_Diagnosis_DX-2002

[15]Cincotti A, Cutello V, Pappalardo F. An ant-algorithm for the weighted minimum hitting set problem[C] //Proc of the 2003 IEEE Symp on Swarm Intelligence. Piscataway, NJ: IEEE, 2003: 1-5

[16]Huang Jie, Chen Lin, Zou Peng. Computing minimal diagnosis by compounded genetic and simulated annealing algorithm[J]. Journal of Software, 2004, 15(9): 1345-1350 (in Chinese)

(黃杰, 陳琳, 鄒鵬. 一種求解極小診斷的遺傳模擬退火算法[J]. 軟件學(xué)報(bào), 2004, 15(9): 1345-1350)

[17]Abreu R, Gemund A J C V. A low-cost approximate minimal hitting set algorithm and its application to model-based diagnosis[C] //Proc of the 8th Symp on Abstraction, Reformulation, and Approximation, Vol 9. Menlo Park, CA: AAAI, 2009: 2-9

[18]Zhou Gan, Feng Wenquan, Jiang Bofeng, et al. Computing minimal hitting set based on immune genetic algorithm[J]. International Journal of Modelling, Identification and Control, 2014, 21(1): 93-100

[19]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

[20]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

[21]Han B, Lee S J. Deriving minimal conflict sets by CS-tree with mark set in diagnosis from first principles[J]. IEEE Trans on Systems, Man, and Cybernetics: Cybernetics, 1999, 29(2): 281-286

[22]Rymon R. Search through systematic set enumeration[C] //Proc of the 3rd Int Conf on Principles of Knowledge Representation and Reasoning. San Francisco, CA: Morgan Kaufmann, 1992: 539-550

Liu Siguang, born in 1988. Master candidate at Jilin University. His main research interests include model-based diagnosis, SAT problem and automated reasoning.

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

Wang Yiyuan, born in 1988. PhD candidate at Jilin University. His main research interests include model-based diagnosis, SAT problem and automated reasoning (yiyuanwangjlu@126.com).

Jia Fengyu, born in 1991. Master candidate at Jilin University. His main research interests include model-based diagnosis, SAT problem and automated reasoning (jiafy13@mails.jlu.edu.cn).

Zhang Liming, born in 1980. PhD, post-doctor at Jilin University. His main research interests include model-based diagnosis, model checking and boolean satisfiability.

Algorithm of Computing Minimal Hitting Set Based on the Structural Feature of SE-Tree

Liu Siguang, Ouyang Dantong, Wang Yiyuan, Jia Fengyu, and Zhang Liming

(CollegeofComputerScienceandTechnology,JilinUniversity,Changchun130012) (KeyLaboratoryofSymbolicComputationandKnowledgeEngineering(JilinUniversity),MinistryofEducation,Changchun130012)

During the process of computing minimal hitting set (MHS) by SE-Tree, it will generate many redundant nodes that cannot be pruned by current SE-Tree based algorithms, which affects the efficiency of these algorithms, i.e., the higher the ratio of redundant nodes is, the greater likely the impact of algorithms has. In this paper, firstly we introduce the definition of redundant nodes by analyzing the characteristic of leaf-node in SE-Tree and the redundant nodes in solution space in existent algorithms. Secondly, on the basis of analyzing the structural feature of SE-Tree and the theory that the subset of non-hitting set is non-hitting set, we propose the concept of assistant pruning tree. Specially, the decision nodes are added into the assistant pruning tree, which can largely reduce the visit of non-solution space. Furthermore, in order to decrease the visit of non-solution space when computing larger problem as much as possible, the algorithm of computing minimal hitting set combining with multi-level assistant pruning tree is proposed. Finally, we set a reasonable termination condition to make our algorithm stop without losing correct solution as early as possible, and then prove its correctness. Results show that the proposed algorithm is easily implemented and efficient. Moreover, our algorithm significantly outperforms a state-of-the-art minimal hitting set algorithm Boolean, even up to one order of magnitude for some instances.

model-based diagnosis; minimal hitting set; SE-Tree; assistant pruning tree; non-solution space pruning

2015-05-28；

2016-02-16

國(guó)家自然科學(xué)基金項(xiàng)目(61133011,61402196,61272208,61003101,61170092)；中國(guó)博士后科學(xué)基金項(xiàng)目(2013M541302)；吉林省科技發(fā)展計(jì)劃基金項(xiàng)目(20140520067JH)；浙江師范大學(xué)計(jì)算機(jī)軟件與理論省級(jí)重中之重學(xué)科開(kāi)放基金項(xiàng)目(ZSDZZZZXK12)

張立明(limingzhang@jlu.edu.cn)

TP18

This work was supported by the National Natural Science Foundation of China (61133011,61402196,61272208,61003101,61170092), the China Postdoctoral Science Foundation (2013M541302), the Science and Technology Development Program of Jilin Province (20140520067JH), and the Provincial Key Disciplines Foundation of Computer Software and Theory of Zhejiang Normal University (ZSDZZZZXK12).