Algoritmos voraces que producen la solución óptima

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)

Ejemplo: Caminos mínimos

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 ] = $\infin$ si (i, j) $\notin$ 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.

Algoritmo de Dijkstra

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

Función Dijkstra ( L[1..n][1..n] : matriz ) retorna (D[2..n], P[2..n] : vector )
      C = { 2, 3, …, n }     # implícitamente S = { 1 }
      para i  = 2  hasta   n  hacer
            D[ i ] = L[ 1 ][ i ]
            P[ i ] = 1
      fpara
      repetir   n-2 veces     # bucle voraz
	v -> aquel elemento de C que minimice D[v]
	C = C – {v}         # implícitamente  S = S  { v }
	para cada  w in C   hacer
		si D[w] > D[v] + L[v][w] entonces
		        D[w]=D[v] + L[v][w]
		        P[w]=v
		fsi
 	fpara
      frepetir
      retorna (D[2..n],P[2..n])
ffunción

Ejemplo: Búsqueda del árbol de recubrimiento de coste mínimo

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>

donde T $\sub$ A, que satisfaga las siguientes condiciones:

• 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

Estrategia Kruskal

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.

Función Kruskal ( G = <N,A> : grafo; L : A  R+ ) retorna ( T : conjunto de ejes )
         n = | N |
         T = conjunto vacío       # conjunto de ejes que forman la solución
         Inicializar las n componentes conexas 
         mientras | T | < n - 1 hacer    # bucle voraz
                  e -> eje {u,v} de menor longitud de los aún no seleccionados
                  comp_u  = buscar(u)
                  comp_v  = buscar(v)
                  si (comp_u != comp_v) entonces
		      fusionar (comp_u, comp_v)
		      T = T union {e}
                  fsi
         fmientras
         retornar T
ffuncion

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.

Estrategia de Prim

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.

Función PRIM ( G = <N,A> : grafo; L : A  R+ )  retorna ( T : conjunto de ejes )
     B ->  un nodo arbitrario de N
     T = conjunto vacío   # conjunto de ejes que forman la solución
     mientras  B != N    hacer    # bucle voraz
	Buscar e = {u,v} de longitud mínima, tal que u in B  y  v in B
	T = T  union {e}
             B = B  union {v}
     fmientras
     retorna T
ffunción

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.

iteración 1

iteración 2

… continúa hasta incorporar n-1 ejes en la solución o hasta que los N nodos estén en B

Función PRIM ( L[1..n, 1..n])  retorna (T : conjunto de ejes )
# inicialización
B = {nodo 1}
T = conjunto vacío   # conjunto de ejes que forman la solución
para i = 2   hasta  n   hacer 
	Mas_proximo[i] = 1
        Dist_min[i] = L[i][1]
fpara
Repetir  n - 1 veces    # bucle voraz
      min  = infinito
      para i = 2   hasta  n   Hacer 
             si  0 <= Dist_min[ i ] < min   entonces
            	min = Dist_min[i] 
	        k = i
             fsi
      fpara
      T <- T union { Mas_proximo[k], k }
      Dist_min[k] = -1      # se añade k a B
      para i=2  hasta  n   hacer 
           si  L[i][k] < Dist_min[i]   entonces
            	Dist_min[i] = L[i][k] 
	        Mas-proximo[i] = k
           fsi
      fpara
  frepetir
retorna T
ffunción

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.

Órdenes de complejidad de Kruskal y Prim

Disponemos de 2 algoritmos que resuelven el mismo problema

¿Cuál usamos?

Prim $\in O(n^2)$ siendo n el número de nodos.

Kruskal $\in O(a log n)$, siendo a el número de ejes del grafo.

Grafo completo: el número de ejes es n(n-1)/2 -> $\in O(n log n)$,

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.