Можно ли решить проблемы удовлетворения ограничений с помощью Пролога?

Разрешены ли проблемы типа «посещение вечеринки» в Прологе? Например:

Лопух Малдун и Карлотта Пинкстоун сказали, что придут, если придет Альбус Дамблдор. Альбус Дамблдор и Дейзи Доддридж оба сказали, что придут, если придет Карлотта Пинкстоун. Альбус Дамблдор, Бердок Малдун и Карлотта Пинкстоун сказали, что придут, если придет Эльфрида Клэгг. Карлотта Пинкстоун и Дейзи Доддридж сказали, что придут, если придет Фалько Эзалон. Лопух Малдун, Эльфрида Клэгг и Фалько Эзалон сказали, что придут, если придут Карлотта Пинкстоун и Дейзи Доддридж. Дейзи Доддридж сказала, что придет, если придут Альбус Дамблдор и Бердок Малдун. Кого нужно убедить присутствовать на вечеринке, чтобы обеспечить присутствие всех ее приглашенных?

Я попытался выразить это в GNU Prolog:

attend(BM) :- attend(AD).
attend(CP) :- attend(AD).
attend(AD) :- attend(CP).
attend(DD) :- attend(CP). 
attend(AD) :- attend(EC).
attend(BM) :- attend(EC).
attend(CP) :- attend(EC). 
attend(CP) :- attend(FA).
attend(DD) :- attend(FA).
attend(BM) :- attend(CP),attend(DD).
attend(EC) :- attend(CP),attend(DD).
attend(FA) :- attend(CP),attend(DD).
attend(DD) :- attend(AD),attend(BM).

attend(FA). /* try different seed invitees in order to see if all would attend*/

/* input:
write('invited:'),nl,
  attend(X),write(X),nl,
  fail.*/

Я испытываю переполнение стека (без каламбура) и не знаю, как вычислить пролог, поэтому и спрашиваю.

Вообще говоря, эту проблему можно привести к булевой формуле удовлетворения CNF (с 6 булевыми переменными). Следовательно, есть ли у перспективы пролога какие-либо достоинства?

Чтобы решить проблему с Прологом, как и с любым языком программирования, будь то декларативный или императивный, вам нужно подумать о представлении решения и входных данных.

Поскольку это вопрос программирования, он был бы популярен на StackOverflow.com, где программисты решают задачи программирования. Здесь я бы попытался быть более научным.

