一种改进的回答集逻辑程序分割方法及程序化简研究

发布时间：2017-11-07 13:41

  本文关键词：一种改进的回答集逻辑程序分割方法及程序化简研究

  更多相关文章： 非单调逻辑 回答集编程 分割集 程序分割 程序化简

【摘要】：人工智能是计算机科学中的一个重要分支,其中的知识表示与推理则是一门通过刻画知识和理解逻辑,以计算机为载体实现人类智能为目的的学科。非单调逻辑是进行知识表示与推理的主要手段。本文研究的回答集编程(ASP:Answer Set Programming)则是非单调逻辑的研究热点。随着回答集编程领域多年以来的发展,其求解器已比较成熟。然而,回答集编程求解器的效率问题依旧是该领域的研究重点。在ASP求解器提速的发展过程中,Lifschitz和Turner在1994年提出了分割集(Splitting Set)和程序分割(Program Splitting)的概念,并从理论上证明了一个ASP逻辑程序可以通过分割集被划分为底部(bottom)和顶部(top)两部分,并根据这两部分的回答集可以计算得到原程序的回答集。分割集和程序分割的提出,为ASP求解器的提速带来了新思路。在后续的时间里,分割集和程序分割得到了不断的推广。然而,Lifschitz和Turner当初定义的分割集需要满足较为苛刻的条件,在实际情况中往往会出现一个ASP逻辑程序的分割集就只有空集和程序中全部原子构成的集合,而这样的分割集对于分割程序是没有任何意义的。本文对Lifschitz和Turner提出的分割集和程序分割方法进行了探讨和研究,所获得的主要成果具体如下:首先,把Lifschitz和Turner原来定义的分割集扩展为任意原子集,同时为正规逻辑程序提出了新程序分割方法,及把新程序分割方法扩展到了析取逻辑程序,和提出强程序分割方法。在分割集可以为任意原子集的情况下,程序分割方法的适用范围得到了扩展。其次,本文分析了任意原子集构成的分割集对新程序分割的性能影响,找出主要性能瓶颈所在并给出了改进的方案。同时,通过实验数据验证了使用新分割集和新程序分割方法求解一个ASP逻辑程序的回答集比直接求解更快,提速效果大致维持在2到3倍。最后,在分析新分割集对新程序分割方法的性能影响之时,得到结论:如果分割集中原子都被原程序的每个回答集所满足,那么使用这样的分割集来分割程序可以有效降低原程序回答集的计算复杂性。基于这个发现,本文把分割集的应用扩展到了程序化简当中,即通过程序结论(Consequence)去化简ASP逻辑程序。程序化简的目的依旧是为了让回答集程序的求解提速。本文提出的新分割集与新程序分割给求解回答集程序的提速带来了实质性的效果,并由此推广分割集的思想到程序化简这样的实际应用当中,为回答集程序的求解提速带来了新思路。
【学位授予单位】：中山大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP18

【相似文献】

中国期刊全文数据库 前10条

1 柴振荣;逻辑程序的操作优化问题[J];管理科学文摘;1995年03期

2 王克文,周立柱,陈火旺;扩充析取逻辑程序的争论语义(英文)[J];软件学报;2000年03期

3 张永刚,孙吉贵;约束逻辑程序的一个新语义研究[J];广西师范大学学报(自然科学版);2003年01期

4 谢红梅,王建东,周勇;含有文字序逻辑程序的一种辩论语义[J];南京航空航天大学学报;2005年01期

5 谭成予;董红斌;梁意文;钱立进;;逻辑程序的事实维护[J];计算机工程与应用;2006年09期

6 周勇;朱梧i，

本文编号：1152676