Algoritmos voraces

Algoritmos y estructuras de datos II

José Antonio Hernández López1

1 Departamentode Informática y Sistemas

Universidad de Murcia

4 de marzo de 2025

José A. (UMU) Algoritmos voraces 4 de marzo de 2025 1 / 23

Índice

1 Algoritmo voraz y el problema de la

2 Mochila no 0/1

José A. (UMU) Algoritmos voraces 4 de marzo de 2025 2 / 23

Algoritmo voraz

Definición
Los algoritmos voraces (o de avance rápido) son un tipo de algoritmos que
construyen la solución paso a paso y, en cada paso, toma un decisión que
es localmente óptima con la esperanza de que, al final, lleguemos a la
solución óptima global.

1 Una vez que se toma la decisión, no hay vuelta atrás.

2 Se suelen utilizar en problemas de optimización.
3 Hay veces que obtenemos la solución óptima usando un algoritmo
voraz y otras que no (en la gran mayoría no).
4 Suelen ser métodos iterativos muy rápidos y eficientes (suele ser
posible tener una implementación recursiva).

José A. (UMU) Algoritmos voraces 4 de marzo de 2025 3 / 23

Algoritmo voraz: esquema

Dado un problema P y una solución S inicialmente vacía, el algoritmo

voraz hace lo siguiente:
1 Se toma una decisión voraz en base a información local de P y se
añade a la solución S. Si es la solución final, terminamos.
2 Se construye un subproblema P 0 en base a la decisión voraz de la
misma naturaleza que P.
3 Volver a ejecutar 1 y 2 para P 0 hasta que tengamos la solución final.

José A. (UMU) Algoritmos voraces 4 de marzo de 2025 4 / 23

Ejemplo: el problema de la rana

Descripción del problema

La rana empieza en la posición 0 y quiere llegar a la posición n.
Hay nenúfares en varias posiciones. Hay uno en la posición 0 y otra en
la posición n.
La rana puede saltar, como máximo, d unidades en un solo salto.
Objetivo: Encontrar el camino que la rana debería seguir que
minimize el número de saltos. Se asume que existe una solución.

José A. (UMU) Algoritmos voraces 4 de marzo de 2025 5 / 23

Ejemplo: el problema de la rana

José A. (UMU) Algoritmos voraces 4 de marzo de 2025 6 / 23

Ejemplo: el problema de la rana

Nuestra decisión voraz: en cada paso escoger el nenúfar más alejado.

José A. (UMU) Algoritmos voraces 4 de marzo de 2025 6 / 23

Ejemplo: el problema de la rana

El problema P inicial está parametrizado por (i, f ) donde i es el inicio y f

es el final. Así pues, en cada paso,
1 La decisión voraz viene dada por el nenúfar l más alejado alcanzable
desde i que no sobrepase a f . Si es f , entonces hemos terminado. Si
no es f , se añade a S.
2 Construimos P(l, f ) (llegar de l a f ).
3 Volver a ejecutar 1 y 2 para P(l, f ) hasta llegar a f .

José A. (UMU) Algoritmos voraces 4 de marzo de 2025 7 / 23

Ejemplo: el problema de la rana
1 def rana_voraz(nenufares , d):
2 # inicializamos la solución como lista vacía
3 S = []
4 # posición actual
5 x = 0
6 # tamaño tablero
7 n = len(nenufares) - 1
8
9 while x < n:
10 # si podemos saltar al final y terminar lo hacemos
11 if x + d >= n:
12 x = n
13 else:
14 # elección voraz: escogemos el nenúfar
15 # más alejado de x al que podemos saltar
16 eleccion_voraz = -1
17 for j in range(d, 0, -1): para j en rango 3, 2, 1;
18 if nenufares[x + j] == 1:
19 eleccion_voraz = x + j
20 break
21
22 # añadimos la elección voraz a S
23 [Link](eleccion_voraz)
24 # transformamos el problema en uno más pequeño avanzando la pos actual
25 x = eleccion_voraz
26
27 return S
28
29 nenufares = [1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1]
30 d = 3
31 rana_voraz(nenufares , d)
32 # salida: [3, 5, 8]

José A. (UMU) Algoritmos voraces 4 de marzo de 2025 8 / 23

Teorema del algoritmo voraz

Para este problema, ¿el algoritmo voraz devuelve la solución óptima?

José A. (UMU) Algoritmos voraces 4 de marzo de 2025 9 / 23

Teorema del algoritmo voraz

Para este problema, ¿el algoritmo voraz devuelve la solución óptima?

En general, probar que un algoritmo voraz devuelve la solución óptima, no
es trivial...

José A. (UMU) Algoritmos voraces 4 de marzo de 2025 9 / 23

Teorema del algoritmo voraz

