王 冬 馮文全 李景文 趙 琦

(北京航空航天大學(xué) 電子信息工程學(xué)院，北京 100191)

計(jì)算極小碰集是基于模型診斷的關(guān)鍵步驟之一［1－2］.極小碰集問題已被證明是非決定性多項(xiàng)式(NP，Non-deterministic Polynomia)完全問題，其難度決定了對(duì)該問題的算法研究只能是近似計(jì)算，不存在固定參數(shù)可解的算法［3］.目前大部分極小碰集算法都是從參數(shù)計(jì)算理論出發(fā)［3－4］，對(duì)一般化的問題加上權(quán)值或賦予其它約束，如限制碰集維度和各元組維度，從而尋找降低時(shí)間復(fù)雜度的方法.但在基于模型診斷中，沖突集的維度和診斷解的維度是不確定的，過多限制反而對(duì)診斷效果不利，因此針對(duì)這個(gè)實(shí)際問題，研究一般化的極小碰集求解算法是非常必要的.

極小碰集求解算法大致可分為:基于碰集(HS，Hitting Set)樹［5－8］、基于布爾代數(shù)［9］、基于智能理論［10］等方法，各類算法的優(yōu)劣已經(jīng)過廣泛的討論.HSSE(Hitting Set-Set Enumeration)算法［11］解決了傳統(tǒng)HS樹在剪枝過程中丟失解的問題，但運(yùn)算量隨著問題規(guī)模而急劇增加，且對(duì)數(shù)據(jù)的規(guī)律性依賴過強(qiáng)，不適合用于大型系統(tǒng)診斷;BNB-HSSE(Branch and Bound-HSSE)算法［12］在HSSE基礎(chǔ)上結(jié)合了分支界定法，將問題逐步分解，但其參數(shù)化的求解方式使分支樹反復(fù)生成，增加了計(jì)算復(fù)雜度;基于二維數(shù)組結(jié)構(gòu)［13－14］的算法避免了使用搜索樹，易于編程實(shí)現(xiàn)，但由于其本質(zhì)上屬于枚舉法，因此計(jì)算效率不高.此外在大型系統(tǒng)診斷中，狀態(tài)空間規(guī)模的增加會(huì)使算法性能急劇惡化，甚至無法診斷，因此進(jìn)行大規(guī)模計(jì)算時(shí)的求解效率也是衡量算法的重要標(biāo)準(zhǔn)之一.

本文提出的M-MHS(Matrix-based Minimal Hitting Set)算法，利用參數(shù)矩陣描述元素與集合的關(guān)系，通過矩陣分解和有效的剪枝規(guī)則進(jìn)行求解，不僅能夠求出全體極小碰集，且在進(jìn)行較大規(guī)模計(jì)算時(shí)具有明顯優(yōu)勢(shì)，為大型系統(tǒng)基于模型診斷提供了可行方法.

1 問題描述

定義1 稱H為集合簇 S={ci，i=1，2，…，N}的碰集，當(dāng)且僅當(dāng) H?U(U=∪ci={e1，e2，…，em}，表示集合簇中所有元素的集合.數(shù)目為m)，并且對(duì)每一個(gè)ci∈S，都有H∩ci≠?.若H的任意真子集都不是碰集，則它是極小碰集(MHS).

定義2 定義m×n參數(shù)矩陣，其中m為沖突集合簇中包含元素的個(gè)數(shù)，n為沖突集合簇中包含沖突的個(gè)數(shù).矩陣中第i行第j列位置的值表示第j個(gè)沖突是否包含第i個(gè)元素，是為1，否為0.

參數(shù)矩陣描述了元素與沖突的關(guān)聯(lián)關(guān)系，可以得到以下推論:

推論1 若矩陣的某一行為全1，則該行對(duì)應(yīng)的元素是一個(gè)極小碰集.

推論2 若矩陣的某一行為全0，則該行對(duì)應(yīng)的元素不可能出現(xiàn)在極小碰集中.

推論3 若參數(shù)矩陣的某一列為全0，則該問題無碰集解;若矩陣沒有全0列，則該問題一定有解.反之也成立.

2 算法描述

