Introducción a los Algoritmos – Parte X

Con lo poco que ya vimos de los grafos seguramente se ha abierto una puerta a imaginar inclusive resoluciones mediante grafos de cuestiones meramente procedurales y estáticas… Lo digo por experiencia porque sé que confunden.

El ejemplo más claro para aprenderlos siempre es la teoría de redes. Pero sigamos:

Árboles

En esta parte del curso vamos estudiar un caso particular de la Teoría de Grafos que son los árboles. Primero, vamos definir el concepto de árbol.

Simplemente, un árbol es un grafo conexo sin ciclos. Notar que como un grafo requiere contener un mínimo de un vértice, un árbol contiene un mínimo de un vértice. También tenemos que un árbol es un grafo simple, puesto arcos y aristas paralelas forman ciclos. Un grafo no conexo que no contiene ciclos será denominado bosque. En ese caso tenemos un grafo donde cada componente es un árbol.

Árboles cobertores
Dado un grafo G no dirigido, conexo, se dice que un subgrafo T de G es un árbol cobertor si es un árbol y contiene el mismo conjunto de nodos que G.

Todo recorrido de un grafo conexo genera un árbol cobertor, consistente del conjunto de los arcos utilizados para llegar por primera vez a cada nodo.

Para un grafo dado pueden existir muchos árboles cobertores. Si introducimos un concepto de “peso” (o “costo”) sobre los arcos, es interesante tratar de encontrar un árbol cobertor que tenga costo mínimo.

Árbol Cobertor Mínimo

En general estamos interesados en el caso en que H = T es un árbol de cobertura de G. Ya que G es finito, la función w(t) alcanza su mínimo en algún árbol T. Nos interesa hallar algún árbol T que minimice el costo total; dicho grafo no tiene por qué se único.

En esta sección veremos dos algoritmos para encontrar un árbol cobertor mínimo para un grafo no dirigido dado, conexo y con costos asociados a los arcos. El costo de un árbol es la suma de los costos de sus arcos.

Algoritmo de Kruskal

Este es un algoritmo del tipo “avaro” (“greedy“). Comienza inicialmente con un grafo que contiene sólo los nodos del grafo original, sin arcos. Luego, en cada iteración, se agrega al grafo el arco más barato que no introduzca un ciclo. El proceso termina cuando el grafo está completamente conectado.

En general, la estrategia “avara” no garantiza que se encuentre un óptimo global, porque es un método “miope”, que sólo optimiza las decisiones de corto plazo. Por otra parte, a menudo este tipo de métodos proveen buenas heurísticas, que se acercan al óptimo global.

En este caso, afortunadamente, se puede demostrar que el método “avaro” logra siempre encontrar el óptimo global, por lo cual un árbol cobertor encontrado por esta vía está garantizado que es un árbol cobertor mínimo.

Una forma de ver este algoritmo es diciendo que al principio cada nodo constituye su propia componente conexa, aislado de todos los demás nodos. Durante el proceso de construcción del árbol, se agrega un arco sólo si sus dos extremos se encuentran en componentes conexas distintas, y luego de agregarlo esas dos componentes conexas se fusionan en una sola.

Descripción del Algoritmo

Entrada: Un grafo G con costos, conexo.

Idea: Mantener un subgrafo acíclico cobertor H de modo que en cada paso exista al menos un árbol de cobertura de costo mínimo T, tal que H sea subgrafo de T. Considérense las aristas de G ordenadas por costo en forma no decreciente, los empates se rompen arbitrariamente.

Inicialización: E(H) = Ø

Iteración: Si la siguiente arista e de G (en el orden dado) une dos componentes de H, entonces agregamos e a E(H). Si no, la ignoramos.

Terminación: Termínese el algoritmo cuando H sea conexo o cuando se acaben las aristas de G.

Complejidad del Algoritmo

El algoritmo requiere que las |E| aristas estén ordenadas previamente. Esto toma O(|E| log(|E|)) operaciones.

El proceso de examinar las |E| aristas toma a lo más O(|E|) iteraciones; de ellas, n-1 requieren actualizar la lista de componentes a las que pertenecen los n vértices. Esto puede ser hecho en un total de O(nlog₂n) operaciones, o incluso en forma más astuta en O(na (n)), donde:

Algoritmo de Prim

La característica principal del algoritmo de Kruskal es que éste selecciona las mejores aristas sin preocuparse de las conexiones con las aristas selecionadas antes. El resultado es una proliferación de árboles que eventualmente se juntan para formar un árbol.

Ya que sabemos que al final tenemos que producir un solo árbol, por qué no intentar hacer como que el árbol crezca naturalmente hasta la obtención de un árbol generador mínimo? Así, la próxima arista seleccionada sería siempre una que se conecta al árbol que ya existe.

