Не может понять ограничение количества элементов в клинго - PullRequest
Новая
       32

Не может понять ограничение количества элементов в клинго

0 голосов
/ 13 ноября 2018

У меня есть проблема раскраски графа, определенная в 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/clingo/run/

1 Ответ

0 голосов
/ 19 ноября 2018 
{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 грубо говоря, означает выбрать один элемент из набора {assign(sa,r), assign(sa,g), assign(sa,b)}.

Если вы посмотрите руководство по клинго, общий синтаксис {assign(sa,r), assign(sa,g), assign(sa,b)} rel EXPR, где rel - арифметическое отношение, а EXPR - некоторое выражение.

...