Robert Espinoza Domínguez

Algoritmos voraces
 Algoritmos voraces

 Comprar papas en el mercado. Seleccionar las

mejores papas.

2 Kg.

¿Sí o no?
Algoritmos voraces

 Inicialmente empezamos con una solución “vacía”, sin

papas.
 Seleccionamos la mejor papa del montón o la que
“parezca” que es la mejor
 Examinamos la papa detenidamente y decidimos si se
coge o no (considerarlo).
 Si no se coge, se aparta del montón (rechazo).
 Si se coge, se mete a la bolsa y ya no se saca
(seleccionado).
 Una vez que tenemos 2 kilos paramos.

3
Algoritmos voraces

 Es un método que puede ser aplicado a numerosos

problemas, especialmente los de optimización.
 Suelen ser los más sencillos y fáciles de implementar.
 Cuando funcionan, son eficientes.
 Estas técnicas están diseñadas para aplicarse en
fases, donde se toma una decisión basándose en la
información que tiene disponible.
 Para ello se considera la alternativa más prometedora (el valor
más pequeño ó el valor más grande) en un determinado
instante.
 Su enfoque es “miope” porque no se tiene en cuenta los
efectos que estas decisiones puedan producir en el futuro.
 Nunca se reconsidera la decisión tomada, ni se retrocede por
ninguna circunstancia.
Algoritmos voraces

 Uno de sus principales inconvenientes es que en

algunos casos no encuentre ninguna solución aún
cuando ésta exista.
 El nombre de voraces o ávidos (del inglés greedy) se
debe a su comportamiento: en cada etapa “toman lo
que pueden” sin analizar la consecuencias, es decir
son “glotones” por naturaleza.
 Características Generales
 Para solucionar algún problema de forma óptima,
disponemos de un conjunto de candidatos.
 Las monedas disponibles.
 Las aristas de un grafo que se pueden usar para construir
un grafo.
 El conjunto de tareas que hay que planificar.
 Una función objetivo que determine el valor de la
solución hallada. Es la función que queremos maximizar
o minimizar y no aparece explícitamente en el algoritmo.
 El número de monedas utilizadas para dar el cambio.
 La longitud de ruta que hemos construido.
 El tiempo necesario para procesar todas las tareas de la
planificación.
 Características Generales

 Una función de selección que indica en cualquier

momento el candidato idóneo para formar la solución
entre los que aún no han sido seleccionados o
rechazados.
 Pueden existir varias funciones de selección, que están
relacionadas con la función objetivo.
 Una función que compruebe si un cierto subconjunto de
candidatos constituye una solución de nuestro
problema, ignorando si es o no óptima por el momento.
 ¿Suman las monedas seleccionadas la cantidad a pagar?
 ¿Las aristas seleccionadas forman una ruta hasta el nodo
que deseamos alcanzar?
 ¿Están planificadas todas las tareas?
 Características Generales

 Una función que compruebe si un cierto subconjunto de

candidatos es factible, es decir que sea posible seguir
añadiendo candidatos y encontrar una solución.
 A medida que avanza el algoritmo se forman dos
conjuntos
 Uno contiene candidatos que ya han sido considerados y
seleccionados (solución).
 El otro contiene candidatos que ya han sido considerados
y rechazados.
Método General
 Buscamos un subconjunto de candidatos que
constituya la solución óptima, es decir, maximice o
minimice la función objetivo.
 El problema se interpreta como: “tomar algunos
elementos de entre un conjunto de candidatos”.
 El orden el que se cogen puede ser importante o no.
 Los algoritmos trabajarán por etapas, tomando en
cada un de ellas la decisión que le parece mejor, sin
considerar las consecuencias futuras.
 Inicialmente el conjunto de elementos seleccionados
estará vacío.
 En cada paso se considera añadir a éste conjunto el
mejor candidato sin considerar los restantes, guiándonos
por la función de selección.
Método General

 Antes de añadir un candidato a la solución que estamos

construyendo, se evaluará si ésta es factible.
 Si el conjunto ampliado sigue siendo factible entonces
añadimos el candidato actual al conjunto de candidatos
seleccionados.
 En caso contrario, se rechaza el candidato.
 Cada vez que se incluye un candidato al conjunto de
candidatos seleccionados se comprobará si el conjunto
obtenido es la solución.
Método General

 Se puede generalizar el proceso intuitivo a un

esquema algorítmico general.

 El esquema trabaja con los siguientes conjuntos de

