王 肖，趙相福

（浙江師范大學(xué) 數(shù)理與信息工程學(xué)院，浙江 金華 321004）

1 問題的提出

基于模型的診斷（Model-Based Diagnosis，MBD）［1］作為國內(nèi)外研究的熱點(diǎn)，有力地克服了傳統(tǒng)故障診斷方法的不足（即存在知識(shí)獲取瓶頸，復(fù)雜度高），是一項(xiàng)全新的、智能化的推理技術(shù)，在人工智能的發(fā)展上有強(qiáng)大的推動(dòng)力。如圖1［2］所示，MBD的主要過程整體分為三步：①為系統(tǒng)建立正確、合適的模型，一般使用一階邏輯語句（first-order logic statements）建立模型；②借助傳感器等觀測(cè)系統(tǒng)的實(shí)際表現(xiàn)行為，同時(shí)使用邏輯推理導(dǎo)出模型系統(tǒng)的預(yù)測(cè)行為，判定這兩種行為是否相容；③如果實(shí)際行為和預(yù)測(cè)行為不相容（有差異），則表明該系統(tǒng)不能按照正常原理運(yùn)行，可以借助模型診斷的主要方法推理確定引發(fā)故障的部件集合。

假設(shè)給定一個(gè)系統(tǒng)模型，該模型是由一階邏輯語句建立起來的，則從系統(tǒng)模型和由傳感器等獲得的實(shí)際觀測(cè)出發(fā)，利用基于假設(shè)的真值維護(hù)系統(tǒng)（Assumption-based Truth Maintenance System，ATMS）［3］、定理證明器（Theorem Prover，TP）等方法，找出所有沖突部件的集合，計(jì)算極小沖突集，再根據(jù)所有極小沖突集計(jì)算其極小碰集，這些極小碰集就是極小候選診斷，可以解釋系統(tǒng)故障的原因。容易看出，極小沖突集和極小碰集的計(jì)算是模型診斷中兩個(gè)至關(guān)重要的步驟，本文主要關(guān)注極小碰集求解的算法。

越來越多的專家學(xué)者對(duì)極小碰集求解方法進(jìn)行了全面深入的討論和研究，目前有許多改進(jìn)的方法，每種方法都有其適用范圍和各自的優(yōu)點(diǎn)與不足。Reiter最早提出經(jīng)典的HS-tree［4］方法計(jì)算所有極小碰集，但該方法產(chǎn)生了較多的中間節(jié)點(diǎn)，因此空間復(fù)雜度較高，計(jì)算量也相對(duì)較大，加入的剪枝規(guī)則會(huì)導(dǎo)致部分真解丟失；林笠等對(duì)HS-tree進(jìn)行改進(jìn)，提出BHS-tree［5］方法，相比HS-tree方法效率較高，但該方法不能直接產(chǎn)生所有極小碰集，需要自底向上進(jìn)行遞歸，同時(shí)去掉包含極小碰集的真超集，才能得到所有極小碰集，因此占用了更多的內(nèi)存空間，其時(shí)間復(fù)雜度相對(duì)較高；由趙相福等提出的HSSEtree［6］算法和顯示枚舉法比較接近，空間復(fù)雜度較高，運(yùn)算量會(huì)隨沖突集個(gè)數(shù)的增加而急劇增加。

針對(duì)這些問題，本文提出了CHS-tree（cardinality-based hitting set-tree）方法，在該方法的求解過程中，每次選擇當(dāng)前集合簇中勢(shì)最小的集合進(jìn)行擴(kuò)展，并借助集合簇中元素出現(xiàn)的頻率作為輔助判斷，不斷降低問題求解規(guī)模，然后依次求出不包含該擴(kuò)展集合中各元素的集合簇的所有極小碰集。該方法適用于規(guī)模較大、各元素出現(xiàn)頻率較高的數(shù)據(jù)，通過對(duì)最小勢(shì)的選擇和相關(guān)集合的化簡(jiǎn)，使其產(chǎn)生較少的中間節(jié)點(diǎn)。另外，編程實(shí)現(xiàn)時(shí)，可以動(dòng)態(tài)地申請(qǐng)空間和釋放空間，進(jìn)而提高求解效率。一般情況下，CHS-tree方法求解效率較高，在給定特殊集合簇（集合的勢(shì)不相等，不同集合中包含的相同元素較多）的情況下，其效率高于當(dāng)前求解效率最高的Boolean［7］方法。

