prolog - recorrer - eliminar elementos repetidos de una lista python

Optimizar un programa Prolog(eliminar duplicados, repetir el recálculo)

Question

No tengo mucha experiencia con Prolog. Tengo un conjunto de datos que contiene elementos y relaciones en el gráfico que tiene circularidad (bastante). Hay reglas para calcular la relación de resumen de una ruta. Uno de estos es: uno toma el camino, luego toma la relación más débil, y esa es la que se mantiene entre ambos extremos.

Con los elementos E1 , E2 , E3 y
Relaciones R1/R1c , R2 , R3 (intensidad baja a alta) y
estructura E1-R3-E2 , E1-R1-E2 , E2-R2-E3 , E3-R1-E2

Puedo hacer el siguiente ejemplo mínimo:

% weaker table
isWeaker( r1, r2).
isWeaker( r2, r3).
weaker( X, Y) :- isWeaker( X, Y).
weaker( X, Y) :-
    isWeaker( X, Z),
    weaker( Z, Y).
% ''weakest'' is <= not <
weakest( X, X, Y) :- =(X,Y).
weakest( X, X, Y) :- weaker( X, Y).

% All direct relations
isADirectRelation( e1, r1, e2).
isADirectRelation( e1, r3, e2).
isADirectRelation( e2, r2, e3).
isADirectRelation( e3, r1, e2).
isADirectRelation( e1, r3, e4).
isADirectRelation( e4, r2, e3).
isADirectRelation( e1, r1, e4).
isADirectRelation( e3, r1, e4).

% derived relations calculations

% Structural Chains
isADerivedRelation( Source, Relation, Target, Visited) :-
    /+ member( [Source,Relation,Target], Visited),
    weakest( Relation, RelationOne, RelationTwo),
    isARelation( Source, RelationOne, Intermediate, [[Source,Relation,Target]|Visited]),
    isARelation( Intermediate, RelationTwo, Target, [[Source,Relation,Target]|Visited]).

% major workhorse with anti-circularity
isARelation( Source, Relation, Target, Visited) :-
    (isADirectRelation( Source, Relation, Target);
     isADerivedRelation( Source, Relation, Target, Visited)).

El resultado de isARelation( Source, Relation, Target, []). es

e1,r1,e2
e1,r3,e2
e2,r2,e3
e3,r1,e2
e1,r3,e4
e4,r2,e3
e1,r1,e4
e3,r1,e4

e1,r1,e3
e3,r1,e3
e1,r1,e3 duplicate
e3,r1,e3 duplicate

Faltan

e4,r1,e4
e2,r2,e2

¿Es posible resolver esto en Prolog? Formalmente, sí, por supuesto, ¿pero también con un rendimiento decente?

Answer 1

Hay muchas cosas que decir acerca de esta pregunta, por lo que esta será una respuesta larga y compleja y, en última instancia, insatisfactoria. Así que bien podría comenzar con un fastidio: No use camelCaseIdentifiers para los predicados, generalmente usamos underscore_separated_words lugar. No estoy seguro de por qué esto me molesta en Prolog en particular, pero sospecho que en parte porque las letras mayúsculas son sintácticamente significativas.

Continuando, tu predicado weakest/3 está roto:

?- weakest(Weakest, r2, r1).
false.

Creo que tenía este derecho en la primera versión de su pregunta, pero luego eliminó la tercera cláusula de weakest/3 porque pensó que causaba respuestas redundantes. No hace falta decir que la "eficiencia" es inútil sin corrección. (Además, usualmente ponemos los argumentos de "salida" al final, no primero).

Parte del motivo por el que obtiene respuestas redundantes es el uso de dos (indirectamente) llamadas recursivas a isARelation/4 en isADerivedRelation/4 . Lo que estás computando es algo así como el cierre transitivo de la unión de relaciones "directas". La forma habitual de expresar el cierre transitivo en Prolog es así:

transitive_closure(A, B) :-
    base_relation(A, B).
transitive_closure(A, C) :-
    base_relation(A, B),
    transitive_closure(B, C).

Es decir, primero "damos un paso básico", luego recurse. Si nuestra relación de base tiene pares ab , bc , cd , entonces esto encontrará la solución ad exactamente una vez, como la composición del par base ab y el par transitivo derivado bd . En cambio, si tuviéramos que estructurar la segunda cláusula como lo hizo, con dos llamadas recursivas a transitive_closure/2 , obtendríamos el ad la solución dos veces: una vez como arriba, pero también una vez porque obtendríamos el par transitivo ac y lo componíamos con cd para dar ad .

Puede solucionar esto cambiando su primera llamada a isADerivedRelation/4 en isADerivedRelation/4 en una llamada a isADirectRelation/3 .

Otro problema es que está utilizando incorrectamente Visited : ¡está marcando el par Source-Target visitado antes de que haya probado que tal solución existe! Probablemente debería marcar Source-Intermediate como visitado en su lugar.

