金星波，張文磊

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

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

金星波，張文磊

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

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

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

1 前言

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

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

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

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

2 相關(guān)的基本概念

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

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

1）H為∪S的子集；

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

則稱H是C的一個碰集。

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

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

1）A∩B＝Φ；

2）A∪B＝C；

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

3 算法簡述

3.1 算法的基本思想

算法的基本思想即是將一個較大規(guī)模的問題集劃分為兩個或多個問題集，以其降低問題集的規(guī)模，劃分后的每個問題集可以獨立求解，最后求各獨立解的交叉并集來求得問題的解。如圖［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 算法的數(shù)學基礎(chǔ)

定理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的碰集。

綜上所述，本節(jié)所提供的數(shù)學基礎(chǔ)可以嚴格保證Algorithm A與Algorithm B是正確的。

3.5 算法的時間復雜度簡述

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

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

3.6 算法優(yōu)點：

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

4 結(jié)論

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

［1］林笠.基于模型診斷中用邏輯數(shù)組計算最小碰集［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－），男，吉林集安人，現(xiàn)任92493部隊88分隊工程師，研究方向：軟件理論及信息系統(tǒng)研制方向。