基于矩阵计算极小碰集的启发式算法  

Heuristic algorithm of computing minimal hitting sets matrix

作　　者：欧阳丹彤[1,2] 耿雪娜[1,2] 郭劲松[1,2] 王晓宇[1,2] 

机构地区：[1]吉林大学符号计算与知识工程教育部重点实验室,长春130012 [2]吉林大学计算机科学与技术学院长春130012

出　　处：《吉林大学学报（工学版）》2013年第1期106-110,共5页Journal of Jilin University:Engineering and Technology Edition

基　　金：国家自然科学基金项目(60973089,60873148,60773097,61003101);高等学校博士学科点专项科研基金项目(20100061110031);吉林大学符号计算与知识工程教育部重点实验室开放项目(93K-17-2009-K05);浙江师范大学计算机软件与理论省级重中之重学科开放基金项目;浙江省自然科学基金项目(Y1100191)

摘　　要：提出了一种基于矩阵模型计算极小碰集的新方法。通过在矩阵中存储冲突集合簇的相关信息,引入集合簇中元素的频率作为启发信息,完成对极小碰集的计算。该算法的数据结构简单,程序易于实现,同时启发信息的引入减少了节点的生成。该算法可以产生而且仅产生所有的极小碰集。实验结果表明该算法有较高的计算效率。In model-based diagnosis, computing minimal hitting sets is an important part of the representationof candidate diagnostic results. In this paper, a new method is proposed to obtain the minimal hitting sets by matrix. In this method, the related information of the conflict sets is stored in a matrix. The frequencies ofelements of the set cluster are taken as the heuristic information to compute the minimal hitting sets. The data structure of the algorithm is simple and the implementation of the algorithm is easy. The introduction ofheuristic information reduces the number of the generated nodes. This algorithm can generate and only generate all the minimal hitting sets. Experiment results show that the proposed algorithm has a bettercomputational efficiency than other algorithms.

关 键 词：人工智能 基于模型诊断 冲突集 极小碰集 启发式算法 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]