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

Heuristic algorithm of computing minimal hitting sets matrix

提出了一种基于矩阵模型计算极小碰集的新方法。通过在矩阵中存储冲突集合簇的相关信息,引入集合簇中元素的频率作为启发信息,完成对极小碰集的计算。该算法的数据结构简单,程序易于实现,同时启发信息的引入减少了节点的生成。该算法可以产生而且仅产生所有的极小碰集。实验结果表明该算法有较高的计算效率。

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.