結合SE-Tree結構特征的極小碰集求解算法

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

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

?

結合SE-Tree結構特征的極小碰集求解算法

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

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

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

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

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

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

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

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

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

1 預備知識

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

1.1 基于模型診斷的相關概念

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

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

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

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].設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的相關概念及性質

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

Fig. 1 SE-Tree of S={1,2,3,4}.圖1 S={1,2,3,4}對應的SE-Tree

按上述規則生成的SE-Tree具有2個性質：

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

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

根據以上性質和碰集的定義,我們可以得到以下推論：

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

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

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

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

定義4. 若一個節點內所有元素都是連續的,則稱此節點為純節點(只含有1個元素的節點是純節點).若一個葉節點是純節點,則稱該葉節點為純葉節點.

例如圖1中,{2,4}不是純節點,{2,3}是純節點,{2,3,4}是純葉節點.

定義5. 稱SE-Tree中最左側的葉節點為頭葉節點;最右側葉節點為尾葉節點.

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

顯然,頭葉節點和尾葉節點都是純葉節點.并且,頭葉節點包含了該SE-Tree任意節點中可出現的全部元素.

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

2 基于SE-Tree的深度優先碰集求解算法

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

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

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

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

例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個節點,其中{1,2,3},{2,3,4}為極小碰集節點.通過觀察可以發現對{1,2,4},{1,3},{1,3,4},{1,4},{2,4},{3},{3,4},{4}這8個節點對應分支的遍歷沒有碰集產生,即這些節點是冗余節點.

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

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

3 結合子集刪減的碰集求解算法

在給出具體的算法之前,我們先介紹SE-Tree中葉節點在一些結構中的性質.

3.1 SE-Tree中葉節點的特殊性質及輔助剪枝樹

3.1.1 SE-Tree中葉節點的特殊性質

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

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

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

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

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

3.1.2 輔助剪枝樹

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

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

Fig. 2 Assistant pruning tree of example 1.圖2 例1對應的輔助剪枝樹

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

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

下面給出SE-Tree中結合輔助剪枝樹的深度優先求解算法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 多級輔助剪枝樹

結合輔助剪枝樹的深度優先算法已經能對部分冗余葉節點所在分支進行剪枝,但剪枝效果十分有限.為了能夠將剪枝最大化,下面引入多級輔助剪枝樹的概念.

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

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

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

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

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

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

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

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

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

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

推論3. 一棵SE-Tree中某個葉節點A的首次出現級即為該節點中最大的尾元素個數.

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

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

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

3.2 結合SE-Tree結構特征的極小碰集求解算法

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

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

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

證明. 設純葉節點A為冗余葉節點.若純葉節點A為SE-Tree中的尾葉節點,則SE-Tree中已無未遍歷節點,算法應終止；否則純葉節點A所在1級子樹的右側必有其他1級子樹.從SE-Tree的結構可知:

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

2) 純葉節點A所在1級子樹右側所有1級子樹的純葉節點都是純葉節點A的真子集,即若純葉節點A為冗余葉節點,則純葉節點A右側的所有純葉節點皆為冗余葉節點.

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

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

Fig. 4 Structure of assistant pruning table.圖4 輔助剪枝表結構

圖4中的Last_layer用來記錄最近遍歷到的冗余葉節點的首次出現級.在算法SPHS中,會用當前需遍歷分支對應葉節點的首次出現級與Last_layer進行比較.若當前葉節點的首次出現級大于或等于Last_layer,則使用與當前葉節點首次出現級相對應的表位置存儲的信息對該葉節點進行檢測;否則,使用與Last_layer相對應的表位置存儲的信息進行檢測.這主要是因為首次出現級較低的節點可能是首次出現級較高的節點的子集,而相反的情況則不會出現.

下面給出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節中,我們會以多組實驗數據對比的方式,分析說明SPHS算法相較于Boolean算法的優勢.

4 實驗結果

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

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

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

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

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

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

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

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

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

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

5 結束語

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

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

(姜云飛, 林笠. 用布爾代數方法計算最小碰集[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)

(張立明, 歐陽丹彤, 曾海林. 基于動態極大度的極小碰集求解方法[J]. 計算機研究與發展, 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]. 計算機研究與發展, 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)；吉林省科技發展計劃基金項目(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).