2 基本原理

基于模型診斷的基本原理如下：

定義1［4］系統(tǒng)。用三元組（SD，COMPS，OBS）表示一個(gè)待診斷系統(tǒng)，其中：SD 為一階謂詞公式描述的系統(tǒng)的結(jié)構(gòu)、行為、功能、連接關(guān)系等；COMPS 為常量集合｛c1，c2，…，cn｝表示的系統(tǒng)的所有組成元件；OBS 為一階謂詞公式表示的系統(tǒng)的觀測(cè)集合。

定義2［4］沖突集。給定一個(gè)模型，如果它滿足SD∪OBS∪｛?AB（c1），?AB（c2），…，?AB（cn）｝不相容，說明系統(tǒng)存在故障，則元件集｛c1，c2，…，cn｝是系統(tǒng)的一個(gè)沖突元件集CS，其中ci∈COMPS，AB（ci）表示元件ci當(dāng)前工作不正常（abnormally）。

給定一沖突集C，如果C 的所有真子集都不是沖突集，則C 為極小沖突集MCS［8］。

定義3［4］碰集。設(shè)F 是集合簇，集合S 是F的元素，如果存在集合H，使得H 滿足∈F，都有H ∩S ≠?兩個(gè)條件，則稱H 是F 的一個(gè)碰集HS［9］。

給定一碰集F，如果F 的所有真子集都不是碰集，則F 為極小碰集MHS，為表示方便，在不引起歧義的情況下，以后也用MHS（F）表示集合簇F 的所有極小碰集。

Reiter最早提出用HS-tree計(jì)算極小碰集，其基本算法如下［4］：

（1）如果給定沖突集F，則先將F 化簡(jiǎn)，即將F中的所有真超集刪除。

（2）如果F 是空集，則將其根節(jié)點(diǎn)標(biāo)記為“√”，否則用集合簇F 的一個(gè)集合標(biāo)記。

（3）如果n 是HS-tree的一個(gè)節(jié)點(diǎn)，則H（n）定義為從根節(jié)點(diǎn)到n 路徑上的邊緣標(biāo)簽；如果n 被標(biāo)記為“√”，則其在HS-tree中沒有后繼節(jié)點(diǎn)；如果n被F 中的一個(gè)集合Σ 標(biāo)記，?a∈Σ，則n 都通過邊沿標(biāo)簽a 和一個(gè)后繼節(jié)點(diǎn)na相連；如果存在集合S∈F，且滿足S∩H（na）=｛｝，則na的標(biāo)簽為該集合S，否則na的標(biāo)簽是“√”。

例1 給定一個(gè)沖突集簇CS=｛｛2，4，5｝，｛1，2，3｝，｛1，3，5｝，｛2，4，6｝，｛2，4｝，｛2，3，5｝，｛1，6｝｝，計(jì)算CS的所有極小碰集為｛1，2｝，｛2，3，6｝，｛2，5，6｝，｛1，3，4｝，｛1，4，5｝，｛3，4，6｝。

用Reiter的算法構(gòu)造的HS-tree如圖2所示。可以看出，用HS-tree方法計(jì)算所有極小碰集時(shí)，不但產(chǎn)生的節(jié)點(diǎn)數(shù)很多，而且剪枝規(guī)則比較繁瑣，容易丟失真解，求解效率較低。

3 用CHS-tree計(jì)算極小碰集

3.1 相關(guān)的基本概念

在用CHS-tree方法計(jì)算極小碰集的過程中，涉及的幾個(gè)基本概念和相關(guān)命題如下：