基于參數(shù)矩陣的極小碰集計(jì)算算法通過判斷矩陣中0，1元素出現(xiàn)的次數(shù)和位置，快速將原始問題分解為一系列子問題，并且在進(jìn)行碰集判斷時(shí)利用上述3個(gè)推論，簡(jiǎn)化了傳統(tǒng)搜索算法中集合覆蓋的判斷過程，大大提高了求解效率.

2.1 M-MHS 算法

1)輸入?yún)?shù)矩陣Mm×n和用于存儲(chǔ)計(jì)算結(jié)果的列表H;

2)刪除全0行;

3)統(tǒng)計(jì)各元素在沖突集中出現(xiàn)的次數(shù)，即各行包含1的個(gè)數(shù);

4)若當(dāng)前參數(shù)矩陣不為空，則取出當(dāng)前出現(xiàn)次數(shù)最多的元素及矩陣中對(duì)應(yīng)的行;若為空，則轉(zhuǎn)9);

5)若該行為全1行，則加入H，并刪除該行，返回4);

6)若該行包含0，則分解矩陣.若該行第i個(gè)值為1，則刪除參數(shù)矩陣中對(duì)應(yīng)的列，若為0，則保留這一列.假設(shè)該行包含k個(gè)0，可以得到一個(gè)新的矩陣M'm×k;

7)輸入 M'm×(n－k)和 H'，遞歸調(diào)用算法 MMHS;

8)刪除該行，并將H'歸并于H，返回4)或轉(zhuǎn)9);

9)返回H.

2.2 參數(shù)矩陣分解方法

M-MHS算法是遞歸調(diào)用的，根據(jù)不同的參數(shù)矩陣計(jì)算相應(yīng)的極小碰集.除初始參數(shù)矩陣由沖突集合簇計(jì)算得出，其余各矩陣都是在初始矩陣基礎(chǔ)上根據(jù)擴(kuò)展元素進(jìn)行分解的結(jié)果.分解的方法為:

矩陣1 記錄擴(kuò)展元素所在行中所有0值的位置，并從初始矩陣中提取這些0值所屬的列，合并為一個(gè)新矩陣，即 M'm×(n－k).

矩陣2 初始矩陣中刪除擴(kuò)展元素所在行，即執(zhí)行步驟8)后的結(jié)果.

通過上述方法，初始問題被分解為兩個(gè)子問題.根據(jù)參數(shù)矩陣中0，1所表示的意義，可知該分解思想類似于分支定界樹搜索中的二叉擴(kuò)展，兩個(gè)子問題對(duì)應(yīng)于元素在碰集中和元素不在碰集中.但由于M-MHS算法在分解時(shí)考慮了各元素在沖突集簇中出現(xiàn)的頻率，因此能夠更快地計(jì)算出碰集.

2.3 剪枝規(guī)則

為了避免非極小碰集的產(chǎn)生，將H'歸并于HS時(shí)需加入剪枝規(guī)則:

1)對(duì)H'中的某個(gè)碰集h，若H中存在它的子集，則放棄h;

2)對(duì)H'中的某個(gè)碰集h，若H中存在它的超集，則用h代替它的超集;

3)若H'列表為空，則直接退出本次循環(huán).即在該子問題中，所有出現(xiàn)次數(shù)小于等于當(dāng)前擴(kuò)展元素的元素，都不可能構(gòu)成碰集.

M-MHS算法考慮了各元素在沖突集簇中出現(xiàn)的次數(shù)，同時(shí)又使用了剪枝規(guī)則，這樣不僅保證了計(jì)算出的碰集是極小的，且能夠及早避免對(duì)無解子問題的計(jì)算，因此在求解效率上較以往算法有很大提高.

3 系統(tǒng)仿真驗(yàn)證

3.1 算例分析

給定沖突集合簇 S={{B，D，E}，{A，B，C}，{A，C，E}，{B，D，F(xiàn)}，{B，D}，{B，C，E}，{A，F(xiàn)}}，求解極小碰集.

1)參數(shù)矩陣增加一列為統(tǒng)計(jì)各元素在沖突集簇中出現(xiàn)的次數(shù)，可得初始參數(shù)矩陣為

2)首先擴(kuò)展元素B.由于該行不是全1行，取出0值對(duì)應(yīng)的列.刪除全0行并統(tǒng)計(jì)各元素出現(xiàn)的次數(shù)，可得

