命题知识库更新的算法及其复杂性  

THE ALGORITHM AND COMPLEXITY OF PROPOSITIONAL KNOWLEDGE BASE REVISION

作　　者：陶雪红[1] 孙伟[1] 马绍汉[1] 

机构地区：[1]山东大学计算机系

出　　处：《软件学报》1996年第5期300-305,共6页Journal of Software

基　　金：国家自然科学基金

摘　　要：本文介绍了知识库更新的基本概念及命题知识库更新的复杂性研究现状．近年来，学者们提出了许多方法进行命题知识库的更新，一类是基于公式的方法；一类是基于模型的方法，但所有这些方法在通常情况下都是难解的．本文讨论基于公式的Ｇｉｎｓｂｅｒｇ更新方法，并给出在公式个数远小于变元个数情况下的一个多项式时间算法．This paper gives an outline of knowledge base revision and some recently presented complexity results about propositional knowledge base revision. Different methods for revising propositional knowledge base have been proposed recently by several researchers, some are formula--based methods and the others are model-based methods, but all methods are intractable in the general case. This paper discusses a formula-based method-Ginsberg's method, and presents a polynomial algorithm when the number of formulas is far less than the number of variables.

关 键 词：人工智能 知识加更新 算法 复杂性 知识库 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]