¿Se pueden resolver los problemas de satisfacción de restricciones con Prolog?

18

¿Se pueden resolver los problemas de "asistencia a la fiesta" en Prolog? Por ejemplo:

Burdock Muldoon y Carlotta Pinkstone dijeron que vendrían si venía Albus Dumbledore. Albus Dumbledore y Daisy Dodderidge dijeron que vendrían si viniera Carlotta Pinkstone. Albus Dumbledore, Burdock Muldoon y Carlotta Pinkstone dijeron que vendrían si venía Elfrida Clagg. Carlotta Pinkstone y Daisy Dodderidge dijeron que vendrían si venía Falco Aesalon. Burdock Muldoon, Elfrida Clagg y Falco Aesalon dijeron que vendrían si Carlotta Pinkstone y Daisy Dodderidge vinieran. Daisy Dodderidge dijo que vendría si Albus Dumbledore y Burdock Muldoon vinieran. ¿A quién se debe convencer para que asista a la fiesta para asegurarse de que asistan todos sus invitados?

He tratado de expresar esto en 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.*/

Estoy experimentando un desbordamiento de pila (sin juego de palabras) y no tengo conocimiento de la evaluación del prólogo, es por eso que pregunto.

En términos generales, este problema se puede incluir en la fórmula de satisfacción del CNF booleano (con 6 variables booleanas). Por lo tanto, ¿la perspectiva del prólogo tiene algún mérito?

logic constraint-programming prolog logic-programming Tegiri Nenashi
fuente

2

Creo que su problema es que los identificadores en mayúscula son variables, por lo que attend(BM) :- attend(AD).es exactamente lo mismo queattend(X) :- attend(Y).

svick

Intentado con letras pequeñas ( ideone.com/w622Z ) sigue siendo el mismo resultado.

Tegiri Nenashi

Obviamente no he hecho ningún Mercury / Prolog en demasiado tiempo, por supuesto, el punto de svick es correcto, y su primer programa corresponde aproximadamente a decir "se admite a una persona si se admite a otra persona". Habiendo reemplazado las variables con términos concretos, entonces te encuentras con el problema explicado en mi respuesta.

Ben

La respuesta simple es "Sí", ya que Prolog es un lenguaje completo de Turing.

David Richerby

13

Para resolver un problema con Prolog, como con cualquier lenguaje de programación, ya sea declarativo o imperativo, debe pensar en la representación de la solución y la entrada.

Como se trata de una pregunta de programación, habría sido popular en StackOverflow.com, donde los programadores resuelven problemas de programación. Aquí intentaría ser más científico.

Para resolver el problema en el OP uno tiene que revertir la relación definida por las dependencias establecidas en la entrada. Las cláusulas de la forma son fáciles de revertir. Las cláusulas $Attend(X) \to Attend(Y) \wedge Attend(Z)$ como $Attend(AD)\wedge Attend(BM)\to Attend(DD)$

Daisy Dodderidge dijo que vendría si Albus Dumbledore y Burdock Muldoon vinieran

son más difíciles de tratar

Con Prolog, el primer enfoque simple es evitar una inversión completa de la relación y, en su lugar, ser dirigido a un objetivo.

Asuma un pedido en la lista de invitados y use una regla

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

(Usamos lugar de para mantenerlo corto) $A(X)$ $Attend(X)$

Esta regla es fácil de implementar.

Un enfoque bastante ingenuo

Para followsfacilitar la lectura, sea la relación dada como entrada, y bringssea su reverso.

Entonces la entrada está dada por

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

Y bringsse puede definir de la siguiente manera:

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$

Si definimos

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

Obtenemos las siguientes soluciones únicas:

 [ad,ec]

Esta no es la lista completa, ya que bajo el orden alfabético de la cláusula

 follows(bm,[cp,dd]).

no está trabajando.

Una solución bastante complicada para el rompecabezas original.

Para resolver el problema por completo, debe dejar que el sistema intente probar la asistencia para invitados posteriores sin introducir bucles infinitos en el árbol de búsqueda. Hay múltiples formas de lograr este objetivo. Cada uno tiene sus ventajas y desventajas.

Una forma es redefinir de la brings/2siguiente manera:

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

El último argumento brings/4es necesario para evitar un bucle infinito try_bring.

Esto da las siguientes respuestas: Albus, Carlotta, Elfrida y Falco. Sin embargo, esta solución no es la más eficiente ya que se introduce el retroceso donde a veces se puede evitar.

Una solución general

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

