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