Ir al contenido
wannacode

Cuándo falla un algoritmo voraz

En resumen: Un algoritmo voraz falla cuando la mejor opción de ahora bloquea una respuesta mejor más tarde; un contraejemplo basta, y la solución suele ser la programación dinámica.

Problema

Un vale de más

La tienda paga los puntos de fidelidad como vales de 4, 3 y 1 punto. Cada vale es un código aparte que el cliente teclea en la caja. Así que el programa da el menor número de vales posible: cada vez el mayor que cabe, como el cambio en monedas de euro de la lección anterior.

function greedy(vouchers, points) {
  const used = [];
  for (const v of vouchers) {
    while (points >= v) {
      used.push(v);
      points -= v;
    }
  }
  return used;
}
const vouchers = [4, 3, 1];
console.log("6 puntos: " + "[" + greedy(vouchers, 6).join(", ") + "]");
Salida
6 puntos: [4, 1, 1]

Tres códigos para 6 puntos. Sin embargo 3 + 3 son dos. El programa no tiene ningún error en su código: la regla «el mayor que cabe» simplemente no es cierta para estos vales. Con monedas de euro es cierta, aquí no.

La idea

Lo voraz no vuelve atrás

Un algoritmo voraz toma, en cada paso, la opción que parece mejor ahora mismo, y nunca la reconsidera. Una vez que ha tomado 4, para los 2 puntos restantes solo quedan vales de 1 punto. Que 3 + 3 es mejor, lo voraz no lo ve: no prueba nada más.

Así que una idea voraz solo se acepta con una demostración de que la opción local nunca perjudica. Y se rechaza con una sola entrada en la que da una respuesta peor. Una entrada así se llama contraejemplo. 6 puntos es un contraejemplo para lo voraz con los vales 4, 3 y 1.

El mismo tipo de vales puede ser seguro o inseguro según sus valores. 4, 2 y 1 son seguros: cada mayor es múltiplo del menor. 4, 3 y 1 no lo son.

Míralo

Lo voraz y el DP lado a lado

La solución no es decidir de una vez, sino calcular el menor número de vales para cada importe de 0 a 6. Para p puntos pruebas cada vale v como el último: quedan p − v puntos, y el mínimo para ellos ya está calculado. Esto es programación dinámica para monedas, con una tabla best. last guarda qué vale fue el último, para poder volver hasta los propios vales.

function fewest(vouchers, points) {
  const best = [0];
  const last = [0];
  for (let p = 1; p <= points; p++) {
    best[p] = points + 1;
    last[p] = 0;
    for (const v of vouchers) {
      if (v <= p && best[p - v] + 1 < best[p]) {
        best[p] = best[p - v] + 1;
        last[p] = v;
      }
    }
  }
  const used = [];
  for (let p = points; p > 0; p -= last[p]) {
    used.push(last[p]);
  }
  return used;
}
const vouchers = [4, 3, 1];
console.log("6 puntos: voraz " + "[" + greedy(vouchers, 6).join(", ") + "]" + ", mínimo " + "[" + fewest(vouchers, 6).join(", ") + "]");
console.log("10 puntos: voraz " + "[" + greedy(vouchers, 10).join(", ") + "]" + ", mínimo " + "[" + fewest(vouchers, 10).join(", ") + "]");
Salida
6 puntos: voraz [4, 1, 1], mínimo [3, 3]
10 puntos: voraz [4, 4, 1, 1], mínimo [4, 3, 3]

