# 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 (<mark style="color:red;">algoritmo de Dijkstra</mark>) y
* la búsqueda del árbol de recubrimiento de coste mínimo de un grafo (<mark style="color:red;">algoritmo de Kruskal y algoritmo de Prim</mark>)

### 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.

&#x20;

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

<figure><img src="/files/OS3Zz6ItOgpPof4Lr1xi" alt=""><figcaption></figcaption></figure>

**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

```python
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.

&#x20;

El problema consiste en <mark style="color:red;">hallar un grafo parcial</mark> de G,&#x20;

<mark style="color:red;">G’ = \<N, T></mark>

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 <mark style="color:red;">ÁRBOL</mark> (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.

&#x20;CONCLUSIÓN.-  G´ debe de ser un ÁRBOL -> n-1 ejes. | T | = n-1

#### Estrategia Kruskal

<mark style="color:red;">Candidatos</mark>: Los ejes de A

<mark style="color:red;">Estrategia</mark>: 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.

<mark style="color:red;">Candidato más prometedor</mark>: Eje de A con MENOR longitud

&#x20;<mark style="color:red;">Factibilidad</mark>: 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.

```python
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

```

<figure><img src="/files/sPCdyGP1cCBki5Ai1Rfl" alt=""><figcaption></figcaption></figure>

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.

<figure><img src="/files/732qYCqd8Y8sRg6cMKqR" alt="" width="563"><figcaption></figcaption></figure>

#### Estrategia de Prim

<mark style="color:red;">Candidatos</mark>: Los ejes de A

<mark style="color:red;">Estrategia</mark>: 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.

<mark style="color:red;">Candidato más prometedor</mark>: Eje de A con MENOR longitud.

<mark style="color:red;">Factibilidad</mark>: 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.

<mark style="color:red;">B -> conjunto de nodos ya conectados</mark>

<mark style="color:red;">Dicho conjunto se inicializa con un nodo cualquiera.</mark>

<figure><img src="/files/iVAlhSlwrA3IIWOUxLYg" alt=""><figcaption></figcaption></figure>

```python
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

```

<mark style="color:red;">Mas\_proximo\[i]</mark>

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.

<mark style="color:red;">Dist\_min\[i]</mark>

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.

<figure><img src="/files/9Mi2g1LDifGvpJd35F24" alt="" width="375"><figcaption></figcaption></figure>

<figure><img src="/files/vwtXFQOFAVhbiUqzKaQ2" alt="" width="563"><figcaption><p>iteración 1</p></figcaption></figure>

<figure><img src="/files/sVdALE7LfZkbmPWQNusl" alt="" width="563"><figcaption><p>iteración 2</p></figcaption></figure>

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

```python
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.

<figure><img src="/files/LCO4mtv3TuPL1NnYdQrV" alt="" width="563"><figcaption></figcaption></figure>

### Ó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.

&#x20;

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.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://nahuels-organization.gitbook.io/algoritmia/algoritmia/tema-5-algoritmos-voraces/algoritmos-voraces-que-producen-la-solucion-optima.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.