PDF de programación - Análisis y Diseño de Algoritmos - Algoritmos Greedy

Algoritmos
Algoritmos Greedy
Greedy
Análisis y Diseño de Algoritmos
Análisis y Diseño de Algoritmos

Algoritmos Greedy
Algoritmos
Greedy

Características generales
 Características generales
Elementos de un algoritmo greedy
 Elementos de un algoritmo
greedy
Esquema de un algoritmo greedy
 Esquema de un algoritmo
greedy
Ejemplos
 Ejemplos
 Selección de actividades
 Selección de actividades
Selección de actividades
Selección de actividades
 Almacenamiento óptimo en cintas
Almacenamiento óptimo en cintas
 Problema de la mochila fraccional
Problema de la mochila fraccional
Heurísticas greedy
greedy
 Ejemplo: El problema de la mochila
Ejemplo: El problema de la mochila
 Aplicaciones
Aplicaciones

 Heurísticas

11

Características generales
Características generales

 Se utilizan generalmente para resolver problemas de
Se utilizan generalmente para resolver problemas de
optimización (obtener el máximo o el mínimo).
optimización (obtener el máximo o el mínimo).

Toman decisiones en función de la información que
 Toman decisiones en función de la información que
está disponible en cada momento.
está disponible en cada momento.
está disponible en cada momento.
está disponible en cada momento.

Una vez tomada la decisión, ésta no vuelve a
 Una vez tomada la decisión, ésta no vuelve a
replantearse en el futuro.
replantearse en el futuro.

 Suelen ser rápidos y fáciles de implementar.
Suelen ser rápidos y fáciles de implementar.

 No siempre garantizan alcanzar la solución óptima.
No siempre garantizan alcanzar la solución óptima.

22

Características generales
Características generales

greedy (adj):
avaricioso, voraz, ávido, codicioso, glotón…

¡Cómete siempre todo
¡Cómete siempre todo
lo que tengas a mano!

33

Características generales
Características generales

NOTA IMPORTANTE
NOTA IMPORTANTE

El enfoque “
El enfoque “greedy
soluciones óptimas.
soluciones óptimas.
soluciones óptimas.
soluciones óptimas.

greedy” no nos garantiza obtener
” no nos garantiza obtener

Por lo tanto, siempre habrá que estudiar la
Por lo tanto, siempre habrá que estudiar la
corrección del algoritmo para demostrar si las
para demostrar si las
corrección del algoritmo
soluciones obtenidas son óptimas o no.
soluciones obtenidas son óptimas o no.

44

Elementos
Elementos

Para poder resolver un problema usando el enfoque
Para poder resolver un problema usando el enfoque
greedy
greedy, tendremos que considerar

, tendremos que considerar 6 6 elementos:
elementos:

4.4. Función de factibilidad

Conjunto de candidatos (elementos seleccionables).
(elementos seleccionables).
1.1. Conjunto de candidatos
Solución parcial (candidatos seleccionados).
(candidatos seleccionados).
2.2. Solución parcial
Función de selección (determina el mejor candidato
Función de selección (determina el mejor candidato
(determina el mejor candidato
(determina el mejor candidato
Función de selección
3.3. Función de selección
del conjunto de candidatos seleccionables).
del conjunto de candidatos seleccionables).
Función de factibilidad (determina si es posible
(determina si es posible
completar la solución parcial para alcanzar una solución
completar la solución parcial para alcanzar una solución
del problema).
del problema).
Criterio que define lo que es una solución (indica
(indica
si la solución parcial obtenida resuelve el problema).
si la solución parcial obtenida resuelve el problema).
Función objetivo (valor de la solución alcanzada).
(valor de la solución alcanzada).

5.5. Criterio que define lo que es una solución

6.6. Función objetivo

55

Esquema general
Esquema general

 Se parte de un conjunto vacío: S =

Se parte de un conjunto vacío: S = ∅∅..

De la lista de candidatos, se elige el mejor (de
 De la lista de candidatos, se elige el mejor (de
acuerdo con la función de selección
acuerdo con la

función de selección).).

Comprobamos si se puede llegar a una solución con el
 Comprobamos si se puede llegar a una solución con el
 Comprobamos si se puede llegar a una solución con el
Comprobamos si se puede llegar a una solución con el
candidato seleccionado (
candidato seleccionado (función de factibilidad
Si no es así, lo eliminamos de la lista de candidatos
Si no es así, lo eliminamos de la lista de candidatos
posibles y nunca más lo consideraremos.
posibles y nunca más lo consideraremos.

función de factibilidad). ).

Si aún no hemos llegado a una solución,
 Si aún no hemos llegado a una solución,
seleccionamos otro candidato y repetimos el proceso
seleccionamos otro candidato y repetimos el proceso
hasta llegar a una solución [o quedarnos sin posibles
hasta llegar a una solución [o quedarnos sin posibles
candidatos].
candidatos].

Esquema general
Esquema general

Greedy (conjunto de candidatos C): solución S
Greedy
(conjunto de candidatos C): solución S

S = Ø
S = Ø

while (S no sea una solución y C ≠ Ø) {
while
(S no sea una solución y C ≠ Ø) {

x = selección(C)
x = selección(C)

C = C
C = C –– {x}{x}
C = C
C = C –– {x}{x}

ifif (S(S∪∪∪∪∪∪∪∪{x} es factible)
{x} es factible)

S = S∪∪∪∪∪∪∪∪{x}{x}
S = S

}}

ifif (S es una solución)
(S es una solución)

return
return S;S;

elseelse

return “No se encontró una solución”;
return
“No se encontró una solución”;

66

77

Ejemplo
Ejemplo
Selección de actividades
Selección de actividades

Tenemos que elegir de entre un conjunto de actividades:
Tenemos que elegir de entre un conjunto de actividades:
 Para cada actividad, conocemos su hora de comienzo
Para cada actividad, conocemos su hora de comienzo
y su hora de finalización.
y su hora de finalización.
Podemos asistir a todas las actividades que queramos.
 Podemos asistir a todas las actividades que queramos.
 Podemos asistir a todas las actividades que queramos.
Podemos asistir a todas las actividades que queramos.
 Sin embargo, hay actividades que se solapan en el
Sin embargo, hay actividades que se solapan en el
tiempo y no podemos estar en dos sitios a la vez.
tiempo y no podemos estar en dos sitios a la vez.

Posibles objetivos
Posibles objetivos
1.1. Asistir al mayor número de actividades posible.
Asistir al mayor número de actividades posible.
2.2. Minimizar el tiempo que estamos ociosos.
Minimizar el tiempo que estamos ociosos.

Ejemplo
Ejemplo
Selección de actividades
Selección de actividades

Problema de selección de actividades
Problema de selección de actividades

Dado un conjunto C de n actividades, con
Dado un conjunto C de n actividades, con

ssii = tiempo de comienzo de la actividad i
= tiempo de comienzo de la actividad i
ffii = tiempo de finalización de la actividad i
= tiempo de finalización de la actividad i

encontrar el subconjunto S de actividades compatibles
encontrar el subconjunto S de actividades compatibles
de tamaño máximo (esto es, actividades que no se
de tamaño máximo (esto es, actividades que no se
solapen en el tiempo).
solapen en el tiempo).

88

99

Ejemplo
Ejemplo
Selección de actividades
Selección de actividades

Elementos del problema
Elementos del problema

 Conjunto de candidatos: C = {actividades ofertadas}.
 Solución parcial: S (inicialmente, S=∅).
 Solución parcial: S (inicialmente, S=∅).
 Función de selección: menor duración, menor

solapamiento, terminación más temprana…

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

(esto es, no se solapa) con las actividades de S.
 Criterio que define lo que es una solución: C=∅.
 Función objetivo (lo que tratamos de optimizar):

El tamaño de S.

Ejemplo
Ejemplo
Selección de actividades
Selección de actividades

Estrategias
Estrategias greedy
Orden en el que se pueden considerar las actividades:
Orden en el que se pueden considerar las actividades:

greedy alternativas
alternativas

 Orden creciente de hora de comienzo.
 Orden creciente de hora de comienzo.

 Orden creciente de hora de finalización.

 Orden creciente de duración: ffi i -- ssii
 Orden creciente de conflictos con otras actividades
Orden creciente de conflictos con otras actividades
(con cuántas actividades se solapa).
(con cuántas actividades se solapa).

1010

1111

Ejemplo
Ejemplo
Selección de actividades
Selección de actividades

Estrategias
Estrategias greedy
Contraejemplos (para descartar alternativas)
Contraejemplos (para descartar alternativas)

greedy alternativas
alternativas

 Orden creciente de hora de comienzo.
 Orden creciente de hora de comienzo.

 Orden creciente de duración: ffi i -- ssii

 Orden creciente de conflictos con otras actividades
Orden creciente de conflictos con otras actividades

Ejemplo
Ejemplo
Selección de actividades
Selección de actividades

Algoritmo Greedy
Algoritmo
Greedy
SelecciónActividades (C: actividades): S
SelecciónActividades
(C: actividades): S

Ordenar C en orden creciente de tiempo de finalización.
Ordenar
Ordenar
Ordenar C en orden creciente de tiempo de finalización.
C en orden creciente de tiempo de finalización.
C en orden creciente de tiempo de finalización.
Seleccionar
Seleccionar la primera
(esto es, extraerla del conjunto C y añadirla a S).
(esto es, extraerla del conjunto C y añadirla a S).
Repetir
Repetir

la primera actividad de C
actividad de C

la siguiente actividad del del conjunto

Extraer
Extraer la siguiente actividad
Si comienza
Si comienza después de que la actividad
haya terminado, seleccionarla (añadirla a S).
haya terminado, seleccionarla (añadirla a S).

conjunto ordenado:
ordenado:
después de que la actividad previa en S
previa en S

hasta que C C esté vacío.
hasta que
esté vacío.

1212

1313

Ejemplo
Ejemplo
Selección de actividades
Selección de actividades

Algoritmo Greedy
Algoritmo
Greedy
SelecciónActividades (C: actividades): S
SelecciónActividades
(C: actividades): S

{{

sortsort(C);
sortsort(C);

(C); // ordenar según tiempo
(C); // ordenar según tiempo

// ordenar según tiempo de finalización
// ordenar según tiempo de finalización
de finali