①擴(kuò)展元素A，由于該行為全1行，直接加入碰集列表HB={{A}}，并刪除A行;

②元素C，E，F(xiàn)出現(xiàn)次數(shù)相等，隨機(jī)選擇一個(gè)進(jìn)行擴(kuò)展，假設(shè)擴(kuò)展C，可得參數(shù)矩陣:

F行為全1行，因此加入碰集列表HBC={{F}}，將其與擴(kuò)展元素C合并可得碰集{{C，F(xiàn)}}，刪除C行.

③ 碰集列表HB={{A}，{C，F(xiàn)}}.繼續(xù)擴(kuò)展元素E，可得參數(shù)矩陣:

F行為全1行，因此加入碰集列表HBE={{F}}，將其與擴(kuò)展元素E合并可得碰集{{E，F(xiàn)}}，刪除E行.

④ 碰集列表 HB={{A}，{C，F(xiàn)}，{E，F(xiàn)}}.繼續(xù)擴(kuò)展元素F，得到的參數(shù)矩陣為空，因此包含元素B的碰集求解完畢.將碰集列表HB合并擴(kuò)展元素 B，可得 H={{B，A}，{B，C，F(xiàn)}，{B，E，F(xiàn)}}，并刪除B行;

3)元素A，C，D，E出現(xiàn)次數(shù)相等，隨機(jī)選擇一個(gè)進(jìn)行擴(kuò)展，假設(shè)擴(kuò)展A，可得參數(shù)矩陣:

①擴(kuò)展元素D，可得參數(shù)矩陣:

刪除M'AD中全0行，C，E行都是全1行，因此HAD={{C}，{E}}，將其與擴(kuò)展元素D合并可得HA={{D，C}，{D，E}}，刪除 D 行.

②擴(kuò)展元素E，可得參數(shù)矩陣:

矩陣中包含全0列，因此HAE≠?.根據(jù)剪枝準(zhǔn)則3)，出現(xiàn)次數(shù)小于元素E的C，F(xiàn)都無需擴(kuò)展，包含元素A的碰集求解完畢.將碰集列表HA合并擴(kuò)展元素 A，可得 H={{B，A}，{B，C，F(xiàn)}，{B，E，F(xiàn)}，{A，D，C}，{A，D，E}}，刪除 A 行.

4)同理，擴(kuò)展元素C可得H={{B，A}，{B，C，F(xiàn)}，{B，E，F(xiàn)}，{A，D，C}，{A，D，E}，{C，D，F(xiàn)}}，刪除C行.

5)繼續(xù)擴(kuò)展元素D，可得HD≠?.根據(jù)剪枝準(zhǔn)則3)，出現(xiàn)次數(shù)小于元素D的E，F(xiàn)都無需擴(kuò)展.循環(huán)至此退出.

6)返回極小碰集列表 H={{B，A}，{B，C，F(xiàn)}，{B，E，F(xiàn)}，{A，D，C}，{C，D，F(xiàn)}}.

按照HSSE方法求得的結(jié)果與上述結(jié)果相同，從而驗(yàn)證了該算法的正確性.

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

采用Visual C++6.0編程實(shí)現(xiàn)了M-MHS算法，并在 Intel Core2 Duo CPU 2.66 GHz 1.95 GB內(nèi)存，Windows XP操作系統(tǒng)下運(yùn)行.用于實(shí)驗(yàn)的比對(duì)數(shù)據(jù)分為3組:隨機(jī)數(shù)據(jù)、有規(guī)律數(shù)據(jù)、不同規(guī)律數(shù)據(jù).

為了驗(yàn)證該算法的效率，比較了HSSE和修改的BNB-HSSE兩種算法的計(jì)算結(jié)果.其中對(duì)BNB-HSSE算法的修改有2個(gè)方面:

1)取消了上下界計(jì)算;

2)修改了節(jié)點(diǎn)是否分支的判斷條件.

這兩處修改主要為了去除原BNB-HSSE算法中參數(shù)化的影響，使之能夠從通用碰集計(jì)算的角度進(jìn)行求解，仿真結(jié)果如下.

3.2.1 隨機(jī)數(shù)據(jù)

集合簇個(gè)數(shù)和元素總數(shù)都為n，每個(gè)集合的長度和包含元素為隨機(jī)產(chǎn)生，但元素沒有重復(fù).表1為集合簇個(gè)數(shù)從20遞增到40時(shí)3種算法的運(yùn)行時(shí)間比較.

表1 隨機(jī)數(shù)運(yùn)行時(shí)間比較

可以看出，M-MHS和修改后的BHB-HSSE算法的性能要優(yōu)于HSSE.當(dāng)集合簇個(gè)數(shù)大于27時(shí)，HSSE的枚舉過程耗時(shí)嚴(yán)重，而另外兩種算法仍可以在較短時(shí)間內(nèi)求解.當(dāng)碰集個(gè)數(shù)較多時(shí)，M-MHS的性能要優(yōu)于修改后的BHB-HSSE算法，而當(dāng)碰集較少時(shí)，修改后的BHB-HSSE能夠在更短時(shí)間結(jié)束運(yùn)算.

3.2.2 有規(guī)律數(shù)據(jù)

集合簇個(gè)數(shù)為 n，各集合分別為{1，2，…，n}，{2，3，…，0}，…，{n，0，…，n －2}.圖 1 為集合簇個(gè)數(shù)從35遞增到60時(shí)3種算法運(yùn)行時(shí)間比較.

圖1 有規(guī)律數(shù)運(yùn)行時(shí)間比較

可以看出，HSSE算法的運(yùn)行時(shí)間要大大少于M-MHS算法和修改后的BHB-HSSE算法，這主要得益于數(shù)據(jù)的規(guī)律性.由于對(duì)于元素集合內(nèi)的任一元素，至少會(huì)在n個(gè)集合簇中會(huì)出現(xiàn)n－1次，因此所有雙元素集合都是碰集，所有三元素集合都不是極小碰集.而HSSE算法由空集到全集按寬度優(yōu)先擴(kuò)展，求解極小碰集時(shí)只需擴(kuò)展到第2層，因此在這種情況下，HSSE枚舉樹中的節(jié)點(diǎn)有用率非常高，求解速度很快.

M-MHS和修改后的BHB-HSSE算法的運(yùn)算速度在集合簇個(gè)數(shù)等于47時(shí)發(fā)生了翻轉(zhuǎn).當(dāng)碰集個(gè)數(shù)較少時(shí)，修改后的 BHB-HSSE性能優(yōu)于M-MHS，而碰集個(gè)數(shù)較多時(shí)，M-MHS的運(yùn)算時(shí)間更短.

3.2.3 不同規(guī)律數(shù)據(jù)

集合簇個(gè)數(shù)為固定值n，各集合分別為{1，2，…，n －i}，{2，3，…，n － i+1}，…，{n，1，…，2n －i}，其中i＜n為可變參數(shù)，決定了各集合的維度.仿真中集合簇個(gè)數(shù)為50，i為［0，10］.3種算法運(yùn)行時(shí)間比較如圖2所示.

圖2 不同規(guī)律數(shù)運(yùn)行時(shí)間比較

隨著i的增長，HSSE和修改后的BHB-HSSE算法性能下降明顯，而M-MHS算法的運(yùn)行時(shí)間始終維持在一個(gè)比較穩(wěn)定的范圍內(nèi).因?yàn)閷?duì)M-MHS算法而言，初始參數(shù)矩陣大小是不變的，變化的只是各行中0，1值的個(gè)數(shù)，因此矩陣分解所用總的時(shí)間波動(dòng)不大.而對(duì)于基于分支的BHB-HSSE算法，隨著i的增加，擴(kuò)展產(chǎn)生的“不包含某元素的集合列表”分支中集合個(gè)數(shù)越來越多，相應(yīng)地搜索樹也會(huì)越來越復(fù)雜，因此求解時(shí)間受搜索樹規(guī)模影響呈指數(shù)增長.

從上面仿真結(jié)果可以得出，當(dāng)集合簇和元素個(gè)數(shù)越多時(shí)，M-MHS算法明顯具有計(jì)算效率上的優(yōu)勢(shì)，且當(dāng)數(shù)據(jù)按不同規(guī)律變化時(shí)，算法性能仍維持相對(duì)穩(wěn)定.因此M-MHS算法能夠適用于大型系統(tǒng)診斷.

4 結(jié)束語

本文提出了一種基于參數(shù)矩陣計(jì)算極小碰集的M-MHS算法.該方法利用參數(shù)矩陣描述元素與集合簇的關(guān)系，通過矩陣分解將原始問題逐步分解為多個(gè)子問題，并采用有效的剪枝規(guī)則避免對(duì)無解子問題的計(jì)算，從而提高了效率.仿真結(jié)果表明:該算法在進(jìn)行較大規(guī)模碰集計(jì)算時(shí)具有明顯優(yōu)勢(shì)，且對(duì)不同規(guī)律數(shù)據(jù)能夠維持性能穩(wěn)定，從而為實(shí)現(xiàn)大型系統(tǒng)基于模型診斷提供了可行方法.

References)

［1］ de Kleer J，Williams B C.Diagnosing multiple faults［J］.Artificial Intelligence，1987，32(1):97 －130

［2］ Williams B C，Ragno R J.Conflict-directed A*and its role in model-based embedded systems［J］.Discrete Applied Mathematics，2007，155(12):1562 －1595

［3］李紹華，王建新，馮啟龍，等.Set Cover和 Hitting Set問題的研究進(jìn)展［J］.計(jì)算機(jī)科學(xué)，2009，36(10):1 －4 Li Shaohua，Wang Jianxin，F(xiàn)eng Qilong，et al.Set cover and hitting set:a survey［J］.Computer Science，2009，36(10):1 － 4(in Chinese)

［4］蔡烜.d-Hitting Set問題的固定參數(shù)化算法［D］.上海:上海交通大學(xué)計(jì)算機(jī)科學(xué)與工程系，2009 Cai Xuan.Fixed-parameter algorithms for d-Hitting set problems［D］.Shanghai:Department of Computer Science and Engineering，Shanghai Jiao Tong University，2009(in Chinese)

［5］ Reiter R.A theory of diagnosis from first principles［J］.Artificial Intelligence，1987，32(1):57 －95

［6］ Wotawa F.A variant of Reiter's hitting-set algorithm［J］.Information Processing Letters，2001，79(1):45 － 51

［7］ Greiner R，Smith B A，Wilkerson RW.A correction to the algorithm in Reiter's theory of diagnosis［J］.Artificial Intelligence，1989，41(1):79 －88

［8］姜云飛，林笠.用對(duì)分HS—樹計(jì)算最小碰集［J］.軟件學(xué)報(bào)，2002，13(12):2267 －2274 Jiang Yunfei，Lin Li.Computing the minimal hitting sets with binary HS-tree［J］.Journal of Software，2002，13(12):2267 －2274(in Chinese)

［9］姜云飛，林笠.用布爾代數(shù)方法計(jì)算最小碰集［J］.計(jì)算機(jī)學(xué)報(bào)，2003，26(8):919 －924 Jiang Yunfei，Lin Li.The computing of hitting sets with boolean formulas［J］.Chinese Journal of Computers，2003，26(8):919 －924(in Chinese)

［10］黃杰，陳琳，鄒鵬.一種求解極小診斷的遺傳模擬退火算法［J］.軟件學(xué)報(bào)，2004，15(9):1345 －1350 Huang Jie，Chen Lin，Zou Peng.A compounded genetic and simulated annealing algorithm for computing minimal diagnosis［J］.Journal of Software，2004，15(9):1345 － 1350(in Chinese)

［11］ 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

［12］陳曉梅，孟曉風(fēng)，喬仁曉.基于BNB-HSSE計(jì)算全體碰集的方法［J］.儀器儀表學(xué)報(bào)，2010，31(1):61 －67 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)

［13］林笠.基于模型診斷中用邏輯數(shù)組計(jì)算最小碰集［J］.暨南大學(xué)學(xué)報(bào):自然科學(xué)與醫(yī)學(xué)版，2002，23(1):24－27 Lin Li.Computing minimal hitting sets with logic array in model-based diagnosis［J］.Journal of Jinan University:Natural Science ＆ Medicine Edition，2002，23(1):24 －27(in Chinese)

［14］ Fijany A，Vatan F.New approaches for efficient solution of hitting set problem［C］//Proceedings of the Winter International Symposium on Information and Communication Technologies.Cancun，Mexico:Trinity College Dublin，2004