Algoritmos Ávidos - Algoritmos y Programación II

Los algoritmos ávidos o greedy en inglés, son algoritmos diseñados generalmente para resolver problemas de optimización. Los algoritmos que resuelven este tipo de problemas generalmente lo hacen en etapas, realizando, a cada paso, algunos cálculos hasta llegar al resultado buscado. Un algoritmo ávido o codicioso siempre hace la elección que parece mejor en el momento. Es decir, hace una elección localmente óptima con la esperanza de que esta elección conduzca a una solución globalmente óptima. En otras palabras con los datos que está procesando en ese momento, toma la mejor decisión posible.

La estrategia ávida no siempre funciona, depende de la naturaleza del problema y de los datos, por lo que hay que analizar bien el problema antes de seguir esta estrategia.

La principal ventaja de este tipo de algoritmos es que es muy fácil de implementar y entender.

Por ejemplo veamos a continuación un problema clásico:

Cambio de moneda

Un cajero automático tiene que ser capaz de entregar la cantidad de pesos que se le requiere utilizando la menor cantidad de billetes y monedas.

Por ejemplo, en Argentina, a mayo de 2024 se emplean monedas de $1, $2, $5 y $10, y billetes de $10, $20, $50, $100, $200, $500, $1.000, $2.000 y $10.000. Si el cajero tiene que entregar $5.528

La solución será:

2 \times 2000 + 1 \times 1000 + 1 \times 500 + 1 \times 20 + 1 \times 5 + 1 \times 2 +1 \times 1

(1)

En total se entregan 8 piezas.

1
2
3
4
5
6
7
PARA CADA denominacion EN billetes HACER
    SI cantidad >= denominacion ENTONCES
        cantidad_billetes ← cantidad / denominacion
        cambio[denominacion] ← cantidad_billetes
        cantidad ← cantidad MOD denominacion
    FIN SI
FIN PARA

A partir de este fragmento nos podemos preguntar:

¿Siempre puede entregar el cambio solicitado?
¿Siempre entrega la menor cantidad de billetes?

Para que siempre pueda entregar el monto solicitado, es preciso contar con la moneda de $1, para asegurarnos que podrá entregar cualquier monto.

Para asegurar que siempre da la menor cantidad de billetes, el sistema de denominaciones debe ser canónico. Es decir las denominaciones no pueden ser cualquiera, sino que deben ser un conjunto que asegure que siempre funciona el algoritmo ávido. Además deben estar ordenadas de mayor a menor.

Por ejemplo si las denominaciones fueran: $1, $2, $5, $10, $20, $50, $100, $200, $500, $800 y $1.000 y tiene que dar $2.400, nuestro algoritmo ávido daría 2 x $1.000 + 2 x $200 en lugar de dar 3 billetes de $800.

La verificación formal de que un algoritmo ávido es correcto es un tema complejo y no siempre se puede hacer. En general se hace por inducción, es decir se prueba que la elección localmente óptima lleva a una solución globalmente óptima. Se puede hacer utilizando técnicas de programación dinámica.

A continuación otro ejemplo de algoritmo ávido muy popular en la literatura:

Plan de actividades

Se tiene un conjunto de actividades que se pueden realizar en un tiempo determinado. Cada actividad $a_i$ tiene un tiempo de inicio $s_i$ y un tiempo de finalización $f_i$ . Se desea seleccionar la mayor cantidad de actividades que no se superpongan.

Dos actividades $a_i$ y $a_j$ son compatibles si los intervalos $[s_i, f_i)$ y $[s_j, f_j)$ no se superponen. Es decir:

f_i \leq s_j

(2)

f_j \leq s_i

(3)

Supongamos que tenemos las siguientes actividades, ordenadas por tiempo de finalización:

A continuación el diagrama de actividades. En principio no hay ninguna actividad seleccionada.

Paso 1: Se selecciona la tarea que termina primero de entre todas las tareas a planificar. En este caso la tarea 1. Inmediatamente las tareas 2, 3, 5, 10 se marcan como incompatibles, ya que se superponen con la tarea 1.

Paso 2: De entre las tareas disponibles (4, 6, 7, 8, 9 y 11) se selecciona la tarea 4, que es la que finaliza primero, por lo tanto las tareas 6 y 7 dejan de ser compatibles con la planificación.

Paso 3: Se selecciona la tarea 8, ya que es la que finaliza primero entre las tareas disponibles (8, 9 y 11). La tarea 9 se vuelve incompatible.

Paso 4: Por último se selecciona la única tarea disponible, la 11.

El algoritmo ávido para este problema es el siguiente:

1
2
3
4
5
6
7
8
9
actividades_seleccionadas ← []
actividad_actual ← actividades[0]
actividades_seleccionadas ← actividades_seleccionadas + [actividad_actual]
PARA CADA actividad EN actividades HACER
    SI actividad_inicio >= actividad_actual_fin ENTONCES
        actividades_seleccionadas ← actividades_seleccionadas + [actividad]
        actividad_actual ← actividad
    FIN SI
FIN PARA

1Ejercicios¶

Los ejercicios de este capítulo están en el directorio 03-algoritmos-avidos/ejercicios/ del repositorio taller-algoritmos. Cada ejercicio tiene un esqueleto con // TODO y su correspondiente batería de tests. Para resolverlos, clonar el repositorio, completar las funciones y ejecutar go test ./....