Conceptos y representaciones. Recorridos, Caminos Minimos e Implementación en Java PDF

Preview

Summary

Download Conceptos y representaciones. Recorridos, Caminos Minimos e Implementación en Java PDF

Description

ŽŶĐĞƉƚŽƐLJ ƌĞƉƌĞƐĞŶƚĂĐŝŽŶĞƐ ZĞĐŽƌƌŝĚŽƐĐĂŵŝŶŽƐ ŵşŶŝŵŽƐĞŝŵƉůĞŵĞŶƚĂĐŝſŶ ĞŶ:ĂǀĂ

dĂůůĞƌĚĞ ůŐŽƌŝƚŵŽƐ LJƐƚƌƵĐƚƵƌĂ ĚĞĂƚŽƐ//

Introducción El objetivo de esta unidad es realizar una introducción a una estructura de datos muy utilizada como son los grafos. En esta unidad se presentarán los conceptos esenciales para comprender su funcionamiento, lo cual nos permitirá realizar nuestra propia implementación en Java. Además, analizaremos distintos problemas tipos, las distintas representaciones y los algoritmos para el recorrido y solución de problemas. Finalmente, realizaremos un breve análisis de la implementación de los grafos propios de Java.

Conceptos básicos Un grafo es un conjunto de vértices o nodos unidos por aristas o arcos. Típicamente, un grafo se representa gráficamente como un conjunto de puntos (vértices o nodos) unidos por líneas (aristas) como se puede ver en la Figura 1 y 2. La definición formal de esta estructura es: Un grafo es una tupla , donde: V: conjunto de vértices (nodos) E: conjunto de aristas (arcos) y cada arista es un par (v,w), donde v,w ε V

Grafos dirigidos y no dirigidos Existen 2 tipos de grafos, los dirigidos y los no dirigidos. Los grafos de denominan no dirigidos cuando sus aristas no tienen un sentido dado, es decir, si existe una arista desde un nodo A a un nodo B, significa que puedo recorrer el grado desde A  B como así también desde B  A. La Figura 1 muestra un ejemplo de grafo no dirigido.

Figura 1: Grafo no dirigido

Los grafos también pueden ser dirigidos (o dígrafos), y en ese caso (v,w) se trata un par ordenado. En la figura 2 se muestra un ejemplo de grafo dirigido. Observe que en este caso es válido ir de 12, pero el camino directo de 21 no existe.

Figura 2: Grafo dirigido

Adyacencia Decimos que un vértice w es adyacente a un vértice v si existe una arista (v,w) en E. En el caso de grafos no dirigidos, si w es adyacente a v, entonces v es adyacente a w. En el caso de dígrafos, esto no se cumple, a no ser que tanto (v,w) y (w.v) sean aristas del grafo. La Figura 3 muestra un ejemplo de adyacencia para grafos no dirigidos.

Figura 3: Adyacencia en grafos no dirigidos

La Figura 4 muestra un ejemplo de adyacencia para grafos dirigidos.

Figura 4: Adyacencia en grafos dirigidos

Algunas veces, las aristas tienen un peso o costo asociado (v,w,p), v,w ε V, p ε R.

Figura 5: Grafo con pesos

Grafos conexos Un grafo es conexo si cada par de vértices está conectado por un camino, es decir, si para cualquier par de vértices (1, 2), existe al menos un camino posible desde 1 hacia 2.

En la siguiente figura se muestra un ejemplo de grafos conexos y no conexos.

Figura 6: Grafo conexo

Caminos Un camino es una secuencia de vértices w1,..,wN donde (wi,wi+1) ε E, para 1≤ i < N. La longitud de un camino (sin pesos) es el número de aristas en el camino. En el caso de grafos con pesos, la longitud de un camino está dada por la suma de los pesos. Por ejemplo, en la figura 5, un posible camino desde el vértice 1 al vértice 3 es: 123 y su longitud es 2070 (1085 + 985) Un ciclo es un camino w1,..,wN donde w1 y wN son el mismo vértice, es decir, es un camino donde el vértice origen y destino coinciden. Se dice que un ciclo es hamiltoniano cuando tiene que recorrer todos los vértices exactamente una vez (excepto el vértice del que parte y al cual llega). Un grafo acíclico es, como su nombre lo sugiere, simplemente un grafo dirigido y que no contiene ciclos. Un orden topológico ordena los vértices de un grafo dirigido, donde si existe un camino de un vértice v a otro vértice w, entonces w debe aparecer después de u en la ordenación. Uno de los problemas más comunes en la Teoría de Grafos es encontrar el camino mínimo entre 2 vértices dados. Para ello vamos a analizar los siguientes algoritmos: •