function fewest(vouchers, points) {
  const best = [0];
  const last = [0];
  for (let p = 1; p <= points; p++) {
    best[p] = points + 1;
    last[p] = 0;
    for (const v of vouchers) {
      if (v <= p && best[p - v] + 1 < best[p]) {
        best[p] = best[p - v] + 1;
        last[p] = v;
      }
    }
  }
  const used = [];
  for (let p = points; p > 0; p -= last[p]) {
    used.push(last[p]);
  }
  return used;
}
Paso a paso, en palabras
  1. Voraz, 6 puntos. El vale mayor que cabe es 4: lo toma. Quedan 2 puntos.
  2. Quedan 2 puntos: 4 y 3 no caben. Toma 1. Quedan 1 punto.
  3. Otro 1. Listo: 4 + 1 + 1, 3 vales. La elección de 4 fue definitiva y cerró el camino a 3 + 3.
  4. El DP calcula el menor número de vales para cada importe de 0 a 6. best[0] = 0: 0 puntos no necesitan ningún vale.
  5. best[1]: 1 → 1 + best[0] = 1. Lo mínimo es 1, último vale 1.
  6. best[2]: 1 → 1 + best[1] = 2. Lo mínimo es 2, último vale 1.
  7. best[3]: 3 → 1 + best[0] = 1; 1 → 1 + best[2] = 3. Lo mínimo es 1, último vale 3.
  8. best[4]: 4 → 1 + best[0] = 1; 3 → 1 + best[1] = 2; 1 → 1 + best[3] = 2. Lo mínimo es 1, último vale 4.
  9. best[5]: 4 → 1 + best[1] = 2; 3 → 1 + best[2] = 3; 1 → 1 + best[4] = 2. Lo mínimo es 2, último vale 4.
  10. best[6]: 4 → 1 + best[2] = 3; 3 → 1 + best[3] = 2; 1 → 1 + best[5] = 3. Lo mínimo es 2, último vale 3.
  11. Hacia atrás por last: 6 → 3 → 0. Los vales son 3 y 3: 2.
  12. El mismo importe, dos respuestas: lo voraz da 3 vales, el DP da 2. Lo voraz nunca vuelve sobre una elección; el DP prueba cada último vale para cada importe.

El DP hace más trabajo: importes × vales, es decir, O(n·k), mientras que lo voraz dura tanto como los vales que toma. Pero el DP es correcto para cualquier vale, y lo voraz solo para algunos.

«Infinito» en best es points + 1: más que cualquier respuesta real, porque con un vale de 1 punto la respuesta es como mucho points. En JavaScript también funciona Infinity: Infinity + 1 sigue siendo Infinity. En Java y C# MAX_VALUE + 1 da la vuelta a un número negativo, así que allí points + 1 es obligatorio, mientras que aquí es una elección.

Pruébalo

Predice

Los mismos vales, 10 puntos. ¿Qué da lo voraz?

function greedy(vouchers, points) {
  const used = [];
  for (const v of vouchers) {
    while (points >= v) {
      used.push(v);
      points -= v;
    }
  }
  return used;
}


const vouchers = [4, 3, 1];
console.log("[" + greedy(vouchers, 10).join(", ") + "]");
Respuesta

Pruébalo

Completa

Para p puntos con v como último vale: ¿de qué importe sale el resto?

function fewest(vouchers, points) {
  const best = [0];
  const last = [0];
  for (let p = 1; p <= points; p++) {
    best[p] = points + 1;
    last[p] = 0;
    for (const v of vouchers) {
      if (v <= p && best[p - v] + 1 < best[p]) {
        best[p] = best[] + 1;
        last[p] = v;
      }
    }
  }
  const used = [];
  for (let p = points; p > 0; p -= last[p]) {
    used.push(last[p]);
  }
  return used;
}

Míralo

La mochila por tarifa por kilogramo

El mensajero tiene sitio para 10 kg. Esperan tres paquetes: uno de 6 kg con una tarifa de 30 €, y dos de 5 kg con una tarifa de 20 € cada uno. La idea voraz: ordenar los paquetes por tarifa por kilogramo y tomarlos mientras quepan.

function byRatio(parcels, capacity) {
  const sorted = [...parcels].sort((a, b) => b[1] / b[0] - a[1] / a[0]);
  let total = 0;
  for (const [kg, fee] of sorted) {
    if (kg <= capacity) {
      capacity -= kg;
      total += fee;
    }
  }
  return total;
}


