1

我正在学习人工智能课程，我们正在使用答案集编程（特别是 Clingo）。我们目前主要谈论的是理论，我在区分模型和最小模型时遇到了一些麻烦。我有以下定义：

满足定程序的规则、模型、最小模型和答案集

  1. 如果程序在其规则主体中没有“不”，则称为确定程序。
  2. 集合 S 被称为满足以下形式的规则 a :- b1, ..., bm, not c1, ..., not cn。如果它的主体被 S 满足（即 b1 ... bm 在 S 中，而 c1 ... cn 都不在 S 中）意味着它的头部必须被 S 满足（即 a 在 S 中）。
  3. 如果集合 S 满足该程序的所有规则，则称它满足该程序。
  4. 如果 (a) S 满足 P（也称为 S 是 P 的模型）并且 (b) S 的严格子集不满足 P（即 S 是P 的最小模型）。

带着问题（从讲座幻灯片中提取，而不是家庭作业）：

P is defined as:
a :- b,e.
b. 
c :- d,b.
d.

Which of the following are models and least models?
{}, {b}, {b,d}, {b,d,c}, {b,d,c,e}, {b,d,c,e,a}

谁能告诉我上述问题的答案是什么？我可能可以从那里找出区别，尽管如果有人可以解释普通话的区别（而不是教科书的定义），那就太好了。我不确定在哪个论坛发布这个问题 - 请让我知道它是否应该发布在其他地方。

谢谢

4

1 回答 1

2

首先，请注意幻灯片的这一部分是在讨论肯定程序 P（也称为确定程序）的答案集，即使它也提到了not。正程序是简单的情况，对于一个正程序P总是存在一个唯一的最小模型LM ( P )，它是它所有模型的交集。

在规则主体中不允许规则使事情变得更加复杂。规则的主体是 的右侧。:-

问题的答案是，按组设置：

  • S={}不是模型，因为 b 和 d 是事实b. d.
  • S={b}不是模型，因为 d 是事实d.
  • S={b,d}不是模型，因为 c 隐含在 S 中，c :- d,b.而 c 不在 S 中
  • S={b,d,c} 是一个模型
  • S={b,d,c,e}不是模型，因为 a 被隐含a :- b,e.并且 a 不在 S
  • S={b,d,c,e,a} 是一个模型

那么最小的模型是什么？这是 S={b,c,d} 因为没有 S 的严格子集满足P。

我们可以通过两种方式得出正规划P的最小模型：

  • 枚举所有模型并取它们的交集（此处为 {b,c,d}∩{a,b,c,d,e}={b,c,d}）。
  • 从事实开始（此处b. d.）并迭代地将隐含原子（此处c :- b,d.）添加到 S，重复直到 S 成为模型并在该点停止。

就像您的幻灯片说的那样，肯定程序P的答案集的定义是：如果 S 是P的最小模型，则 S 是P的答案集。更严格地说，这实际上是当且仅当，因为最小模型LM ( P ) 是唯一的。

最后一点，因此您以后不会被它们弄糊涂，约束 :- a, b实际上只是x :- not x, a, b. 因此，包含约束的程序不是正程序；尽管它们一开始可能看起来像，因为约束的主体似乎不包含not。

于 2014-09-23T07:05:55.053 回答