定義4 元素的關(guān)聯(lián)集合。對(duì)于集合S，若元素e∈S，則稱e與S 相關(guān)聯(lián)。用Rcount（F，e）表示集合簇F 中與元素e 相關(guān)聯(lián)（correlation）的集合的個(gè)數(shù)，即元素e在集合簇F 中出現(xiàn)的頻率。

定義5 有限集合的勢(shì)。有限集合的勢(shì)（cardinality）定義為該集合中元素的個(gè)數(shù)，即集合的勢(shì)是用來度量集合規(guī)模大小的屬性的。如集合A=｛a，b，c，d｝，則集合A 的勢(shì)為4。

定義6 若集合S1和S2滿足S2?S1，則稱S1為S2的真超集。例如S1=｛a，b，c，d｝，S2=｛a，c｝，則S1是S2的真超集。

命題1 給定一個(gè)非空集合簇F，若存在集合S∈F，集合S′∈F，并且S ?S′，則有MHS（F-｛S′｝）=MHS（F），即F -｛S′｝與F 有相同的極小碰集。

證明

（1）先證MHS（F -｛S′｝）?MHS（F）。

2）?x∈F-｛S′｝，H∩x≠?。因?yàn)镾∈F，且S ≠S′（因?yàn)镾 ?S′），S∈F-｛S′｝，H∩S≠?。

又因?yàn)镾?S′，所以H∩S′≠?，有?x∈（F-｛S′｝）∪｛S′｝，H ∩x≠?。于是得?x∈F，H ∩x≠?。

綜合上述兩條，根據(jù)碰集的定義可知H ∈MHS（F），因此有MHS（F -｛S′｝）?MHS（F）。

（2）再證MHS（F）?MHS（F -｛S′｝）。

?H∈MHS（F），根據(jù)碰集的定義有：

2）?x∈F，H ∩x≠?。顯然有?x∈F-｛S′｝，H∩x≠?。

綜合上述兩條，根據(jù)碰集的定義可知H ∈MHS（F-｛S′｝）。因此有MHS（F）?MHS（F -｛S′｝）。

例如：集合簇F=｛｛a，b｝，｛a，c｝，｛a，b，d｝｝，集合S=｛a，b｝，集合S′=｛a，b，d｝。則F-｛S′｝=｛｛a，b｝，｛a，c｝｝。

F 的所有極小碰集為｛a｝，｛b，c｝，F(xiàn)-｛S′｝的所有極小碰集為｛a｝，｛b，c｝。

3.2 CHS-tree算法基本步驟

（1）CHS-tree算法步驟

步驟1 對(duì)集合簇F 進(jìn)行化簡(jiǎn)，去掉F 中的真超集。

步驟2 先找到F 中勢(shì)最小的集合作為擴(kuò)展節(jié)點(diǎn)。如果某幾個(gè)集合的最小勢(shì)相等，則找出元素出現(xiàn)頻率最大的集合作為擴(kuò)展節(jié)點(diǎn)。

步驟3 在化簡(jiǎn)后的集合簇F 中，對(duì)于勢(shì)最小的集合CS=｛a1，a2，…，am｝，首先刪除F 中包含a1的集合，返回步驟1，直到F 變?yōu)榭占?，……，依次類比，直至刪除F 中包含am的集合。

步驟4 從根節(jié)點(diǎn)到葉節(jié)點(diǎn)進(jìn)行遍歷，每條路徑構(gòu)成一個(gè)碰集，對(duì)其進(jìn)行化簡(jiǎn)（去掉真超集），得到所有極小碰集。

用CHS-tree方法計(jì)算所有小碰集的優(yōu)勢(shì)及算法復(fù)雜性分析如下：

1）用CHS-tree方法計(jì)算所有極小碰集時(shí)，考慮從集合的最小勢(shì)出發(fā)可以減少節(jié)點(diǎn)數(shù)目的產(chǎn)生，集合的勢(shì)越小，分支節(jié)點(diǎn)越少。

2）用CHS-tree計(jì)算所有極小碰集中，考慮與元素相關(guān)聯(lián)集合的數(shù)目也是為了減少節(jié)點(diǎn)數(shù)目的產(chǎn)生。與元素相關(guān)聯(lián)的集合數(shù)越多，被刪掉的包含某一元素的集合越多，剩余集合越少，節(jié)點(diǎn)數(shù)目也相應(yīng)越少。

用CHS-tree方法計(jì)算極小碰集的過程中，每次選擇沖突集簇中勢(shì)最小的集合，并以此作為擴(kuò)展節(jié)點(diǎn)，以保證樹的寬度最小，同時(shí)按照深度優(yōu)先的方法分別刪除包含擴(kuò)展集合中每一個(gè)元素的集合，使得需要考慮的沖突集不斷減少，樹的深度也不斷減小。該方法類似于遞歸法，但是加入的規(guī)則使算法收斂速度加快，從而提高了效率。該方法又類似于枚舉法，當(dāng)集合簇成為空集時(shí)算法終止，因此一定可以得到所有極小碰集。

（2）算法復(fù)雜性分析

CHS-tree方法的時(shí)間復(fù)雜度及空間復(fù)雜度都與產(chǎn)生節(jié)點(diǎn)的個(gè)數(shù)有關(guān)。通過刪除F 中與帶擴(kuò)展集合中各元素相關(guān)聯(lián)的集合，使得F 不斷減小，樹的深度隨之減小，同時(shí)刪除樹的同一層中已出現(xiàn)過的終止節(jié)點(diǎn)元素，使得樹的寬度隨之減小。這樣可以避免產(chǎn)生大量冗余節(jié)點(diǎn)，從而降低算法復(fù)雜度，尤其是時(shí)間復(fù)雜度。

4 實(shí)例執(zhí)行及結(jié)果驗(yàn)證

按照CHS-tree方法的基本求解步驟，通過一個(gè)實(shí)例具體說明算法的執(zhí)行過程，找出所有極小碰集，并對(duì)結(jié)果進(jìn)行驗(yàn)證（基本過程也可參照?qǐng)D3）。

例2 使用CHS-tree方法求集合簇F=｛｛2，4，5｝，｛1，2，3｝，｛1，3，5｝，｛2，4，6｝，｛2，4｝，｛2，3，5｝，｛1，6｝｝的所有極小碰集。

（1）將F 中為其他集合超集的集合刪除，即刪除｛2，4，5｝｛2，4，6｝，因?yàn)樗鼈兪羌希?，4｝的超集。剩余集合組成一個(gè)新的集合簇F′=｛｛1，2，3｝，｛1，3，5｝，｛2，4｝，｛2，3，5｝，｛1，6｝｝。

（2）找出F′中勢(shì)最小的集合為｛2，4｝和｛1，6｝。分別統(tǒng)計(jì)F 中與元素2，4，1，6相關(guān)聯(lián)的集合的個(gè)數(shù)為3，1，3，1。由于元素2和4屬于同一集合，與它們相關(guān)聯(lián)的集合個(gè)數(shù)之和為4；元素1和6也屬于同一集合，與它們相關(guān)聯(lián)的集合個(gè)數(shù)之和為4，個(gè)數(shù)之和相等。因此從集合｛2，4｝和｛1，6｝中任意選一個(gè)集合作為根節(jié)點(diǎn)進(jìn)行擴(kuò)展，假設(shè)選擇集合｛2，4｝。

（3）刪除F′中包含2 的集合，剩余集合｛1，3，5｝，｛1，6｝構(gòu)成一個(gè)新的集合簇F1，選擇F1中勢(shì)最小的集合｛1，6｝進(jìn)行擴(kuò)展；刪除F1中包含1 的集合，集合簇變?yōu)榭占?為終止節(jié)點(diǎn)；刪除F1中包含6的集合，剩余集合為｛1，3，5｝；去掉元素1（1在左邊碰集中已經(jīng)出現(xiàn)），集合變?yōu)椋?，5｝，對(duì)集合｛3，5｝進(jìn)行擴(kuò)展；刪除元素3，集合簇為空集，3為終止節(jié)點(diǎn)；刪除元素5，集合簇為空集，5為終止節(jié)點(diǎn)。

