1

我在 Clingo 中定义了图形着色问题，如下所示：

node(sa;wa;nt;q;nsw;v;t).
color(r;g;b).

edge(sa,(wa;nt;q;nsw;v)).
edge(wa,nt). edge(nt,q). edge(q,nsw). edge(nsw,v).
edge(X,Y) :- edge(Y,X).

我有这样的解决方案：

{assign(N,C) : color(C)} = 1 :- node(N).
:- edge(X,Y), assign(X,C1), assign(Y,C2), C1 == C2.
#show assign/2.

我无法理解= 1代码生成部分的含义。我知道它是“设置基数”，但我不明白如何，因为代码必须在每个答案中生成七个节点。此外，以下生成器（生成所有节点组合和在一组长度 7 中选择的颜色）需要= 7：

{assign(N,C) : color(C), node(N)} = 7.

这是我正在解决的图形着色问题的图片：https ://imgur.com/a/tX7qtkJ

和坚持： https ://potassco.org/cligo/run/

4

1 回答 1

2 
{assign(N,C) : color(C)} = 1 :- node(N).

这意味着“为每个节点选择一种颜色”。或者，更准确地说，对于每个节点n，选择一种颜色c以使其assign(n, c)成为真的。

为了更好地理解这一点，我们需要深入研究 ASP 的语义。这里 N 出现在基数约束之外，因此可以将其视为该规则中的“全局变量”。该规则本质上是以下内容的简写：

 {assign(sa,C) : color(C)} = 1 :- node(sa).
 {assign(wa,C) : color(C)} = 1 :- node(wa).
 {assign(nt,C) : color(C)} = 1 :- node(nt).
 {assign(q,C) : color(C)} = 1 :- node(q).
 {assign(nsw,C) : color(C)} = 1 :- node(nsw).
 {assign(v,C) : color(C)} = 1 :- node(v).
 {assign(t,C) : color(C)} = 1 :- node(t).

现在，这个集合{assign(sa,C) : color(C)}只是 {assign(sa,r), assign(sa,g), assign(sa,b)}. 现在，{assign(sa,r), assign(sa,g), assign(sa,b)}=1粗略地说是从 set 中选择一个元素{assign(sa,r), assign(sa,g), assign(sa,b)}。

如果您查看 cligo 手册，一般语法是 {assign(sa,r), assign(sa,g), assign(sa,b)} rel EXPR, whererel是算术关系并且EXPR是一些表达式。

于 2018-11-18T23:14:16.517 回答