function bestFee(parcels, i, capacity) {
  if (i === parcels.length) {
    return 0;
  }
  const skip = bestFee(parcels, i + 1, capacity);
  const [kg, fee] = parcels[i];
  if (kg > capacity) {
    return skip;
  }
  const take = fee + bestFee(parcels, i + 1, capacity - kg);
  return Math.max(skip, take);
}
const parcels = [[6, 30], [5, 20], [5, 20]];
console.log(`Por tarifa por kilogramo: ${byRatio(parcels, 10)} €`);
console.log(`Lo mejor: ${bestFee(parcels, 0, 10)} €`);
Salida
Por tarifa por kilogramo: 30 €
Lo mejor: 40 €

El paquete de 6 kg son 5 € por kg, los otros 4 € por kg. Lo voraz lo toma primero, y los 4 kg restantes no bastan para nada. Los dos paquetes de 5 kg llenan la furgoneta justo y dan 40 €. bestFee prueba cada subconjunto: para cada paquete «tomar» u «omitir». Eso es 2ⁿ, y para un número real de paquetes hace falta DP para la mochila.

b[1] / b[0] en JavaScript siempre da un número con fracción. En Java y C# dividir dos enteros es una división entera, y allí hace falta (double).
Más precisamente, para curiosos

Si los paquetes se pueden dividir, lo voraz por tarifa por kilogramo es correcto. Así funciona con la mercancía a granel: granos de café, harina, combustible. Tomas todo lo que cabe del más caro por kilogramo, luego del siguiente, y cortas el último. Esta es la mochila fraccionaria, y allí ninguna opción local cierra un camino mejor.

Un paquete entero no se puede cortar. Justo eso hace peligroso lo voraz: los 6 kg ocupan un sitio que los dos paquetes de 5 kg aprovecharían mejor.

La idea

Cómo probar una idea voraz

Una idea voraz suena correcta casi siempre. ¿Cómo averiguas si lo es? Buscas un contraejemplo, no a mano, sino con un programa:

  1. Escribe una solución lenta pero seguramente correcta: una fuerza bruta que pruebe todas las posibilidades.
  2. Ejecuta lo voraz y la fuerza bruta con todas las entradas pequeñas: cada importe de 1 a 100.
  3. El primer sitio donde discrepan es un contraejemplo. Si coinciden en todas partes, no has demostrado nada, pero tienes un motivo para buscar una demostración.

La fuerza bruta de aquí prueba cuántas de cada moneda tomar: de 0 a tantas como quepan, de forma recursiva para la siguiente. La última moneda es 1, y cubre lo que quede.

function tryAll(coins, i, amount) {
  if (i === coins.length - 1) {
    return amount;
  }
  let best = Infinity;
  for (let k = 0; k * coins[i] <= amount; k++) {
    const rest = tryAll(coins, i + 1, amount - k * coins[i]);
    best = Math.min(best, k + rest);
  }
  return best;
}


function check(name, coins, upTo) {
  for (let a = 1; a <= upTo; a++) {
    const g = greedy(coins, a).length;
    const b = tryAll(coins, 0, a);
    if (g !== b) {
      console.log(`${name}: ${a} → voraz ${g}, mínimo ${b}`);
      return;
    }
  }
  console.log(`${name}: hasta ${upTo} no hay contraejemplo`);
}
check("Vales 4, 3, 1", [4, 3, 1], 20);
check("Monedas de euro", [200, 100, 50, 20, 10, 5, 2, 1], 100);
check("Antiguas británicas", [30, 24, 12, 6, 3, 1], 100);
Salida
Vales 4, 3, 1: 6 → voraz 3, mínimo 2
Monedas de euro: hasta 100 no hay contraejemplo
Antiguas británicas: 48 → voraz 3, mínimo 2

Tres sistemas en un segundo:

  • los vales 4, 3 y 1 fallan en 6;
  • las monedas de euro en céntimos (1, 2, 5, 10, 20, 50 céntimos, 1 € y 2 €) no fallan hasta 100 céntimos;
  • las antiguas monedas británicas en peniques (1, 3, 6, 12, 24 y 30, parte del sistema anterior a 1971) fallan en 48: lo voraz da 30 + 12 + 6, mientras que 24 + 24 son dos.

