En prolog, ¿por qué no añadir "edge(X, Y) :- borde(Y, X)." solo trabajo para la conversión de un grafo dirigido de la definición de un grafo no dirigido

Question

Estoy aprendiendo de Prolog, y estoy revisando los apuntes de clase y todas las notas de decir es que:

dada la siguiente definición de gráficos:

path(X, Y) :- edge(X, Y).
path(X, Y) :- edge(X, Z), path(Z, Y).

Si queremos hacer de este un grafo no dirigido, la definición de edge(X, Y) :- edge(Y, X). sola no funciona, y no puedo entender por qué.X a Y tiene una arista si Y a X tiene un borde.Parece que tiene sentido para mí.

Las notas realmente no aclarar por qué no, pero lo que hace es definir que la solución adecuada sería:

edge1(X, Y) :- edge(X, Y).
edge1(X, Y) :- edge(Y, X). 

a lo que ya había.

¿Alguien puede explicar esto a mí, por favor y gracias?<3

Answer 1

Dado que las reglas no funcionan de la misma como en los hechos, y que están creciendo en un bucle infinito si se utiliza el mismo predicado.

Tomemos el ejemplo ?-edge(5,2).Vamos a terminar llamando --

edge(5,2) :- edge(2,5).

Ok, ¿qué sucede cuando nos llame edge(2,5)?

edge(2,5) :- edge(5,2).

...Uh oh.La lógica de círculo.

Cuando se utiliza edge1, que , simplemente, crear un contenedor para su predicado para escapar de la definición recursiva.

Answer 2

Existen varias fuentes potenciales de no terminación en su programa.

En primer lugar, con la regla edge(X, Y) :- edge(Y, X). el programa se nunca terminar.Independientemente de donde agregar esta regla a su programa.Lo que a menudo es bastante irritante es que el programa va a producir muchas de las respuestas que de alguna manera sugiere que funciona.Sin embargo, nunca se detendrá.

La mejor manera de entender esto, es considerar modificado ligeramente el programa, llamado el fracaso-de la rebanada.Este programa modificado se comparten muchas propiedades con el programa.No todos, pero algunos.Vamos a añadir objetivos false en su programa.Si el programa resultante de bucles, el original programa de bucle.

path(X, Y) :- edge(X, Y), falso.
camino(X, Y) :-  falso,  de borde(X, Z), camino(Z, Y).

borde(a, b) :-  falso.
edge(X, Y) :- edge(Y, X).

En segundo lugar, existe otra fuente de no-terminación en su programa mejorado.Aquí está la relacionada con el fracaso-slice:

camino(X, Y) :-  falso, edge1(X, Y).
path(X, Y) :- edge1(X, Z), path(Z, Y), falso.

edge1(X, Y) :- edge(X, Y).
edge1(X, Y) :- edge(Y, X).

edge(a, b).

edge1/2 ahora siempre contiene ciclos, por lo que este fragmento de bucle para path(a, Y).y, más en general también path(X, Y), false.

Para resolver este problema, tendrá que reescribir path/2.

Usted puede volver a escribir esto de una manera genérica por el uso de closure0/3 y path/4!

Así path/2 puede ser definido como:

path(X, Y) :-
   closure(edge, X, Y).