Algoritmos greedy

Qué cubre este capítulo

Un algoritmo greedy construye la solución paso a paso, tomando siempre la opción que se ve mejor en ese momento y sin voltear atrás. Cuando funciona, es el tipo de algoritmo más simple y más rápido que hay: sin árbol de recursión, sin tabla que llenar, nada más un barrido tomando decisiones localmente óptimas que terminan sumando una respuesta globalmente óptima. Ya viste greedy triunfar: Dijkstra fija el nodo más cercano, Prim y Kruskal agregan la arista segura más barata, Huffman fusiona los dos símbolos más raros. Este capítulo estudia el paradigma en sí y encara su peligro central: greedy es correcto solo con el criterio greedy correcto, y un "mejor" equivocado te da un algoritmo perfectamente plausible que en silencio regresa peores respuestas. El caso estrella es interval scheduling — meter la mayor cantidad de actividades que no se traslapen en un solo salón — donde la regla correcta (tomar la actividad que termina más temprano) es demostrablemente óptima, y dos reglas igual de intuitivas (la que empieza más temprano, la más corta) no lo son. El duelo entre ellas es la lección: en algoritmos greedy, el criterio lo es todo.

Un poco de historia

Los métodos greedy son tan viejos como la optimización, pero su teoría — cuándo se garantiza que greedy es correcto — se trabajó a mediados del siglo veinte junto con los problemas que los hicieron famosos. Interval scheduling y su regla del fin más temprano son ejemplos de libro de texto que vienen desde la literatura de investigación de operaciones. La codificación de Huffman (1952) es el greedy óptimo canónico, demostrado óptimo con un argumento de intercambio. El resultado más profundo es la caracterización de Jack Edmonds en 1971: los algoritmos greedy producen soluciones óptimas exactamente para los problemas cuyos conjuntos factibles forman un matroide, una estructura abstracta que captura la "independencia". Ese teorema traza una línea precisa entre los problemas donde greedy funciona (árboles de expansión mínima — el MST es un matroide, así que el greedy de Kruskal es óptimo) y los problemas donde no, y explica por qué la misma forma greedy tiene éxito en MST pero falla en, digamos, el problema del agente viajero. Aunque la moraleja práctica es anterior a la teoría: un algoritmo greedy siempre necesita una demostración, porque es facilísimo escribir uno que parece correcto y no lo es.

La intuición

Interval scheduling pregunta: dadas actividades con horas de inicio y fin, compitiendo por un solo salón, selecciona la mayor cantidad que no se traslapen. La idea greedy es elegir una actividad tras otra y comprometerse con ella. La pregunta es cuál — y hay varias respuestas tentadoras. ¿Tomas la actividad que empieza más temprano? ¿La más corta, para dejar espacio a las demás? ¿La que termina más temprano? Las tres son "greedy", y solo la última es correcta.

Aquí va por qué gana el fin más temprano. Ordena las actividades por hora de fin y barre: toma la primera (es la que termina más pronto de todas), luego salta todo lo que se traslape con ella, luego toma la siguiente compatible (que ahora es la que termina más pronto del resto), y así. La razón de que esto sea óptimo es un argumento de intercambio: haga lo que haga primero el horario óptimo, puedes cambiar su primera actividad por la que termina más temprano sin ningún conflicto — la actividad que termina más temprano no acaba después, así que solo puede liberar más espacio para lo que sigue. Repite el intercambio a lo largo del horario y habrás transformado el óptimo en la elección del greedy sin reducir nunca el conteo, lo que significa que el greedy también es óptimo. La intuición es "terminar temprano es lo más generoso que puedes hacer por todo lo que viene después", y la hora de fin, no la de inicio ni la duración, es lo que mide esa generosidad. Los criterios equivocados fallan justamente porque optimizan lo que no es: el inicio más temprano puede agarrar una actividad larga que bloquea muchas; la más corta puede agarrar una actividad brevísima a la mitad que choca con otras dos que entre ellas no chocan.

Complejidad: cómo escala

El greedy de fin más temprano es O(n log n): un sort por hora de fin y luego un solo barrido lineal. Eso es típico de los algoritmos greedy: el trabajo es un sort (o una cola de prioridad, como en Dijkstra y Prim) más una pasada, sin recursión ni memoización. El espacio es O(n) por la lista ordenada, O(1) más allá de eso. Pero la complejidad no es el eje interesante en greedy — la corrección sí lo es. El duelo no compite en velocidad; compite los tres criterios greedy en la calidad de sus respuestas, contando cuántas actividades selecciona cada uno:

El fin más temprano es demostrablemente óptimo — la prueba de corrección confirma que coincide con un óptimo por fuerza bruta en cada instancia pequeña. El inicio más temprano queda dramáticamente peor: con 64 actividades candidatas programó alrededor de 7.7 contra las 13.1 del fin más temprano, como 40% menos, porque una sola actividad que empieza temprano pero termina tarde bloquea a un montón de otras. La más corta primero es la tramposa: con estas entradas aleatorias promedió 13.0, casi empatando al óptimo — tan cerca que podrías mandarla a producción y jamás notar que está mal. Pero sí está mal, y se demuestra: con los intervalos [0,10), [9,11), [10,20), la más corta primero agarra el diminuto [9,11), que se traslapa con los otros dos, programando una actividad donde el óptimo programa dos. Un greedy que casi siempre acierta sigue siendo un bug, y ese "casi siempre acierta" es justo lo que hace peligroso al criterio equivocado.

En qué es bueno y en qué no

Los algoritmos greedy son la elección correcta cuando un problema tiene la propiedad de elección greedy y subestructura óptima — demostrablemente, vía un argumento de intercambio o una estructura de matroide. Entonces son imbatibles: más simples, más rápidos (normalmente nada más un sort y un barrido) y con menos memoria que programación dinámica o búsqueda. Los clásicos son todos greedy: árboles de expansión mínima (Prim, Kruskal), caminos más cortos con pesos no negativos (Dijkstra), códigos prefijo óptimos (Huffman), selección de actividades/intervalos, la mochila fraccionaria y muchos problemas de scheduling y asignación de recursos. Greedy también es la columna vertebral de los algoritmos de aproximación: incluso cuando no puede encontrar el óptimo exacto, una regla greedy suele quedar demostrablemente cerca (set cover, vertex cover), lo cual es valioso para problemas NP-difíciles donde la optimización exacta es inviable.

Donde greedy falla es en los problemas que carecen de la propiedad de elección greedy, y las fallas son traicioneras porque el algoritmo igual corre y produce una respuesta plausible. El problema de la mochila 0/1 (siguiente capítulo) no se puede resolver con greedy — tomar primero el objeto con mayor valor por peso puede salir arbitrariamente mal — y necesita programación dinámica. El cambio de monedas es greedy-óptimo para algunos sistemas de monedas (como la moneda estándar) pero no para otros: con monedas {1, 3, 4} para formar 6, greedy toma 4+1+1 (tres monedas) cuando 3+3 (dos) es lo óptimo. El agente viajero, la coloración de grafos y la mayoría de los problemas NP-difíciles no tienen un greedy óptimo. La regla de dedo: greedy es una hipótesis, no una solución — necesita demostración, y si no puedes demostrar la propiedad de elección greedy, asume que está mal y échale mano a programación dinámica o a búsqueda.

Los datos, o las entradas

El duelo genera conjuntos aleatorios de actividades dentro de una ventana de tiempo fija y cuenta cuántas logra programar cada uno de los tres criterios greedy — fin más temprano, inicio más temprano, más corta — conforme crece el número de candidatas. La corrección se verifica contra un óptimo por fuerza bruta (probar todos los subconjuntos) en cientos de instancias pequeñas: el fin más temprano siempre debe igualar al máximo verdadero, y los otros dos nunca deben excederlo. La animación corre el greedy de fin más temprano sobre el ejemplo de libro de texto con once actividades, dibujando las actividades como barras en una línea de tiempo ordenada por hora de fin y barriendo hacia abajo, tomando cada una que sea compatible.

Constrúyelo, una función a la vez

El greedy óptimo — ordenar por hora de fin, barrer y tomar cada actividad compatible:

def schedule_earliest_finish(intervals):
    """The optimal greedy for interval scheduling: sort activities by FINISH time, then sweep
    left to right taking each activity whose start is not before the last taken finish. Finishing
    early leaves the most room for what follows — that's the intuition the exchange argument makes
    rigorous. O(n log n), dominated by the sort. Returns the chosen intervals."""
    chosen = []
    last_finish = float("-inf")
    for start, finish in sorted(intervals, key=lambda iv: iv[1]):   # by finish time
        if start >= last_finish:                 # compatible with everything chosen so far
            chosen.append((start, finish))
            last_finish = finish
    return chosen

Y los dos criterios plausibles pero equivocados, para comparar:

def schedule_earliest_start(intervals):
    """A plausible-but-WRONG greedy: take the activity that starts earliest. One long early
    activity can block many short later ones, so this can badly underperform the optimum."""
    chosen = []
    last_finish = float("-inf")
    for start, finish in sorted(intervals, key=lambda iv: iv[0]):   # by start time
        if start >= last_finish:
            chosen.append((start, finish))
            last_finish = finish
    return chosen