elementos:
 C: Conjunto de elementos candidatos, pendientes de
seleccionar (inicialmente todos).
 S: Candidatos considerados y seleccionados para la
solución.
 R: Candidatos considerados pero rechazados.

 ¿Qué o cuáles son los candidatos? Depende de cada

problema.
Método General
Método Voraz (C: Candidatos, S: Solución, R: Rechazados )
Mientras (No Solución(S) y C <> vacío) hacer
x  Seleccionar( C )
C  C - {x}
Si (Factible(S, {x})) entonces
Insertar(S,{x})
Sino
R  R U {x}
FinSi
FinMientras
Si (Solución(S)) entonces
Retornar S
Sino
Retornar “No hay solución”
FinSi
FinMétodo
Funciones Genéricas
 Solución (S). Comprueba si un conjunto de candidatos
es una solución (independientemente de que sea
óptima o no).
 Seleccionar (C). Devuelve el elemento más
“prometedor” del conjunto de candidatos pendientes
(no seleccionados ni rechazados).
 Factible (S, x). Indica si a partir del conjunto S y
añadiendo x, es posible construir una solución
(posiblemente añadiendo otros elementos).
 Insertar (S, x). Añade el elemento x al conjunto
solución. Además, puede ser necesario hacer otras
cosas.
 Objetivo (S). Dada una solución devuelve el coste
asociado a la misma (resultado del problema de
optimización).
 Análisis de tiempos de ejecución

 La complejidad depende del número de candidatos, de las

funciones básicas a utilizar, del número de elementos de la
solución.
 n: número de elementos de Candidatos. m: número de
elementos de una solución.
 Repetir, como máximo n veces y como mínimo m:

 Selección de un elemento entre los candidatos: f( n ).

Entre O(1) y O( n ).
 Comprobar si el valor actual es solución: h( m ).
Normalmente O( m ).
 La función factible es parecida a solución, pero con una
solución parcial g( m ).
 La unión de un nuevo elemento a la solución puede
requerir otras operaciones de cálculo, k( n, m ).
 Aplicaciones

 Planificación de tareas.
 Minimización del tiempo de espera = Almacenamiento en
cintas.
 Planificación de tareas a plazo fijo = Selección de
actividades.
 Cajero, cambio de monedas (devolver un numero
mínimo de monedas/billetes)
 Caminos mínimos en grafos (algoritmo de Dijkstra).
 Árbol generador mínimal (algoritmos de Prim & Kruskal).
 Códigos Huffman y compresión de datos.
 Construcción de arboles de decisión.
 Heurísticas voraz
Cambio de monedas
Problema del cambio de monedas

Pagar una cierta cantidad P a un

cliente utilizando el menor número
de monedas posible
 Problema del cambio de monedas

 Se tienen las monedas de 5, 2, 1, 0.50, 0.20, 0.10,

0.05 y 0.01 céntimos.

 El monto que debe de pagar es de 1.11 soles

 Se paga con una moneda de 5 soles
 Problema del cambio de monedas

 El vuelto que se debe dar es de 3.89 soles.

 1 moneda de 2
 1 moneda de 1
 1 moneda de 50 céntimos
 1 moneda de 20 céntimos
 1 moneda de 10 céntimos
 1 moneda de 5 céntimos
 4 monedas de 1 céntimo.
 Total: 10 monedas.
 El método intuitivo se puede entender como un
algoritmo voraz: en cada paso añadir una moneda
nueva a la solución actual, hasta llegar a P.
 Problema del cambio de monedas
 Conjunto de candidatos: todos los tipos de monedas
disponibles. Suponemos una cantidad ilimitada de cada
tipo.
 Solución: conjunto de monedas que sumen P.
 Función objetivo: minimizar el número de monedas.

Representación de la solución:
 El conjunto solución S está constituido por s1, s2, s3, s4,
s5, s6, s7 y s8 donde si es el número de monedas
usadas de tipo i.
 Suponemos que la moneda i vale vi.
 Formulación: Minimizar  si, sujeto a  si·vi = P, si≥0
i=1..8 i=1..8
 Problema del cambio de monedas

Funciones del esquema:

 inicialización. Inicialmente si= 0, para todo i= 1..8

 solución. El valor actual es solución si  si·vi = P

 seleccionar. ¿Qué moneda se elige en cada paso de entre los

candidatos?

 Respuesta: Elegir en cada paso la moneda de valor más alto posible,

pero sin sobrepasar la cantidad que queda por devolver.

 factible. Valdrá siempre verdad.

 En lugar de seleccionar monedas de una en una, usamos la división

