Algoritmos voraces explicados: cómo funcionan, código y ejemplos

Qué problema resuelven los algoritmos voraces

Los algoritmos voraces atacan problemas de optimización: elegir el mayor número de actividades, usar el menor número de monedas, construir la red más barata, comprimir un archivo en el menor número de bits. En lugar de explorar todas las combinaciones, un algoritmo voraz ordena o prioriza las opciones y se compromete con la mejor en cada paso. Eso suele dar un tiempo O(n log n), a menudo solo el coste de ordenar.

Lo difícil no es el código sino la demostración. Muchas reglas voraces naturales son incorrectas, así que debes demostrar que la regla es correcta o contrastarla con una solución de fuerza bruta.

La idea en palabras sencillas

1. Encuentra una regla que ordene las opciones, por ejemplo "primero la que termina antes" o "primero la arista más ligera".
2. Ordena las opciones según esa regla o guárdalas en una cola de prioridad.
3. Recorre las opciones y toma cada una que las restricciones todavía permitan.
4. Nunca deshagas una elección.

Un algoritmo voraz es correcto cuando se cumplen dos propiedades. Propiedad de elección voraz: alguna solución óptima contiene la primera elección voraz. Subestructura óptima: tras tomar esa elección, el resto del problema es una instancia más pequeña del mismo problema. La demostración habitual es un argumento de intercambio: toma cualquier solución óptima y muestra que cambiar una de sus elecciones por la elección voraz no la empeora.

Ejemplo resuelto: planificación de intervalos

Tienes una sala de reuniones y estas solicitudes (inicio, fin): A (1, 4), B (3, 5), C (0, 6), D (5, 7), E (3, 9), F (5, 9), G (6, 10), H (8, 11). Reserva el mayor número posible de reuniones sin solapamientos. La regla voraz correcta es: elegir siempre la reunión que termina antes entre las que empiezan después de que termine la última reservada.

Resultado: A, D, H, tres reuniones, que es el máximo. Por qué funciona: la reunión que termina antes deja más tiempo libre para todo lo demás, así que sustituir la primera reunión de cualquier horario óptimo por ella nunca provoca un conflicto.

Implementación en Python

def max_meetings(meetings):
    """meetings: list of (name, start, end). Returns the booked names."""
    booked, last_end = [], float("-inf")
    for name, start, end in sorted(meetings, key=lambda m: m[2]):
        if start >= last_end:
            booked.append(name)
            last_end = end
    return booked

requests = [("A", 1, 4), ("B", 3, 5), ("C", 0, 6), ("D", 5, 7),
            ("E", 3, 9), ("F", 5, 9), ("G", 6, 10), ("H", 8, 11)]
print(max_meetings(requests))  # ['A', 'D', 'H']

Un segundo ejemplo clásico es la mochila fraccionaria: cuando puedes tomar parte de un objeto, tomar los objetos en orden de valor por unidad de peso es óptimo.

def fractional_knapsack(items, capacity):
    """items: list of (value, weight). Returns the best total value."""
    total = 0.0
    for value, weight in sorted(items, key=lambda i: i[0] / i[1], reverse=True):
        take = min(weight, capacity)
        total += value * take / weight
        capacity -= take
        if capacity == 0:
            break
    return total

print(fractional_knapsack([(60, 10), (100, 20), (120, 30)], 50))  # 240.0

Cuando el voraz falla: contraejemplos

Complejidad temporal y espacial

El espacio suele ser O(n) para la copia ordenada o el montículo. Si la entrada ya está ordenada, muchos algoritmos voraces se ejecutan en O(n).

Cuándo usar un algoritmo voraz y usos en el mundo real

• Usa un algoritmo voraz cuando puedas demostrar la propiedad de elección voraz, o cuando una respuesta aproximada rápida sea aceptable. En caso contrario, usa programación dinámica o backtracking.
• Compresión: la codificación de Huffman construye códigos de prefijo óptimos fusionando repetidamente los dos símbolos menos frecuentes; se usa dentro de formatos como DEFLATE (ZIP, gzip, PNG).
• Redes: árboles de expansión mínima (Kruskal, Prim) y enrutamiento por caminos más cortos (Dijkstra).
• Planificación: primero el plazo más próximo (earliest deadline first) y reserva de salas o máquinas.
• Aproximación: para el recubrimiento de conjuntos (set cover), la regla voraz "elige el conjunto que cubra más elementos aún sin cubrir" no es óptima, pero tiene garantizado quedar dentro de un factor logarítmico del óptimo.
• Problemas de entrevista: jump game, gas station, assign cookies, intervalos sin solapamiento, número mínimo de flechas para reventar globos, task scheduler.