Esa es la idea del algoritmo de Prim. Se caracteriza por hacer la selección en forma local, partiendo de un nodo seleccionado y construyendo el árbol en forma ordenada.

Dado que el arco es seleccionado de aquellos que parten del árbol ya construído, la viabilidad está asegurada. También se puede demostrar que el algoritmo de Prim es correcto, es decir que devuelve un árbol de recubrimiento minimal en todos los casos.

Al inicio el conjunto B cont iene un vértice arbitrario. En cada paso, el algoritmo considera todas las aristas que tocan a B y selecciona a la de menor peso. Después, el algoritmo aumenta en B el vértice ligado por esa arista que no estaba en B. El proceso continúa hasta que B contenga a todos los vértices de G.

Una descripción del algoritmo se describe a continuación

Complejidad del Algoritmo

Para implementar este algoritmo eficientemente, podemos mantener una tabla donde, para cada nodo de V-A, almacenamos el costo del arco más barato que lo conecta al conjunto A. Estos costos pueden cambiar en cada iteración.

Si se organiza la tabla como una cola de prioridad, el tiempo total es O(m log n). Si se deja la tabla desordenada y se busca linealmente en cada iteración, el costo es O(n²). Esto último es mejor que lo anterior si el grafo es denso, pero no si está cerca de ser un grafo completo.

Distancias Mínimas en un Grafo Dirigido

Dado un grafo (o digrafo) ponderado y dos vértices s y t se quiere hallar d(s,t) y el camino con dicha longitud. Los primeros algoritmos que presentamos obtienen todos los caminos de longitud mínima desde un vértice dado s al resto de vértices del grafo. El último algoritmo resuelve el problema para un par cualquiera de vértices de G.

Si el vértice u se encuentra en un camino C de longitud mínima entre los vértices s y z entonces, la parte de C comprendida entre los vértices s y u es un camino de longitud mínima entre s y u. Por tanto, el conjunto de caminos mínimos desde s a los restantes vértices del grafo G es un árbol, llamado el árbol de caminos mínimos desde s.

Definición: En un grafo con pesos, la distancia entre dos vértices es:

d(u,v) = min{ w(P) : P es un camino que une u y v }.

Note que en particular, esto coincide con la definición usual de distancia, si consideramos la función de peso w donde w(e)= 1 para todo e ∈ E(G). Nos interesa hallar la distancia más corta entre dos vértices dados u y v, o bien hallar todas las distancias más cortas entre un vértice dado u y todos los otros vértices de G.

En general, no es mucho más eficiente hallar la ruta más corta entre u y v que hallar todas las rutas más cortas entre u y los otros vértices. Para esto usamos el algoritmo de Dijkstra.

Algoritmo de Dijkstra

La idea básica del algoritmo es la siguiente: Si P es un camino de longitud mínima s → z y P contiene al vértice v, entonces la parte s → v de P es también camino de longitud mínima de s a v. Esto sugiere que si deseamos determinar el camino óptimo de s a cada vértice z de G, podremos hacerlo en orden creciente de la distancia d(s,z).

Descripción del algoritmo

Entrada: Un grafo (o digrafo) G con pesos no negativos, y un vértice de partida u. El peso de una arista xy es w(xy); si xy no es una arista diremos que w(xy) = ∞.

Idea: Mantener un conjunto S de vértices a los que conocemos la distancia más corta desde u, junto con el predecesor de cada vértice de S en dicha ruta. Para lograr esto, mantenemos una distancia tentativa t(z) desde u a cada z ∈ V(G). Si z ∉ S, t(z) es la distancia más corta encontrada hasta ahora entre u y z. Si z ∈ S, t(z) es la distancia más corta entre u y z. En cualquier caso, pred[z] es el predecesor de z la ruta u → z en cuestión.

Inicialización: S = {u}, t(u)=0, t(z) = w(uz) y pred[z] = u para z ≠u.

Iteración: Sea v ∈ V(G) – S, tal que: t(z) = min{t(v) : v∈ V(G) – S }

Agrégase v a S.

Para z ∈ V(G) – S actualícese t(z) = min{t(z),t(v)+w(vz) }.

Si cambia t(z), cámbiese pred[z] a v.

Terminación: Termínese el algoritmo cuando S = V(G) o cuando t(z) = ∞ para todo z Î V(G) – S .

Al terminar, la distancia más corta entre u y v está dada por: d(u,v) = t(v).

Análisis de la complejidad

En cada iteración se añade un vértice a T, luego el número de iteraciones es n. En cada una se elige una etiqueta mínima, la primera vez entre n-1, la segunda entre n-2, …, luego la complejidad total de estas elecciones es O(n2). Por otra parte cada arista da lugar a una actualización de etiqueta, que se puede hacer en tiempo constante O(1), en total pues O(q). Por tanto la complejidad total del algoritmo es O(n2).

Algoritmo de Ford