（4）刪除F′中包含4的集合，集合簇為｛｛1，2，3｝，｛1，3，5｝，｛2，3，5｝，｛1，6｝｝，去掉集合中的元素2（2和4在同一層，包含2的碰集已經(jīng)求出），得到新的集合簇F2=｛｛1，3｝，｛1，3，5｝，｛3，5｝，｛1，6｝｝。

（5）對(duì)F2去超集后為F′2=｛｛1，3｝，｛3，5｝，｛1，6｝｝，分別統(tǒng)計(jì)與元素1，3，5，6相關(guān)聯(lián)的集合的個(gè)數(shù)為2，2，1，1。因?yàn)樵?和3屬于同一集合，與它們相關(guān)聯(lián)的集合個(gè)數(shù)之和為4，和最大，所以對(duì)集合｛1，3｝進(jìn)行擴(kuò)展。

（6）刪除F′2中包含元素1的集合，剩余集合為｛3，5｝，對(duì)集合｛3，5｝進(jìn)行擴(kuò)展；刪除包含元素3的集合，集合簇為空集，故3為終止節(jié)點(diǎn)；刪除元素包含元素5的集合，集合簇為空集，故5為終止節(jié)點(diǎn)；去掉F′2中包含3的集合，剩余集合為｛1，6｝，去掉元素1（1和3在同一層，包含1的碰集已經(jīng)求出），得到集合｛6｝，對(duì)6進(jìn)行擴(kuò)展；刪除包含元素6的集合，集合簇變?yōu)榭占?為終止節(jié)點(diǎn)。

（7）分別從根節(jié)點(diǎn)到葉節(jié)點(diǎn)進(jìn)行遍歷，每條路徑上的元素組成一個(gè)集合，這些集合構(gòu)成了所有極小碰集MHSs，即｛2，1｝，｛2，6，3｝，｛2，6，5｝，｛4，1，3｝，｛4，1，5｝，｛4，3，6｝，如圖3所示。

從圖3可以看出，用CHS-tree算法得到的所有極小碰集為｛2，1｝，｛2，6，3｝，｛2，6，5｝，｛4，1，3｝，｛4，1，5｝，｛4，3，6｝，此結(jié)果與Reiter方法的結(jié)果一致。

需要說明的是，｛2，4｝是最小沖突集中勢(shì)最小的集合，它包含的所有元素為2和4。以｛2，4｝為根節(jié)點(diǎn)進(jìn)行擴(kuò)展，樹的左邊葉子節(jié)點(diǎn)構(gòu)成了極小碰集中所有包含2的集合，樹的右邊葉子節(jié)點(diǎn)構(gòu)成碰集中所有包含4的集合。整棵樹的節(jié)點(diǎn)所在的路徑就構(gòu)成所給集合簇的所有碰集。

5 相關(guān)算法的比較

5.1 CHS-tree和HS-tree算法比較

CHS-tree算法和HS-tree算法相比，具有以下優(yōu)點(diǎn)：

（1）CHS-tree根據(jù)集合的勢(shì)以及與集合相關(guān)聯(lián)元素的個(gè)數(shù)來選擇擴(kuò)展節(jié)點(diǎn)，集合的勢(shì)越小，樹的寬度越??；同時(shí)，與某元素相關(guān)聯(lián)的集合的個(gè)數(shù)越多，刪掉的集合就越多，需要考慮的集合相對(duì)越少。相對(duì)于Reiter早期的HS-tree，CHS-tree產(chǎn)生的樹的節(jié)點(diǎn)數(shù)明顯減少，因此算法的時(shí)間和空間復(fù)雜度也隨之降低。

（2）對(duì)于給定的任意集合簇，CHS-tree算法第一步先去超集，這樣可以減少節(jié)點(diǎn)數(shù)目和循環(huán)次數(shù)，提高效率。

