Algoritmos voraces y cuándo funcionan
En resumen: Un algoritmo voraz toma en cada paso la mejor opción del momento y nunca da marcha atrás; da la respuesta óptima solo en los problemas en los que esa opción es segura, lo que necesita una demostración como el argumento de intercambio.
Problema
La sala de reuniones
El espacio de coworking tiene una sala de reuniones. Para mañana han llegado ocho solicitudes, cada una con una hora de inicio y una de final. Dos reuniones que se solapan no pueden estar a la vez en la sala. Quieres aceptar a tantos equipos como sea posible: cada equipo que rechazas se va a la competencia.
Las primeras ideas son reglas sencillas: la solicitud más temprana primero, o la más corta primero (las cortas ocupan menos tiempo). Ordenas según la regla y aceptas cada solicitud que no se solape con las ya aceptadas:
static List<int[]> Book(int[][] requests, Func<int[], int> rule){ var taken = new List<int[]>(); foreach (var r in requests.OrderBy(rule)) { bool free = taken.All(t => r[1] <= t[0] || t[1] <= r[0]); if (free) taken.Add(r); } return taken;}
static void Show(string rule, List<int[]> taken){ var slots = string.Join(", ", taken.Select(t => $"{t[0]}–{t[1]}")); Console.WriteLine($"{rule}: {slots} ({taken.Count})");}Show("Por inicio", Book(requests, r => r[0]));Show("Por duración", Book(requests, r => r[1] - r[0]));Show("Por final", Book(requests, r => r[1]));Por inicio: 8–16, 17–20 (2)Por duración: 11–13, 14–16, 18–20 (3)Por final: 9–12, 12–15, 15–18, 18–20 (4)Por inicio da 2 reuniones, por duración 3, y por final 4. ¿Es 4 lo máximo? Prueba los 2⁸ = 256 subconjuntos: sí, 5 no caben. Pero ¿por qué justo la regla «por final», y cómo puedes estar seguro sin probarlo todo?
La idea
Un algoritmo voraz
Un algoritmo voraz (greedy) toma la opción que parece mejor ahora y nunca vuelve a reconsiderarla. No hay una tabla como en la programación dinámica ni se prueban todas las posibilidades: normalmente un ordenamiento y una pasada.
Para la sala, lo voraz es: ordenar las solicitudes por final y aceptar cada una que empiece no antes del momento en que la sala queda libre. Una variable, freeFrom, guarda ese momento, para no tener que comparar con cada reunión ya aceptada.
Las tres reglas del problema son todas voraces. La diferencia es qué cuentan como «mejor ahora», y solo una de ellas es correcta. Lo voraz es rápido y sencillo, pero viene sin garantía: toda regla voraz necesita un argumento de que la opción del momento no estropea el futuro.
Míralo
Voraz por final
static List<int[]> MaxMeetings(int[][] requests){ var taken = new List<int[]>(); int freeFrom = 0; foreach (var r in requests.OrderBy(r => r[1])) { if (r[0] >= freeFrom) { taken.Add(r); freeFrom = r[1]; } } return taken;}OrderBy(r => r[1]) da las solicitudes por final sin tocar el arreglo requests.int[][] requests =[ [8, 16], [12, 15], [9, 12], [15, 18], [11, 13], [17, 20], [14, 16], [18, 20],];var taken = MaxMeetings(requests);foreach (var t in taken) Console.WriteLine($"{t[0]}–{t[1]}");Console.WriteLine($"Reuniones: {taken.Count}");9–1212–1515–1818–20Reuniones: 4static List<int[]> MaxMeetings(int[][] requests){ var taken = new List<int[]>(); int freeFrom = 0; foreach (var r in requests.OrderBy(r => r[1])) { if (r[0] >= freeFrom) { taken.Add(r); freeFrom = r[1]; } } return taken;}Paso a paso, en palabras
- Ocho solicitudes para una sala, en el orden en que llegaron. Ordénalas por final: primero va la que termina antes.
- La línea naranja marca desde cuándo está libre la sala. Al principio nada está reservado: libre desde 0.
- La solicitud 1 (9–12) empieza a las 9, la sala está libre desde las 0: acéptala. Ahora la sala está ocupada hasta las 12.
- La solicitud 2 (11–13) empieza a las 11, antes de las 12: se solapa con una reunión ya aceptada, recházala.
- La solicitud 3 (12–15) empieza a las 12, la sala está libre desde las 12: acéptala. Ahora la sala está ocupada hasta las 15.
- La solicitud 4 (8–16) empieza a las 8, antes de las 15: se solapa con una reunión ya aceptada, recházala.
- La solicitud 5 (14–16) empieza a las 14, antes de las 15: se solapa con una reunión ya aceptada, recházala.
- La solicitud 6 (15–18) empieza a las 15, la sala está libre desde las 15: acéptala. Ahora la sala está ocupada hasta las 18.
- La solicitud 7 (17–20) empieza a las 17, antes de las 18: se solapa con una reunión ya aceptada, recházala.
- La solicitud 8 (18–20) empieza a las 18, la sala está libre desde las 18: acéptala. Ahora la sala está ocupada hasta las 20.
- 4 reuniones: 9–12, 12–15, 15–18, 18–20. Cada una aceptada termina antes que las demás, así que deja la mayor parte del día para las otras.
Cada reunión aceptada deja la sala libre lo antes posible. Las rechazadas no son una pérdida: cada una se solapa con una reunión que termina no más tarde que ella.
Más precisamente, para curiosos
Si dos solicitudes terminan a la misma hora, el orden entre ellas no cambia la cantidad: una vez aceptada la primera, la segunda empieza antes de su final. El ordenamiento incorporado es estable en los cuatro lenguajes (los elementos iguales se quedan en el orden en que llegaron), así que la salida es la misma en todos.
OrderBy es estable. Array.Sort y List.Sort no: con finales iguales puedes obtener el otro orden.Pruébalo
Encuentra el error
Un compañero copió el algoritmo voraz y obtuvo solo tres reuniones:
static List<int[]> MaxMeetings(int[][] requests){ var taken = new List<int[]>(); int freeFrom = 0; foreach (var r in requests.OrderBy(r => r[1])) { if (r[0] > freeFrom) { taken.Add(r); freeFrom = r[1]; } } return taken;}int[][] requests =[ [8, 16], [12, 15], [9, 12], [15, 18], [11, 13], [17, 20], [14, 16], [18, 20],];var taken = MaxMeetings(requests);foreach (var t in taken) Console.WriteLine($"{t[0]}–{t[1]}");Console.WriteLine($"Reuniones: {taken.Count}");9–1214–1617–20Reuniones: 3¿En qué línea está el error?
Elige la línea con el error.
La reunión de 9–12 libera la sala a las 12, y 12–15 puede empezar justo entonces. Con el > estricto se rechazan las reuniones seguidas. Lo correcto es if (r[0] >= freeFrom).
La idea
Por qué por final es lo correcto: el argumento de intercambio
Toma cualquier mejor plan, por ejemplo uno con 4 reuniones. Ordena sus reuniones por hora. Lo voraz toma primero la solicitud que termina antes de todas, digamos 9–12.
- La primera reunión del mejor plan no termina antes de las 12, porque las 12 son el final más temprano de todos.
- Cámbiala por 9–12. Las otras reuniones del plan empiezan después del final de la antigua primera, o sea después de las 12 también: nada se solapa, y la cantidad es la misma.
- Ahora los dos planes empiezan igual. Quita 9–12 y las solicitudes que se solapan con ella, y repite lo mismo con el resto.
Paso a paso conviertes el mejor plan en el voraz sin perder ni una reunión. Así que lo voraz es al menos tan bueno como el mejor: es el mejor.
El mismo argumento falla con las otras dos reglas. Por inicio, 8–16 va primero: ponla en el lugar de la primera reunión y cierra la sala hasta las 16, y las otras reuniones ya no caben.
Más precisamente, para curiosos
Formalmente el argumento es una inducción sobre el número de reuniones aceptadas: tras k pasos existe un mejor plan que empieza con las primeras k opciones voraces. Esta es la forma habitual de demostrar un algoritmo voraz: «la opción voraz es segura» (hay una mejor solución que la contiene) más «subestructura óptima» (el resto es la misma tarea, solo que más pequeña). La segunda propiedad la comparte con la programación dinámica. La primera es la que falta cuando lo voraz falla.
Pruébalo
Completa la condición
static List<int[]> MaxMeetings(int[][] requests)
{
var taken = new List<int[]>();
int freeFrom = 0;
foreach (var r in requests.OrderBy(r => r[1]))
{
if ()
{
taken.Add(r);
freeFrom = r[1];
}
}
return taken;
}Una solicitud se acepta si empieza no antes del momento en que la sala queda libre: r[0] >= freeFrom.
La idea
Un segundo ejemplo: el cambio en euros
La caja de la tienda da el cambio con el menor número posible de monedas. Las monedas de euro son 2 €, 1 €, 50, 20, 10, 5, 2 y 1 céntimo. Voraz: da la moneda mayor que aún quepa en lo que queda.
static List<int> Change(int cents){ int[] coins = [200, 100, 50, 20, 10, 5, 2, 1]; var given = new List<int>(); foreach (int coin in coins) { while (cents >= coin) { given.Add(coin); cents -= coin; } } return given;}
static void Pay(int cents){ var given = Change(cents); Console.WriteLine($"{cents} céntimos: {string.Join(" ", given)} ({given.Count} monedas)");}Pay(485);485 céntimos: 200 200 50 20 10 5 (6 monedas)Con las monedas de euro esto da el menor número de monedas para cada importe: está comprobado con la tabla de cambio para cada importe hasta 5 €. Las monedas se eligieron así a propósito.
Pero la regla «la mayor primero» no es correcta para cualquier moneda. Con monedas de 1, 3 y 4 céntimos, para 6 céntimos lo voraz da 4 + 1 + 1, tres monedas, y bastan dos: 3 + 3. No hay una señal que se vea de un vistazo: incluso con monedas que son cada una al menos el doble de la siguiente, lo voraz puede fallar. Con 1, 4 y 9 céntimos, para 12 céntimos da 9 + 1 + 1 + 1, y bastan 4 + 4 + 4. Cómo buscar esos casos está en la siguiente lección.
Pruébalo
Predice la salida
static List<int> Change(int cents){ int[] coins = [200, 100, 50, 20, 10, 5, 2, 1]; var given = new List<int>(); foreach (int coin in coins) { while (cents >= coin) { given.Add(coin); cents -= coin; } } return given;}
static void Pay(int cents){ var given = Change(cents); Console.WriteLine($"{cents} céntimos: {string.Join(" ", given)} ({given.Count} monedas)");}
Pay(99);La idea
Un tercer ejemplo: Kruskal
Un proveedor de internet conecta barrios con cable de fibra. Cada cable tendido tiene un precio, y el objetivo es que todos los barrios estén conectados por el menor dinero posible. Eso es el árbol de expansión mínima, y Kruskal lo construye de forma voraz: ordena los cables posibles por precio y toma cada vez el siguiente más barato, salvo que cierre un ciclo (los dos barrios ya están conectados). Quién está conectado con quién lo guarda union-find.
Aquí también el argumento es un intercambio: si el mejor árbol no contiene el cable más barato entre dos grupos, mételo y quita el cable más caro del ciclo que se cierra. El precio no sube.
Más precisamente, para curiosos
Otros algoritmos conocidos también son voraces. Dijkstra toma siempre el vértice más cercano aún no procesado y nunca lo reconsidera, y eso es correcto porque los caminos no tienen longitudes negativas. La codificación de Huffman (detrás de ZIP y JPEG) fusiona siempre los dos símbolos más raros. Tienen una cosa en común: cada uno tiene una demostración de que la opción del momento es segura.
Míralo
Cuánto cuesta
Lo voraz es un ordenamiento, O(n log n), y una pasada, O(n). Probar cada subconjunto es O(2ⁿ): con 20 solicitudes son más de un millón de subconjuntos, con 60 no termina nunca. Aquí Bench ordena con el ordenamiento por mezcla y cuenta sus comparaciones. El ordenamiento incorporado de tu lenguaje hace un número algo distinto, pero crece igual.
- Cada subconjunto
O(2ⁿ) - Voraz por el final
O(n log n)
| Algoritmo | n = 10 | n = 20 | n = 1000 | n = 100.000 | n = 1.000.000 |
|---|---|---|---|---|---|
| Cada subconjunto | 1024 | 1.048.576 | ≈ 10³⁰¹ | ≈ 10³⁰¹⁰² | ≈ 10³⁰¹⁰²⁹ |
| Voraz por el final | 33 | 85 | 9691 | 1.636.658 | ≈ 19.639.896 |
static List<int[]> MaxMeetings(int[][] requests){ var taken = new List<int[]>(); int freeFrom = 0; foreach (var r in requests.OrderBy(r => r[1])) { if (r[0] >= freeFrom) { taken.Add(r); freeFrom = r[1]; } } return taken;}Ejercicio
El mensajero
Resuelve la tarea en tu editor.
El mensajero. Un mensajero reparte paquetes en un parque empresarial. Cada cliente ha dicho en qué ventana está en la dirección: 9–11, 10–12, 11–14, 13–15, 14–17, 16–18 y 17–19. En cada pasada el mensajero deja los paquetes de todos los que están en la dirección en ese momento. ¿Cuántas pasadas hacen falta como mínimo, y a qué horas? Escribe el algoritmo voraz e imprime:
Pasadas en: 11, 15, 18 (3)Pista: ordena las ventanas por final. La primera pasada es al final de la ventana que termina antes: más tarde pierdes a ese cliente, y antes no atiendes a más. Luego omite todas las ventanas que ya contienen esa hora.
Más tareas
- El argumento. Escribe el argumento de intercambio para el mensajero: ¿por qué la primera pasada al final de la ventana más temprana no es peor que la primera pasada de la mejor solución?
- Una segunda sala. Si el espacio de coworking tiene dos salas, ¿funciona «por final» si das cada solicitud a la sala que quedó libre más tarde, pero a tiempo?
- Precios. Si las solicitudes pagan importes distintos y quieres el mayor dinero, no el mayor número de reuniones, lo voraz por final ya no es correcto. Encuentra tres solicitudes donde no lo es, y resuelve la tarea con la receta de la programación dinámica.
Test