Как мне указать моей программе раскраски графа назначать цвет 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.

Если бы кто-нибудь мог мне помочь, это было бы очень признательно.


answer-set-programming clingo
person Tha Mikenater    schedule 17.10.2019    source источник

Ответы (2)


arrow_upward
1
arrow_downward

В этом простом случае ограничения на однократное использование одного цвета вы можете написать единственное ограничение

:- assign(N, 1), assign(M, 1), node(N), node(M), N!=M.
person vukk    schedule 18.10.2019

arrow_upward
0
arrow_downward

На самом деле, строка, которую вы пометили как под вопросом:

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 является узлом. Это будет учитывать все узлы, а не каждый отдельный.

person BobHU    schedule 17.11.2019