我如何告诉我的图形着色问题程序一次只分配颜色 1？

Question

基本上，我有一个图形着色程序，其中每个节点与另一个节点的边必须是不同的颜色。这是我的代码：

node(1..4).

edge(1,2).
edge(2,3).
edge(3,4).
edge(4,1).
edge(2,4).

color(1..3).

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

1 { assign(N,1) : color(1) } 1 :- node(N). %line in question

:- edge(N,M), assign(N,C), assign(M,C).

我如何告诉程序只分配颜色 1 一次？标记为 %line in question 的行是给我带来问题的行。这是我试过的另一个解决方案，但没有用：

node(1..4).

edge(1,2).
edge(2,3).
edge(3,4).
edge(4,1).
edge(2,4).

color(1..3).

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

:- edge(N,M), assign(N,C), assign(M,C).

vtx(Node, Color) :- node(Node), color(Color).

1 { vtx(N, 1) : color(1) } 1 :- node(N).

#show vtx/2.

如果有人能帮助我，我将不胜感激。

Answer 1

在这种限制单一颜色使用一次的简单情况下，您可以编写单一约束

:- assign(N, 1), assign(M, 1), node(N), node(M), N!=M.

Answer 2

实际上，您标记为 的行有问题 :

1 { assign(N,1) : color(1) } 1 :- node(N). %line in question

可以翻译成

If N is a node, we will (and we must) assign color(1) to node(N) and only assign once, i.e. If node(i) is true, we will have exactly one node(i, 1).

因此，根据这条规则和您的事实node(1..4)，您将立即得到assign(1,1)、assign(2,1)、assign(3,1)、assign(4,1)。这在颜色问题下是绝对不能满足的（有最后一个约束）。

回到您的要求：

How would I tell the program to only assign color 1, once?

这里的问题是您在行中设置的约束：“color 1 is assigned only once”适用于每个 node(i), i=1,2,3,4 而不是所有节点。

为了更清楚，您不妨考虑将此行实例化为：

1 { assign(1,1) : color(1) } 1 :- node(1). 
1 { assign(2,1) : color(1) } 1 :- node(2). 
1 { assign(3,1) : color(1) } 1 :- node(3). 
1 { assign(4,1) : color(1) } 1 :- node(4).

如果 node(1..4) 全部为真，我们将有 assign(1,1)、assign(2,1)、assign(3,1)、assign(4,1).

你想要的是 assign(N, 1) 在答案中出现一次且仅出现一次，因此在你的规则中，这应该是没有首发条件的。

因此，把问题行改成：

{ assign(N,1): node(N), color(1) } = 1. %problem line changed

您将得到正确的分配：

clingo version 5.4.0
Reading from test.lp
Solving...
Answer: 1
assign(2,2) assign(1,3) assign(3,3) assign(4,1)
Answer: 2
assign(1,2) assign(2,3) assign(3,2) assign(4,1)
Answer: 3
assign(2,1) assign(1,3) assign(3,3) assign(4,2)
Answer: 4
assign(2,1) assign(1,2) assign(3,2) assign(4,3)
SATISFIABLE

直觉上，这一行意味着 assign(N, 1) 在任何情况下都应该在答案集中，只要 N 是一个节点。这将计算所有节点而不是每个节点。

我如何告诉我的图形着色问题程序一次只分配颜色 1？

How do I tell my graph coloring problem program to only assign color 1 one time?

answer-set-programming

clingo