UNIVERSIDAD DE LOS ANDES
COORDINACION GENERAL DE ESTUDIOS INTERACTIVOS A DISTANCIA
MERIDA - VENEZUELA
Curso de Lógica y Matemática
Postgrado en Modelado y Simulación de Sistemas
MANUAL de PROLOG - BRATKO
ALGORÍTMO GENERALIZADO PARA BÚSQUEDA DE GRAFOS
En esta sección presentamos un esquema general de un algoritmo para búsqueda en grafos. Este esquema está basado sobre las nociones de vértices abiertos y cerrados. Un vértice abierto fue visitado por el algoritmo pero no ha sido explorado | procesado todavía, mientras que un vértice cerrado ya ha sido visitado y explorado.
El algoritmo toma algún vértice abierto V y lo expande, es decir, el algoritmo procesa el vértice V, encuentra su vecindad, enlaza ésta vecindad con el resto de los vértices abiertos y agrega éste vértice V al conjunto de vértices cerrados. Notar, que los vértices cerrados son removidos de la vecindad antes de enlazarlos con los vértices abiertos. El algoritmo para tan pronto como el conjunto de vértices abiertos está vacío.
% busqueda_cerr_abier(+Grafo,+Abierto,+Cerrado,-Resultado)
busqueda_cerr_abier(Grafo,[],Cerrado,Resultado) :-
afinar_resultado(Grafo,Cerrado,Resultado).
busqueda_cerr_abier(Grafo,[Vertice|Abierto],Cerrado,Resultado) :-
explorar(Vertice,Grafo,Vecindad,CerradoVertice),
diff(Vecindad,Cerrado,AbiertoNB), % removedor de vértices cerrados
mezclar(AbiertoNB,Abierto,NuevoAbierto), % enlaza con el resto
% de vértices abiertos
busqueda_cerr_abier(Grafo,NuevoAbierto,[CerradoVertice|Cerrado],Resultado).
El programa de arriba contiene "hooks", como por ejemplo, afinar_resultado o explorar, el cual tiene que ser programado para obtener un algoritmo particular. Mostramos tales extensiones ahora (los procedimientos para hooks son etiquetados con texto en bold).
COLOREADO
Primero, programamos el algoritmo de coloreado de grafos usando el esquema general presentado arriba. Este algoritmo corresponde al bien conocido algoritmo que colorea un vértice y, entonces, colorea la vecindad del vértice y así sucesivamente. Notar, que después de colorear un segmento del grafo, tenemos que recomenzar la búsqueda en el procedimiento afinar_resultado si allá permanecen otros componentes.
% abierto_close_coloreado(+Grafo,+Colores,-Coloreado)
abierto_close_coloreado(Grafo,Colores,Coloreado) :-
vertices(Grafo,[V|Vertices]),
busqueda_cerr_abier(Grafo-Colores,[V-Colores],[],Coloreado).
explorar(V-Cs,Grafo-Colores,Vecindad,V-C) :-
miembro(C,Cs), % Asignar color al vértice
vecindad(Grafo,V,NB), % encontrar la vecindad
borrar(C,Colores,NBColores), % preparar los posibles colores para la vecindad
adicionar_Colores(NB,NBColores,Neigbourhood). % asignar colores a la vecindad
adicionar_Colores([],_,[]).
adicionar_Colores([V|Vs],Cs,[V-Cs|CVc]) :-
adicionar_Colores(Vs,Cs,CVs).
diff([],_,[]).
diff([V-Cs|CVs],Cerrado,NonCerrado) :-
(miembro(V-_,Cerrado) -> NonCerrado=[V-Cs|Rest] ; NonCerrado=Rest),
diff(CVs,Cerrado,Rest).
mezclar([],Abierto,[]).
mezclar([V-Cs|CVs],Abierto,[V-NCs|Rest]) :-
(miembro(V-OCs,Abierto)
-> interseccion(Cs,OCs,NCs) % interseccion de conjunto clásica
; NCs=Cs),
NCs\=[], % Es posible asignar color
mezclar(CVs,Abierto,Rest).
afinar_resultado(Grafo-Colores,Cerrado,Resultado) :-
vertices(Grafo,Vertices),
adicionar_Colores(Vertices,Colores,CVertices),
diff(CVertices,Cerrado,NonCerrado),
(NonCerrado=[CV|_] % ¿Hay otro componente del grafo?
-> busqueda_cerr_abier(Grafo-Colores,[CV],Cerrado,Resultado)
; Resultado=Cerrado).
ALGORÍTMO DE DIJKSTRA
Programaremos ahora la extensión del esquema abierto|cerrado que se comporta parecido al algoritmo de Dijkstra el cual usa los conjuntos de vértices abiertos y cerrados naturalmente. Recuerda, que el algoritmo de Dijkstra encuentra la distancia mínima a todos los vértices en el grafo desde un vértice dado.
% abierto_close_dijkstra(+Grafo,+Start,-MinDist)
abierto_close_dijkstra(Grafo,Start,MinDist) :-
busqueda_cerr_abier(Grafo,[Start-0],[],MinDist).
explorar(V-D,Grafo,Neigbourhood,V-D) :-
vecindad(Grafo,V,NB),
adicionar_dist(NB,D,Vecindad).
adicionar_dist([],_,[]).
adicionar_dist([V-D1|Vs],D,[V-VD|Rest]) :-
VD is D+D1,
adicionar_dist(Vs,D,Rest).
diff([],_,[]).
diff([V-D|VDs],Cerrado,NotCerrado) :-
(miembro(V-_,Cerrado) -> NotCerrado=[V-D|Rest] ; NotCerrado=Rest),
diff(VDs,Cerrado,Rest).
mezclar([],Abierto,Abierto).
mezclar([V-D1|VDs],Abierto,NuevoAbierto) :-
(del(V-D2,Abierto,RestAbierto)
-> min(D1,D2,D),ins(V-D,RestAbierto,SAbierto)
; ins(V-D1,Abierto,SAbierto),
mezclar(VDs,SAbierto,NuevoAbierto).
del(X,[X|T],T).
del(X,[Y|T],Rest) :- X\=Y,del(X,T,Rest).
ins(VD,[],[VD]).
ins(V-D,[U-D1|T],[V-D,U-D1|T]) :- D<=D1.
ins(V-D,[U-D1|T],[U-D1|Rest]) :- D>D1,ins(V-D,T,Rest).
afinar_resultado(_,Cerrado,Cerrado).
La generalización puede simplificar el desarrollo y comprensión del programa.