Algoritmos voraces y cuándo funcionan en JavaScript

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:

function book(requests, rule) {
  const taken = [];
  for (const [start, end] of [...requests].sort(rule)) {
    if (taken.every(([s, e]) => end <= s || e <= start)) {
      taken.push([start, end]);
    }
  }
  return taken;
}

function show(rule, taken) {
  const slots = taken.map(([s, e]) => `${s}–${e}`).join(", ");
  console.log(`${rule}: ${slots} (${taken.length})`);
}

show("Por inicio", book(requests, (a, b) => a[0] - b[0]));
show("Por duración", book(requests, (a, b) => (a[1] - a[0]) - (b[1] - b[0])));
show("Por final", book(requests, (a, b) => a[1] - b[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

function maxMeetings(requests) {
  const byEnd = [...requests].sort((a, b) => a[1] - b[1]);
  const taken = [];
  let freeFrom = 0;
  for (const [start, end] of byEnd) {
    if (start >= freeFrom) {
      taken.push([start, end]);
      freeFrom = end;
    }
  }
  return taken;
}

[...requests].sort(...) ordena una copia, y const [start, end] desempaqueta cada par.

const requests = [
  [8, 16], [12, 15], [9, 12], [15, 18],
  [11, 13], [17, 20], [14, 16], [18, 20],
];
const taken = maxMeetings(requests);
for (const [start, end] of taken) console.log(`${start}–${end}`);
console.log(`Reuniones: ${taken.length}`);

9–12
12–15
15–18
18–20
Reuniones: 4

function maxMeetings(requests) {
  const byEnd = [...requests].sort((a, b) => a[1] - b[1]);
  const taken = [];
  let freeFrom = 0;
  for (const [start, end] of byEnd) {
    if (start >= freeFrom) {
      taken.push([start, end]);
      freeFrom = end;
    }
  }
  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.

Array.prototype.sort es estable desde ES2019. Sin función de comparación ordena como texto: [9, 12].sort() da [12, 9].

Pruébalo

Encuentra el error

Un compañero copió el algoritmo voraz y obtuvo solo tres reuniones:

function maxMeetings(requests) {
  const byEnd = [...requests].sort((a, b) => a[1] - b[1]);
  const taken = [];
  let freeFrom = 0;
  for (const [start, end] of byEnd) {
    if (start > freeFrom) {
      taken.push([start, end]);
      freeFrom = end;
    }
  }
  return taken;
}

const requests = [
  [8, 16], [12, 15], [9, 12], [15, 18],
  [11, 13], [17, 20], [14, 16], [18, 20],
];
const taken = maxMeetings(requests);
for (const [start, end] of taken) console.log(`${start}–${end}`);
console.log(`Reuniones: ${taken.length}`);

9–12
14–16
17–20
Reuniones: 3

¿En qué línea está el error?

Elige la línea con el error.

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

function maxMeetings(requests) {
  const byEnd = [...requests].sort((a, b) => a[1] - b[1]);
  const taken = [];
  let freeFrom = 0;
  for (const [start, end] of byEnd) {
    if () {
      taken.push([start, end]);
      freeFrom = end;
    }
  }
  return taken;
}

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.

const COINS = [200, 100, 50, 20, 10, 5, 2, 1];

function change(cents) {
  const given = [];
  for (const coin of COINS) {
    while (cents >= coin) {
      given.push(coin);
      cents -= coin;
    }
  }
  return given;
}

function pay(cents) {
  const given = change(cents);
  console.log(`${cents} céntimos: ${given.join(" ")} (${given.length} 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

const COINS = [200, 100, 50, 20, 10, 5, 2, 1];

function change(cents) {
  const given = [];
  for (const coin of COINS) {
    while (cents >= coin) {
      given.push(coin);
      cents -= coin;
    }
  }
  return given;
}

function pay(cents) {
  const given = change(cents);
  console.log(`${cents} céntimos: ${given.join(" ")} (${given.length} monedas)`);
}

pay(99);

Respuesta

99 céntimos: 50 20 20 5 2 2 (6 monedas)

99 céntimos: 20 20 20 20 10 5 2 2 (8 monedas)

99 céntimos: 50 20 20 5 2 1 1 (7 monedas)

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

El código se ejecuta en tu navegador, en JavaScript. La cantidad de operaciones es la misma en todos los lenguajes, porque el algoritmo es el mismo. El tiempo depende de la máquina, así que solo sirve para comparar. «≈» es una estimación a partir de la curva: un n tan grande no lo ejecutamos, para que la página no se congele.

function maxMeetings(requests) {
  const byEnd = [...requests].sort((a, b) => a[1] - b[1]);
  const taken = [];
  let freeFrom = 0;
  for (const [start, end] of byEnd) {
    if (start >= freeFrom) {
      taken.push([start, end]);
      freeFrom = end;
    }
  }
  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

Ponte a prueba

1. ¿Qué hace que un algoritmo sea «voraz»?En cada paso toma la mejor opción del momento y nunca la reconsideraPrueba todas las posibilidades y se queda con la mejorGuarda una tabla con las respuestas a las tareas más pequeñas

2. ¿Por qué las solicitudes de la sala se ordenan por final y no por inicio?Porque ordenar por inicio no es posiblePorque ordenar por final da reuniones más cortasLa reunión que termina antes deja la mayor parte del día para las demás

3. ¿Se solapan las solicitudes 9–12 y 12–15?Sí: las dos contienen las 12:00No: la primera termina justo cuando empieza la segunda, por eso la comprobación es >=Depende del lenguaje

4. ¿Qué muestra el argumento de intercambio?La primera reunión de cualquier mejor plan se puede cambiar por la opción voraz sin que baje la cantidadQue todo algoritmo voraz es correctoQue lo voraz es más rápido que cualquier subconjunto

5. El cambio en monedas de euro es voraz. ¿Cuándo falla la misma regla?Con monedas de 1, 3 y 4 céntimos: para 6 céntimos lo voraz da 4 + 1 + 1, y lo mínimo es 3 + 3Solo para importes de más de 5 €Nunca: la moneda mayor primero siempre es lo mejor

Algoritmos voraces y cuándo funcionan

Cookies