entera y cogemos todas las monedas posibles de mayor valor.
 Cambio de monedas - Algoritmo

Método Voraz (S, V, cambio)

i0
Mientras (No Solución(S, V, cambio) y i < numDenominaciones)
//Seleccionar moneda
x V[i]
Si (Factible(S, V, cambio, x)) entonces
//insertar moneda
S[i]S[i]+1
Sino
//rechazar moneda
i  i +1
Fin si
Fin Mientras
 Cambio de monedas - Algoritmo

Si (Solución(S, V, cambio)) entonces

i 0
Mientras (i < numDenominacion)
Si (S [ i ] > 0) entonces
Escribir S [ i ], “ monedas de ", V[ i ]
Fin Si
i i+1
Fin Mientras
Sino
Escribir "No hay solución“
Fin Si
Fin Método
 Cambio de monedas - Algoritmo

Método Factible(S, V, cambio, x)

suma  0
Para i  0 hasta numDenominacion -1 hacer
suma suma + S[ i ] * V[ i ]
Fin Para
suma suma + x;
Si (suma <= cambio) entonces
Retornar Verdadero
Sino
Retornar Falso
Fin Método
 Cambio de monedas - Algoritmo

Método Solución(S, V, cambio, x)

suma  0
Para i  0 hasta numDenominacion -1 hacer
suma suma + S[ i ] * V[ i ]
Fin Para
Si (suma = cambio) entonces
Retornar Verdadero
Sino
Retornar Falso
Fin Método
 Problema del cambio de monedas

 ¿Garantiza siempre la solución óptima? Para este

sistema monetario sí. Pero no siempre...
 Supongamos que tenemos monedas de 100, 90 y 1.
Queremos devolver 180.
 Algoritmo voraz. 1 moneda de 100 y 80 monedas de 1,
en total 81 monedas.
 Solución óptima. 2 monedas de 90, en total 2
monedas.
 Problema del cambio de monedas
Análisis de tiempos de ejecución
 El orden de complejidad depende de:
 El número de candidatos existentes.
 Los tiempos de las funciones básicas utilizadas.
 El número de elementos de la solución.

 Ejemplo. n: número de elementos de C. m: número de

elementos de una solución.

 Repetir, como máximo n veces y como mínimo m:

 Función de selección: f(n). Entre O(1) y O(n).
 Función solución: g(m). Normalmente O(1) ó O(m).
 Función factible (parecida a solución, pero con una solución
parcial): h(m).
 Inserción de un elemento: k(n, m).
 Problema del cambio de monedas
Análisis de tiempos de ejecución

 Tiempo de ejecución genérico:

t(n,m)  O(n*(f(m)+g(n)+h(m)) + m*k(n, m))

 Ejemplos:
 Algoritmos de Prim y Dijkstra: n candidatos, la función de selección
e inserción son O(n): O(n2).

 Devolución de monedas: podemos encontrar el siguiente elemento

en un tiempo constante (ordenando las monedas): O(n).

 El análisis depende de cada algoritmo concreto.

 En la práctica los algoritmos voraces suelen ser bastante rápidos,

encontrándose dentro de órdenes de complejidad polinomiales.
Selección de actividades
 Selección de actividades

Tenemos que elegir de entre un conjunto de actividades:

 Para cada actividad, conocemos su hora de comienzo

y su hora de finalización.
 Podemos asistir a todas las actividades que queramos.

 Sin embargo, hay actividades que se solapan en el

tiempo y no podemos estar en dos sitios a la vez.

Posibles objetivos
1. Asistir al mayor número de actividades posible.
2. Minimizar el tiempo que estamos ociosos.
 Selección de actividades

8 9 10 11 12 13 14 15 16 17 18 19
 Selección de actividades

Problema de selección de actividades

Dado un conjunto C de n actividades, con

si = tiempo de comienzo de la actividad i
fi = tiempo de finalización de la actividad i

encontrar el subconjunto S de actividades compatibles de

tamaño máximo (esto es, actividades que no se solapen
en el tiempo)
 Selección de actividades

Elementos del problema

 Conjunto de candidatos: C = {actividades ofertadas}.

 Solución parcial: S (inicialmente, S=∅).

 Función de selección: menor duración, menor

solapamiento, terminación mas temprana…

 Función de factibilidad: x es factible si es compatible

(esto es, no se solapa) con las actividades de S.

 Función solución: criterio que define lo que es una

