EDA365欢迎您登录！
您需要 登录 才可以下载或查看，没有帐号？注册
x
结合问题特征利用SE-Tree反向深度求解冲突集的方法
' d/ Q$ ^. E2 x* Q; u/ H) e) X/ R摘要:基于模型诊断是人工智能领域内的一个重要研究方向,求解极小冲突集在基于模型诊断中有着重要应用.在对结合CSISE-Tree求解冲突集方法深入研究的基础上,根据冲突集求解特征重构了结合枚举树的计算冲突集的过程,提出基于深度优先反向搜索求解冲突集的方法.针对CSISE-Tree方法求解时占用内存空间与元件总数指数级相关的缺点,构建反向深度搜索方法减小求解时所占用内存空间;针对CSISE-Tree方法不能对部分非极小的冲突集进行剪枝的问题,给出对非冲突集和更多非极小的冲突集进行剪枝的方法,有效减少了求解时调用SAT( Boolean SATisfi-ability problem)求解器的次数;实验结果表明,与CSISE-Tree方法相比,本文提出的方法求解效率有明显的提升,并避免了求解时的内存爆炸问题.
/ u5 }" I' U M$ w B关键词:基于模型诊断;冲突集;布尔约束可满足;集合枚举树. Y$ [' u) L6 `$ F8 m! {
6 M! B7 O3 l. T# E/ X6 }- F1 引言
& z5 u3 ]% Z8 f* ~基于模型诊断( Model _ based Diagnosis , MBD)是人工智能领域内的重要的研究方向之一,对整个人工智能领域的发展起着十分重要的作用”.著名诊断学者de Kleer首次提出了冲突集的概念2,对基于模型诊断的求解起到了巨大的推动作用,在人工智能其它领域也得到了广泛的应用.
, m% o, b0 J3 ^) X) ~著名MBD专家 Reiter指出求解极小冲突集( Minimal Conflict Set , MCS)和求解极小冲突集的极小碰集(Hitting-Set , HS)是求解最终诊断结果的两个重要步骤[ 3.随后有许多学者参与到求解极小冲突集与求解极小碰集的研究中4~61,出现了许多求解冲突集的算法.早期冲突集求解方法主要有利用定理证明器的方法 DART[7]和 Haenni[8]使用归结的方法.国内也有许多学者对冲突集的求解做过研究,如栾尚敏等给出的用系统结构信息来求解极小冲突集9],代树武等人利用元件参数矩阵求解极小冲突集[ 10].Feldman等!"1学者指出冲突集和诊断集间存在二元关系,即冲突集的碰集是诊断,而诊断的碰集是冲突集,并给出了基于冲突集和诊断集二元性的诊断求解方法. Amgoud 等[ 12学者则将冲突集用于
9 A' C: Q8 t1 _ L& K. ~. E. ?! d
' F/ d2 T1 j0 E# O& S0 _+ z A
2 V% e2 I+ u: Y$ A# t) Q" `2 O) C( E3 q7 o5 A( q; I: x% \
| 
/1 
发表于 2021-5-17 13:39
收藏
淘帖
支持！
反对！