1

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

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 的行是给我带来问题的行。这是我尝试过的另一种无效的解决方案：

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.

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

4

2 回答 2

1

在这个限制单一颜色使用一次的简单案例中，您可以编写单一约束

:- assign(N, 1), assign(M, 1), node(N), node(M), N!=M.
于 2019-10-18T12:53:37.533 回答
0

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

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

可以翻译为

如果N是一个节点，我们将（而且我们必须）分配color(1)给node(N)并且只分配一次，即如果node(i)为真，我们将只有一个node(i, 1)。

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

回到您的要求：

我如何告诉程序一次只分配颜色 1？

这里的问题是您在该行中设置的约束：“颜色 1 仅分配一次”适用于每个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是一个节点。这将计算所有节点而不是每个节点。

于 2019-11-17T13:08:52.950 回答