Können Constraint-Zufriedenheitsprobleme mit Prolog gelöst werden?

Ist „Partybesuch“ Art von Problemen auflösbar in Prolog? Beispielsweise:

Klette Muldoon und Carlotta Pinkstone sagten beide, sie würden kommen, wenn Albus Dumbledore käme. Albus Dumbledore und Daisy Dodderidge sagten beide, sie würden kommen, wenn Carlotta Pinkstone käme. Albus Dumbledore, Burdock Muldoon und Carlotta Pinkstone sagten alle, sie würden kommen, wenn Elfrida Clagg käme. Carlotta Pinkstone und Daisy Dodderidge sagten beide, sie würden kommen, wenn Falco Aesalon käme. Klette Muldoon, Elfrida Clagg und Falco Aesalon sagten alle, sie würden kommen, wenn Carlotta Pinkstone und Daisy Dodderidge beide kämen. Daisy Dodderidge sagte, sie würde kommen, wenn sowohl Albus Dumbledore als auch Burdock Muldoon kämen. Wen muss man dazu überreden, an der Party teilzunehmen, um sicherzustellen, dass alle ihre Eingeladenen teilnehmen?

Ich habe versucht, dies in GNU Prolog auszudrücken:

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.*/

Ich habe einen Stapelüberlauf (kein Wortspiel) und keine Kenntnisse über die Prologauswertung. Deshalb frage ich.

Im Allgemeinen kann dieses Problem in eine boolesche CNF-Zufriedenheitsformel (mit 6 booleschen Variablen) umgewandelt werden. Hat die Prologperspektive also irgendeinen Vorteil?

Um ein Problem mit Prolog zu lösen, müssen Sie wie bei jeder Programmiersprache, sei es deklarativ oder imperativ, über die Darstellung der Lösung und die Eingabe nachdenken.

Da es sich um eine Programmierfrage handelt, wäre sie auf StackOverflow.com beliebt gewesen, wo Programmierer Programmierprobleme lösen. Hier würde ich versuchen, wissenschaftlicher zu sein.

Um das Problem im OP zu lösen, muss die Beziehung umgekehrt werden, die durch die in der Eingabe angegebenen Abhängigkeiten definiert ist. Sätze der Form sind leicht umzukehren. Die Klauseln A t t e n d ( A D ) ∧ A t t e n d $Attend(X) \to Attend(Y) \wedge Attend(Z)$ mögen$Attend(AD)\wedge Attend(BM)\to Attend(DD)$

Daisy Dodderidge sagte, sie würde kommen, wenn sowohl Albus Dumbledore als auch Burdock Muldoon kämen

sind schwieriger zu behandeln.

Bei Prolog besteht der erste einfache Ansatz darin, eine vollständige Umkehrung der Beziehung zu vermeiden und stattdessen zielgerichtet zu sein.

Nehmen Sie eine Reihenfolge in der Gästeliste an und verwenden Sie eine Regel

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

(Wir verwenden anstelle von A t t e n d ( X ) , um es kurz zu halten.)$A(X)$$Attend(X)$

Diese Regel ist einfach zu implementieren.

Ein eher naiver Ansatz

Zur besseren Lesbarkeit sei followsdie Beziehung als Eingabe angegeben und bringsumgekehrt.

Dann ist die Eingabe durch gegeben

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

Und bringskann wie folgt definiert werden:

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$

Wenn wir definieren

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

Wir erhalten die folgenden einzigartigen Lösungen:

 [ad,ec]

Dies ist nicht die vollständige Liste, da unter der alphabetischen Reihenfolge die Klausel

 follows(bm,[cp,dd]).

funktioniert nicht.

Eine ziemlich komplizierte Lösung für das ursprüngliche Rätsel

Um das Problem vollständig zu lösen, muss das System versuchen, die Anwesenheit späterer Gäste nachzuweisen, ohne Endlosschleifen in den Suchbaum einzufügen. Es gibt mehrere Möglichkeiten, um dieses Ziel zu erreichen. Jeder hat seine Vor- und Nachteile.

Eine Möglichkeit ist die brings/2folgende Neudefinition :

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

Das letzte Argument in brings/4ist notwendig, um eine Endlosschleife in zu vermeiden try_bring.

