王 冬 冯文全 李景文 赵 琦

(北京航空航天大学 电子信息工程学院，北京 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］的算法避免了使用搜索树，易于编程实现，但由于其本质上属于枚举法，因此计算效率不高.此外在大型系统诊断中，状态空间规模的增加会使算法性能急剧恶化，甚至无法诊断，因此进行大规模计算时的求解效率也是衡量算法的重要标准……