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.
def greedy(vouchers, points): used = [] for v in vouchers: while points >= v: used.append(v) points -= v return usedvouchers = [4, 3, 1]print("6 puntos: " + str(greedy(vouchers, 6)))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.
def fewest(vouchers, points): best = [0] + [points + 1] * points last = [0] * (points + 1) for p in range(1, points + 1): for v in vouchers: if v <= p and best[p - v] + 1 < best[p]: best[p] = best[p - v] + 1 last[p] = v used = [] p = points while p > 0: used.append(last[p]) p -= last[p] return usedvouchers = [4, 3, 1]print(f"6 puntos: voraz {greedy(vouchers, 6)}, mínimo {fewest(vouchers, 6)}")print(f"10 puntos: voraz {greedy(vouchers, 10)}, mínimo {fewest(vouchers, 10)}")6 puntos: voraz [4, 1, 1], mínimo [3, 3]10 puntos: voraz [4, 4, 1, 1], mínimo [4, 3, 3]def fewest(vouchers, points): best = [0] + [points + 1] * points last = [0] * (points + 1) for p in range(1, points + 1): for v in vouchers: if v <= p and best[p - v] + 1 < best[p]: best[p] = best[p - v] + 1 last[p] = v used = [] p = points while p > 0: used.append(last[p]) p -= last[p] return useddef greedy(vouchers, points): used = [] for v in vouchers: while points >= v: used.append(v) points -= v return useddef fewest(vouchers, points): best = [0] + [points + 1] * points last = [0] * (points + 1) for p in range(1, points + 1): for v in vouchers: if v <= p and best[p - v] + 1 < best[p]: best[p] = best[p - v] + 1 last[p] = v used = [] p = points while p > 0: used.append(last[p]) p -= last[p] return usedPaso a paso, en palabras
- Voraz, 6 puntos. El vale mayor que cabe es 4: lo toma. Quedan 2 puntos.
- Quedan 2 puntos: 4 y 3 no caben. Toma 1. Quedan 1 punto.
- Otro 1. Listo: 4 + 1 + 1, 3 vales. La elección de 4 fue definitiva y cerró el camino a 3 + 3.
- 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.
- best[1]: 1 → 1 + best[0] = 1. Lo mínimo es 1, último vale 1.
- best[2]: 1 → 1 + best[1] = 2. Lo mínimo es 2, último vale 1.
- best[3]: 3 → 1 + best[0] = 1; 1 → 1 + best[2] = 3. Lo mínimo es 1, último vale 3.
- 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.
- 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.
- 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.
- Hacia atrás por last: 6 → 3 → 0. Los vales son 3 y 3: 2.
- 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 Python también funciona float("inf"): inf + 1 sigue siendo inf. 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?
def greedy(vouchers, points): used = [] for v in vouchers: while points >= v: used.append(v) points -= v return used
vouchers = [4, 3, 1]print(greedy(vouchers, 10))4 cabe dos veces: quedan 2 puntos, y luego dos vales de 1 punto. Cuatro vales. El mínimo es 4 + 3 + 3: tres. 10 también es un contraejemplo.
Pruébalo
Completa
Para p puntos con v como último vale: ¿de qué importe sale el resto?
def fewest(vouchers, points):
best = [0] + [points + 1] * points
last = [0] * (points + 1)
for p in range(1, points + 1):
for v in vouchers:
if v <= p and best[p - v] + 1 < best[p]:
best[p] = best[] + 1
last[p] = v
used = []
p = points
while p > 0:
used.append(last[p])
p -= last[p]
return usedEl vale v cubre v puntos, y quedan p - v. El mínimo para ellos es best[p - v], calculado antes, porque p - v es menor que p. Más uno por el propio v.
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.
def by_ratio(parcels, capacity): total = 0 for kg, fee in sorted(parcels, key=lambda p: p[1] / p[0], reverse=True): if kg <= capacity: capacity -= kg total += fee return total
def best_fee(parcels, i, capacity): if i == len(parcels): return 0 skip = best_fee(parcels, i + 1, capacity) kg, fee = parcels[i] if kg > capacity: return skip take = fee + best_fee(parcels, i + 1, capacity - kg) return max(skip, take)parcels = [(6, 30), (5, 20), (5, 20)]print(f"Por tarifa por kilogramo: {by_ratio(parcels, 10)} €")print(f"Lo mejor: {best_fee(parcels, 0, 10)} €")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.
p[1] / p[0] en Python 3 es una división verdadera con parte decimal. // sería una división entera: 7 € por 2 kg pasarían a ser 3 € por kg en lugar de 3,5.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:
- Escribe una solución lenta pero seguramente correcta: una fuerza bruta que pruebe todas las posibilidades.
- Ejecuta lo voraz y la fuerza bruta con todas las entradas pequeñas: cada importe de 1 a 100.
- 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.
def try_all(coins, i, amount): if i == len(coins) - 1: return amount best = float("inf") for k in range(amount // coins[i] + 1): rest = try_all(coins, i + 1, amount - k * coins[i]) best = min(best, k + rest) return best
def check(name, coins, up_to): for a in range(1, up_to + 1): g = len(greedy(coins, a)) b = try_all(coins, 0, a) if g != b: print(f"{name}: {a} → voraz {g}, mínimo {b}") return print(f"{name}: hasta {up_to} 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)Vales 4, 3, 1: 6 → voraz 3, mínimo 2Monedas de euro: hasta 100 no hay contraejemploAntiguas británicas: 48 → voraz 3, mínimo 2Tres 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)Vales 4, 3, 1: hasta 5 no hay contraejemploMonedas de euro: hasta 100 no hay contraejemploAntiguas británicas: 48 → voraz 3, mínimo 2Elige la línea con el error.
La comprobación de los vales llega solo hasta 5 puntos, y el primer contraejemplo es 6. El código es correcto, el rango no. Hasta dónde ir lo dice el teorema de «Más precisamente»: hasta la suma de los dos valores mayores, 4 + 3 = 7.
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 no hay contraejemploHasta 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.
Vales 9, 6, 5, 1: 11 → voraz 3, mínimo 2Má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
bestFeepara 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