Teorema del algoritmo voraz

Dado un algoritmo voraz diseñado para un problema de optimización P, si
se cumplen estas dos condiciones:
Propiedad de la decisión voraz: existe una solución óptima de P
que contiene la decisión voraz ⇒ tomando la decisión voraz vamos
encaminados a la solución óptima final
Subestructura óptima: Sea l la decisión voraz para P y S 0 la
solución óptima al problema P 0 , entonces l unido a S 0 es una solución
óptima de P ⇒ podemos resolver el subproblema que queda de la
misma manera.
entonces el agoritmo devuelve la solución óptima.

José A. (UMU) Algoritmos voraces 4 de marzo de 2025 10 / 23

Ejemplo: el problema de la rana

Teorema del algoritmo voraz aplicado a

Dado el problema P(i, f ):
Propiedad de la decisión voraz: si estoy en la posición i y escojo el
más alejado l, existe una solución S de P(i, f ) que empieza por l.
Subestructura óptima: Sea l la decisión voraz y S 0 la solución de
P(l, f ), entonces l concatenado con S 0 es la solución óptima de
P(i, f ).

José A. (UMU) Algoritmos voraces 4 de marzo de 2025 11 / 23

Ejemplo: el problema de la rana

Lema
Propiedad de la decisión voraz: si estoy en la posición i y escojo el más
alejado l, existe una solución óptima S de P(i, f ) que empieza por l.

José A. (UMU) Algoritmos voraces 4 de marzo de 2025 12 / 23

Ejemplo: el problema de la rana

Lema
Propiedad de la decisión voraz: si estoy en la posición i y escojo el más
alejado l, existe una solución óptima S de P(i, f ) que empieza por l.

Demostración. Esta propiedad se suele demostrar partiendo de una

solución óptima y construyendo otra que contenga a la decisión voraz. Sea
S una solución óptima de P(i, j). Tenemos varias opciones:
1 l está en S como primer elemento. En este caso hemos terminado.
2 l está en S pero no como primer elemento. Esto no puede ser, pues
entonces podríamos construir un |S 0 | < |S| quitando todos los que
hay antes que l.
3 l no está en S. Entonces S se puede descomponer en L1 ||L2 donde
L1 , L2 son los que están antes, después de l respectivamente. Si
construimos S 0 = l||L2 tenemos que |S 0 | ≤ |S| ya que |L1 | ≥ 1.

José A. (UMU) Algoritmos voraces 4 de marzo de 2025 12 / 23

Ejemplo: el problema de la rana
Lema
Subestructura óptima: Sea l la decisión voraz y S 0 la solución óptima de
P(l, f ), entonces l concatenado con S 0 es la solución óptima de P(i, f ).

José A. (UMU) Algoritmos voraces 4 de marzo de 2025 13 / 23

Ejemplo: el problema de la rana
Lema
Subestructura óptima: Sea l la decisión voraz y S 0 la solución óptima de
P(l, f ), entonces l concatenado con S 0 es la solución óptima de P(i, f ).

Demostración. Por reducción al absurdo. Supongamos que existe W

solución óptima de P(i, f ) tal que |W | < |S 0 ∪ {l}| = |S 0 | + 1. Entonces:
1 Si W contiene a l como primer elemento, entonces W − {l} sería una

solución válida de P(l, f ) tal que |W − {l}| = W − 1 < |S 0 |. Lo que

sería una contradicción pues S 0 es una solución óptima de P(l, f ).
2 Si W no contiene a l, entonces tiene que haber nenúfares L en W

antes que l ya que l es el nenúfar más alejado posible alcanzable

desde i. W − L es una solución válida P(l, f ) tal que
|W − L| = |W | − |L| < |S 0 |, contraducción.
3 Si W contiene a l pero no como primer elemento, entonces entonces

tiene que haber nenúfares L en W antes que l. Así pues, W − L − {l}

es una solución válida de P(l, f ) tal que
|W − L − {l}| = |W | − |L| − 1 < |S 0 |, contradicción.
José A. (UMU) Algoritmos voraces 4 de marzo de 2025 13 / 23
Mochila no 0/1
Descripción del problema
Tenemos O = {1, . . . , n}, n objetos con pesos pi > 0 beneficios
bi > 0.
En la mochila tenemos que meter objetos, con un peso máximo de M.
Se pueden fraccionar los objetos.
Objetivo: Llenar la mochila maximizando el beneficio sin superar la
capacidad
Pn máxima. Se asume que el problema no es trivial (es decir,
p
i=1 i > M).

José A. (UMU) Algoritmos voraces 4 de marzo de 2025 14 / 23

