基于矩阵运算的极小碰集求解方法  

Computing minimal hitting sets based on matrix operations

作　　者：陈旭琳 赵相福 褚鹏 陈中育 CHEN Xu-lin;ZHAO Xiang-fu;CHU Peng;CHEN Zhong-yu(College of Mathematics and Computer Science,Zhejiang Normal University,Jinhua 321004,China)

机构地区：[1]浙江师范大学数学与计算机科学学院,浙江金华321004

出　　处：《计算机工程与设计》2020年第9期2538-2542,共5页Computer Engineering and Design

基　　金：国家自然科学基金项目(61972360);浙江省自然科学基金项目(LY16F020004)。

摘　　要：根据冲突集簇计算极小碰集是基于模型诊断的关键步骤,提出一种基于矩阵运算求解极小碰集的方法,在考虑集合之间联系的基础上,通过构造矩阵体现极小碰集的特性,找出所有的极小碰集。从理论上分析利用矩阵求解极小碰集的算法,通过实例进行验证,与其它极小碰集求解算法进行比较。实验结果表明,所提方法数据结构简单,算法程序容易编写,能够确保得到所有极小碰集,在某些情况下比传统的CSSE-Tree算法、HST-Tree算法等具有更高的求解效率。In model-based diagnosis theory,it is an important step to compute all minimal hitting sets for the cluster of conflict sets.An algorithm for computing minimal hitting sets was presented by matrix.The correlation between sets was considered,and the matrix was structured to reflect the characteristics of minimal hitting sets to find all of them.The algorithm was analyzed and verified in theory.An example was given to verify the algorithm.The algorithm was compared with many other algorithms for generating minimal hitting sets.Experimental results show that the data structure of this algorithm is simple.This algorithm is easy to be implemented,and all minimal hitting sets are obtained.Compared with some well-known approaches like CSSE-Tree method and HST-Tree method,this method has higher efficiency in many cases.

关 键 词：故障诊断 基于模型的诊断 矩阵 冲突集 极小碰集 

分 类 号：TP31[自动化与计算机技术—计算机软件与理论]