Czy problemy z ograniczeniami można rozwiązać za pomocą Prolog?

Czy problemy typu „obecność na imprezie” można rozwiązać w Prologu? Na przykład:

Łopian Muldoon i Carlotta Pinkstone powiedzieli, że przybędą, jeśli przyjdzie Albus Dumbledore. Albus Dumbledore i Daisy Dodderidge powiedzieli, że przybędą, jeśli przyjdzie Carlotta Pinkstone. Albus Dumbledore, Burdock Muldoon i Carlotta Pinkstone powiedzieli, że przyjdą, jeśli przyjdzie Elfrida Clagg. Carlotta Pinkstone i Daisy Dodderidge zapowiedziały, że przybędą, jeśli przyjdzie Falco Aesalon. Łopian Muldoon, Elfrida Clagg i Falco Aesalon wszyscy powiedzieli, że przyjdą, jeśli pojawią się Carlotta Pinkstone i Daisy Dodderidge. Daisy Dodderidge powiedziała, że ​​przyjdzie, jeśli przyjdą Albus Dumbledore i Burdock Muldoon. Kogo należy przekonać do udziału w przyjęciu, aby zapewnić udział wszystkich zaproszonych przez nią osób?

Próbowałem to wyrazić w 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.*/

Mam problem z przepełnieniem stosu (bez gry słów) i nie mam wiedzy na temat oceny prologu, dlatego pytam.

Ogólnie rzecz biorąc, problem ten można przerzucić na formułę logicznego zadowolenia CNF (z 6 zmiennymi logicznymi). Czy zatem perspektywa prologu ma jakąś wartość?

Aby rozwiązać problem z Prologiem, jak w każdym języku programowania, zarówno deklaratywnym, jak i imperatywnym, musisz pomyśleć o reprezentacji rozwiązania i danych wejściowych.

Ponieważ jest to pytanie programistyczne, byłoby popularne na StackOverflow.com, gdzie programiści rozwiązują problemy z programowaniem. Tutaj chciałbym być bardziej naukowy.

Aby rozwiązać problem w PO, należy odwrócić relację określoną przez zależności określone na wejściu. Klauzule postaci można łatwo odwrócić. Klauzule A t t e n d ( A D ) ∧ A t t e n d $Attend(X) \to Attend(Y) \wedge Attend(Z)$ jak$Attend(AD)\wedge Attend(BM)\to Attend(DD)$

Daisy Dodderidge powiedziała, że ​​przyjdzie, jeśli przyjdą Albus Dumbledore i Burdock Muldoon

są trudniejsze do leczenia.

W przypadku Prologu pierwsze proste podejście polega na unikaniu pełnego odwrócenia relacji i kierowaniu się celem.

Załóż zamówienie na liście gości i zastosuj regułę

$\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)$

(Używamy zamiast A t t e n d ( X ), aby było krótkie)$A(X)$$Attend(X)$

Ta zasada jest łatwa do wdrożenia.

Raczej naiwne podejście

Dla czytelności niech followsbędzie relacją podaną jako dane wejściowe i bringsodwrotnie.

Następnie dane wejściowe są podawane przez

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]).

I bringsmożna zdefiniować w następujący sposób:

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$

Jeśli zdefiniujemy

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

Otrzymujemy następujące unikalne rozwiązania:

 [ad,ec]

To nie jest pełna lista, ponieważ w kolejności alfabetycznej klauzula

 follows(bm,[cp,dd]).

nie działa.

Raczej zaangażowane rozwiązanie oryginalnej układanki

Aby całkowicie rozwiązać problem, musisz faktycznie pozwolić systemowi udowodnić obecność późniejszych gości bez wprowadzania nieskończonych pętli do drzewa wyszukiwania. Istnieje wiele sposobów osiągnięcia tego celu. Każdy ma swoje zalety i wady.

Jednym ze sposobów jest przedefiniowanie brings/2w następujący sposób:

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).

Ostatni argument brings/4jest niezbędny, aby uniknąć nieskończonej pętli try_bring.

To daje następujące odpowiedzi: Albus, Carlotta, Elfrida i Falco. Jednak to rozwiązanie nie jest najskuteczniejsze, ponieważ wycofywanie jest wprowadzane tam, gdzie czasem można go uniknąć.