Mochila no 0/1
Descripción del problema
Tenemos O = {1, . . . , n}, n objetos con pesos pi > 0 beneficios
bi > 0.
En la mochila tenemos que meter objetos, con un peso máximo de M.
Se pueden fraccionar los objetos.
Objetivo: Llenar la mochila maximizando el beneficio sin superar la
capacidad
Pn máxima. Se asume que el problema no es trivial (es decir,
p
i=1 i > M).

Por ejemplo: n = 3, M = 20 y
p = (18, 15, 10)
b = (25, 24, 15)
1 S1 = (1, 2/15, 0), beneficio = 28, 2
2 S2 = (0, 2/3, 1), beneficio = 31
Las soluciones se representan como una tupla de n, 0 ≤ xi ≤ 1.
José A. (UMU) Algoritmos voraces 4 de marzo de 2025 14 / 23
Mochila no 0/1

El problema P está parametrizado por (M, O) donde M es el peso máximo

de la mochila y O son los objetos. Así pues, en cada paso,
1 Tomamos una decisión voraz y la añadimos a S. La decisión voraz es
el objeto l que metemos con su proporción xl .
2 Construimos P(M − xl pl , O − {l})
3 Volver a ejecutar 1 y 2 para P(M − xl pl , O − {l}).

José A. (UMU) Algoritmos voraces 4 de marzo de 2025 15 / 23

Mochila no 0/1

El problema P está parametrizado por (M, O) donde M es el peso máximo

de la mochila y O son los objetos. Así pues, en cada paso,
1 Tomamos una decisión voraz y la añadimos a S. La decisión voraz es
el objeto l que metemos con su proporción xl .
2 Construimos P(M − xl pl , O − {l})
3 Volver a ejecutar 1 y 2 para P(M − xl pl , O − {l}).

Nota
Vamos a asumir que, una vez seleccionado el objeto, la proporción que
vamos a añadir va a ser la máxima posible. Es decir, si el objeto
seleccionado cabe entero, lo metemos. Si no cabe, metemos lo máximo
posible de eso objeto hasta llenar la mochila.

José A. (UMU) Algoritmos voraces 4 de marzo de 2025 15 / 23

Mochila no 0/1

1 def seleccion_voraz(O, B, P, capacidad_restante):

2 ...
3
4 def mochila(O, B, P, M):
5 # solución como array de 0s de longitud el número de objetos
6 S = [0] * len(O)
7 # peso actual
8 m = 0
9 # los objetos disponibles en cada paso
10 O_disponibles = set(O)
11 while m < M:
12 capacidad_restante = M - m
13 # selecciono el objeto y la cantidad que quiero meter
14 x_l , l = seleccion_voraz(O_disponibles , B, P, capacidad_restante)
15 # añado la solución
16 S[l] = x_l
17
18 # transformo el problema en uno más pequeño
19 # elimino el objeto seleccionado de los disponibles
20 O_disponibles.remove(l)
21 # aumento el peso actual
22 m += x_l*P[l]
23 return S

José A. (UMU) Algoritmos voraces 4 de marzo de 2025 16 / 23

Mochila no 0/1
Posibles criterios:
El objeto con más beneficio

José A. (UMU) Algoritmos voraces 4 de marzo de 2025 17 / 23

Mochila no 0/1
Posibles criterios:
El objeto con más beneficio
n = 4; M = 10
p = (10, 3, 3, 4)
b = (10, 9, 9, 9)
Si ejecutamos el algoritmo con este criterio obtendríamos un beneficio
total de 10 pues solo escogeríamos el primer elemento. Esta solución
dista de la óptima...

José A. (UMU) Algoritmos voraces 4 de marzo de 2025 17 / 23

Mochila no 0/1
Posibles criterios:
El objeto con más beneficio
n = 4; M = 10
p = (10, 3, 3, 4)
b = (10, 9, 9, 9)
Si ejecutamos el algoritmo con este criterio obtendríamos un beneficio
total de 10 pues solo escogeríamos el primer elemento. Esta solución
dista de la óptima...
El objeto menos pesado

José A. (UMU) Algoritmos voraces 4 de marzo de 2025 17 / 23

Mochila no 0/1
Posibles criterios:
El objeto con más beneficio
n = 4; M = 10
p = (10, 3, 3, 4)
b = (10, 9, 9, 9)
Si ejecutamos el algoritmo con este criterio obtendríamos un beneficio
total de 10 pues solo escogeríamos el primer elemento. Esta solución
dista de la óptima...
El objeto menos pesado n = 2; M = 10
p = (10, 9)
b = (10, 1)
Siguiendo un razonamiento similar, al ejecutar el algoritmo no
obtenemos la solución óptima.
El objeto con mejor proporción bi /pi ...
José A. (UMU) Algoritmos voraces 4 de marzo de 2025 17 / 23
Mochila no 0/1

