结合问题特征利用SE-Tree反向深度求解冲突集的方法

发布时间：2018-08-19 14:08

【摘要】：基于模型诊断是人工智能领域内的一个重要研究方向,求解极小冲突集在基于模型诊断中有着重要应用.在对结合CSISE-Tree求解冲突集方法深入研究的基础上,根据冲突集求解特征重构了结合枚举树的计算冲突集的过程,提出基于深度优先反向搜索求解冲突集的方法.针对CSISE-Tree方法求解时占用内存空间与元件总数指数级相关的缺点,构建反向深度搜索方法减小求解时所占用内存空间;针对CSISE-Tree方法不能对部分非极小的冲突集进行剪枝的问题,给出对非冲突集和更多非极小的冲突集进行剪枝的方法,有效减少了求解时调用SAT(Boolean SATisfiability problem)求解器的次数;实验结果表明,与CSISE-Tree方法相比,本文提出的方法求解效率有明显的提升,并避免了求解时的内存爆炸问题.
[Abstract]:Model based diagnosis is an important research direction in the field of artificial intelligence. Solving minimal conflict sets has an important application in model based diagnosis. On the basis of deep research on the method of solving conflict set with CSISE-Tree, this paper reconstructs the process of computing conflict set combined with enumeration tree according to the feature of conflict set solving, and puts forward a method of solving conflict set based on depth first reverse search. In order to solve the problem that the memory occupied by the CSISE-Tree method is related to the exponential level of the total number of components, the inverse depth search method is constructed to reduce the memory space occupied in the solution, and the CSISE-Tree method can not prune some non-minimal conflict sets. The pruning method for non-conflict sets and more non-minimal conflict sets is given, which effectively reduces the number of calls to SAT (Boolean SATisfiability problem) solvers in the solution, and the experimental results show that the efficiency of the proposed method is significantly improved compared with that of the CSISE-Tree method. The problem of memory explosion is avoided.
【作者单位】：吉林大学计算机科学与技术学院;符号计算与知识工程教育部重点实验室(吉林大学);吉林大学软件学院;
【基金】：国家自然科学基金(No.61133011,No.61402196,No.61272208,No.61003101,No.61170092) 吉林省科技发展计划项目基金(No.20140520067JH) 浙江省自然科学基金(No.LY16F020004)
【分类号】：TP18

【相似文献】