Es una variante del algoritmo de Dijkstra que admite la asignación de pesos negativos en los arcos, aunque no permite la existencia en el digrafo de ciclos de peso negativo.

Descripción del algoritmo

Entrada: Un digrafo ponderado con pesos no negativos en los arcos, un vértice sÎV. El peso del arco uv se indica por w(uv), poniendo w(uv)= ∞ si uv no es arco.

Salida: La distancia desde s a cada vértice del grafo.

Clave: Mejorar en cada paso las etiquetas de los vértices, t(u).

Inicialización: Sea T={s}, t(s)=d(s,s)=0, t(z)= ¥ para z ¹ s.

Iteración: Mientras existan arcos e=xz para los que t(z) > t(x) + w(e) actualizar la etiqueta de z a min{t(z), t(x)+w(xz)}.

Análisis de la complejidad

En primer lugar debemos observar que cada arco puede considerarse varias veces. Empecemos ordenando los arcos del digrafo D siendo este el orden en que se considerarán los arcos en el algoritmo. Después de la primera pasada se repite el proceso hasta que en una pasada completa no se produzca ningún cambio de etiquetas. Si D no contiene ciclos negativos puede demostrarse que, si el camino mínimo s→u contiene k arcos entonces, después de k pasadas se alcanza la etiqueta definitiva para u.

Como k £ n y el número de arcos es q, resulta que la complejidad de algoritmo de Ford es O(qn). Además podemos detectar un ciclo negativo si se produce una mejora en las etiquetas en la pasada número n.

Algoritmo de Floyd-Warshall

A veces no es suficiente calcular las distancias con respecto a un vértice s, si no que necesitamos conocer la distancia entre cada par de vértices.

Para ello se puede aplicar reiteradamente alguno de los algoritmos anteriores, variando el vértice s de partida. Así tendríamos algoritmos de complejidad O(n³) (si usamos el algoritmo de Dijkstra) u O(n²q) (si usamos el algoritmo de Ford).

A continuación se describe un algoritmo, debido a Floyd y Warshall, con una estructura sencilla, que permite la presencia de arcos de peso negativo y que resuelve el mismo problema. (Naturalmente los ciclos de peso negativo siguen estando prohibidos).

La idea básica del algoritmo es la construcción de una sucesión de matrices W0, W1, …, Wn, donde el elemento ij de la matriz Wk nos indique la longitud del camino mínimo i→j utilizando como vértices interiores del camino los del conjunto {v1, v2, …, vk}. La matriz W0 es la matriz de pesos del digrafo, con w0ij=w(ij) si existe el arco i→j, w0ii=0 y w0ij=∞ si no existe el arco i→j.

Para aplicar este algoritmo, los nodos se numeran arbitrariamente 1,2,…n. Al comenzar la iteración k-ésima se supone que una matriz D[i,j] contiene la distancia mínima entre i y j medida a través de caminos que pasen sólo por nodos intermedios de numeración <k.

Estas distancias se comparan con las que se obtendrían si se pasara una vez por el nodo k, y si de esta manera se obtendría un camino más corto entonces se prefiere este nuevo camino, de lo contrario nos quedamos con el nodo antiguo.

Al terminar esta iteración, las distancias calculadas ahora incluyen la posibilidad de pasar por nodos intermedios de numeración <=k, con lo cual estamos listos para ir a la iteración siguiente.

Para inicializar la matriz de distancias, se utilizan las distancias obtenidas a través de un arco directo entre los pares de nodos (o infinito si no existe tal arco). La distancia inicial entre un nodo y sí mismo es cero.

Descripción del algoritmo

Entrada: Un digrafo ponderado sin ciclos de peso negativos. El peso del arco uv se indica por w(uv), poniendo w(uv)= ∞ si uv no es arco.

Salida: La distancia entre dos vértices cualesquiera del grafo.

Clave: Construimos la matriz Wk a partir de la matriz Wk -1 observando que w^k_y = min { w^k-1_y , w^k-1 _ik + w^k-1_kj }

Iteración: Para cada k=1,…,n, hacer w^k_y = min { w^k-1_y , w^k-1 _ik + w^k-1_kj } ∀i,j=1,…,n. El elemento ij de la matriz W n nos da la longitud de un camino mínimo
entre los vértices i y j.

Análisis de la complejidad

Se deben construir n matrices de tamaño nxn y cada elemento se halla en tiempo constante. Por tanto, la complejidad del algoritmo es O(n³) El algoritmo de Floyd–Warshall es mucho más eficiente desde el punto de vista de almacenamiento dado que puede ser implementado una vez atualizado la distancia de la matriz con cada elección en k; no hay ninguna necesidad de almacenar matrices diferentes. En muchas aplicaciones específicas, es más rápido que cualquier versión de algoritmo de Dijkstra.

Ejemplo: