A Method of Computing Minimal Conflict Sets Combining the Structure Property with the Anti-depth SE-Tree

OUYANG Dan-tong; LIU Bo-wen; ZHOU Jian-hua; ZHANG Li-ming

doi:10.3969/j.issn.0372-2112.2017.05.021

您当前的位置：

首页 >

文章列表页 >

A Method of Computing Minimal Conflict Sets Combining the Structure Property with the Anti-depth SE-Tree

更新时间：2025-07-16

- A Method of Computing Minimal Conflict Sets Combining the Structure Property with the Anti-depth SE-Tree
- Acta Electronica Sinica Vol. 45, Issue 5, Pages: 1175-1181(2017)
- 作者机构：
  
  1. 吉林大学计算机科学与技术学院,吉林,长春,130012
  2. 吉林大学软件学院,吉林,长春,130012
  3. 符号计算与知识工程教育部重点实验室(吉林大学),吉林,长春,130012
  4. 吉林大学计算机科学与技术学院,吉林,长春,130012
  5. 吉林大学软件学院,吉林,长春,130012
  6. 符号计算与知识工程教育部重点实验室(吉林大学),吉林,长春,130012
- 作者简介：
- 基金信息：
- DOI：10.3969/j.issn.0372-2112.2017.05.021
  CLC： TP306
- Published：2017
- 稿件说明：
移动端阅览
OUYANG Dan-tong, LIU Bo-wen, ZHOU Jian-hua, et al. A Method of Computing Minimal Conflict Sets Combining the Structure Property with the Anti-depth SE-Tree[J]. Acta Electronica Sinica, 2017, 45(5): 1175-1181.
DOI：

OUYANG Dan-tong, LIU Bo-wen, ZHOU Jian-hua, et al. A Method of Computing Minimal Conflict Sets Combining the Structure Property with the Anti-depth SE-Tree[J]. Acta Electronica Sinica, 2017, 45(5): 1175-1181. DOI： 10.3969/j.issn.0372-2112.2017.05.021.

摘要

基于模型诊断是人工智能领域内的一个重要研究方向，求解极小冲突集在基于模型诊断中有着重要应用.在对结合CSISE-Tree求解冲突集方法深入研究的基础上，根据冲突集求解特征重构了结合枚举树的计算冲突集的过程，提出基于深度优先反向搜索求解冲突集的方法.针对CSISE-Tree方法求解时占用内存空间与元件总数指数级相关的缺点，构建反向深度搜索方法减小求解时所占用内存空间；针对CSISE-Tree方法不能对部分非极小的冲突集进行剪枝的问题，给出对非冲突集和更多非极小的冲突集进行剪枝的方法，有效减少了求解时调用SAT（Boolean SATisfiability problem）求解器的次数；实验结果表明，与CSISE-Tree方法相比，本文提出的方法求解效率有明显的提升，并避免了求解时的内存爆炸问题.

Abstract

Model-based diagnosis is an important problem in the field of artificial intelligence.In model-based diagnosis

how to get the minimal conflict sets is a well-known problem with extensive applications.In this paper

according to the characteristics of the conflict sets

we use the enumeration tree to reconstruct the process of solving conflict sets and then design a reverse depth algorithm based on the previous algorithm CSISE-Tree.Firstly

this proposed reverse depth search algorithm can reduce as many memory spaces as possible when obtaining some conflict sets

while CSISE-Tree have to expend some unnecessary memory spaces in this case

where the consume of memory spaces exponentially grows with the number of circuit elements.Secondly

compared with CSISE-Tree

our algorithm can effectively cut down the number of calling the SAT(Boolean SATisfiability problem) solver by pruning some non-minimal conflict sets and non-conflict sets.The experimental results show that our algorithm performs better than its competitor CSISE-Tree in terms of run time in most instances.More importantly

our algorithm avoids the memory explosion when solving some large instances.

关键词

Keywords

references

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

CIMHS: A Method of Computing all Minimal Hitting Sets for Minimal Conflict Sets Based on an Optimized Incremental Strategy

IBWIICC:Incrementally Computing Minimal Hitting-Sets Combing Local Independence Cover Checking

A Block-Based Diagnostic Method Combining with the Circuit Structure

Related Author

HUANG Sen

ZHAO Xiang-fu

WEI Xia

ZHANG Xing-lin

ZHANG Li-ming

ZHAO Xiang-fu

HUANG Sen

TONG Xiang-rong

Related Institution

Department of Computer， Zhejiang Normal University

School of Computer and Control Engineering， Yantai University

School of Computer and Control Engineering, Yantai University

Department of Computer, Zhejiang Normal University

Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education Jilin UniversityChangchunJilin130012China

⁰