Algoritmo voraz — Greedy Algorithm

Al finalizar este tema

Comprenderás el principio de funcionamiento del algoritmo voraz, podrás determinar cuándo es aplicable y resolverás problemas representativos por tu cuenta.

Idea central

Debes dar un cambio de 1260 wones en una tienda de conveniencia. Las monedas disponibles son de 500, 100, 50 y 10 wones.

Método intuitivo: Utiliza la moneda de mayor valor siempre que sea posible.

def coin_change(amount):
    coins = [500, 100, 50, 10]
    count = 0
    for coin in coins:
        count += amount // coin
        amount %= coin
    return count

print(coin_change(1260))  # 6 monedas (500×2 + 100×2 + 50×1 + 10×1)

En cada paso, se toma la mejor decisión posible en ese momento. No se considera el pasado ni el futuro. Este es el algoritmo voraz.

¿Por qué "voraz"?

Características del algoritmo voraz:

1. Óptimo local: La mejor opción en el momento actual.
2. Sin retroceso: Una vez tomada una decisión, no se revierte.
3. Garantía de óptimo global: Solo se obtiene la solución óptima global cuando se cumplen ciertas condiciones.

En el problema del cambio de monedas, usar primero una moneda de 500 parece intuitivamente correcto. Sin embargo, esta estrategia no funciona para todos los problemas.

Condiciones para que el algoritmo voraz funcione

Para que el algoritmo voraz garantice la solución óptima, se requieren dos propiedades:

Propiedad de elección voraz

La mejor elección en cada paso debe formar parte de la solución óptima global.

Ejemplo del cambio de monedas: Usar la mayor cantidad posible de monedas de 500 siempre forma parte de la solución óptima, porque 500 = 100 × 5; por lo tanto, si no se usa una moneda de 500, el número total de monedas aumentará inevitablemente.

Subestructura óptima

La solución óptima de un problema grande incluye la solución óptima de sus subproblemas.

La solución óptima para 1260 = elegir 2 monedas de 500 + "la solución óptima para 260". Los 260 restantes también se pueden resolver con la misma estrategia.

Casos en los que el algoritmo voraz falla

Si las monedas disponibles son de [400, 300, 100] y se debe dar un cambio de 600:

# Algoritmo voraz: 400 + 100 + 100 = 3 monedas
# Solución óptima: 300 + 300 = 2 monedas

Si primero eliges las monedas de 400, deberás completar los 200 restantes con dos monedas de 100. Sin embargo, usar dos monedas de 300 implica un número menor de monedas. La estrategia de usar primero las monedas de mayor valor falla.

Esto ocurre porque, en este caso, el valor de la moneda más grande no es un múltiplo entero del valor de la moneda más pequeña (por ejemplo, 500, 100, 50, 10). Cuando se rompe esta relación de múltiplos, el algoritmo voraz no garantiza la solución óptima. Para este tipo de problemas, se requiere la programación dinámica (DP).

Problema representativo 1: Selección de actividades

Hay una sala de reuniones y varias solicitudes de reuniones. ¿Cómo programar el mayor número posible de reuniones sin que se superpongan?

def max_meetings(meetings):
    # Ordenar por hora de finalización
    meetings.sort(key=lambda m: m[1])

    count = 0
    last_end = 0
    for start, end in meetings:
        if start >= last_end:
            count += 1
            last_end = end
    return count

meetings = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11)]
print(max_meetings(meetings))  # 4 reuniones

Estrategia voraz: Selecciona las reuniones que terminan antes.

¿Por qué es óptima? Al elegir las reuniones que terminan antes, se dispone de más tiempo para programar más reuniones. Esta propiedad de selección voraz está demostrada matemáticamente para este problema.

Problema representativo 2: Mochila fraccionaria

Capacidad de la mochila: 50 kg. Maximiza el valor cuando los objetos se pueden dividir para incluirlos:

def fractional_knapsack(capacity, items):
    # Ordenar descendente por valor por unidad de peso
    items.sort(key=lambda x: x[1] / x[0], reverse=True)

    total_value = 0
    for weight, value in items:
        if capacity >= weight:
            total_value += value
            capacity -= weight
        else:
            total_value += value * (capacity / weight)
            break
    return total_value

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

Estrategia voraz: Se seleccionan los elementos con mayor relación valor/peso (mejor costo-beneficio) primero.

Advertencia: En el problema de la mochila 0-1, donde los objetos no se pueden dividir, el algoritmo voraz no garantiza la solución óptima. El problema de la mochila 0-1 debe resolverse mediante programación dinámica (DP).

Algoritmo voraz vs. búsqueda exhaustiva vs. DP

El algoritmo voraz es rápido, pero solo produce la respuesta correcta cuando se cumplen las condiciones. Si no se cumplen, se debe utilizar DP o búsqueda exhaustiva.

Criterios de decisión en pruebas de programación

1. "Parece que basta con seleccionar lo más ~ primero" → Candidato para el algoritmo voraz
2. Intenta construir un contraejemplo → Si no hay contraejemplos, aplica la estrategia voraz
3. El criterio de ordenación es claro → Alta probabilidad de aplicabilidad del algoritmo voraz
4. "La parte restante también se puede resolver de la misma manera" → Se cumple la subestructura óptima

Si tienes dudas sobre el algoritmo voraz, busca primero contraejemplos con entradas pequeñas. Si aparece un contraejemplo, cambia a DP. En la práctica, en los problemas del algoritmo voraz, la ordenación suele ser el elemento clave.

Conclusión clave: La estrategia voraz consiste en "elegir lo mejor en cada momento para lograr el mejor resultado global". Funciona en O(n) cuando se cumplen las condiciones (como en el cambio de monedas), pero produce respuestas incorrectas si no se satisfacen.