Aún así, obtendrá soluciones redundantes para un par de elementos si hay varias rutas diferentes entre esos elementos en el gráfico. Así es como funciona la lógica de Prolog: Prolog encuentra respuestas individuales a su consulta, pero no le permite hablar directamente sobre las relaciones entre esas respuestas. Si queremos obligarlo a enumerar todo exactamente una vez, debemos dejar la lógica pura.

Algunos sistemas Prolog ofrecen una función llamada "presentación" que esencialmente almacena en caché todas las soluciones para un predicado "presentado" y evita recálculos. Esto debería evitar respuestas redundantes e incluso simplificar su definición: si su relación de clausura está en la lista, ya no es necesario rastrear una lista de Visited porque las recutaciones cíclicas se evitarán mediante la presentación. No puedo darte el código probado porque no tengo Prolog con las mesas por ahí. Incluso sin las presentaciones ofrecidas por su sistema, existe la posibilidad teórica de "memorizar" soluciones usted mismo, utilizando la base de datos impura de Prolog. Es difícil hacerlo exactamente bien sin soluciones redundantes de ningún tipo.

Como alternativa a Prolog impuro, su problema parece encajar mejor con el registro de datos o la programación de respuesta . Estos son modelos de programación que usan la sintaxis similar a Prolog pero con una semántica establecida que parece ser exactamente lo que usted quiere: una propuesta es una solución o no, no hay un concepto de soluciones redundantes. El conjunto completo de soluciones se calcula de una sola vez. La eliminación del ciclo también es automática, por lo que no es necesario (de hecho, debido al idioma de entrada restringido, no puede usar) una lista de Visited . Si yo fuera tú, intentaría hacer esto en Datalog.

Como una extensión adicional de Prolog, puede haber una gran solución basada en las reglas de manejo de restricciones (CHR). Pero realmente, intente Datalog.

Finalmente, no veo por qué piensas que e2,r2,e2 es una solución faltante. El único camino desde e2 a e2 que veo pasa por e3 y vuelve a e2 través de una relación r1 , que es la más débil, por lo que la solución debería ser e2,r1,e2 .

Answer 2

Lo que terminé con, gracias a los comentarios de Lurker y la respuesta de Isabelle es esto:

% weaker table
isWeaker( r1, r2).
isWeaker( r2, r3).
weaker( X, Y) :- isWeaker( X, Y).
weaker( X, Y) :-
    isWeaker( X, Z),
    weaker( Z, Y).
% ''weakest'' is <= not <
weakest( X, X, Y) :- =(X,Y).
weakest( X, X, Y) :- weaker( X, Y).

% All direct relations
isADirectRelation( e1, r1, e2).
isADirectRelation( e1, r3, e2).
isADirectRelation( e2, r2, e3).
isADirectRelation( e3, r1, e2).
isADirectRelation( e1, r3, e4).
isADirectRelation( e4, r2, e3).
isADirectRelation( e1, r1, e4).
isADirectRelation( e3, r1, e4).

% derived relations calculations

isARelation( Source, Relation, Target, _) :-
    isADirectRelation( Source, Relation, Target).

% Structural Chains
isARelation( Source, Relation, Target, Visited) :-
    /+ member( [Source,Relation,Target], Visited),
    weakest( Relation, RelationOne, RelationTwo),
    isADirectRelation( Source, RelationOne, Intermediate),
    isARelation( Intermediate, RelationTwo, Target, [[Source,RelationOne,Intermediate]|Visited]).
isARelation( Source, Relation, Target, Visited) :-
    /+ member( [Source,Relation,Target], Visited),
    weakest( Relation, RelationOne, RelationTwo),
    isADirectRelation( Source, RelationTwo, Intermediate),
    isARelation( Intermediate, RelationOne, Target, [[Source,RelationTwo,Intermediate]|Visited]).

write_relation( Result) :-
    write( Result), nl.

writeAllRelations :-
   setof( (Relation, Source, Target), Relation^isARelation( Source, Relation, Target, []), ListOfAllRelations),
% maplist( write_relation, ListOfAllRelations). % For SWIProlog
write( ListOfAllRelations). % for JIProlog

Esto funciona y produce el resultado correcto:

r1,e1,e2
r1,e1,e3
r1,e1,e4
r1,e2,e2
r1,e2,e3
r1,e2,e4
r1,e3,e2
r1,e3,e3
r1,e3,e4
r1,e4,e2
r1,e4,e3
r1,e4,e4
r2,e1,e3
r2,e2,e3
r2,e4,e3
r3,e1,e2
r3,e1,e4

Sin embargo, en el mundo real, con 60 entidades o más y más o menos 800 relaciones directas, no he encontrado un Prólogo que pueda manejarlo. Buscaré en Datalog.