.png){kind=icon}
.png){kind=icon}
返回
Computing all minimal hitting sets by subset recombination
.png){kind=icon}
PRE
AI
DOI：10.1007/s10489-017-0971-7.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
In model-based diagnosis from first principles, the efficient computation of all minimal hitting sets (MHS) as candidates for the conflict component sets of a device is a vital task. However, deriving all MHS is NP-hard. In this paper, the principle of Divide and Conquer is used to decompose a large family of conflict sets into many smaller sub-families. To efficiently merge the sub-MHS to give sub-families of conflict sets, the relations between the sub-MHS and sub-families of conflict sets are exploited. Based on this, a new method called Subset-Rec-MHS is proposed. In theory, our method based on sub-MHS recombination generally has lower complexity than that based on whole MHS families, as it avoids a large number of set unions and comparisons (to minimize the family of hitting sets). Compared with the direct merge of whole MHS families, the proposed approach reduces the computation time by a factor of approximately 7/16. Experimental results on both synthetic examples and ISCAS-85 benchmark circuit conflict sets show that, in many cases, our approach offers better performance than previous algorithms.
Keyword:
Model-based diagnosis
Hitting set
Divide and conquer
Conflict set
Subset
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。