Algoritmos greedy
Toma la mejor opción local, nunca voltees atrás.
Funciona solo con el criterio CORRECTO — que necesita una demostración.
Interval scheduling: ¿cuál greedy?
- Meter la mayor cantidad de actividades sin traslape en un salón
- ¿INICIO más temprano? ¿FIN más temprano? ¿La MÁS CORTA? Todas suenan lógicas.
- Solo el FIN más temprano es óptimo
- Terminar temprano deja el mayor espacio para lo que sigue
Mira el barrido de fin más temprano
Ordenadas por hora de fin; línea punteada = fin de la última tomada (salón libre a su derecha).
Se toma si empieza después de la línea; se salta si se traslapa. → 4 actividades, el máximo.
El criterio lo es todo
Fin más temprano: óptimo. Inicio más temprano: ~40% peor. Más corta: 13.0 vs 13.1 — se ve correcta, no lo es.
Demuéstralo, no lo midas con benchmarks
- Corrección = peor caso sobre TODAS las entradas; un contraejemplo la mata
- La más corta primero falla con [0,10),[9,11),[10,20): elige 1 donde el óptimo elige 2
- Argumento de intercambio: cambia la elección del óptimo por la del greedy, sin empeorar
- Edmonds: greedy es óptimo exactamente sobre matroides
Para llevar
El más simple de escribir, el más fácil de equivocar sutilmente.
Un greedy que casi siempre acierta sigue siendo un bug.
Sigue: programación dinámica — para los casos de subproblemas traslapados que greedy ni toca.