Cómo funciona un algoritmo voraz

Tomar lo mejor de ahora

Supongamos que hay que dar 870 wones de cambio. El método voraz es sencillo: tomar la moneda más grande que puedas dar en este momento.
Una de 500, tres de 100, una de 50 y dos de 10.
Solo tomaste la moneda más grande cada vez, y terminaste enseguida.

Toca las monedas de la más grande a la más pequeña para tomarlas. (870 wones → 500 · 100 · 100 · 100 · 50 · 10 · 10)

Eso es un algoritmo voraz. No piensa a lo lejos en lo que pasará; simplemente elige lo mejor en este preciso instante.
Como el cálculo es ligero, las decisiones son rápidas.

No mira el conjunto

Lo que de verdad distingue al método voraz es que nunca despliega el mapa completo.
En cada bifurcación, solo da un paso hacia el lado que parece mejor ahora. Como no mira a lo lejos, hay poco que pensar y es rápido.
A cambio, nunca vuelve a mirar una decisión ya tomada.

En cada bifurcación, toca el número mayor para avanzar un paso. No se ve el mapa completo; solo eliges entre los dos que tienes delante.

No mirar el conjunto es a la vez una virtud y un punto débil. La rapidez es la virtud.
Pero como no ve a lo lejos, un camino que ahora parece bueno puede resultar un callejón sin salida más adelante.
Aun así, en algunos problemas este método rápido encaja a la perfección, casi de forma sorprendente.

Cuando funciona bien

Supongamos que quieres meter el mayor número posible de reuniones en una sola sala, sin que los horarios se crucen.
El truco voraz es reservar primero la reunión que termina antes, porque cuanto antes quede libre la sala, más reuniones caben después.
Curiosamente, esta avaricia da la respuesta realmente óptima.

Toca primero las reuniones que terminan antes para reservarlas. Las que se cruzan quedan fuera solas, y el método voraz llena el máximo de 4.

¿Por qué es esta la respuesta correcta? Al elegir la reunión que termina antes, la sala queda libre lo antes posible.
Así queda el mayor tiempo libre, y en él cabe el mayor número de otras reuniones. Por eso, aunque se sea voraz paso a paso, el conjunto acaba siendo el mejor posible.
En problemas como este, el método voraz es la respuesta.

Un contraejemplo en el que falla

Esta vez las monedas son raras: solo hay de 1, 3 y 4, y hay que dar 6 de cambio.
Si vas a lo voraz, de mayor a menor, das una de 4 y luego dos de 1: tres monedas. Pero con dos de 3 bastan dos monedas.
Lo mejor de cada momento se perdió lo mejor del conjunto.

Toca los dos métodos para compararlos: el voraz (4·1·1 → 3 monedas) y el camino mejor (3·3 → 2 monedas). El voraz cayó en la trampa.

El método voraz falló porque, en cuanto tomó la de 4, los 2 que quedaban solo podían cubrirse con dos de 1.
Un gran paso de ahora arruinó lo que venía después. Por eso acierta con monedas corrientes y falla con monedas descompensadas como estas.
Si el método voraz funciona o no hay que comprobarlo problema por problema.

Resumen

En una línea, un algoritmo voraz «elige en cada momento lo que parece mejor ahora». Como no mira el conjunto, es rápido y sencillo.
En algunos problemas, como dar cambio o reservar una sala, es exactamente la respuesta correcta. Pero con monedas raras o caminos enredados, lo mejor de cada momento se convierte en una trampa.
Así que el método voraz es rápido y suele acertar, pero si de verdad acierta hay que comprobarlo en cada problema.

Toca los cuatro puntos clave en orden para resumir: lo mejor ahora → no mira el conjunto → suele acertar → a veces falla.

Si la programación dinámica, que vimos antes, es el método prudente que reúne todas las respuestas pequeñas sin dejarse ninguna, el voraz está en el extremo opuesto: la avaricia más simple, que elige lo bueno de ahora y sigue adelante.
Resulta atractivo por rápido y ligero, pero esa misma sencillez a veces lo hace caer en una trampa.
Cuando ya tengas una idea de cuándo funciona y cuándo no, en la próxima lección veremos otro truco: elegir tirando los dados.