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

发布时间：2024-05-13 23:01

　　基于回答集(或稳定模型)语义的逻辑程序(Answer Set Program,简称ASP),是一种描述性问题求解的范例。由于其非单调的本质特征和各种有效的回答集求解系统的出现,而被广泛应用于智能规划、诊断、调度等领域。相变(phase transition)是研究复杂系统性质的一种重要方法,在可满足性问题(SAT)和正规逻辑程序等方面获得了深刻的理论结果。析取逻辑程序回答集存在性等问题的复杂性在多项式分层上比正规逻辑程序高一层,本文研究析取逻辑程序的相变性质,主要包括:(1)证明了任何析取逻辑程序模等价于句法简单的析取逻辑程序,即对任何析取逻辑程序P,存在一个析取逻辑程序Q,其中的所有规则头中(至多)含有2个原子,规则体中(至多)含有两个文字,使得在限制到P中出现的原子集上时P和Q有相同的回答集。(2)证明了规则头中(至多)含有2个原子的最大析取逻辑程序回答集的存在性问题,规则体中文字数大于1时,最大逻辑程序没有回答集;规则体文字数为1时,最大逻辑程序有n个大小为n)1(-的回答集,其中n为程序中的原子数。(3)借用图的kernel性质,将判断逻辑程序是否具有回答集用能量函数表示出来,...

【文章页数】：68 页

【学位级别】：硕士

【部分图文】：

图2-2ASP求解过程

图2-2ASP求解过程两个实例来进行说明：：基于回答集逻辑程序比较直观的应用就是排课系统。虽然排课

图2-3析取逻辑程序编写图着色用gringo基化器和claspD求解器求解程序，能够很容易得到图中可能的着色方案，如

条规则就能把问题表述清楚。规则r1表示每一个节点可以有三的节点之间不能是相同的颜色，规则r3表示一个节点只能有一事实的集合F表示。F{r1,r2,r3}有回答集当且仅当图G是可有6个节点，11条边。我们可以得到下面的程序，如图2-3：

图2-4求解图可着色方案

图2-4求解图可着色方案解相关概念

图5-4随着m/n值的增加，不同ratio，对应求解逻辑程序需要的loop

(b)n=15(a)n=10图5-4随着m/n值的增加，不同ratio，对应求解逻辑程序需要的loop为了增加实验数据的可信度，我们对n15、ratio0.5的22DLP(n,m)类程序在

本文编号：3972839