Teorema del algoritmo voraz aplicado a

Dado el problema P(M, O) y el algoritmo voraz de la mejor proporción:
Propiedad de la decisión voraz: existe una solución óptima que
contiene al elemento con mejor proporción y en la mayor cantidad
posible.
Subestructura óptima: sea xl la decisión voraz escogida para P(M, O)
y S 0 la solución óptima de P(M − xl pl , O − {l}), entonces {xl } ∪ S 0
es solución óptima de P(M, O).

José A. (UMU) Algoritmos voraces 4 de marzo de 2025 18 / 23

Mochila no 0/1

Lema
Propiedad de la decisión voraz: existe una solución óptima que contiene al
elemento con mejor proporción y en la mayor cantidad posible.

1
ya que si no existiera al menos uno significaría que o bien, la mochila está vacía o
bien solo está i en la solución pero no en la mayor cantidad posible
José A. (UMU) Algoritmos voraces 4 de marzo de 2025 19 / 23
Mochila no 0/1

Lema
Propiedad de la decisión voraz: existe una solución óptima que contiene al
elemento con mejor proporción y en la mayor cantidad posible.

Demostración. Sea S la solución óptima de P e i el objeto con mejor

proporción. Entonces tenemos dos opciones:
1 S contiene a i y en la mayor cantidad posible. No hay nada que hacer

y hemos terminado
2 S no contiene a i o lo contiene pero no en la mayor cantidad posible.

En este segundo caso, podemos suponer que existe otro objeto en la

solución j con 0 6= xj ∈ S 1 . Este objeto cumple que

bi bj
≥ .
pi pj
1
ya que si no existiera al menos uno significaría que o bien, la mochila está vacía o
bien solo está i en la solución pero no en la mayor cantidad posible
José A. (UMU) Algoritmos voraces 4 de marzo de 2025 19 / 23
Mochila no 0/1

Dado un r > 0, construimos un S 0 quitando un peso r de j y poníendoselo

a i. Sea xj0 y xi0 las cantidades de cada objeto que se quitan/añaden tales
que pj xj0 = r y pi xi0 = r (lo que se añade de cada objeto es igual a r ). Así
pues
bi bj
Si pi > pj , entonces

bi bj
 
b(S ) = b(S) −
0
bj xj0 + bi xi0 = b(S) + r − > b(S).
pi pj

Esto no puede darse ya que hemos supuesto que S es la solución

óptima.

José A. (UMU) Algoritmos voraces 4 de marzo de 2025 20 / 23

Mochila no 0/1

bi bj
No nos queda más remedio que suponer que pi = pj , entonces

bi bj
 
b(S ) = b(S) −
0
bj xj0 + bi xi0 = b(S) + r − = b(S)
pi pj

Esto podría darse y corresponde al caso de que haya objetos que

tengan la misma proporción beneficio-peso que i. En ese caso, como
para cada r siempre podemos pasar ese peso de un objeto j 6= i a i y
obtener una solución igual de buena (óptima), pues pasamos peso de
todos los objetos distintos a i hasta conseguir la mayor cantidad
posible.

José A. (UMU) Algoritmos voraces 4 de marzo de 2025 21 / 23

Mochila no 0/1

Lema
Subestructura óptima: sea xl la decisión voraz escogida para P(M, O) y S 0
la solución óptima de P(M − xl pl , O − {l}), entonces {xl } ∪ S 0 es solución
óptima de P(M, O).

José A. (UMU) Algoritmos voraces 4 de marzo de 2025 22 / 23

Mochila no 0/1

Lema
Subestructura óptima: sea xl la decisión voraz escogida para P(M, O) y S 0
la solución óptima de P(M − xl pl , O − {l}), entonces {xl } ∪ S 0 es solución
óptima de P(M, O).

Por reducción a lo absurdo, supongamos que existe W solución óptima de

P(M, O) tal que b(W ) > b({xl } ∪ S 0 ) = b(S 0 ) + xl bl . Sea
W 0 = W − {xl }, entonces:

p(W 0 ) = p(W ) − xl pl = M − xl pl

b(W 0 ) = b(W ) − xl bl > b(S 0 )

de este modo, llegamos a una contradicción.

José A. (UMU) Algoritmos voraces 4 de marzo de 2025 22 / 23

Mochila no 0/1

1 def seleccion_voraz(O, B, P, capacidad_restante):

2 l = -1
3 l_prop = -1
4
5 for o in O:
6 if B[o]/P[o] > l_prop:
7 l_prop = B[o]/P[o]
8 l = o
9
10 if capacidad_restante > P[l]:
11 return 1, l
12 else:
13 return capacidad_restante/P[l], l

José A. (UMU) Algoritmos voraces 4 de marzo de 2025 23 / 23