Abstract: In model-based diagnosis and test,the efficiency of computing all minimal hitting sets for the cluster of conflict sets has a significant influence on the final diagnostic process.A new algorithm namely JMatrix was proposed to obtain all minimal hitting sets by using a dynamic minimum cardinality parameter matrix.The parameter matrix was constructed to store the correlation information of minimal conflict sets,and the minimal cardinality was considered to decompose the problem gradually into smaller subproblems.The search space could be considerably reduced by introducing the effective pruning strategy and heuristic information into the process of generating hitting sets.Besides,combining with the characteristics of the original parameter matrix,the obtained hitting sets were checked efficiently.Experimental results showed that JMatrix had higher computational efficiency than many other well-known approaches,not only on regular synthetic data,but also on many circuits in the widely used ISCAS-85 benchmark circuits.

Key words: model-based diagnosis, minimal hitting set, minimal conflict set, parameter matrix, minimal cardinality

摘要： 在基于模型的故障诊断与测试过程中,求解极小碰集是诊断与测试的一个关键步骤,极大地影响了故障诊断的最终效率。鉴于此,提出一种基于动态极小势的参数矩阵计算极小碰集的新算法JMatrix,利用参数矩阵描述冲突集合簇中元素与集合的关系,每次动态选取当前矩阵中势最小的集合进行分解,将大问题逐步分解成规模更小的子问题,并在碰集求解过程中通过加入剪枝策略和启发式信息,避免了对无解空间的搜索;在对每一个碰集进行极小化时,根据原始冲突集合簇的矩阵特性,可以快速地找到特定元素所在的集合,从而加快极小化的速度。实验结果表明,所提算法JMatrix不但在大量人工测试数据集上较其他经典极小碰集求解算法具有更高的效率,而且在国际基准ISCAS-85电路数据集上仍具有高效稳定的性能。

关键词: 基于模型的诊断, 极小碰集, 极小冲突集, 参数矩阵, 极小势