Camino Mínimo sin Pesos con un único origen desde el vértice de origen a cualquier otro vértice del grafo  BFS (Búsqueda en anchura)

•

Camino Mínimo con Pesos positivos y origen único, desde el vértice origen al resto de vértices del grafo  Dijkstra

Figura 7: Ciclos

Representación Grafos

de

Uno de los primeros problemas a resolver es cómo se representan internamente los grafos. Una implementación sencilla de esta estructura de datos es la matriz de adyacencia. La matriz de adyacencia es la forma más común de representación y la más directa. Consiste en una tabla de tamaño nxn, donde n es el número de vértices y para cada arista (v,w), a[v][w] representa el costo de la arista. Las aristas que no existen pueden representarse con un valor infinito. Esta representación resulta útil cuando el grafo es denso. Si el grafo es no dirigido hay que asegurarse de que se marca tanto la entrada a[v][w] como la entrada a[w][v], puesto que se puede recorrer en ambos sentidos. En la Figura 8 se muestra un grafo de ejemplo y la matriz resultante de su implementación.

Figura 8: Representación matricial

Dado que la matriz de adyacencia siempre ocupa un espacio de n*n, es decir, depende solamente del número de nodos y no del de aristas, esta representación será útil para representar grafos densos. Por otro lado, cuando nos encontramos ante un grafo disperso, resulta más eficiente utilizar una estructura de datos de tipo lista de adyacencia. Una lista de adyacencia consiste de una lista de los vértices del grafo y para cada vértice de una lista de sus vértices vecinos. Lo que se hace es definir una lista enlazada para cada nodo, que contendrá los nodos a los cuales es posible acceder. Es decir, un vértice i tendrá una lista enlazada asociada en la que aparecerá un elemento con una referencia al vértice j si i y j tienen una arista que los une. Obviamente, si el grafo es no dirigido, en la lista enlazada de j aparecerá la correspondiente referencia al vértice i. En este caso el espacio ocupado es n*m, muy distinto del necesario en la matriz de adyacencia, que era de n2. La representación por listas de adyacencia, por tanto, será más adecuada para grafos dispersos. Un aspecto importante es que la implementación con listas de adyacencias determina fuertemente el tratamiento del grafo posterior. Una consecuencia de esto es que si un problema tiene varias soluciones la primera que se encuentre dependerá de la entrada dada. Podría presentarse el caso de tener varias soluciones y tener que mostrarlas siguiendo un determinado orden. Ante una situación así podría ser conveniente modificar la forma de meter los nodos en la lista de manera que el algoritmo mismo diera las soluciones ya ordenadas.1

En la siguiente figurase muestra un ejemplo y su representación con listas de adyacencia.

1

http://docencia.udea.edu.co/regionalizacion/teoriaderedes/representacionordenadoru1.html

Figura 9: Representación con listas de adyacencia

Observe que en la lista de adyacentes se hace referencia a la posición en el vector del nodo adyacente en lugar de su nombre. Esto nos permite un acceso directo a los datos para la ejecución de algoritmos. A la derecha de la Figura 9 se puede ver el diccionario que mapea la ciudad con la posición del vector.

En el ejemplo anterior se muestra un grafo con 3 vértices representando 3 aeropuertos (Jujuy, Ezeiza, Iguazú). Cada uno de estos vértices es representado por una posición en el arreglo. A partir de cada posición del arreglo se listan los vértices adyacentes. Por ejemplo, para a[1] que representa Ezeiza, se adjunta una lista de nodos adyacentes en el que se encuentra Iguazú (2) y Jujuy (0).

Problemas tipo Esta estructura de datos es muy utilizada dado que nos sirve para representar numerosas situaciones y problemas conocidos: Ciudades y rutas: cada nodo representa una ciudad y cada arista una ruta que une dichas ciudades. ¿Cuál es el camino más corto? ¿Hay un camino que partiendo de una ciudad visite todas las ciudades una sola vez volviendo a la ciudad de partida?