def schedule_shortest(intervals):
    """Another plausible-but-WRONG greedy: take the shortest activity first. A short activity in
    the middle can conflict with two others that don't conflict with each other, losing one."""
    chosen = []
    taken = []
    for start, finish in sorted(intervals, key=lambda iv: iv[1] - iv[0]):   # by duration
        if all(finish <= s or start >= f for s, f in taken):        # overlaps nothing chosen
            taken.append((start, finish))
            chosen.append((start, finish))
    return chosen

Míralo funcionar

Aquí está el greedy de fin más temprano programando once actividades, dibujadas como barras en una línea de tiempo y ordenadas de arriba a abajo por hora de fin — el orden en que el greedy las considera. La línea punteada azul marca la hora de fin de la última actividad tomada: el salón está libre a su derecha. Barre hacia abajo: la primera actividad [1,4) se toma (verde) y la línea salta al tiempo 4. Las siguientes barras empiezan antes de 4, así que se traslapan y se saltan (rojo). [5,7) empieza en 5, después de la línea, así que se toma y la línea se mueve a 7. Y así — el greedy agarra [1,4), [5,7), [8,11), [12,16), cuatro actividades, cada una la que termina más temprano entre las que siguen siendo compatibles. Ninguna otra selección mete más; eso es lo que garantiza el argumento de intercambio:

El código completo

La pestaña "desde cero" trae los tres criterios greedy — el óptimo de fin más temprano y los dos equivocados; la pestaña de librería trae el óptimo por fuerza bruta que se usa para verificar que el fin más temprano sí es genuinamente óptimo. Cambia entre ellas: los tres greedies son código casi idéntico y difieren solo en la llave de ordenamiento, que es justamente el punto — el criterio es un cambio de una línea y es toda la diferencia entre correcto y equivocado.

"""Greedy algorithms — build a solution by repeatedly making the choice that looks best right
now, never reconsidering. When a problem has the right structure, those locally-best choices add
up to a globally optimal answer, with none of the backtracking or table-filling of the other
paradigms. You've already seen greedy work: Dijkstra settles the nearest node, Prim and Kruskal
add the cheapest safe edge, Huffman merges the two rarest symbols. This chapter studies the
paradigm itself, and the delicate thing about it: greedy is only correct for the RIGHT greedy
criterion, and choosing the wrong "best" gives a plausible algorithm that quietly returns
suboptimal answers.

The showcase is interval scheduling: given a set of activities with start and finish times, select
the largest number that don't overlap (the classic "how many meetings fit in one room"). The
correct greedy rule is surprising — always take the activity that FINISHES EARLIEST among those
still compatible. It's provably optimal. Two equally intuitive rules — take the earliest-starting,
or the shortest — are both wrong, and comparing them is the whole lesson: in greedy algorithms, the
criterion is everything.
"""


# region: earliest_finish
def schedule_earliest_finish(intervals):
    """The optimal greedy for interval scheduling: sort activities by FINISH time, then sweep
    left to right taking each activity whose start is not before the last taken finish. Finishing
    early leaves the most room for what follows — that's the intuition the exchange argument makes
    rigorous. O(n log n), dominated by the sort. Returns the chosen intervals."""
    chosen = []
    last_finish = float("-inf")
    for start, finish in sorted(intervals, key=lambda iv: iv[1]):   # by finish time
        if start >= last_finish:                 # compatible with everything chosen so far
            chosen.append((start, finish))
            last_finish = finish
    return chosen
# endregion


# region: wrong_greedies
def schedule_earliest_start(intervals):
    """A plausible-but-WRONG greedy: take the activity that starts earliest. One long early
    activity can block many short later ones, so this can badly underperform the optimum."""
    chosen = []
    last_finish = float("-inf")
    for start, finish in sorted(intervals, key=lambda iv: iv[0]):   # by start time
        if start >= last_finish:
            chosen.append((start, finish))
            last_finish = finish
    return chosen


def schedule_shortest(intervals):
    """Another plausible-but-WRONG greedy: take the shortest activity first. A short activity in
    the middle can conflict with two others that don't conflict with each other, losing one."""
    chosen = []
    taken = []
    for start, finish in sorted(intervals, key=lambda iv: iv[1] - iv[0]):   # by duration
        if all(finish <= s or start >= f for s, f in taken):        # overlaps nothing chosen
            taken.append((start, finish))
            chosen.append((start, finish))
    return chosen
# endregion

