传统的知识推理算法主要依赖于通用的定理证明器,因此会有明显的组合爆炸问题和半自动化问题,只能处理小规模的问题.在文[1]中,给出了一个实用而紧致的知识的语义模型--知识结构(knowledge structure),并给出相应的利用BDD(Binary Decision Diagram)的符号化计算方法,实验表明这种基于BDD的算法比传统方法有很大的优势,但这种基于BDD的方法在计算规模大的例子时仍存在明显的组合爆
lSSN1673—94l8of
CODENJKYTA8
ScienceandTechnology
E—nmll
Journal
Computer
1673—9418/2007/01(01)一0079—08
Frontiersof
Tcl+86一lO一51616056
hnp1lvn㈣eeaj
fcst@nci
术
acell
org
一种规约于可满足性问题
苏开乐.陈清亮+.岳伟亚
SUKai—le,CHEN
(SAT)的
知识推理算法
Qing—liang,YUEWei—ya
中f『I大学计算机科学系.J'州510275
Department
of
Comput,r
Science.Sun
Yat—senUniversity。,Gumlgzhou510275,China
+Cm'respondingauthor:E—main:tsingliangchen@94nail.com
SUKai—le.CHlENFrontiersof
Qing—liang.YUEWei—ya.SAT—basedalgorithm
for
knowledgereasoning.Journal
of
ComputerScienceandTechnology,2007,1(1):79-86.
Abstract:Traditionalplosion
problemandhas
been
knowledge
can
reasoningsrely
on
the
generaltheoremprovers
concrete
andmayof
sull;rthe
called
stateex—
only
deat
withtoyexamoreples.Am
presents
a
model
knowledgeknowledge
and
OFt
structure
introduced
in(1】,whichBDD-basedapproachfor
a
computingknowledge
showsthe
greatimprovement.But
structure,anis
the
BDD—basedapproachstillhas
way
substantialstate
explosionproblem.Basedknowledge
the
reasoning
state
knowledge
agents
alternativeandeffective
SAT
can
by
SATsolvingpowerful
in
forthein
a
groupofillustrated,since
bemuchmore
this.
ithdealingw
explosion
problemthan
BDDs.Finallytheexperimental
resultsprove
Keywords:knowledge
structure;knowledgereasoning;satis6ability(sAT)
摘要:传统的知识推理算法主要依粕于通用的定理证明器.因此会有明显的组合爆炸问题和半自动化问题.
只能处理小规模的问题。在文『1]中,给出了一个实用而紧致的知识的语义模型——知识结构(knowledge
ture),并给出相应的利用BDD(Binary
Decision
struc—
Diagram)的符号化计算方法,实验表明这种基于BDD的算法比
传统方法有很大的优势,但这种基于BDD的方法在计算规模大的例子时仍存在明显的组合爆炸。文章在知识结构(knowledgestructure)的语义基础上,通过挖掘知识结构语义中各元素的关系,把知识的计算规约于可满足性问题(SAT),因为SATSoh,er在符号化计算方面以及在计算规模和效率上都要明显优于BDD,、实验结果证实了这种方法的有效性.
关键词:知识结构;知识推理;可满足性问题(SAT)文献标识码:A
中图分类号:TP3叭
8
theNationalthe
GrandFundamentalResesreh973ProgramofChinaunderGrant
ScienceFoundationofof
ChinaunderGrantof
China
under
No.2005CB321902(囤家重点基础研究发展规划(973));
Natural
in
NafimmlNatural
No.60496327,10410638,60473004(国家自然科学基金);the
Grant
ScienceFoundation
Guangdong
Province
No.04205407(r东省自然科学基金);the
Open
Fund
Shan曲ai
Intelligent
INbrmafionProcessingKaboratoryundereyLGrar,t(k淘t市智能信息处理重点实验室开放课题资助项目)
Received2007—02,Accepted2007—04
对可满足性SAT问题求全解的算法研究及实现_IT/...在这 一推理算法中,每个子句有两个相关的指针,分别... 中医养生知识大全 女人养生之道 78份文档 笑翻...
2012 利用一种 SAT 问题全解算法求 Trivium 可滑动对戴江海, 戚文峰( 信息工程大学 信息工程学院, 河南 郑州 450002) 摘要: Trivium 是进入到 eSTREAM 计划最终...
实验结果验证了 这项新的正向推理技术的有效性,并...可满足性问题算法(TheSatisfiabilityProblem, 简称SAT...章简要介绍和说明了有关可满足性问题的基础知识和 ...
(如C,C++),或者学过数字电路的基本 知识的人,对...而且在自动化推理,人工智 能,资源调度,VLSI集成电路...电子科技大学硕士学位论文 1.1.2 SAT问题及其算法...
一种新的SAT问题预处理算法熊 伟.唐璞山(复旦大学专用集成电路与系统国家重点实验室.上海201203) 抽要:提出了一项新的正向推理技术:对祢扩展的一元子句推导(...
一种新的SAT问题预处理算法一种新的SAT问题预处理算法隐藏>> 20 年第 2卷...算法的 有 效性, 证明了 这项对 称扩展一元推导技术的 强大正 向 推理能力...
命题逻辑 可满足性问题的算法 分析[J]. 计算机科学...? BMC问题能够有效地规约成命题SAT问题。 只考虑一...它们的最短的推理出空 子句的归结证明长度是指数的...
改进了二种组合电路设计错误诊断DED(Design Error Diagnosis)算法。它使用多可满足性问题(SAT)求解技术,通过对布尔可满足解计数来实现对多个逻辑错误的诊断定位。...
产生了传统语言设计所不存在的错误可能性,或者使 得传统软件测试中的重点不再...基于范畴划 分方法构造测试层次算法, 将操作的输入空间划分为具有某些相同性质的...
规约为命题逻辑的可 满足性问题,从而可以使用 SAT ...魏小勇 基于OBDD的SMC中PRE操作的改进算法 2008(14...分析方法,在验证电子商务协议时,它的 逻辑推理能力...
热门文档