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

baqiao

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

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

$ G% Z6 P& K" R, C6 \* j3 M1 引言
! e5 Q: A6 O" D4 q5 g, M6 t% X基于模型诊断( Model _ based Diagnosis , MBD)是人工智能领域内的重要的研究方向之一,对整个人工智能领域的发展起着十分重要的作用”.著名诊断学者de Kleer首次提出了冲突集的概念2,对基于模型诊断的求解起到了巨大的推动作用,在人工智能其它领域也得到了广泛的应用.
# A+ |4 \3 x% j  f- s5 h著名MBD专家 Reiter指出求解极小冲突集( Minimal Conflict Set , MCS)和求解极小冲突集的极小碰集(Hitting-Set , HS)是求解最终诊断结果的两个重要步骤[ 3.随后有许多学者参与到求解极小冲突集与求解极小碰集的研究中4~61,出现了许多求解冲突集的算法.早期冲突集求解方法主要有利用定理证明器的方法 DART[7]和 Haenni[8]使用归结的方法.国内也有许多学者对冲突集的求解做过研究,如栾尚敏等给出的用系统结构信息来求解极小冲突集9],代树武等人利用元件参数矩阵求解极小冲突集[ 10].Feldman等!"1学者指出冲突集和诊断集间存在二元关系,即冲突集的碰集是诊断,而诊断的碰集是冲突集,并给出了基于冲突集和诊断集二元性的诊断求解方法. Amgoud 等[ 12学者则将冲突集用于
4 `; z6 X  c# G, {+ f& B

游客，如果您要查看本帖隐藏内容请回复

6 m  N) Q3 Q  Q$ m  c

regngfpcb

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