LOGOSJUNTOS.gif (3585 bytes)      

UNIVERSIDAD DE LOS ANDES 

COORDINACION GENERAL DE ESTUDIOS INTERACTIVOS A  DISTANCIA

MERIDA - VENEZUELA

 

 

 

                wpe1.jpg (1485 bytes)

              wpe2.jpg (2265 bytes)

Curso de Lógica y Matemática

    Postgrado en Computación         

    Postgrado en Modelado y Simulación de Sistemas      


                  ANTERIOR

                 PRINCIPAL

 

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.
 

               ANTERIOR

                PRINCIPAL