solución  C=∅.
 Función objetivo (lo que tratamos de optimizar): El
tamaño de S.
 Selección de actividades

Estrategias voraces alternativas

Orden en el que se pueden considerar las actividades:

 Orden creciente de hora de comienzo.

 Orden creciente de hora de finalización.
 Orden creciente de duración: fi - si
 Orden creciente de conflictos con otras actividades
(con cuantas actividades se solapa).
 Selección de actividades

Estrategias voraces alternativas

Contraejemplos (para descartar alternativas)

 Orden creciente de hora de comienzo.

 Orden creciente de duración: fi – si

 Orden creciente de conflictos con otras actividades

 Selección de actividades

Algoritmo Voraz
selecciónActividades (C: actividades, S: solución, n:
número de actividades)
Ordenar C en orden creciente de tiempo de finalización.
Seleccionar la primera actividad de C (esto es, extraerla
del conjunto C y añadirla a S).
Repetir
Extraer la siguiente actividad del conjunto ordenado:
Si comienza después de que la actividad previa en S
haya terminado, seleccionarla (añadirla a S).
Hasta que C este vacío.
Selección de actividades
Selección de actividades
Selección de actividades
Selección de actividades
Selección de actividades
Selección de actividades
Selección de actividades
Selección de actividades
 Selección de actividades

Método selecciónActividades (C, S, n)

ordenar(C) // ordenar según tiempo de finalización
S[0]  C[0] // seleccionar la primera actividad
i  1;
prev  0
Mientras (i <n) hacer // ¿solución(S)?
x  C[ i ] // seleccionar x
Si ([Link] >= S[prev].fin) entonces // ¿factible(x)?
S[prev+1]  x // añadir x a S
prev  prev + 1
Fin Si
i  i +1 // Descartar
Fin Mientras
Fin Método
Problema de la Mochila fraccional
 Problema de la Mochila fraccional

El problema consiste en llenar una mochila:

 La mochila puede soportar como máximo un peso P.

 Tenemos n objetos fraccionables.
 Cada objeto i tiene un peso pi y proporciona un
beneficio bi

Objetivo:
 Maximizar el beneficio de los objetos transportados.
Problema de la Mochila fraccional

Ejemplo
Beneficio ($) 20 30 65 40 55
Mochila de 100kg
Peso (Kg) 10 20 30 40 50

¿Cómo seleccionamos los objetos?

 Primero el más ligero

Peso = 10+20+30+40 = 100 kg

Beneficio = 20+30+65+40 = $155
 Primero el más valioso
Peso = 30 + 50 + 40/2 = 100 kg
Beneficio = 65 + 55 + 40/2 = $140
 Primero el que tenga mas valor por unidad de peso
bi/pi
Peso = 30 + 10 + 20 + (4/5)*50= 100 kg
Beneficio = 65 + 20 + 30 + (4/5)*55 = $159
Problema de la Mochila fraccional

 Definimos la densidad del objeto Oi como bi/pi

 Algoritmo voraz: Seleccionamos los objetos en orden

decreciente de densidad.
bi/pi ≥ bi+1/pi+1 para 1 ≤ i < n

 Se añade a la mochila todo lo que se pueda:

Si un objeto Oi no cabe entero, se rellena el espacio
disponible con la fracción del objeto que quepa hasta
completar la capacidad de la mochila.
 Problema de la Mochila fraccional

Ejemplo:
n=3 P = 17
(b1,b2,b3) = (36,22,40)
(p1,p2,p3) = (12,8,15)
Tres soluciones factibles:

(1, 5/8,0) 49.75 (Solución voraz)

(1/6, 0, 1) 46 (Ordenado desc. por beneficio)
(3/4, 1, 0) 49 (Ordenado asc. por beneficio)
 Problema de la Mochila fraccional

cap: Capacidad de la mochila

peso: Vector que contiene los pesos de los objetos
benef: Vector que contiene los beneficios de los objetos
sol: Vector solución
 Problema de la Mochila fraccional

Método mochila(benef, peso, cap, sol)

// peso y beneficio ordenados descendentemente
// por benef/peso
Para i desde 0 a n-1 hacer
sol[i] 0.0 // inicializar solución
Fin para
resto cap // capacidad restante
i0
Mientras (i<=n-1) and (peso[i]<=resto) hacer
sol[i]1
resto resto - peso[i]
ii+1
Fin Mientras
 Problema de la Mochila fraccional