La fuerza bruta es exponencial, y con entradas grandes no sirve. Pero los contraejemplos casi siempre son pequeños, y recorre las entradas pequeñas en un instante.

Pruébalo

Encuentra el error

Un compañero ejecutó la comprobación de los vales y anunció que lo voraz es correcto. Tú sabes que 6 es un contraejemplo. ¿Dónde está el error?

check("Vales 4, 3, 1", [4, 3, 1], 5);
check("Monedas de euro", [200, 100, 50, 20, 10, 5, 2, 1], 100);
check("Antiguas británicas", [30, 24, 12, 6, 3, 1], 100);
Salida
Vales 4, 3, 1: hasta 5 no hay contraejemplo
Monedas de euro: hasta 100 no hay contraejemplo
Antiguas británicas: 48 → voraz 3, mínimo 2

Elige la línea con el error.

Más precisamente, para curiosos

Hasta dónde comprobar. Para monedas y vales hay una respuesta exacta (Kozen y Zaks, 1994): si lo voraz falla en algún sitio, el contraejemplo más pequeño es menor que la suma de los dos valores mayores. Así que una comprobación completa hasta ahí es una demostración:

  • los vales 4, 3 y 1: hasta 7;
  • las monedas de euro: hasta 300 céntimos (2 € + 1 €). Ejecuta hasta 300, la comprobación no encuentra ningún contraejemplo, así que lo voraz es correcto para las monedas de euro con cualquier importe;
  • las antiguas monedas británicas: hasta 54 (30 + 24), y 48 está por debajo de ese límite.
Monedas de euro hasta 300 céntimos
Monedas de euro: hasta 300 no hay contraejemplo

Hasta 300 la fuerza bruta hace unas 26 millones de llamadas y aun así termina en segundos. Para un rango mayor la mejor comprobación es el DP en lugar de la fuerza bruta: es igual de seguramente correcto, y es O(importe × monedas).

Para otros problemas normalmente no existe un límite así. Entonces comprobar entradas pequeñas no demuestra, solo busca. La demostración es un argumento: casi siempre, que cualquier solución óptima se puede transformar paso a paso en la voraz sin empeorar.

Ejercicio

Los vales nuevos de marketing

Resuelve la tarea en tu editor.

Los vales nuevos. Marketing quiere vales de 9, 6, 5 y 1 punto y pregunta si la caja puede seguir siendo voraz. Usa la comprobación de la lección (greedy, la fuerza bruta y check) para importes hasta 30 puntos y encuentra el contraejemplo más pequeño.

Salida
Vales 9, 6, 5, 1: 11 → voraz 3, mínimo 2

Más tareas

  • Arreglar el sistema. ¿Qué vale añades a 4, 3 y 1 para que lo voraz sea correcto hasta 7? Pruébalo con la comprobación.
  • La mochila con comprobación. Escribe una comprobación para la mochila: lo voraz por tarifa por kilogramo contra bestFee para todas las combinaciones de tres paquetes con pesos de 1 a 6 kg y tarifas de 1 € a 9 €. ¿Cuántos contraejemplos encuentra?
  • Plazos. Las tareas tienen una duración y un plazo. ¿Cumple lo voraz «la más corta primero» la mayoría de plazos? Encuentra un contraejemplo probando cada orden de 4 tareas.

Test

Ponte a prueba

1. Los vales son de 4, 3 y 1 punto. ¿Cuántos vales da lo voraz para 6 puntos, y cuál es el mínimo?
2. Una idea voraz pasó 50 pruebas. ¿Qué demuestra eso?
3. El mensajero tiene sitio para 10 kg. Paquetes: 6 kg por 30 €, 5 kg por 20 € y 5 kg por 20 €. ¿Qué toma lo voraz por tarifa por kilogramo?
4. ¿Por qué «infinito» en el DP de los vales es points + 1 y no Integer.MAX_VALUE en Java?
5. La comprobación busca un contraejemplo para los vales 4, 3 y 1 solo hasta 5 puntos y no encuentra ninguno. ¿Por qué?

Creado por Ivo Gergov como parte de la campaña de Evo Tech por una educación accesible en programación ·