Ahora si, por ejemplo, el conjunto de datos # 2 se da como

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

Obtenemos la respuesta L = [[ad, bm, dd, ec]]. Lo que significa que todos los invitados excepto Carlotte y Falco deben ser invitados.

Las respuestas que me dio esta solución coincidieron con las soluciones dadas en el artículo de Wicked Witch con la excepción del conjunto de datos # 6, donde se produjeron más soluciones. Esta parece ser la solución correcta.

Finalmente, debo mencionar la biblioteca CLP (FD) de Prolog que es particularmente adecuada para este tipo de problemas.

Dmitri Chubarov
fuente

La respuesta correcta también incluye F (es decir, A, C, E, F). Tiene un error tipográfico en las reglas o un problema más grave en el programa.

Tegiri Nenashi

Confirmado: ideone.com/Q3pqU

Tegiri Nenashi

Conjunto de datos # 2 del sitio vinculado en el artículo ideone.com/21AmX Parece que no funciona ...

Tegiri Nenashi

¿Su solución maneja múltiples alternativas (conjunto de datos # 8) ideone.com/rBjXi

Tegiri Nenashi

@TegiriNenashi Hay 6 supuestos de "no asumir" en el sitio vinculado. Mi solución no satisface № 2 y № 5. № 5 parece fácil de solucionar: generalice dos reglas "% No seguidor". Si eso se soluciona, debería obtener la primera respuesta para el conjunto de datos # 8. Hasta que se asuma el supuesto № 2, ninguno de los conjuntos de datos de ejemplo se puede resolver correctamente.

Dmitri Chubarov

10

Como lo detectó svick, el primer problema con el código en el OP es que los nombres que comienzan con letras mayúsculas son variables en Prolog. Por admit(CP) :- admit(AD)lo tanto, es equivalente a attend(X) :- attend(Y), lo que resulta en que Prolog ingrese inmediatamente a un ciclo infinito tratando de demostrar que se attendcumple para algún término al encontrar algún término para el cual se attendmantiene.

Sin embargo, si quisiste decir que cada conjunto de iniciales es un término distinto concreto, entonces todavía te encontrarás con un desbordamiento de pila porque tienes ciclos, por ejemplo

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

Por lo tanto attend(cp), para determinar si las attend(ad)retenciones, Prolog tratará de determinar si retenciones, lo que hará mediante la verificación de las attend(cp)retenciones, y así sucesivamente hasta que se desborde la pila.

No creo que Vanilla Prolog haga ningún intento de determinar si existe tal ciclo, y examinar otras formas de hacer que uno attend(cp)sea attend(ad)verdadero o no en lugar de quedarse atrapado en un bucle infinito.

Puede haber o no versiones de Prolog que admitan dicha función. Estoy más familiarizado con Mercury, y creo que la "tabla mínima de modelos" de Mercury es exactamente lo que necesita para este caso. En realidad, nunca lo he usado, pero entiendo que más o menos permite que un término que implique se considere verdadero si hay alguna otra forma de probarlo, o falso de lo contrario, sin quedar atrapado en un bucle infinito. Consulte la sección correspondiente de los documentos de Mercury y, si le interesa, un documento que describa la implementación.

Mercury es un lenguaje de programación lógico de pureza forzada, con una sintaxis similar a Prolog pero con sistemas de tipo y modo fuertes, y se compila en lugar de interpretarse.

Acabo de volver a leer la introducción al documento (que no he leído en mucho tiempo), y menciona que la tabulación se ha implementado en varias versiones de Prologs, por lo que es posible que pueda avanzar más buscando en Google para la presentación. en Prolog.

Ben
fuente

4

Encontré el siguiente documento sobre la resolución de SAT usando prolog:

A Pearl on SAT Resolviendo en Prolog por Jacob M. Howe y Andy King

Una implementación del solucionador se puede encontrar aquí .

Consulte esta respuesta de stackoverflow para obtener detalles sobre el código y cómo usarlo.

Dave Clarke
fuente

0

Dejando a un lado el tema en minúsculas / mayúsculas, hay un ciclo en las cláusulas:

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

Entonces, cuando llame a un intérprete de arriba hacia abajo, se repetirá. Es posible que tenga más suerte con la Programación de conjunto de respuestas (ASP), que funciona de abajo hacia arriba. Aquí hay una codificación a través de la biblioteca ( mínimo / 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).

Aquí hay un ejemplo de ejecución:

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

Colapso de Mostowski
fuente

¿Se pueden resolver los problemas de satisfacción de restricciones con Prolog?

Respuestas: