利用集合劃分方法加速碰集的計算

金星波，張文磊

（92493部隊88分隊，遼寧葫蘆島125000）

利用集合劃分方法加速碰集的計算

金星波，張文磊

（92493部隊88分隊，遼寧葫蘆島125000）

基于模型的診斷對于靶場裝設備的保障具有重大的意義，碰集的計算則是基于模型診斷中最為關鍵的技術，本文通過對碰集計算方法的研究，提出利用集合劃分的方法加速對碰集的計算，從理論上保證了本方法的正確性與有效性，能夠對大規模的問題集提供有效的方法，具有一定的實用性。而且當問題規模擴大時，具有很好的可擴展性。

基于模型的診斷；劃分；碰集

1 前言

靶場承擔了海軍新裝備的試驗任務，責任重大，而裝設備的保障對于試驗任務的完成具有關鍵性作用。基于模型的診斷因其客觀性、建成后并不依賴于專家、相對較好的可移植性，較適合靶場設備的維護。對碰集（Hitting-set）的計算是基于模型診斷的關鍵技術之一，具有較高的研究價值及實際意義。

對碰集的計算方法研究一直為眾多學者關注，其方法主要有以下幾種：邏輯數組計算方法；HS-tree方法；遞歸方法；BHS-tree方法；布爾代數法；遺傳算法（GA）等。近年也有學者將粒子群方法引入碰集的計算。

其中邏輯數組方法容易實現，資源占用量低，但效率較低；而GA算法在問題規模較大時效率較高，但算法實現較為復雜；遞歸方法及HS-tree方法當問題規模較大時效率較低；布爾代數法則具有較好的時間及空間效率。

碰集的計算是一個NP問題，也就意味著無論算法如何改進，隨著問題規模的擴大，其需要的時間及空間一定是指數型增長。當問題規模擴大到一定程度，問題將變得不可解。而實際運用中，問題的規模往往較大，這就意味著問題規模的控制是碰集計算的一個重要問題。本文目的有兩個：（1）當問題的規模較大時，可以將問題劃分為幾個較小規模的問題，并提供理論上的保證；（2）在此的基礎上，提供一個完整的算法，并能夠吸收其他算法的長處。

2 相關的基本概念

概念一（集合簇（Sc）：set cluster，為一個集合，這個集合的每個元素都為集合；即集合簇是由集合組成的集合。

概念二（碰集）：設C是一個由n個集合元素構成的集合簇，每個集合元素記為Si，其中1≦i≦n；而H是一個集合，如果

1）H為∪S的子集；

2）對任意S∈C，都有H∩S≠Φ；

則稱H是C的一個碰集。

概念三（極小碰集）：稱C的一個碰集H為極小碰集，即H的任意一個真子集均非C的碰集。

概念四（劃分）：設C、A、B均為集合，如果：

1）A∩B＝Φ；

2）A∪B＝C；

則稱A、B為集合C的一個劃分。

3 算法簡述

3.1 算法的基本思想

算法的基本思想即是將一個較大規模的問題集劃分為兩個或多個問題集，以其降低問題集的規模，劃分后的每個問題集可以獨立求解，最后求各獨立解的交叉并集來求得問題的解。如圖［1］所示：

圖一算法流程

3.2 Algorithm A（求碰集的算法）：

（1）將集合簇Sc劃分為兩個集合ScA、ScB（也可以為多個）；（2）分別求出ScA與ScB的碰集（集合簇A與集合簇B）；（3）A與B交叉求并。

3.3 Algorithm B（求全部極小碰集的算法）：

（1）將集合簇Sc劃分為兩個集合ScA、ScB（也可以為多個）；（2）分別求出ScA與ScB的全部極小碰集（集合簇A與集合簇B）；（3）A與B交叉求并，并極小化。

3.4 算法的數學基礎

定理1：令A為集合簇ScA的一個碰集，B為集合簇ScB的一個碰集，則A∪B為ScA∪ScB的一個碰集。

推論1：令ScA與ScB為集合簇Sc的一個劃分，且A為ScA的一個碰集，B為ScB的一個碰集，則A∪B為集合簇Sc的一個碰集。

推論2：令ScAi（I=1，2，…，n）為集合簇Sc的一個劃分，且Ai為ScAi的一個碰集，則A1∪A2∪…∪An為CS的一個碰集。

推論1與推論2是定理1的推論，共同保證Algorithm A與Algorithm B中第三步中每個所求的并集均為集合簇Sc的碰集。

定理2：令ScA與ScB為集合簇Sc的一個劃分，且集合簇A（A1，A2，…，A n）包含且只包含ScA的全部極小碰集，集合簇B（B1，B2，…，Bm）包含且只包含ScB的全部極小碰集，則集合簇CS的任一極小碰集必然為集合簇A中某一元素與集合簇B中某一元素的并。（可證）

推論3：令CSAi（I=1，2，…，n）為集合簇CS的一個劃分，且集合簇Ai包含且只包含CSAi的全部極小碰集，則CS的任意一個極小碰集必然為A1i1∪A2i2∪…∪Anin。其中A1i1∪為A1的某個極小碰集。

推論3為定理2的推論，推論3與定理2保證Algorithm A與Algorithm B中第三步中所求的碰集包括所有Sc的碰集。

綜上所述，本節所提供的數學基礎可以嚴格保證Algorithm A與Algorithm B是正確的。

3.5 算法的時間復雜度簡述

以algorithm B為例：令n，m為ScA與ScB的集合元素數，令每次求并時間為T，令TA為用某種算法求A全部極小碰集所需時間。則有：如將集合二分，所算法完成所需時間大致為H1=n×m×T+ Tsca+Tscb；再令H2=Tcs。

因為TA是指數函數，而n×m×T基本上是二次函數，當問題規模較大時，H1應顯然遠遠小于H2。簡而言之，即22n＞＞2×2n。也就是說，算法的時間復雜度降低了。

3.6 算法優點：

（1）在算法的第二步，可以采用任何求碰集的輔助算法（如布爾代數法、數組法等）。各種算法往往具有各自的特點及適用情況，本算法可以根據實際情況靈活吸收其他算法的優點，同時又降低了問題的規模；（2）不論采用哪種輔助算法，本算法都能依實際問題的需要降低時間與空間復雜度，此點對于問題規模極大的情況，其他算法無法計算時尤其重要（由上節算法的時間復雜度分析可知）；（3）算法的第二步顯然支持并行計算；并由定理2可知，算法的第三步也支持并行。并行是降低NP問題時間復雜度的有效手段，本算法支持并行，就意味著較其他不能支持并行的方法有極大的優勢；（4）如果是求極小碰集，由定理2可知，如果輔助算法不丟解，則本算法求出的必為全部極小碰集；（5）如果集合簇元素增加，由定理2可知，將新增加元素視為步驟1中新劃分的一須要重新計算。這就意味著，當問題規模在原來的基礎上擴大時，不須要進行重復計算；（6）其實本算法即使不采用任何其他求碰集的輔助算法，本身通過遞歸也是一個完整的求碰集的算法。尤其當每次都劃分為兩個集合時，即成為RSTree算法，因此RSTree算法可以看作本算法的特例。

4 結論

本算法簡單而且容易實現，具有較強的數學基礎，從理論上即可證明能夠有效地降低問題的時間復雜度，并能夠根據實際情況靈活地吸收其他算法的優點，在理論及實踐中都有一定的意義。

［1］林笠.基于模型診斷中用邏輯數組計算最小碰集［J］.暨南大學學報，2002，22（1）：24-27.

［2］R Reiter.A Theory of Diagnosis from First Principles［J］.Artificial Intelligence，1987，32（1）：57-96.

［3］林笠.遞歸建立HS-樹計算最小碰集［J］.微電子學與計算機，2002，19（2）：7-10.

編輯∕岳鳳

金星波（1972－），男，吉林集安人，現任92493部隊88分隊工程師，研究方向：軟件理論及信息系統研制方向。