我如何在答案集编程中对此进行编码？

Question

我是回答集合编程的新手，我正在为一个相当简单的问题而苦苦挣扎。程序需要用clingo编写。

那么问题来了：

An abstract argumentation framework consists of a set A of arguments and an attack relation R ⊆ A X A between them. For any two arguments a1 and a2, if (a1, a2) ∈ R then we say that a1 attacks a2: if one admits argument a1 then it casts doubts on argument a2. Formally, a subset of arguments E ⊆ A is stable if the following two conditions hold:

no arguments in E attack any other argument of E.

any argument outside of E is attacked by an argument from E.

Write an ASP program that identifies stable subsets of arguments in a given instance through answer sets. The instance will be provided via two predicates argument/1 and attack/2 corresponding to A and R respectively.

这是一个例子：

argument (a).    
argument (b).    
argument (c).    
argument (d).    
attack (a,b).    
attack (b,c).    
attack (d,c).

有效输出：

choose (a) choose (d)

这是我试过的，显然是错误的：

choose(X)  :- argument(X), attack(X,Y).

我完全不知道如何处理这个问题。

请帮忙。

Answer 1

一个简单的 3 步解决方法如下：

描述事实（勾选）
生成您想要的结果，但让程序自行选择
给出不适用解决方案的规则

所以从 2 开始：

产生可能的结果。用简单的话来想一想：对于每个参数，我选择它或不选择它。
可能会或可能不会 部分可以用 subsum {}.

来解决

{choose(X)} :- argument(X).

或更简单：我从参数中选择一个小数

{choose(X):argument(X)}.

让我们检查 Potassco 和 #show choose/1. 的解决方案，共振模式 enumerate all:

Answer: 1

Answer: 2
choose(b)
Answer: 3
choose(c).
..
Answer: 15
choose(a) choose(b) choose(c)
Answer: 16
choose(a) choose(b) choose(c) choose(d)
SATISFIABLE

找到所有组合。是时候删除错误的东西了。再说一次：用简单的话来想一想：我不可能选择一个攻击另一个的两个论点。（如果头部保持打开状态，这将被读取为 False。）

:- choose(X), attack(X,Y), choose(Y).

现在再检查一遍：

Answer: 1

Answer: 2
choose(a)
Answer: 3
choose(d)
Answer: 4
choose(a) choose(d)
Answer: 5
choose(c)
Answer: 6
choose(a) choose(c)
Answer: 7
choose(b)
Answer: 8
choose(b) choose(d)
SATISFIABLE

现在我们需要确保每个未选择的参数都受到至少一个选择元素的攻击：

1 {choose(Y):attack(Y,X)} :- argument(X), not choose(X).

读取：对于每个未被选择的论点 X， 攻击它的被选择论点的数量至少是一个。

让我们检查一下：

Answer: 1
choose(a) choose(d)
SATISFIABLE

不错。

由于约束通常是用空头制定的，让我们重新制定最后一条规则：

:- argument(X), not choose(X), {choose(Y):attack(Y,X)} 0.

读取：没有参数 X，它没有被选择并且最多有 0 个选择的参数，攻击 X。 它给出了相同的输出。

完整代码：

argument (a;b;c;d).   
attack (a,b).    
attack (b,c).    
attack (d,c).

{choose(X):argument(X)}.
:- choose(X), attack(X,Y), choose(Y).
:- argument(X), not choose(X), {choose(Y):attack(Y,X)} 0.

#show choose/1.

我如何在答案集编程中对此进行编码？

How do I encode this in answer set programming?

answer-set-programming

clingo