Si i<n entonces
sol[i]resto/peso[i]
Fin Si
Fin
Heurística voraz

 Hay situaciones en las cuales no podemos encontrar

un algoritmo voraz que proporcione una solución
óptima.
 En muchas ocasiones, se podrían obtener mejores
soluciones reconsiderando alternativas desechadas
por un algoritmo voraz (cuando, a partir de una
solución optima local no se puede alcanzar una
solución optima global).
 Pese a ello, resultan útiles los algoritmos voraces que
proporcionan una solución rápida a problemas
complejos, aunque esta no sea óptima.
 Heurística voraz

Heurística: Procedimiento que proporciona una solución

aceptable a un problema mediante métodos que carecen
de justificación formal ([Link]. por tanteo, usando reglas
empíricas).

Satisfacer vs. optimizar

 Cuando el tiempo que se tarda en resolver un

problema es un factor clave, un algoritmo voraz puede

utilizarse como criterio heurístico.
 También puede utilizarse un algoritmo voraz para
encontrar una primera solución (como punto de partida
para otra heurística).
Problema de la mochila 0/1
Problema de la mochila (0/1)

$60 $100 $120 Mochila $160 $180 $220

¿Cómo seleccionamos los objetos de la mochila?

Estrategia: Ordenar los objetos descendentemente por valor
Problema de la mochila (0/1)

 Un algoritmo voraz proporciona la solución óptima del

problema de la mochila cuando se pueden fraccionar
los objetos. Sin embargo, el problema es mas difícil de
resolver cuando no se pueden fraccionar los objetos
 Problema de la Mochila (0,1)

Clase Objeto
peso: real
beneficio: real
Fin Clase
 Problema de la Mochila (0,1)

Método mochila(objetos[]: Objeto, n, S)

Ordenar descendentemente objetos[] por benef/peso
Para i desde 0 a n-1 hacer
S[i] 0 // inicializar solución
Fin para
resto  cap // capacidad restante
i0
Mientras (i<=n-1) and (objetos[i].peso<=resto) hacer
sol[i]1
resto  resto - objetos[i].peso[i]
ii+1
Fin Mientras
Fin Método
 Problema de la mochila (0/1)

Heurística voraz
 Ordenar los objetos por densidad no creciente:

bi/pi ≥ bi+1/pi+1 para 1 ≤ i < n

 Con un número ilimitado de objetos de cada tipo, si M

es el valor máximo de los objetos que se pueden llevar

en la mochila, la heurística garantiza obtener, al
menos, un valor de M/2 (George Dantzig, 1957).
 Sin embargo, la heurística puede proporcionar

resultados mucho peores (muy alejados del óptimo)

para instancias particulares del problema.
Almacenamiento en cintas
Almacenamiento en cintas

Almacenamiento óptimo en cintas

 Tenemos n ficheros que hay que almacenar en una

cinta de longitud L.
 Cada fichero i tiene una longitud li , 1 ≤ i ≤ n

 Todos los ficheros se recuperan del mismo modo,

siendo el tiempo medio de recuperación (TMR),

Almacenamiento en cintas

 Nos piden que encontremos una permutación de los n

ficheros tal que, cuando estén almacenados en la cinta
el TMR sea mínimo, lo que equivalente a minimizar
 Almacenamiento en cintas

Almacenamiento óptimo en cintas

Ejemplo: n=3 número de cintas
(l1,l2,l3) = (5,10,3) longitudes de las cintas

óptimo
Almacenamiento en cintas

Almacenamiento óptimo en cintas (algoritmo voraz)

Partiendo de la cinta vacía.

Mientras queden ficheros por guardar
Elegir el fichero más pequeño
Añadirlo a continuación en la cinta

 El algoritmo escoge la opción más inmediata sin tener

en cuenta si esa decisión será la mejor a largo plazo...
 Almacenamiento en cintas

Almacenamiento óptimo en cintas - Teorema

Si l1 ≤ l2 ≤ … ≤ ln,
entonces el orden de colocación ij = j, 1 ≤ j ≤ n
minimiza

para todas las posibles permutaciones ij

Demostración: Ellis Horowitz & Sartaj Sahni.

Fundamentals of Computer Algorithms, 1978
Tarea
 Aplicaciones

 Implementar en Java
 Cambio de monedas con cantidades limitadas de monedas
 Planificación de tareas a plazo fijo = Selección de
actividades.
 Problema de la mochila (0/1) y fraccional
 Diseñar el algoritmo e implementar en Java
 Asignación de tareas uno a uno, por ejemplo: