利用集合划分方法加速碰集的计算

2014-01-12金星波张文磊

黑龙江教育·理论与实践 2014年6期

关键词：复杂度规模定理

金星波，张文磊

（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算法可以看作本算法的特例。