（3）在生成CHS-tree時(shí)，每增加一層，集合簇的個(gè)數(shù)就會(huì)減少，直到出現(xiàn)空集，因此算法可以終止，具有可行性。

5.2 CHS-tree和BHS-tree算法及HSSE-tree算法比較

CHS-tree 算 法、BHS-tree 算 法 和HSSE-tree算法均是在HS-tree算法的基礎(chǔ)上做出的相關(guān)改進(jìn)，對(duì)這幾種方法進(jìn)一步討論如下：

（1）CHS-tree能直接產(chǎn)生所有碰集，即每個(gè)分支節(jié)點(diǎn)上的元素組成的集合構(gòu)成一個(gè)碰集；BHStree算法不能直接產(chǎn)生出碰集，需要自底向上遞歸才能得到所有碰集，從而占用更多內(nèi)存空間，時(shí)間復(fù)雜度較高。

（2）對(duì)一些特殊的集合簇，例如集合簇｛｛1，2，3，4｝，｛5，6，7，8｝，｛9，10，11，12｝｝，F(xiàn) 中各個(gè)集合的交集為空集，則用CHS-tree算法實(shí)現(xiàn)效率較高，由于很多擴(kuò)展節(jié)點(diǎn)都可以重用，減少了對(duì)集合簇中集合的訪問次數(shù)。

（3）HSSE-tree算法和顯示枚舉法較為類似，其運(yùn)算量會(huì)隨問題規(guī)模的增大而急劇增加。CHStree算法可以根據(jù)與元素相關(guān)聯(lián)的集合個(gè)數(shù)，在求解過程中將問題規(guī)模不斷減小，從而提高求解效率。

5.3 統(tǒng)計(jì)分析

為了進(jìn)行算法效率的驗(yàn)證比較，假設(shè)集合簇F為｛0，1，…，m｝，｛1，2，…，m+1｝，｛2，3，…，m+2｝，｛3，4，…，m+2，0｝，…，然后在計(jì)算機(jī)（Intel（R）Core（TM）2Quad CPU 2.66GHz，2.66GHz，2.00GB內(nèi)存）Windows XP 操作系統(tǒng)下，采用Microsoft Visual C++6.0 編程來比較BHS-tree，Boolean，HSSE-tree和本文所提CHS-tree的計(jì)算效率，運(yùn)行結(jié)果如表1、圖4和圖5所示。

表1 CHS-tree，BHS-tree，Boolean，HSSE-tree運(yùn)行時(shí)間比較

續(xù)表1

從表1 和圖4 可以看出，相對(duì)于BHS-tree和HSSE-tree算法，本文提出的CHS-tree算法的運(yùn)行效率有明顯提高，尤其是與目前效率最高的Boolean方法相比（如圖5），CHS-tree方法的求解速度也較快，對(duì)于每組沖突集，時(shí)間都大大減小，效率提高了近三倍。并且在給定特定沖突集的情況下，運(yùn)行時(shí)間比較穩(wěn)定，不會(huì)隨著沖突集中元素個(gè)數(shù)的增加而急劇增加。

此外，CHS-tree還具有以下特征：

（1）當(dāng)沖突集中各元素出現(xiàn)的頻率較高時(shí)，CHS-tree的節(jié)點(diǎn)數(shù)量相對(duì)較少，運(yùn)行時(shí)間最快。如F=｛｛0，1，2｝，｛1，2，3｝，｛2，3，4，0｝，｛3，4，0，1｝｝。

（2）一般情況下，運(yùn)行時(shí)間會(huì)隨沖突集簇中元素個(gè)數(shù)的增加而增加。對(duì)于一些特殊的集合簇，如F=｛｛0，1，2，3｝，｛4，5，6，7｝，｛8，9，10，11｝｝，CHStree方法的求解效率最高，且求解時(shí)間不會(huì)隨沖突集簇中集合個(gè)數(shù)的增加而急劇增加。