Figura 10: Ciudades y rutas

Actividades y dependencias: cada nodo representa una actividad. Las aristas sirven para representar dependencias entre actividades y de esta forma identificar tareas predecesoras. ¿Cuál es el camino crítico? Problema del viajante de comercio, conocido como TSP por sus siglas en Ingles “Travelling salesman problem”. Dada una lista de las ciudades y la distancia entre ellas, la tarea consiste en encontrar la ruta más corta posible que visita cada ciudad exactamente una vez y regresa a la ciudad de origen. Países limítrofes: cada vértice representa un país y cada arista muestra la relación de países limítrofes. ¿Cuántos colores como mínimo se necesita utilizar para colorear cada país de manera tal que ningún país limítrofe tenga el mismo color? El problema de las casas y servicios: Supongamos 3 casas y 3 servicios (Luz, Gas, Teléfono). ¿Es posible brindarle servicio a cada casa sin que los cables se crucen? Juego de ajedrez: Cada vértice representa un casillero y cada arista una posición válida para un caballo en el juego de ajedrez. ¿Es posible que el caballo parta de un casillero y visite todos los otros 63 casilleros una solo vez volviendo al punto inicial?

Juego de la casa: ¿Es posible dibujar la casa de la Figura sin levantar el lápiz y sin trazar 2 veces el mismo segmento?

Ordenamiento topológico: Un orden topológico ordena los vértices de un grafo dirigido, donde si existe un camino de un vértice v a otro vértice w, entonces w debe aparecer después de u en la ordenación. Podemos utilizar este algoritmo para mostrar orden entre actividades. Supongamos el grafo de la Figura 11, donde se muestra la relación en el orden de la ropa para poder vestirse correctamente.

Figura 11: Grafo representando orden de vestimenta

El orden topológico nos puede dar distintos resultados dado que no hay una única forma de ordenar los elementos. En la Figura 10 se muestras 2 ordenamientos correctos y uno que no lo es.

Figura 11: Resultados de orden de elementos

Recorridos de búsqueda Una de las operaciones más importantes para realizar dentro de las estructuras de grafos es la búsqueda de un determinado vértice. Por ejemplo, imagine en un mapa de ciudades y las carreteras que las unen si queremos identificar qué ciudades pueden alcanzarse a partir de una ciudad dada. Algunas ciudades podrán ser visitadas mientras que otras no. Supongamos que creamos un grafo para modelar la situación anterior. Ahora necesitamos un algoritmo que pueda comenzar la búsqueda desde un nodo de origen y recorriendo las aristas moverse a otros vértices de modo tal que, una vez que finalice el recorrido, se puedan identificar los nodos que fueron alcanzados desde el origen y aquellos que no. Para resolver esta problemática existen 2 soluciones distintas: Búsqueda en anchura (BFS, Breadth first search) Búsqueda en profundidad (DFS, Depth first search)

Si bien estos 2 algoritmos van a encontrar todos los vértices que se encuentran conectados al vértice origen, la forma en que recorren el grafo para resolverlo es distinta. La búsqueda en anchura recorre el grafo a lo ancho, es decir, recorre todos los adyacentes al vértice origen antes de seguir procesando los siguientes adyacentes. Este algoritmo utiliza una cola como estructura auxiliar para su implementación. La búsqueda en profundidad recorre en grafo de manera tal que va entrando en los distintos niveles de profundidad de un grafo antes de recorrer toda la lista de adyacentes. Este algoritmo utiliza una pila como estructura auxiliar para su implementación. En la figura 12 se muestran los pasos de ejecución del algoritmo BFS. Comenzando con el vértice A como origen se pide la lista de adyacentes recorriendo cada uno de ellos como se muestra en la figura los pasos 2,3,4, y 5. Una vez que se procesaron todos los vértices adyacentes a A, comenzamos a procesar la siguiente lista de adyacentes. De esta manera los próximos vértices a visitar son los adyacentes al vértice B y esto se describe en el paso 6 del algoritmo. Como el vértice B no tiene más adyacentes continuo procesando los vértices adyacentes al vértice C. Dado que el vértice C no posee vértices adyacentes sin visitar seguimos con los adyacentes al vértice D y de esta forma se visita el adyacente G, paso 7 del algoritmo. La Figura 12 muestra la ejecución completa del algoritmo.

