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

劉思光 歐陽丹彤 王藝源 賈鳳雨 張立明

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

?

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

劉思光 歐陽丹彤 王藝源 賈鳳雨 張立明

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

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

基于模型診斷;極小碰集;集合枚舉樹;輔助剪枝樹;無解空間剪枝

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

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

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

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

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

1 預(yù)備知識

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

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

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

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

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

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

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

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

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

2) 對于任意一個Si∈F,都有H∩Si≠?；

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

我們可以發(fā)現(xiàn),以上算法可以看作這樣一個過程：每次迭代是對一個葉節(jié)點所在分支中的一部分進行遍歷.此處,一個分支由根節(jié)點到這個葉節(jié)點路徑上的所有節(jié)點構(gòu)成.迭代開始于本分支與上次進行迭代的分支的最后一個共有節(jié)點的下一個節(jié)點.在沒有遇到碰集節(jié)點的情況下,結(jié)束于本分支的葉節(jié)點;否則結(jié)束于第1個碰集節(jié)點.下面給出基于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é)點,Node為當前遍歷節(jié)點,函數(shù)next用于計算當前分支上下一個需要遍歷的節(jié)點,函數(shù)next_begin用于計算本次迭代遍歷分支與下次迭代需遍歷分支的最后一個共有節(jié)點,函數(shù)next_end用于計算下次迭代需遍歷分支上的葉節(jié)點.

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

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

其SE-Tree同圖1給出的一樣.求解過程中,需要按順序遍歷{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個節(jié)點,其中{1,2,3},{2,3,4}為極小碰集節(jié)點.通過觀察可以發(fā)現(xiàn)對{1,2,4},{1,3},{1,3,4},{1,4},{2,4},{3},{3,4},{4}這8個節(jié)點對應(yīng)分支的遍歷沒有碰集產(chǎn)生,即這些節(jié)點是冗余節(jié)點.

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

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

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

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

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

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

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

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

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

顯然,對于一個葉節(jié)點,若其不是頭葉節(jié)點,則頭葉節(jié)點是其真超集;若其不是尾葉節(jié)點,則尾葉節(jié)點是其真子集.

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

3.1.2 輔助剪枝樹

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

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

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

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

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

下面給出SE-Tree中結(jié)合輔助剪枝樹的深度優(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 多級輔助剪枝樹

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

定義8. 稱定義7中得到的輔助剪枝樹為1級輔助剪枝樹,將1級輔助剪枝樹中的葉節(jié)點按照定義7中的規(guī)則生成的樹稱為2級輔助剪枝樹,以此類推可生成級別更高的輔助剪枝樹.i級輔助剪枝樹用Ψi表示.當輔助剪枝樹中只包含1個節(jié)點時,無法生成更高級別的輔助剪枝樹.

圖3為例1中SE-Tree的各級輔助剪枝樹.

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

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

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

因為在多級輔助剪枝樹中,i+1級輔助剪枝樹中的節(jié)點為i級輔助剪枝樹中的所有葉節(jié)點,所以級別較高的輔助剪枝樹中的節(jié)點必然出現(xiàn)在比其級別低的輔助剪枝樹中.這就引出了首次出現(xiàn)的概念.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖4中的Last_layer用來記錄最近遍歷到的冗余葉節(jié)點的首次出現(xiàn)級.在算法SPHS中,會用當前需遍歷分支對應(yīng)葉節(jié)點的首次出現(xiàn)級與Last_layer進行比較.若當前葉節(jié)點的首次出現(xiàn)級大于或等于Last_layer,則使用與當前葉節(jié)點首次出現(xiàn)級相對應(yīng)的表位置存儲的信息對該葉節(jié)點進行檢測;否則,使用與Last_layer相對應(yīng)的表位置存儲的信息進行檢測.這主要是因為首次出現(xiàn)級較低的節(jié)點可能是首次出現(xiàn)級較高的節(jié)點的子集,而相反的情況則不會出現(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é)中,我們會以多組實驗數(shù)據(jù)對比的方式,分析說明SPHS算法相較于Boolean算法的優(yōu)勢.

4 實驗結(jié)果

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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

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

(姜云飛, 林笠. 用對分HS-樹計算最小碰集[J]. 軟件學報, 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]. 計算機學報, 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)

(歐陽丹彤, 歐陽繼紅, 程曉春, 等. 基于模型診斷中計算碰集的方法[J]. 儀器儀表學報, 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)

(陳曉梅, 孟曉風, 喬仁曉. 基于BNB-HSSE計算全體碰集的方法[J]. 儀器儀表學報, 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)

(張立明, 歐陽丹彤, 曾海林. 基于動態(tài)極大度的極小碰集求解方法[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)

(王藝源, 歐陽丹彤, 張立明, 等. 利用CSP求解極小碰集的方法[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]. 軟件學報, 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

國家自然科學基金項目(61133011,61402196,61272208,61003101,61170092)；中國博士后科學基金項目(2013M541302)；吉林省科技發(fā)展計劃基金項目(20140520067JH)；浙江師范大學計算機軟件與理論省級重中之重學科開放基金項目(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).