Algoritmos voraces que producen la solución óptima
Last updated
Last updated
A pesar de los ejemplos vistos (devolver el cambio y mochila), existen algunas familias de problemas para las que existe una solución voraz óptima.
Estudiaremos dos problemas ligados a grafos:
la búsqueda del camino más corto desde un único nodo origen hasta los demás nodos de un grafo (algoritmo de Dijkstra) y
la búsqueda del árbol de recubrimiento de coste mínimo de un grafo (algoritmo de Kruskal y algoritmo de Prim)
Sea un grafo dirigido G = <N,A> donde cada arco (i, j) de A tiene una longitud L[ i ][ j ] >= 0.
Por convenio, asumimos que L[ i ][ j ] = si (i, j) A.
El problema consiste en determinar la longitud del camino mínimo que va desde un nodo cualquiera del grafo hasta cada uno de los restantes nodos.
El algoritmo que permite resolver este problema es el algoritmo de Dijkstra, y se basa en:
Mantener a lo largo del proceso dos conjuntos S y C, de tal forma que S contenga los nodos para los que ya es conocida la longitud del camino mínimo desde el origen (nodos ya seleccionados). C contendrá los restantes nodos (nodos no seleccionados aún). Al inicio del proceso, S sólo contiene el nodo origen. En todo momento se cumple que N = S È C.
Utilizar el concepto de camino especial: Decimos que un camino desde el origen hasta cualquier otro nodo es especial si todos los nodos intermedios de ese camino pertenecen a S.
Mantener actualizado un vector D que contiene para cada nodo la longitud del camino especial más corta desde el origen.
Seleccionar en cada etapa aquel nodo v de C cuya distancia desde el origen sea mínima y lo añadimos a S. El camino especial más corto hasta v es el más corto de todos los caminos posibles hasta v. (demostración por inducción).
De esta forma, al acabar el proceso, todos los nodos estarán incluidos en S y, en consecuencia, D contendrá la solución del problema.
Con estos elementos puede demostrarse que la estrategia propuesta por Dijkstra proporciona los caminos óptimos.
Inicialmente S = { 1 } y C = { 2, 3, 4, 5 } y la composición inicial del vector D[2..5] = [ 50, 30, 100, 10 ] corresponde a las longitudes de los arcos que unen el nodo origen, el 1, con los restantes nodos.
Veamos a continuación cómo la estrategia voraz construye la solución
D[2..5] = { 35, 30, 20, 10 } P[2..5] = { 3, 1, 5, 1 }
Camino mínimo de 1 a 2: 1 -> 3 -> 2
Camino mínimo de 1 a 3: 1 -> 3
Camino mínimo de 1 a 4: 1 -> 5 -> 4
Camino mínimo de 1 a 5: 1 -> 5
Sea G = <N, A> un grafo conexo no dirigido, donde N es el conjunto de nodos y A es el conjunto de ejes. Además, existe una función L: A -> R+ denominada longitud o coste de un eje.
El problema consiste en hallar un grafo parcial de G,
G’ = <N, T>
Los ejes de T deben mantener conectados todos los nodos de G.
La suma de las longitudes de los ejes de T debe ser mínima.
El grafo G´ SIEMPRE existe dado que G es finito y conexo.
G´ debe ser un ÁRBOL (POR TEORÍA DE GRAFOS)
Dado que G´ debe ser conexo debe tener al menos n-1 ejes, supuesto que el número de nodos de G es n.
Si G´ tuviera más de n-1 ejes, eso querría decir que tendría al menos un ciclo, lo que implicaría que podríamos eliminar un eje de ese ciclo y G´ seguiría siendo conexo, lo que daría lugar a una solución de menor coste.
CONCLUSIÓN.- G´ debe de ser un ÁRBOL -> n-1 ejes. | T | = n-1
Candidatos: Los ejes de A
Estrategia: La idea es que todos los nodos están inicialmente aislados (hay n componentes conexas inicialmente) y vamos añadiendo sucesivamente ejes, de modo que en cada selección el número de componentes conexas se reduce en una unidad.
Candidato más prometedor: Eje de A con MENOR longitud
Factibilidad: El eje elegido debe de tener los extremos en componentes conexas diferentes, así nos aseguramos de que no forma ciclo con los que ya han sido seleccionados anteriormente.
Para diseñar el algoritmo hemos necesitado dos operaciones auxiliares:
buscar(x): devuelve la componente conexa a la que pertenece el nodo x
fusionar(A,B): fusiona las componentes conexas A y B como consecuencia de la adicción de un nuevo eje.
Observar que a lo largo del proceso existirán varias componentes conexas.
Cada componente conexa es, en sí misma, un árbol de recubrimiento mínimo para el conjunto de nodos que la forman.
Candidatos: Los ejes de A
Estrategia: Partiendo de un nodo cualquiera vamos creando una componente conexa cada vez mayor, haciendo que cada eje elegido extienda esa componente a un nodo nuevo.
Candidato más prometedor: Eje de A con MENOR longitud.
Factibilidad: El eje a añadir debe tener un extremo dentro y otro fuera de la componente conexa, para aseguramos de que no forma ciclo con los que ya están en la solución.
B -> conjunto de nodos ya conectados
Dicho conjunto se inicializa con un nodo cualquiera.
Mas_proximo[i]
almacena en cada paso el nodo más próximo a i (i NO pertenece a B) entre los pertenecientes a la componente conexa (pertenecientes a B) en ese momento.
Dist_min[i]
almacena en cada paso la distancia del nodo i (i NO pertenece a B) al nodo más próximo entre los pertenecientes a la componente conexa (pertenecientes a B) en ese momento.
Cuando i pasa a pertenecer a B, Dist_min[i] toma valor -1.
… continúa hasta incorporar n-1 ejes en la solución o hasta que los N nodos estén en B
A lo largo del proceso, existirá una componente conexa creciente a la que se van añadiendo sucesivamente ejes.
En todo momento esa componente conexa es en sí misma un árbol de expansión mínima para el conjunto de nodos que la forman.
Disponemos de 2 algoritmos que resuelven el mismo problema
¿Cuál usamos?
Grafo con número mínimo de ejes para ser conexo, esto es, con n-1 ejes Þ Kruskal Î O(n log n).
La preferencia por uno u otro depende de la “densidad” del grafo, de tal forma que a medida que ésta crece, el algoritmo de Kruskal va perdiendo interés, y lo va ganando el de Prim.
donde T A, que satisfaga las siguientes condiciones:
Prim siendo n el número de nodos.
Kruskal , siendo a el número de ejes del grafo.
Grafo completo: el número de ejes es n(n-1)/2 -> ,