Figura 12 – Ejemplo BFS - Fuente: Libro “Data Structures and Algorithms in Java” – Robert Lafore, pág. 625.

En el caso de la búsqueda en profundidad, el algoritmo comienza analizando el vértice de origen A y toma uno de sus adyacentes, en este caso B como se muestra en el paso 1 y 2 de la Figura 13. Luego procesa el primer adyacente de B, que en este caso es F como lo muestra el paso 3 de la figura. Observe que en este paso este algoritmo procesa el vértice F y no el vértice C como hubiese sido en el caso del BFS.

Una vez procesado el vértice F, se prosigue con el adyacente a este vértice y en consecuencia se procesa el vértice H como 4to paso. Como el vértice H no tiene adyacentes vuelve a procesar desde la última lista de adyacentes que en este caso corresponde al nodo C. El algoritmo continua su ejecución hasta procesar todos los vértices alcanzables desde A.

Figura 13 – Ejemplo DFS - Fuente: Libro “Data Structures and Algorithms in Java” – Robert Lafore, pág. 625.

Búsqueda en anchura (BFS), Búsqueda en Profundidad (DFS), Floyd, Dijstra. En un grafo todos los caminos tienen un peso asociado, el cual está indicado por las suma de los pesos de las aristas que forman el camino. Existen numerosas situaciones problemáticas en donde queremos encontrar el camino que minimice estos valores. En la resolución de la problemática de caminos mínimos podemos encontrar tres problemas diferentes: Camino más corto origen-destino: Dados dos nodos v y w de un grafo, encontrar el camino más corto que comience en v y culmine w. Camino más corto a partir de un origen: Dado un nodo v de un grafo, encontrar el camino más corto desde v hasta cada uno de los demás nodos. Camino más corto entre cada par de nodos.

Podemos observar que el primer problema es un caso particular del segundo, dado que si resolvemos el camino más corto desde un origen a todos los demás nodos vamos a resolver el caso desde el origen a un nodo particular. Para la resolución de este problema vamos a estudiar el algoritmo de Dijkstra. En caso de grafos sin pesos, podemos utilizar el algoritmo BFS visto en el apartado anterior para resolver el problema 2 y en consecuencia el 1. El algoritmo de BFS encuentra la ruta más corta cuando el peso entre todos los nodos es 1 por la forma en que este algoritmo recorre el grafo. Para el tercer caso, si bien podemos ejecutar el algoritmo de Dijkstra N veces tomando los distintos vértices como origen, el Algoritmo de Floyd resuelve esta problemática con una complejidad de tiempo similar.

Algoritmo de Dijkstra

“El algoritmo de dijkstra determina la ruta más corta desde un nodo origen hacia los demás nodos para ello es requerido como entrada un grafo cuyas aristas posean pesos. Algunas consideraciones”: “Si los pesos de mis aristas son de valor 1, entonces bastará con usar el algoritmo BFS”. “Si los pesos de mis aristas son negativos no puedo usar el algoritmo de dijsktra, para pesos negativos tenemos otro algoritmo llamado Algoritmo de Bellmand-Ford”.

Este algoritmo funciona de la siguiente manera: “Primero marcamos todos los vértices como no utilizados. El algoritmo parte de un vértice origen que será ingresado, a partir de ese vértice evaluaremos sus adyacentes, entre todos los vértices adyacentes, buscamos el que esté más cerca de nuestro punto origen, lo tomamos como punto intermedio y vemos si podemos llegar más rápido a través de este vértice a los demás. Después escogemos al siguiente más cercano (con las distancias ya actualizadas) y repetimos el proceso. Esto lo hacemos hasta que el vértice no utilizado más cercano sea nuestro destino. Al proceso de actualizar las distancias tomando como punto intermedio al nuevo vértice se lo conoce como relajación.”

Figura 14. Fuente: http://jariasf.wordpress.com/2012/03/19/camino-mas-cortoalgoritmo-de-dijkstra/

“Dijkstra es muy similar a BFS, si recordamos BFS usaba una Cola para el recorrido para el caso de Dijkstra usaremos una Cola de Prioridad o Heap, este Heap debe tener la propiedad de Min-Heap es decir cada vez que extraiga un elemento del Heap me debe devolver el de menor valor, en nuestro caso dicho valor será el peso acumulado en los nodos.” (Jhosimar George Arias Figueroa, 2012, http://jariasf.wordpress.com/2012/03/19/camino-mas-corto-algoritmode-dijkstra/) En el Anexo 1 se muestra paso a paso la ejecución de este algoritmo.

Algoritmo de Floyd Como se presenta en el libro de Robert Lafore, “Data Structures and Algorithms in Java”, estudiaremos el algoritmo de Floyd a partir de un ejemplo concreto. En la Figura 15 se muestra un grafo dirigido junto a su representación por medio de una matriz de adyacencia.

Figura 15: Grafo dirigido con pesos. Fuente: Libro “Data Structures and Algorithms in Java” – SAMS, pág. 708.

La matriz de adyacencia muestra el costo de las aristas del grafo. Vamos a extender esta matriz para mostrar el camino más corto para cualquier par de vértices. En el grafo de la figura podemos ver que se puede ir de BC con un costo de 30 (BD con costo 10 + 20 para ir de D C) Este algoritmo compara todos los posibles caminos entre cada par de vértices. Se va a utilizar una matriz Ak[i][j], que contiene el camino más corto que pasa por los primeros k primeros vértices. Inicialmente Ak[i][j] = matriz de adyacencia i j. Si no hay arista de i a j el costo será (infinito) y los elementos diagonales se ponen a 0. En la iteración k (nodo k como pivote) se calcula, para cada camino de v a Ak[i][j] = min (Ak-1[i][j] , Ak-1[i][k] + Ak-1[k][j] ),

i

j.

w, si es más corto pasando por k aplicando:

Básicamente la expresión anterior nos dice: “si para ir desde el vértice “i” al “j” mejoramos pasando por el vértice “k”, éste se añade al camino. Además, para reconstruir el camino se hace uso de una matriz de trayectorias, donde en cada iteración, si se mejora el camino desde el vértice “i” al vértice “j” pasado por “k”, éste se anota en la matriz de trayectorias.

Figura 16: Ejemplos Floyd. Fuente: Libro “Data Structures and Algorithms in Java” – SAMS, pág. 708.

En el primer caso Figura 16.a, se muestra que el costo de DA es originalmente . Si calculamos: 1. Ak[i][j] = min (Ak-1[i][j] , Ak-1[i][k] + Ak-1[k][j] ),

i

j.

2. Ak[3][0] = min (Ak-1[3][0], Ak-1[3][2] + Ak-1[2][0] ),

i

3. Ak[3][0] = min ( , 20+ 30 ), 4. Ak[3][0] = min ( , 50 ),

i

i

j. k=2

j.

j.

5. Ak[3][0] = 50 Luego, en la figura 16.b, se presenta una situación muy interesante, dado que reduciremos el costo de un camino. 1. Ak[i][j] = min (Ak-1[i][j] , Ak-1[i][k] + Ak-1[k][j] ),

i

2. Ak[1][0] = min (Ak-1[1][0], Ak-1[1][3] + Ak-1[3][0] ), 3. Ak[1][0] = min (70, 10+50 ), 4. Ak[1][0] = min (70, 60 ),

i

i

j. i

j. k=3

j.

j.

5. Ak[1][0] = 60 Finalmente, en la Figura 16.c, tenemos un caso similar al primero: 1. Ak[i][j] = min (Ak-1[i][j] , Ak-1[i][k] + Ak-1[k][j] ), 2. Ak[1][2] = min (Ak-1[1][2], Ak-1[1][3] + Ak-1[3][2] ), 3. Ak[1][2] = min ( , 10+20 ), 4. Ak[1][2] = min ( , 30),

i

i j.

j.

i

j. i

j. k=3

5. Ak[1][2] = 30

Búsqueda en anchura (BFS) como camino mínimo En la siguiente figura se puede observar uno de los pasos de ejecución del algoritmo BFS. Observe que los vértices marcados en verde son los q...