基于參數(shù)矩陣計算全體極小碰集的方法

王 冬 馮文全 李景文 趙 琦

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

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

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

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

1 問題描述

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

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

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

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

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

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

2 算法描述

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

2.1 M-MHS 算法

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

2)刪除全0行;

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

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

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

6)若該行包含0，則分解矩陣.若該行第i個值為1，則刪除參數(shù)矩陣中對應(yīng)的列，若為0，則保留這一列.假設(shè)該行包含k個0，可以得到一個新的矩陣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ù)矩陣計算相應(yīng)的極小碰集.除初始參數(shù)矩陣由沖突集合簇計算得出，其余各矩陣都是在初始矩陣基礎(chǔ)上根據(jù)擴展元素進行分解的結(jié)果.分解的方法為:

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

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

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

2.3 剪枝規(guī)則

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

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

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

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

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

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

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)計各元素在沖突集簇中出現(xiàn)的次數(shù)，可得初始參數(shù)矩陣為

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

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

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

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

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

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

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

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

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

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

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

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

4)同理，擴展元素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ù)擴展元素D，可得HD≠?.根據(jù)剪枝準則3)，出現(xiàn)次數(shù)小于元素D的E，F(xiàn)都無需擴展.循環(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é)果相同，從而驗證了該算法的正確性.

3.2 統(tǒng)計分析

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

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

1)取消了上下界計算;

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

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

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

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

表1 隨機數(shù)運行時間比較

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

本文提出了一種基于參數(shù)矩陣計算極小碰集的M-MHS算法.該方法利用參數(shù)矩陣描述元素與集合簇的關(guān)系，通過矩陣分解將原始問題逐步分解為多個子問題，并采用有效的剪枝規(guī)則避免對無解子問題的計算，從而提高了效率.仿真結(jié)果表明:該算法在進行較大規(guī)模碰集計算時具有明顯優(yōu)勢，且對不同規(guī)律數(shù)據(jù)能夠維持性能穩(wěn)定，從而為實現(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］.計算機科學(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é)計算機科學(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］姜云飛，林笠.用對分HS—樹計算最小碰集［J］.軟件學(xué)報，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］.計算機學(xué)報，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é)報，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］.儀器儀表學(xué)報，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］.暨南大學(xué)學(xué)報:自然科學(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