（3）CHS-tree在某些特殊情況下的節(jié)點(diǎn)數(shù)量可能會(huì)更少。例如，在單故障診斷中，當(dāng)極小沖突集為F=｛a｝時(shí)，CHS-tree有1 個(gè)節(jié)點(diǎn)，HS-tree有2 個(gè)節(jié)點(diǎn)，而BHS-tree有3個(gè)節(jié)點(diǎn)；再如當(dāng)極小沖突集為F=｛｛a｝，｛b｝，｛c｝，｛d｝｝時(shí)，CHS-tree有4 個(gè)節(jié)點(diǎn)，HS-tree有5個(gè)節(jié)點(diǎn)，而BHS-tree有8個(gè)節(jié)點(diǎn)。

（4）用CHS-tree求解極小碰集時(shí)，與沖突集的排列次序無關(guān)，同一沖突集，當(dāng)排列次序發(fā)生變化時(shí)，節(jié)點(diǎn)數(shù)目和運(yùn)行時(shí)間均不受影響。

綜上所述，與HS-tree，BHS-tree，HSSE-tree相比，CHS-tree方法更能有效應(yīng)用于實(shí)際診斷中，尤其是在給定特殊沖突集簇的情況下，CHS-tree的運(yùn)行效率高于當(dāng)前效率最高的Boolean方法。

6 結(jié)束語

本文主要針對(duì)傳統(tǒng)故障診斷中求所有極小碰集的方法，提出一種改進(jìn)的算法CHS-tree。與傳統(tǒng)方法相比，該方法可以不斷地將大問題分解為子問題，降低了問題求解的規(guī)模，且容易編程實(shí)現(xiàn)。實(shí)驗(yàn)結(jié)果表明，CHS-tree方法生成樹的過程較簡(jiǎn)單，能產(chǎn)生較少的節(jié)點(diǎn)，比Reiter提出的經(jīng)典HS-tree方法、林笠等提出的BHS-tree方法以及趙相福等提出的HSSE-tree方法具有更高的求解效率，在某些情況下，其效率也高于當(dāng)前效率最高的Boolean 方法。當(dāng)增量診斷時(shí)，如何將本文所提方法擴(kuò)展到求解動(dòng)態(tài)變化的集小簇的極小碰集，是未來進(jìn)一步研究的重要問題。

［1］HAMSCHER W，CONSOLE L，DE KLEER J.Reading in model-based diagnosis［M］.San Mateo，Cal.，USA：Morgan-Kaufmann Publishers，1992.

［2］OUYANG Dantong，OUYANG Jihong，LIU Dayou.The research and new development on model-based diagnosis［J］.Acta Scientiarum Naturalium Universitatis Jilinensis，2001（2）：38-45（in Chinese）.［歐陽丹彤，歐陽繼紅，劉大有.基于模型診斷的研究與新進(jìn)展［J］.吉林大學(xué)自然科學(xué)學(xué)報(bào)，2001（2）：38-45.］

［3］DE KLEER J.An assumption-based tms［J］.Artificial Intelligence，1986，28（2）：127-162.

［4］REITER R.A theory of diagnosis from first principles［J］.Artificial Intelligence，1987，32（1）：57-96.

［5］JIANG Yunfei，LIN Li.The computation of hitting sets with binary hitting sets［J］.Journal of Software，2002，13（12）：2267-2274（in Chinese）.［姜云飛，林 笠.用對(duì)分-HS樹計(jì)算最小碰集［J］.軟件學(xué)報(bào)，2002，13（12）：2267-2274.］

［6］ZHAO X，OUYANG D.A method of combing SE-tree to compute all minimal hitting sets［J］.Progress in Nature Science，2006，16（2）：169-174.

［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］HAN B，LEE S.Deriving minimal conflict sets by CS-trees with mark set in diagnosis from first principles［J］.IEEE Transactions on Systems，Man，and Cybernetics，1999，29（2）：281-286.

［9］DE KLEER J.Hitting set algorithms for model-based diagnosis［EB／OL］.［2013-05-06］.http：／／www.st.ewi.tudelft.nl／～abreu／DX2011／paper／dx2011＿37.pdf.