"""The reference and the contrast. There's no single 'library' for interval scheduling — it's a
classic exercise, not a stdlib call — so the reference here is a BRUTE-FORCE optimum: try every
subset of activities and keep the largest compatible one. It's O(2^n), usable only on small
instances, but it's the ground truth that proves the earliest-finish greedy is actually optimal
(and that the other greedies are not).

In production, the earliest-finish greedy IS what you'd ship — it's optimal and O(n log n). The
brute force exists only to verify it.
"""
from itertools import combinations


# region: brute_force
def optimal_brute_force(intervals):
    """The true maximum number of non-overlapping activities, by checking every subset from
    largest down. O(2^n) — only for verifying the greedy on small inputs. Returns a largest
    compatible subset."""
    def compatible(subset):
        s = sorted(subset, key=lambda iv: iv[0])
        return all(s[i][1] <= s[i + 1][0] for i in range(len(s) - 1))

    n = len(intervals)
    for size in range(n, 0, -1):
        for subset in combinations(intervals, size):
            if compatible(subset):
                return list(subset)
    return []
# endregion

Desde cero vs. librería

Los tres criterios greedy difieren en una sola llave de ordenamiento, y uno es óptimo mientras los otros no — esa es toda la lección de los algoritmos greedy comprimida en una línea de código. Replantea lo que significa "diseñar un algoritmo greedy": la parte difícil no es el barrido, que es trivial, sino elegir y demostrar el criterio, lo cual requiere un argumento de intercambio o una estructura de matroide. Ese es el doble filo del paradigma — greedy es el algoritmo más simple de escribir y el más fácil de equivocar sutilmente, porque un criterio equivocado produce un programa que funciona y da salidas plausibles. El número más importante del duelo no es el 40% de diferencia obvio del inicio más temprano; es el 13.0 contra 13.1 de la más corta primero, un algoritmo equivocado que se ve correcto en cualquier prueba que hicieras a la ligera. La disciplina que exige greedy — demuéstralo, no lo midas con benchmarks — es el verdadero entregable. Los algoritmos greedy que ya construiste (Dijkstra, Prim, Kruskal, Huffman) venían todos con demostraciones así, por eso son correctos; este capítulo es donde esa obligación de demostrar se vuelve explícita.

Dónde te lo vas a encontrar de verdad

Los algoritmos greedy corren por todos lados en sistemas y optimización. La compresión de datos usa Huffman y códigos greedy relacionados. El ruteo de redes y los protocolos de spanning tree usan Dijkstra y Prim/Kruskal. Los schedulers de sistemas operativos y de tiempo real usan reglas greedy (earliest-deadline-first, shortest-job-first) para agendar tareas y CPU. El interval scheduling en sí aparece en reservación de salas y recursos, en talleres de producción y en la asignación de registros en compiladores. Los algoritmos greedy de aproximación atacan problemas NP-difíciles — set cover para ubicación de instalaciones y selección de features, matching greedy en subastas de anuncios y asignación. Los load balancers, las políticas de desalojo de cache (LRU/LFU greedy) y los algoritmos de streaming se apoyan en elecciones greedy. Y en machine learning, la selección greedy de features, la división de árboles de decisión (cada nodo elige greedily el mejor split) y beam search son todos este paradigma. Donde sea que una regla localmente óptima produzca demostrablemente un óptimo global — o una aproximación suficientemente buena — greedy es la herramienta.

Puntos clave

Un algoritmo greedy toma la mejor elección local en cada paso y nunca la reconsidera, llegando al óptimo global solo cuando el problema tiene la propiedad de elección greedy y subestructura óptima — demostrable con un argumento de intercambio o una estructura de matroide. Interval scheduling muestra tanto la promesa como el peligro: el criterio de fin más temprano es demostrablemente óptimo (empata el máximo por fuerza bruta en cada instancia), mientras que el igual de intuitivo inicio más temprano (40% peor) y la más corta primero (casi siempre cerca del óptimo, pero equivocada con [0,10),[9,11),[10,20)) no lo son. El criterio es el algoritmo, y exige una demostración, porque un greedy equivocado que casi siempre acierta es el tipo de bug más peligroso.

El siguiente capítulo se mete con los problemas que greedy no puede resolver: aquellos con subproblemas traslapados donde ninguna elección localmente óptima es segura. La programación dinámica los maneja considerando todas las opciones pero recordando la respuesta de cada subproblema para calcularla una sola vez — convirtiendo la explosión exponencial de la recursión ingenua en tiempo polinomial, y resolviendo exactamente los problemas de mochila y de camino más corto con decisiones donde greedy no da ninguna garantía.