-
题名结合SE-Tree结构特征的极小碰集求解算法
被引量:3
- 1
-
-
作者
刘思光
欧阳丹彤
王艺源
贾凤雨
张立明
-
机构
吉林大学计算机科学与技术学院
符号计算与知识工程教育部重点实验室(吉林大学)
-
出处
《计算机研究与发展》
EI
CSCD
北大核心
2016年第11期2556-2566,共11页
-
基金
国家自然科学基金项目(61133011
61402196
+5 种基金
61272208
61003101
61170092)
中国博士后科学基金项目(2013M541302)
吉林省科技发展计划基金项目(20140520067JH)
浙江师范大学计算机软件与理论省级重中之重学科开放基金项目(ZSDZZZZXK12)~~
-
文摘
在结合SE-Tree计算集合簇极小碰集的过程中,现有算法会对大量不会产生碰集的冗余节点进行访问.这无疑将影响算法的效率,冗余节点比例越高,影响越大.通过对SE-Tree中叶节点的特殊性质的分析,并结合现有碰集算法有解空间中冗余节点的特征,提出非解冗余节点概念.在对SE-Tree的结构特征进行深入分析基础上,根据非碰集的子集也不是碰集的特点,提出辅助剪枝的概念,通过在剪枝树上设置剪枝判定节点,减少对极小碰集求解过程中无解空间的访问;针对较大规模问题,还提出结合多级辅助剪枝树的极小碰集求解算法,进而较大程度地减少对非解冗余节点的访问;根据多级辅助剪枝树及SE-Tree的结构特征,给出提前终止算法的判定条件,并证明了此算法的正确性.实验结果表明:与效率较高的Boolean算法相比,该算法高效且易于实现,尤其是对规模较大的问题,效率能提升1个数量级.
-
关键词
基于模型诊断
极小碰集
集合枚举树
辅助剪枝树
无解空间剪枝
-
Keywords
model-based diagnosis
minimal hitting set
SE-Tree
assistant pruning tree
nonsolution space pruning
-
分类号
TP18
[自动化与计算机技术—控制理论与控制工程]
-
-
题名基于模型诊断中结合问题特征的新方法
被引量:6
- 2
-
-
作者
欧阳丹彤
周建华
刘伯文
张立明
-
机构
吉林大学软件学院
吉林大学计算机科学与技术学院
符号计算与知识工程教育部重点实验室(吉林大学)
-
出处
《计算机研究与发展》
EI
CSCD
北大核心
2017年第3期502-513,共12页
-
基金
国家自然科学基金项目(61672261
61502199
+2 种基金
61402196
61272208)
浙江省自然科学基金项目(LY16F020004)~~
-
文摘
基于模型诊断一直是人工智能领域中热门的研究问题.近些年来,随着SAT求解器效率的逐渐提高,基于模型的诊断也被转换成SAT问题进行求解.在对基于模型诊断求解方法 CSSE-tree深入研究基础上,结合诊断问题和SAT求解过程的特征,给出先对包含组件个数较多的候选诊断进行求解的方法,进而减小SAT求解问题的规模;在对极小诊断解和非极小诊断解剪枝方法的基础上,首次提出非诊断解定理及非诊断解空间的剪枝方法,有效地实现了对诊断的无解空间进行剪枝.根据组件个数较多的候选诊断先求解及有解无解剪枝方法特征,构建基于反向搜索的LLBRS-tree方法.实验结果表明:与CSSE-tree算法相比,LLBRS-tree算法减少了SAT求解次数、减小了求解问题规模,效率较好,尤其是求解多诊断时效率提高更为显著.
-
关键词
基于模型的诊断
无解空间剪枝
合取范式
SAT求解器
枚举树
-
Keywords
model-based diagnosis
non-solution space pruning
conjunctive normal form
SAT solver
set-enumeration-tree
-
分类号
TP18
[自动化与计算机技术—控制理论与控制工程]
-