es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

¿Cómo encontrar la ruta directa entre dos nodos en un grafo en Prolog?

12 Jul, 2023 Programación

Soy nueva en Prolog y estoy tratando de escribir un predicado que tome dos nodos y un grafo como argumentos y luego verifique si existe un camino directo entre estos dos nodos en el grafo.

Por ejemplo, hay un camino directo desde n(1) hasta n(4) en el siguiente grafo, que va desde n(1) hasta n(3) y desde n(3) hasta n(4):

g[n(1), n(4), g([n(1), n(2), n(3), n(4), n(5), n(6), n(7), n(8)], [e(n(1), n(2)), e(n(1), n(3)), e(n(3), n(4)), e(n(4), n(5)), e(n(5), n(6)), e(n(5), n(7)), e(n(7), n(8))])]

Al final,

?- dirPath(n(1), n(4), g[n(1), n(4), g([n(1), n(2), n(3), n(4), n(5), n(6), n(7), n(8)], [e(n(1), n(2)), e(n(1), n(3)), e(n(3), n(4)), e(n(4), n(5)), e(n(5), n(6)), e(n(5), n(7)), e(n(7), n(8))]))).

debería devolver true.

Mi código provisional se ve así:

edge(n(1),n(2)).
edge(n(1),n(3)).
edge(n(3),n(4)).
edge(n(4),n(5)).
edge(n(5),n(6)).
edge(n(5),n(7)).
edge(n(7),n(8)).

dirPath(A,B, g) :-    % - todavía falta el argumento del grafo.
  move(A,B,[])        % - dos nodos están conectados,
  .                   % - si se puede mover de uno a otro,

move(A,B,V) :-        % - y se puede mover de A a B
  edge(A,X) ,         % - si A está conectado con X, y
  not(member(X,V)) ,  % - no se ha alcanzado X todavía, y
  (                   % - o bien
    B = X             % - X es el destino deseado
  ;                   %   O
    move(X,B,[A|V])   % - se puede llegar a ese destino desde X
  )                   
  .

Mi problema principal es que no puedo entender cómo hacer que mi predicado dirPath acepte un grafo como argumento.

Tags:  ,

Answer

  1. Avatar for davy.ai
    davy.ai

    Para hacer que el predicado dirPath acepte un grafo, necesitas incluir el grafo como uno de los argumentos en el predicado, de esta manera:

    dirPath(A,B,G) :-
  move(A,B,[],G).

move(A,B,Visited,G) :-
  edge(A,B,G) ;
  edge(A,X,G),
  not(member(X,Visited)),
  move(X,B,[A|Visited],G).

    En este código modificado, el predicado move ahora toma cuatro argumentos: el nodo inicial A, el nodo destino B, una lista de nodos visitados Visited y el grafo G. El predicado dirPath llama a move con una lista de nodos visitados vacía adicional y el grafo G.

    En el predicado move, también hemos añadido el grafo G como parámetro, de manera que podamos utilizarlo para buscar aristas entre nodos. El predicado primero verifica si hay una arista directa entre el nodo A y el nodo B en G. Si no la hay, recorre todas las aristas conectadas a A y llama recursivamente a move con el nodo destino B, añadiendo A a la lista de nodos visitados Visited.

    Obsérvese que hemos cambiado el caso base de move de B = X a edge(A,B,G), de manera que no necesitamos comprobar la igualdad de los nodos, sino simplemente la existencia de una arista en el grafo. Esto hace que el predicado sea más flexible y pueda manejar grafos más complejos.

Comments are closed.