基于回答集逻辑程序的相变问题

摘要

基于回答集（或稳定模型）语义的逻辑程序（Answer Set Program，简称ASP），是一种描述性问题求解的范例。由于其非单调的本质特征和各种有效的回答集求解系统的出现，而被广泛应用于智能规划、诊断、调度等领域。相变（phase transition）是研究复杂系统性质的一种重要方法，在可满足性问题（SAT）和正规逻辑程序等方面获得了深刻的理论结果。析取逻辑程序回答集存在性等问题的复杂性在多项式分层上比正规逻辑程序高一层，本文研究析取逻辑程序的相变性质，主要包括： (1)证明了任何析取逻辑程序模等价于句法简单的析取逻辑程序，即对任何析取逻辑程序P，存在一个析取逻辑程序Q，其中的所有规则头中（至多）含有2个原子，规则体中（至多）含有两个文字，使得在限制到P中出现的原子集上时P和Q有相同的回答集。 （2）证明了规则头中（至多）含有2个原子的最大析取逻辑程序回答集的存在性问题，规则体中文字数大于1时，最大逻辑程序没有回答集；规则体文字数为1时，最大逻辑程序有n个大小为(n?1)的回答集，其中n为程序中的原子数。 (3)借用图的kernel性质，将判断逻辑程序是否具有回答集用能量函数表示出来，通过求解能量函数的基函数就可以判断该函数是否具有回答集。 (4)实验结果表明，析取逻辑程序规则体中负文字比 (0,1)ratio? 时，随着m/n值增加，在某个关键值点有回答集概率由1迅速减为0，发生相变；随着m/n增加，求解回答集需要环的数量达到稳定值，等于n。对于ratio?1时，随着m/n值增加，程序存在回答集的概率会有一个“凹陷”现象，称为“首次半相变”，其中，n为程序中的原子数，m为程序中的规则数。

目录

第一个书签之前

摘要

引言

研究背景和现状

研究的意义

研究内容及结果

文章组织结构

基础知识

一阶语言基本知识

ASP基本定义及实例解析

基本定义

回答集编程实例

ASP求解相关概念

基本定义

完备化

环公式

相变基本知识

研究相变的随机模型

研究相变阈值的方法

本章小结

随机析取逻辑程序

随机产生析取逻辑程序

回答集存在性

最大的析取逻辑程序

最大负析取逻辑程序

空的析取逻辑程序

No-odd-cycle析取逻辑程序

等价转化

本章小结

负二文字逻辑程序

回答集与图kernel

回答集与能量函数

本章小结

实验

实验环境

2-2-DLP(n, m)实验结果分析

负文字占比为0.5

不同负文字比

负文字占比为1

2-1-NDLP(n, m)实验结果

本章小结

总结与展望

附录A

A.1两种否定

A.2摹本公式的来源

致谢

参考文献

在攻读硕士期间的学术论文及科研项目

表版