Algoritmos Avaros (Greedy Algorithms)
Agustín J. González
ELO-320: Estructura de Datos y Algoritmos
1
Introducción





Hay muchos algoritmos que pueden ser clasificados bajo la
categoría de Algoritmos Oportunistas, o avaros (Greedy
Algorithms). La idea es optar por la mejor opción de corto plazo.
Sacar mayor provecho inmediato.
Éstos se caracterizan por hacer la elección que parece mejor en el
momento.
Éstos no conducen siempre a una solución óptima, pero para
muchos casos sí.
Éstos producen una solución óptima cuando se puede llegar a ésta
a través de elecciones localmente óptimas.
Este método es muy poderoso y trabaja bien en muchos
algoritmos que veremos en las próximas semanas; por ejemplo:
Minimum-spanning-tree (árbol de mínima extensión), el algoritmo
de Dijkstra para el camino más corto en un grafo desde una única
fuente.
2
Problema de la selección de actividades



Se requiere itinerar el uso de un recurso entre varias actividades
que compiten.
Problema: Tenemos un conjunto de S={0, 1, 2, 3, .. , n-1}
actividades que desean usar un recurso (como una sala de clases
por ejemplo) del cual sólo uno puede usarse a la vez. Cada
actividad tiene un tiempo de partida si y un tiempo de término fi ,
donde si  fi.
La tarea consiste en seleccionar el conjunto de cardinalidad
máxima de actividades mutuamente compatibles; i.e. que no se
traslapen.
Suponemos que las actividades están ordenadas por orden
creciente de tiempo de término: fo  f1  f2  f3  f4 ...  fn-1 Si
no fuera así, sabemos que podemos ordenarlas en tiempo O(n lg
n).
3
Problema de la selección de actividades

Int Selector_de_Actividades(float s[, float f [, int n, int A[) {
/* s y f son arreglos de tiempos de partida y término */
/* n: número de actividades compitiendo */
/* A: Arreglo de salida indicando la asignación óptima para
máximo número de actividades*/
/* se retorna el número de actividad itineradas en A*/
int i, j = 0, m = 0;
A[m++ = 0; /* La primera es la de menor tiempo final*/
for (i=1; i < n; i++)
if (s [i >= f [j) {
A [m++ = i;
j = i;
}
return (m);
}
4
Ejemplo



Se puede demostrar que la solución aquí propuesta es óptima.
La estrategia fue asignar la actividad que dejara el recurso libre la mayor cantidad de tiempo en
el futuro y que fuera compatible con las anteriores.
Ejemplo: sea
0 1
2
3
4
5
6
7
8
9
10
S
1 3
0
5
3
5
6
8
8
2
12
F
4 5
6
7
8
9 10 11 12 13 14
0
1
0
2
0
3
0
3
4
0
3
0
3
5
6
0
3
7
0
3
7
8
3
0
7
9
0
3
7
0
3
7
10
0
1
2
3
4
5
6
7
8
9
10
10
11
12
13
14
5
Otro problema “Greedy”



Considere el problema del saco de mercaderías. Un ladrón que
ingresa a robar a una tienda dispone de un saco que puede cargar
hasta un peso W límite. Las mercaderías que tiene a su disposición
se venden a granel. Conocemos el peso total de cada mercadería y
su precio total.
El problema del ladrón es cuanto tomar de cada producto para
lograr llevar un botín de mayor valor.
Como nuestro límite es en peso, la estrategia greedy primero
calcula el valor por gramo (o kilo) de cada producto. Luego los
ordena de mayor a menor precio por unidad de peso y va tomando
el primer producto hasta agotarlo, luego el segundo y así
sucesivamente hasta completar la carga límite.
6
Variante del problema anterior





Una variante de este problema es el problema del saco de
mercadería discreto. En este caso las mercaderías no se pueden
llegar en fracciones ni tampoco se repiten.
En este caso la estrategia greedy descrita previamente no conduce
a la solución óptima.
Ejemplo: Supongamos que el saco puede cargar 50 kilos. Tenemos
los siguientes productos: A de 10 kilos vale 6 mil, B de 20 kilos
vale 10 mil, y C de 30 kilos vale 12 mil.
Los valores por unidad de peso son: A=> 0.6 $/k, B=> 0.5 $/k, C
=> 0.4 $/k.
Si el ladrón carga A luego sólo puede cargar B o C. Toma B y
consigue productos por 16 mil. La mejor solución es tomar B y C
por un total de 22 mil.
7
Descargar

Algoritmos Avaros (Greedy Algorithms)