Algoritmos golosos y cuándo fallan
Elegir lo mejor en cada paso y no volver atrás es la estrategia más barata que existe. También es la más fácil de aplicar donde no corresponde: casi nunca es obvio si la decisión local es la correcta.
Para este tema conviene tener claro:Complejidad algorítmica, visualmente
Dar el vuelto con la menor cantidad de monedas posible: uno agarra siempre la moneda más grande que entra y listo. Con las monedas argentinas funciona. Con un sistema de monedas de 1, 3 y 4, dar 6 con esa regla da tres monedas —4, 1, 1— cuando dos alcanzaban: 3 y 3. El algoritmo no cambió; cambió el problema.
Elegir lo mejor de ahora y no volver atrás
Un algoritmo goloso construye la solución paso a paso, y en cada paso toma la opción que se ve mejor en ese momento según un criterio fijo. Nunca reconsidera: lo elegido queda.
Eso lo hace rapidísimo —en general ordenar más una pasada— y muy fácil de escribir. El trabajo no está en el código sino en justificar por qué esa secuencia de decisiones locales termina en el óptimo global.
Antes de seguir, predecí
Las dos propiedades que lo hacen correcto
Hacen falta dos propiedades. La subestructura óptima: después de tomar la decisión, lo que queda es una instancia más chica del mismo problema, y su solución óptima completa la global.
Y la propiedad de elección golosa: existe una solución óptima que empieza con la opción que elige el criterio. Sin esta segunda, se puede tener subestructura óptima y aun así fallar; es justo lo que separa lo goloso de la programación dinámica, que prueba todas las primeras decisiones en vez de apostar a una.
Cómo se demuestra que un goloso es óptimo
La demostración típica es el argumento de intercambio. Se toma una solución óptima cualquiera y, si no arranca con la elección golosa, se muestra que se puede reemplazar su primera decisión por la golosa sin empeorarla.
Repitiendo el argumento, la solución golosa es tan buena como la óptima. Es más corto de lo que parece y es la única forma de estar seguro: probar con ejemplos no distingue un goloso correcto de uno que falla en el caso 300.
Dónde funciona y funciona muy bien
Donde funciona, funciona muy bien. Selección de actividades: para agendar la mayor cantidad de tareas que no se solapen, ordenar por hora de finalización y tomar la primera compatible da el óptimo. Ordenar por duración o por hora de inicio, no.
Huffman arma el código de menor longitud promedio fusionando siempre los dos símbolos menos frecuentes. Kruskal y Prim construyen el árbol generador mínimo tomando aristas por peso creciente. Y Dijkstra es goloso: fija la distancia del vértice pendiente más cercano y no la revisa más.
La mochila, el contraejemplo canónico
El contraejemplo canónico es la mochila. En la versión fraccionaria —se puede cortar el objeto— ordenar por valor sobre peso y llenar es óptimo. En la versión 0/1 —cada objeto entra entero o no entra—, el mismo criterio falla: llenar con el de mejor proporción puede dejar un hueco inutilizable que una combinación peor en proporción aprovechaba.
El detalle que rompe la propiedad de elección golosa es la indivisibilidad. Ese caso se resuelve con programación dinámica, y el mismo Dijkstra deja de valer si hay aristas de peso negativo: un camino más largo puede abaratarse después.
Un orden de trabajo para no perder tiempo
En la práctica conviene un orden de trabajo: proponer el criterio, intentar el argumento de intercambio y, si no sale, buscar un contraejemplo chico. Los contraejemplos casi siempre aparecen con tres o cuatro elementos.
Y si el problema es NP-difícil, un goloso puede seguir siendo la respuesta correcta, sólo que como aproximación con garantía —“nunca peor que el doble del óptimo”— en vez de como solución exacta.
Cuándo lo goloso es óptimo
| Problema | ¿Goloso es óptimo? | Por qué |
|---|---|---|
| Cambio con monedas argentinas | sí | el sistema es canónico: tomar la mayor nunca se arrepiente |
| Cambio con monedas de 1, 3 y 4 | no | para 6, goloso da 4+1+1 y el óptimo es 3+3 |
| Árbol generador mínimo | sí | propiedad del corte, demostrada |
| Selección de actividades por fin más temprano | sí | argumento de intercambio |
| Mochila fraccionaria | sí | se puede partir el objeto |
| Mochila 0/1 | no | no se puede partir: hay que probar combinaciones |
Más a fondo · formalMatroides: cuándo lo goloso es óptimo, en general
Hay una caracterización completa, y es de las cosas más lindas del área. Un matroide es un conjunto con una familia de subconjuntos «independientes» que cumple dos propiedades: todo subconjunto de un independiente es independiente, y si un independiente es más chico que otro, se le puede agregar un elemento del grande manteniéndolo independiente.
El teorema dice que el algoritmo goloso —ordenar por peso y agregar lo que mantenga la independencia— encuentra el óptimo si y sólo si la estructura del problema es un matroide.
Kruskal es el caso más conocido: los conjuntos de aristas sin ciclos forman un matroide gráfico, y por eso el goloso funciona. Y explica también el otro lado: en la mochila 0/1, los conjuntos de objetos que entran en la capacidad no forman un matroide, porque la segunda propiedad falla, y por eso ningún goloso puede ser óptimo ahí.
Cierre
Lo goloso decide una vez y sigue. Es la técnica más barata cuando vale, y la que más silencio hace cuando no: devuelve una solución plausible, apenas peor que la óptima, sin ningún aviso. Por eso la demostración no es un trámite académico, es la única verificación real.
Autoevaluación
¿Lo entendiste?
Práctica