Чтобы решить проблему в OP, необходимо изменить отношение, определенное зависимостями, указанными во входных данных. Пункты вида т т е л д ( Х ) → т т е н д ( У ) ∧ т т е н д ( Z ) легко обратное. Пункты A t t e n d ( A D ) ∧ A t t e n d ($Attend(X) \to Attend(Y) \wedge Attend(Z)$ как$Attend(AD)\wedge Attend(BM)\to Attend(DD)$

Дейзи Доддридж сказала, что придет, если Альбус Дамблдор и Бердок Малдун придут

сложнее лечить.

С Прологом первый простой подход состоит в том, чтобы избежать полного изменения отношений и быть направленным на достижение цели.

Принять порядок в списке гостей и использовать правило

$\qquad \left\{\begin{align} A(X)\wedge A(Y) &\to A(Z), \\ A(W)&\to A(X), \\ A(W)&\to A(Y), \\ X&<Z, \\ Y&<Z\end{align}\right\}\quad \vdash \quad A(W) \to A(Z)$

(Мы используем вместо A t t e n d ( X ), чтобы сократить его)$A(X)$$Attend(X)$

Это правило легко реализовать.

Довольно наивный подход

Для удобства чтения позвольте followsбыть отношением, данным как вход, и bringsбыть его обратным.

Тогда вход дается

follows(bm,[ad]).
follows(cp,[ad]).
follows(ad,[cp]).
follows(dd,[cp]).
follows(ad,[ec]).
follows(bm,[ec]).
follows(cp,[ec]).
follows(cp,[fa]).
follows(dd,[fa]).
follows(bm,[cp,dd]).
follows(ec,[cp,dd]).
follows(fa,[cp,dd]).
follows(dd,[ad,bm]).

И bringsможет быть определено следующим образом:

brings(X,S):-brings(X,S,[]).

brings(_X,[],_S).
brings(X,[X|L],S):-brings(X,L,[X|S]).
brings(X,[Y|L],S):-follows(Y,[X]),brings(X,L,[Y|S]).
brings(X,[Y|L],S):-follows(Y,[A,B]),
          member(A,S),member(B,S),brings(X,L,[Y|S]).

brings/3(X,L,S)$X$

Если мы определим

 partymaker(X):-Guests=[ad,bm,cp,dd,ec,fa],member(X,Guests),brings(X,Guests).

Мы получаем следующие уникальные решения:

 [ad,ec]

Это не полный список, так как под алфавитным порядком пункт

 follows(bm,[cp,dd]).

не работает.

Довольно сложное решение оригинальной головоломки

Чтобы полностью решить проблему, вы должны позволить системе попытаться доказать посещаемость для последующих гостей, не вводя бесконечные циклы в дерево поиска. Есть несколько способов достижения этой цели. У каждого есть свои преимущества и недостатки.

Одним из способов является переопределение brings/2следующим образом:

brings(X,S):-brings(X,S,[],[]).

% brings(X,RemainsToBring,AlreadyTaken,AlreadyTried).
%
% Problem solved
brings(_X,[],_S,_N). 
% Self
brings(X,[X|L],S,N):-brings(X,L,[X|S],N). 
% Follower
brings(X,[Y|L],S,N):-follows(Y,[X]),brings(X,L,[Y|S],N). 
% Y is not a follower, but X can bring 2
brings(X,[Y|L],S,N):- \+member(Y,N),\+follows(Y,[X]), 
                   follows(Y,[A,B]),
                   try_bring(X,A,L,S,[Y|N]),
                   try_bring(X,B,L,S,[Y|N]),brings(X,L,[Y|S],N).
% Y is not a follower, but X can bring 1
brings(X,[Y|L],S,N):- \+member(Y,N),\+follows(Y,[X]),\+follows(Y,[_A,_B]), 
                   follows(Y,[C]),
                   try_bring(X,C,L,S,[Y|N]),brings(X,L,[Y|S],N).

try_bring(_X,A,_L,S,_N):-member(A,S).
try_bring(X,A,L,S,N):- \+member(A,S),sort([A|L],Y),brings(X,Y,S,N).

Последний аргумент в brings/4необходим, чтобы избежать бесконечного цикла в try_bring.

Это дает следующие ответы: Альбус, Карлотта, Эльфрида и Фалько. Однако это решение не является самым эффективным, поскольку вводится обратный путь, где его иногда можно избежать.

Общее решение

$r(X,S): V \to V'$

$S \subseteq V$$V' = V \cup \{X\}$

$V$$U$$V$

add_element(X,V,U):- ( var(V) -> % set difference that works in both modes
                           member(X,U),subtract(U,[X],V);
                      \+member(X,V),sort([X|V],U) ).

support(V,U):- guests(G), % rule application
               member(X,G),
               add_element(X,V,U),
               follows(X,S),
               subset(S,V).

set_support(U,V):- support(V1,U), % sort of a minimal set
               ( support(_V2,V1) -> 
                      set_support(V1,V) ; 
                 V = V1). 

is_duplicate(X,[Y|L]):- ( subset(Y,X) ; is_duplicate(X,L) ).

% purging solutions that are not truly minimal
minimal_support(U,L):-minimal_support(U,[],L).
minimal_support([],L,L).
minimal_support([X|L],L1,L2):-( append(L,L1,U),is_duplicate(X,U) -> 
                                    minimal_support(L,L1,L2); 
                                minimal_support(L,[X|L1],L2) ).


solution(L):- guests(G),setof(X,set_support(G,X),S),
              minimal_support(S,L).

Теперь, если, например, набор данных № 2 задан как

follows(fa,[dd,ec]).
follows(cp,[ad,bm]).
guests([ad,bm,cp,dd,ec,fa]).

Мы получаем ответ L = [[ad, bm, dd, ec]]. Это означает, что все гости, кроме Карлотты и Фалько, должны быть приглашены.

Ответы, которые дало мне это решение, совпали с решениями, приведенными в статье Wicked Witch, за исключением набора данных № 6, где было создано больше решений. Кажется, это правильное решение.

Наконец, я должен упомянуть CLP (FD) библиотеку Prolog, которая особенно подходит для такого рода проблем.

Как заметил svick, первая проблема с кодом в OP заключается в том, что имена, начинающиеся с заглавных букв, являются переменными в Прологе. Так admit(CP) :- admit(AD)что эквивалентно attend(X) :- attend(Y), что приводит к Прологу сразу входя в бесконечный цикл , пытаясь доказать , что attendимеет место в течение некоторого срока, находя некоторый срок , на который attendимеет место.

Однако, если вы хотите, чтобы каждый набор инициалов был конкретным отдельным термином, вы все равно столкнетесь с переполнением стека, потому что у вас есть циклы, например

attend(cp) :- attend(ad).
attend(ad) :- attend(cp).

Таким образом, чтобы выяснить, attend(cp)держит ли Пролог, попытается определить, attend(ad)удерживает ли он , что он будет делать, проверяя, attend(cp)держит ли , и так далее, до тех пор, пока стек не переполнится.

Я не верю , что ваниль Пролог делает любую попытку определить , есть ли такой цикл, и рассмотреть другие способы , чтобы сделать один из attend(cp)или attend(ad)истинных , а не застрять в бесконечном цикле.

Могут быть или не быть версии Prolog, которые поддерживают такую ​​функцию. Я больше знаком с Меркурием и думаю, что «минимальная модель таблицы» Меркурия именно то, что вам нужно для этого случая. Я никогда не использовал его на самом деле, но, насколько я понимаю, он более или менее позволяет термину, который подразумевает, что он считается истинным, если есть какой-то другой способ доказать это, или ложным иным образом, не попадая в бесконечный цикл. См. Соответствующий раздел документации по Mercury, и, если вам интересно, документ с описанием реализации.

Mercury - это язык логического программирования с принудительной чистотой, с синтаксисом, аналогичным Prolog, но с сильными системами типов и режимов, и он скорее скомпилирован, чем интерпретирован.

Я только что пересмотрел введение в статью (которую я давно не читал), и в ней упоминается табулирование, реализованное в нескольких версиях Пролога, так что, возможно, вы сможете продвинуться дальше, прибегая к помощи табулирования в прологе.

Я нашел следующую статью о решении SAT с использованием пролога:

• Жемчужина на SAT, решающая в Прологе Джейкобом М. Хоу и Энди Кингом

Реализацию решателя можно найти здесь .

Посмотрите этот ответ stackoverflow для деталей о коде и как его использовать.

Если оставить в стороне вопрос о нижнем / верхнем регистре, в предложениях есть цикл:

attend(cp) :- attend(ad).
attend(ad) :- attend(cp).

Поэтому, когда вы вызываете интерпретатора сверху вниз, он зацикливается. Возможно, вам больше повезет с программированием набора ответов (ASP), которое работает снизу вверх. Вот кодирование через библиотеку ( minimal / asp ):

:- use_module(library(minimal/asp)).

choose([admit(bm)]) <= posted(admit(ad)).
choose([admit(cp)]) <= posted(admit(ad)).
choose([admit(ad)]) <= posted(admit(cp)).
choose([admit(dd)]) <= posted(admit(cp)).
choose([admit(ad)]) <= posted(admit(ec)).
choose([admit(bm)]) <= posted(admit(ec)).
choose([admit(cp)]) <= posted(admit(ec)).
choose([admit(cp)]) <= posted(admit(fa)).
choose([admit(dd)]) <= posted(admit(fa)).
choose([admit(bm)]) <= posted(admit(cp)),posted(admit(dd)).
choose([admit(ec)]) <= posted(admit(cp)),posted(admit(dd)).
choose([admit(fa)]) <= posted(admit(cp)),posted(admit(dd)).
choose([admit(dd)]) <= posted(admit(ad)),posted(admit(bm)).

choose([admit(fa)]) <= posted(init).

Вот пример запуска:

Jekejeke Prolog 3, Runtime Library 1.3.8 (23 May 2019)

?- post(init), listing(admit/1).
admit(fa).
admit(cp).
admit(ad).
admit(bm).
admit(dd).
admit(ec).