Dies gibt die folgenden Antworten: Albus, Carlotta, Elfrida und Falco. Diese Lösung ist jedoch nicht die effizienteste, da das Zurückverfolgen dort eingeführt wird, wo es manchmal vermieden werden kann.

Eine allgemeine Lösung

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

Nun, wenn zum Beispiel Datensatz # 2 als gegeben ist

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

Wir erhalten die Antwort L = [[ad, bm, dd, ec]]. Das bedeutet, dass alle Gäste außer Carlotte und Falco eingeladen werden müssen.

Die Antworten, die diese Lösung mir gab, stimmten mit den im Wicked Witch-Artikel angegebenen Lösungen überein, mit Ausnahme des Datensatzes Nr. 6, in dem mehr Lösungen hergestellt wurden. Dies scheint die richtige Lösung zu sein.

Abschließend muss ich die CLP (FD) -Bibliothek von Prolog erwähnen, die für diese Art von Problemen besonders geeignet ist.

Wie von svick entdeckt, ist das erste Problem mit dem Code im OP, dass Namen, die mit Großbuchstaben beginnen, Variablen in Prolog sind. Also admit(CP) :- admit(AD)ist äquivalent zu attend(X) :- attend(Y), was dazu führt, dass Prolog sofort in eine Endlosschleife eintritt, um zu demonstrieren, dass attendfür einen Begriff gilt, indem ein Begriff gefunden wird, für den attendgilt.

Wenn Sie jedoch jeden Satz von Initialen als einen konkreten unterschiedlichen Begriff verstanden haben, stoßen Sie immer noch auf einen Stapelüberlauf, weil Sie Zyklen haben, z

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

Um herauszufinden, ob attend(cp)Holds vorhanden sind, versucht Prolog herauszufinden, ob Holds vorhanden sind. attend(ad)Überprüfen Sie, ob attend(cp)Holds vorhanden sind, und so weiter, bis der Stack überläuft.

Ich glaube nicht, dass Vanille Prolog einen Versuch unternimmt, festzustellen, ob es einen solchen Zyklus gibt, und andere Wege untersucht, um einen von attend(cp)oder attend(ad)wahr zu machen , anstatt in einer Endlosschleife zu stecken.

Möglicherweise gibt es Versionen von Prolog, die eine solche Funktion unterstützen. Mercury ist mir vertrauter und ich denke, Mercurys "Minimal Model Tabling" ist genau das, was Sie für diesen Fall benötigen. Ich habe es eigentlich nie benutzt, aber meines Wissens lässt es mehr oder weniger zu, dass ein Begriff, der sich als wahr erweist, wenn es eine andere Möglichkeit gibt, es zu beweisen, oder falsch, ohne in eine Endlosschleife geraten zu müssen. Lesen Sie den entsprechenden Abschnitt in den Mercury-Dokumenten und bei Interesse ein Dokument, in dem die Implementierung beschrieben wird.

Mercury ist eine reinste logische Programmiersprache mit einer ähnlichen Syntax wie Prolog, aber starken Typ- und Modus-Systemen. Sie wird kompiliert und nicht interpretiert.

Ich habe gerade die Einleitung zu dem Artikel überflogen (die ich seit einiger Zeit nicht mehr gelesen habe), und es wird erwähnt, dass das Tabling in mehreren Versionen von Prologs implementiert wurde. Es kann also sein, dass Sie durch Googeln zum Tabling weiter kommen in Prolog.

Ich habe das folgende Papier über SAT-Lösungen mit Prolog gefunden:

• Eine Perle über SAT-Lösungen in Prolog von Jacob M. Howe und Andy King

Eine Implementierung des Lösers finden Sie hier .

In dieser Stackoverflow-Antwort finden Sie Details zum Code und dessen Verwendung.

Abgesehen von Klein- und Großbuchstaben gibt es einen Zyklus in den Abschnitten:

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

Wenn Sie also einen Top-Down-Interpreter aufrufen, wird eine Schleife ausgeführt. Möglicherweise haben Sie mehr Glück mit der Antwortsatzprogrammierung ( Answer Set Programming, ASP), die von unten nach oben funktioniert. Hier ist eine Codierung per Bibliothek ( 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).

Hier ist ein Beispiellauf:

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