Ogólne rozwiązanie

Po dodaniu linku do Trzeciego Międzynarodowego Wyzwania NoCOUG SQL i NoSQL w pierwotnym pytaniu stało się jasne, że szukamy ogólnego sprawdzania osiągalności na zbiorze podzbiorów zbioru gości, gdzie relacja przejścia jest zdefiniowana przez zasady podane tak, że zastosowanie reguły $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).

Teraz, jeśli na przykład zestaw danych nr 2 jest podany jako

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

Otrzymujemy odpowiedź L = [[ad, bm, dd, ec]]. Co oznacza, że ​​wszyscy goście oprócz Carlotte i Falco muszą zostać zaproszeni.

Odpowiedzi, które dało mi to rozwiązanie, pasowały do ​​rozwiązań podanych w artykule Wicked Witch, z wyjątkiem zestawu danych nr 6, w którym wyprodukowano więcej rozwiązań. To wydaje się właściwe rozwiązanie.

Na koniec muszę wspomnieć o bibliotece CLP (FD) firmy Prolog, która jest szczególnie odpowiednia do tego rodzaju problemów.

Jak zauważył svick, pierwszym problemem z kodem w OP jest to, że nazwy zaczynające się od wielkich liter są zmiennymi w Prologu. admit(CP) :- admit(AD)Jest to więc równoważne z tym attend(X) :- attend(Y), co powoduje, że Prolog natychmiast wchodzi w nieskończoną pętlę, próbując wykazać, że attendutrzymuje się przez pewien okres, znajdując jakiś termin, dla którego się attendtrzyma.

Jeśli jednak chciałeś, aby każdy zestaw inicjałów był konkretnym odrębnym terminem, nadal będziesz mieć problem z przepełnieniem stosu, ponieważ masz cykle, np.

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

Aby sprawdzić, czy attend(cp)wstrzymania Prolog spróbuje ustalić, czy attend(ad)wstrzymuje, co zrobi, sprawdzając, czy attend(cp)wstrzymania itd., Aż do przepełnienia stosu.

Nie wierzę, że waniliowy Prolog próbuje podjąć próbę ustalenia, czy istnieje taki cykl, i zbadać inne sposoby, aby jeden attend(cp)lub attend(ad)prawdziwe, a nie utknąć w nieskończonej pętli.

Mogą istnieć lub nie wersje Prologa obsługujące taką funkcję. Jestem bardziej zaznajomiony z Mercury i myślę, że „minimalne modelowanie” Mercury jest dokładnie tym, czego potrzebujesz w tym przypadku. Tak naprawdę nigdy go nie użyłem, ale rozumiem, że mniej więcej pozwala na to, aby termin, który implikuje, był uważany za prawdziwy, jeśli istnieje jakiś inny sposób udowodnienia tego, lub fałszywy, bez uwięzienia w nieskończonej pętli. Zobacz odpowiednią sekcję dokumentacji Mercury, a jeśli interesuje Cię artykuł opisujący wdrożenie.

Mercury jest logicznym językiem programowania o wymuszonej czystości, z podobną składnią jak Prolog, ale silnymi systemami typu i trybu, i jest raczej kompilowany niż interpretowany.

Właśnie przerzuciłem wstęp do artykułu (którego nie czytałem od dłuższego czasu) i wspomina, że ​​tabling został zaimplementowany w kilku wersjach Prologów, więc może być tak, że możesz przejść dalej, przeglądając go na tabling w Prolog.

Znalazłem następujący artykuł na temat rozwiązywania problemów SAT za pomocą prologu:

• Perła na temat rozwiązywania problemów SAT w Prologu przez Jacoba M. Howe'a i Andy'ego Kinga

Implementację solvera można znaleźć tutaj .

Zobacz tę odpowiedź dotyczącą przepełnienia stosu, aby uzyskać szczegółowe informacje na temat kodu i sposobu jego użycia.

Pomijając kwestię małych / wielkich liter, w klauzulach występuje cykl:

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

Kiedy zadzwonisz do interpretera odgórnego, zapętla się. Możesz mieć więcej szczęścia dzięki programowi Answer Set Programming (ASP), który działa oddolnie. Oto kodowanie za pomocą biblioteki ( minimalna / 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).

Oto przykładowy przebieg:

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).