Un saludo a la comunidad de Steemit, hoy les traigo Programación lógica en Prolog usando Grafos.
Los Grafos son un conjunto de vértices o nodos conectados donde puedes buscar un camino y no solo un camino, hay grafos que encuentran el camino mas corto, el costo mínimo, etc .
Por ejemplo el google map utiliza grafos para hallar el camino mas corto de un punto a otro.
Este post Uniremos los Grafos con Prolog es un lenguaje de programación lógica utilizado mucho en las Universidades
para aprender paradigmas lógicos lo que es igual aprender sobre IA. Empecemos!
Creamos Hechos que serán nuestras Aristas. “amigos”
amigos(a,b).
amigos(a,c).
amigos(b,c).
amigos(b,d).
.
.
.
Hasta completar todas las Aristas.
Creamos Atributos de los Vértices. “tiene”
tiene(a,redio).
tiene(b,microfono).
tiene(b,tv).
tiene(c,pc).
tiene(c,carro).
.
.
.
Hasta completar todo los Atributos “tiene”.
Creamos Atributos de los Vértices. “puede”
puede(a,bailar).
puede(a,cocinar).
puede(b,traducir).
puede(c,manejar).
puede(d,dibujar).
puede(d,bailar).
.
.
.
Hasta completar todo los Atributos “puede”.
Reglas
Ahora empezamos a crear Reglas para nuestro Grafo, lo que vamos hacer es hallar caminos de un punto a otro. Para después hacer preguntas lógicas como: “a” conoce un X que sabe dibujar
Creamos dos reglas para que nuestro Grafo sea dirigido en ambos sentidos.
conectados(X,Y):- amigos(X,Y). % “X” llego a “Y”
conectados(X,Y):- amigos(Y,X). % “Y” llego a “X”
La Regla “Posee” nos va a servir cuando un atributo esta apuntando por otro, ya X no tiene relación
con los atributos mas externos.
El primer “posee” es nuestra parada, sera cuando un Vértice o Atributo cumple el hecho “tiene”
posee(X,Atrib):-
tiene(X,Atrib).
El segundo “posee” es para tratar de hallar recursivamente los atributo mas externos
posee(X,Atrib):-
tiene(X,A2), % Buscara un Atributo “A2” de X, si no tiene se sale.
posee(A2,Atrib). % Si “A2” cumple el 1re “posee” encontré el atributo, Sino se llamara a si mismo.
Búsqueda En Profundidad (Depth-first search)
conoce(X,Y):-
camino([X],Y). % Enviara una lista solo con X y nuestra parada es Ycamino([Parada|_],Parada). % se detendrá cuando Parada sea la cabeza de la lista.
camino([Act|Camino],Parada):-
conectados(Act,Sig), % Buscara un “Act” que esta conectado con “Sig” , si no tiene se sale.
\+ miembro(Sig,Camino), % “\+” negado, Si no se sale
camino([Sig,Act|Camino],Parada). % llamada recursiva pero ahora con “Sig” de cabeza.
Nota: Ira creando una lista dejando X en ultima posición, en la primera vuelta “Camino” esta vació. Y negado evitara repetir vértices en la lista para no caer en ciclos infinitos.
Búsqueda En Profundidad para caminos específicos (Depth-first search)
Funciona de la misma manera que el anterior con la diferencia de que recibe una lista con un camino y nuestra parada sera verificar que son iguales las listas, el problema es que la lista que se esta generando se genera al revés.
conoce(X,Y,L):-
camino([X],Y,L).camino([Parada|C1],Parada,[L]):-
volteada([Parada|C1],L).
camino([Act|Camino],Parada,Solucion):-
conectados(Act,Sig),
\+ miembro(Sig,Camino),
camino([Sig,Act|Camino],Parada,Solucion).
miembro(X,[X|]). % la parada sera cuando la X sea igual a la cabeza
miembro(X,[|Y]):-
miembro(X,Y). % Se llamara a si mismo pero sin el primer elemento.
volteada(L,LR):-
volteada(L,[],LR).
volteada([],L2,L2). % la parada sera cuando la lista que se esta generando sea igual a “L2”
volteada([H|T],Acum,LR):-
volteada(T,[H|Acum],LR). % ira generando la lista al revés sacando la cabeza y guardándola
Consultas en Prolog
Llegado a este punto ya nuestro grafo esta listo y solo queda crear las ultimas reglas.
quiensabe(P1,P2,Accion):-
conoce(P1,P2), % si “P1” conoce a “P2”
puede(P2,Accion). % si “P2” Sabe “Accion”
quientiene(P1,P2,Cosa):-
conoce(P1,P2), % si “P1” conoce a “P2”
posee(P2,Cosa). % si “P1” tiene “Cosa”
Los datos se repiten porque. hay varias formas de llegar a un mismo punto.
Espero que les guste lo que hago, pronto estaré publicando Cosas interesantes que se pueden hacer en Prolog.