Ruta de impresión en Prolog

program-slicing

Question

Quiero imprimir la ruta de los nodos en un gráfico dirigido. Este código funciona correctamente para una ventaja pero no funcionó para toda la ruta. Devuelve falso cuando se trata de ruta. Aquí está mi código, pero solo se ejecuta solo por un borde y no por todo el camino. Amablemente ayúdenme.

Aquí está mi código:

path(Node1, Node2, X) :-
  edge(Node1, Node2),
  append([Node1], [Node2], X).
path(Node1, Node2, X, N) :-
  edge(Node1, SomeNode),
  append([Node1], [SomeNode], X),
  path(SomeNode, Node2, X, N),
  append([], [Node2], X).

X es una lista.

Answer 1

En su segunda cláusula, tiene las siguientes dos afirmaciones:

append([Node1], [SomeNode], X),
append([], [Node2], X).

Tenga en cuenta que la variable X produce en ambas sentencias, y esto debe crearse una instancia en la misma lista. Esto significa que [Node1]+[SomeNode] = []+[Node2] o [Node1,SomeNode]=[Node2] .

Sin ejecutar este código, ya puede observar que la segunda cláusula siempre fallará, ya que una lista de longitud 2 no se puede unificar con una lista de longitud 1.

Otro punto: las dos cláusulas no pertenecen al mismo predicado, ya que el primero tiene arity 3, mientras que el segundo tiene arity 4. Típicamente, para calcular rutas o profundidad arbitraria, necesita un predicado que consista en dos cláusulas que estén juntas: a caso base y caso recursivo Para el caso recursivo, es una práctica común usar la notación de cabeza / cola para construir la ruta: [FromNode,ToNode|RestOfPath] .

¡Espero que esto ayude!

Answer 2

Mientras que @WouterBeek ya identificó sus problemas, la declaración de Wouter

Sin ejecutar este código, ya puede observar que la segunda cláusula siempre fallará, ya que una lista de longitud 2 no se puede unificar con una lista de longitud 1

merece alguna elaboración. Para un programador de Prolog experimentado, es fácil detectar esos problemas. Pero, ¿qué pueden hacer los principiantes? Pueden aplicar la siguiente técnica: Generalice su programa y si el programa generalizado todavía es demasiado especializado, debe haber un error en la parte restante.

Generalizando un programa Prolog puro

Hay varias formas de generalizar un programa Prolog puro: eliminar objetivos o eliminar subtítulos en argumentos de la cabeza o un objetivo. Para eliminar objetivos, agregaré un * en frente de un objetivo, usando:

:- op(920,fy, *). *_. path(Node1, Node2, X) :- * edge(Node1, Node2), append([Node1], [Node2], X). path(Node1, Node2, X) :- * edge(Node1, SomeNode), append([Node1], [SomeNode], X), * path(SomeNode, Node2, X), append([], [Node2], X).

Ahora podemos hacer la consulta más general de este nuevo predicado:

| ?- path(N1, N2, P).
P = [N1,N2] ? ;
no

Por lo tanto: aunque esta definición ahora es una (sobre) generalización, todavía admite solo rutas de longitud 2. El problema es completamente independiente de la definición de edge/3 , solo la parte restante es responsable. ¡Así que mira la parte restante para solucionar el problema!