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

王 冬 馮文全 李景文 趙 琦

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

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

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

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

1 問題描述

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

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

參數矩陣描述了元素與沖突的關聯關系，可以得到以下推論:

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

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

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

2 算法描述

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

2.1 M-MHS 算法

1)輸入參數矩陣Mm×n和用于存儲計算結果的列表H;

2)刪除全0行;

3)統計各元素在沖突集中出現的次數，即各行包含1的個數;

4)若當前參數矩陣不為空，則取出當前出現次數最多的元素及矩陣中對應的行;若為空，則轉9);

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

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

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

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

9)返回H.

2.2 參數矩陣分解方法

M-MHS算法是遞歸調用的，根據不同的參數矩陣計算相應的極小碰集.除初始參數矩陣由沖突集合簇計算得出，其余各矩陣都是在初始矩陣基礎上根據擴展元素進行分解的結果.分解的方法為:

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

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

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

2.3 剪枝規則

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

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

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

3)若H'列表為空，則直接退出本次循環.即在該子問題中，所有出現次數小于等于當前擴展元素的元素，都不可能構成碰集.

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

3 系統仿真驗證

3.1 算例分析

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

1)參數矩陣增加一列為統計各元素在沖突集簇中出現的次數，可得初始參數矩陣為

2)首先擴展元素B.由于該行不是全1行，取出0值對應的列.刪除全0行并統計各元素出現的次數，可得

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

②元素C，E，F出現次數相等，隨機選擇一個進行擴展，假設擴展C，可得參數矩陣:

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

③ 碰集列表HB={{A}，{C，F}}.繼續擴展元素E，可得參數矩陣:

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

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

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

①擴展元素D，可得參數矩陣:

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

②擴展元素E，可得參數矩陣:

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

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

5)繼續擴展元素D，可得HD≠?.根據剪枝準則3)，出現次數小于元素D的E，F都無需擴展.循環至此退出.

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

按照HSSE方法求得的結果與上述結果相同，從而驗證了該算法的正確性.

3.2 統計分析

采用Visual C++6.0編程實現了M-MHS算法，并在 Intel Core2 Duo CPU 2.66 GHz 1.95 GB內存，Windows XP操作系統下運行.用于實驗的比對數據分為3組:隨機數據、有規律數據、不同規律數據.

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

1)取消了上下界計算;

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

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

3.2.1 隨機數據

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

表1 隨機數運行時間比較

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

3.2.2 有規律數據

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

圖1 有規律數運行時間比較

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

M-MHS和修改后的BHB-HSSE算法的運算速度在集合簇個數等于47時發生了翻轉.當碰集個數較少時，修改后的 BHB-HSSE性能優于M-MHS，而碰集個數較多時，M-MHS的運算時間更短.

3.2.3 不同規律數據

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

圖2 不同規律數運行時間比較

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

從上面仿真結果可以得出，當集合簇和元素個數越多時，M-MHS算法明顯具有計算效率上的優勢，且當數據按不同規律變化時，算法性能仍維持相對穩定.因此M-MHS算法能夠適用于大型系統診斷.

4 結束語

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

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］.計算機科學，2009，36(10):1 －4 Li Shaohua，Wang Jianxin，Feng Qilong，et al.Set cover and hitting set:a survey［J］.Computer Science，2009，36(10):1 － 4(in Chinese)

［4］蔡烜.d-Hitting Set問題的固定參數化算法［D］.上海:上海交通大學計算機科學與工程系，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］.軟件學報，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］姜云飛，林笠.用布爾代數方法計算最小碰集［J］.計算機學報，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］.軟件學報，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］陳曉梅，孟曉風，喬仁曉.基于BNB-HSSE計算全體碰集的方法［J］.儀器儀表學報，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］林笠.基于模型診斷中用邏輯數組計算最小碰集［J］.暨南大學學報:自然科學與醫學版，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