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

王 冬 馮文全 李景文 趙 琦

(北京航空航天大學 電子信息工程學院，北京 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］的算法避免了使用搜索樹，易于編程實現，但由于其本質上屬于枚舉法，因此計算效率不高.此外在大型系統診斷中，狀態空間規模的增加會使算法性能急劇惡化，甚至無法診斷，因此進行大規模計算時的求解效率也是衡量算法的重要標準……