ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2018, Vol. 55 ›› Issue (4): 791-801.doi: 10.7544/issn1000-1239.2018.20160900

Previous Articles     Next Articles

Computing the Minimal Hitting Sets with Dynamic Maximum Element Coverage Value

Deng Zhaoyong, Ouyang Dantong, Geng Xuena, Liu Jie   

  1. (College of Computer Science and Technology, Jilin University, Changchun 130012) (Key Laboratory of Symbolic Computation and Knowledge Engineering (Jilin University), Ministry of Education, Changchun 130012)
  • Online:2018-04-01

Abstract: The minimal conflict set cluster is constructed by all the minimal conflict sets. The minimal hitting sets of all the minimal conflict sets are the faults of the system to be diagnosed. Therefore, computing all the minimal hitting sets according to the minimal conflict set cluster is an important step in model based diagnosis. In this paper, a new algorithm is proposed to obtain all the minimal hitting sets by using dynamic maximum element coverage value. The algorithm processes elements in turn according to the descending order of the element coverage value. The search space can be greatly reduced by joining the corresponding heuristic strategy and pruning strategy in the process of solving the hitting sets. Adjacency list is used to store the minimal conflict set cluster in the algorithm. Among the basic storage structures, adjacency list has better space cost than matrix. Besides, the adjacent pointer can quickly find the elements in the minimal conflict set cluster which can be covered by an element. When a hitting set is obtained, the minimal hitting set is obtained by using the minimal hitting set decision rule. Therefore, the algorithm can generate and only generate all the minimal hitting sets. Experimental results show that the proposed algorithm has better computational efficiency than other algorithms.

Key words: model-based diagnosis (MBD), minimal conflict set, minimal hitting set, dynamic maximum element coverage value, heuristic strategy, pruning strategy

CLC Number: