En la lección anterior aprendimos a trocear problemas con divide y vencerás. La segunda gran estrategia del módulo es de temperamento opuesto: en lugar de resolverlo todo y luego decidir, un algoritmo greedy (voraz) construye la solución paso a paso tomando en cada momento la decisión que parece mejor ahora mismo, sin mirar atrás y sin calcular las consecuencias futuras. Esta impaciencia produce algoritmos sencillos y rapidísimos... que unas veces son óptimos demostrables y otras veces fallan estrepitosamente sin avisar. En RutaBus ya nos topamos con un greedy sin saberlo: el recorrido_supervisor de 01-02, aquella heurística del vecino más cercano. En esta lección aprenderemos la anatomía de un greedy, resolveremos un problema real de asignación de trayectos, veremos con nuestros propios ojos un greedy fallando, y — lo más importante — aprenderemos a distinguir cuándo se puede confiar en uno.

1. La idea: decisión localmente óptima e irrevocable
2. Anatomía de un algoritmo greedy
3. Ejemplo RutaBus: máximo número de trayectos para un autobús
4. Por qué funciona: una demostración informal
5. Cuando greedy falla: dos contraejemplos
6. Cómo reconocer si un problema admite greedy
7. Algoritmos greedy célebres

Un algoritmo greedy se caracteriza por dos rasgos:

• Elección localmente óptima: en cada paso escoge el candidato que maximiza (o minimiza) un criterio inmediato, sin simular el futuro.
• Irrevocabilidad: una decisión tomada no se revisa jamás. No hay vuelta atrás — justo lo contrario del backtracking que veremos en 03-04.

Esta combinación explica sus dos caras:

Casi todos los greedy comparten cuatro piezas. Conviene identificarlas explícitamente antes de escribir código:

1. Conjunto de candidatos: los elementos entre los que se elige (trayectos, monedas, paradas...).
2. Función de selección: el criterio voraz que decide qué candidato tomar a continuación ("el que antes termina", "la moneda más grande", "la parada más cercana").
3. Test de factibilidad: ¿puedo añadir este candidato a la solución parcial sin violar las restricciones?
4. Solución: la construcción termina cuando se agotan los candidatos o la solución está completa.

En pseudocódigo, el esqueleto universal:

Todo el ingenio está en el paso de ordenar: elegir bien la función de selección es diseñar el algoritmo. Con la función correcta, greedy es óptimo; con una plausible pero incorrecta, es solo una heurística (recuerda la distinción exactos vs heurísticos de 01-02).

El problema. RutaBus tiene un único autobús de refuerzo y una lista de trayectos solicitados para mañana, cada uno con hora de inicio y hora de fin (en minutos desde medianoche). El autobús solo puede hacer un trayecto a la vez. Objetivo: asignarle el máximo número de trayectos sin solapamientos. (Es la versión RutaBus del clásico problema de selección de actividades.)

Antes de ver la solución, piensa: ¿qué función de selección usarías? Candidatas razonables: el trayecto más corto primero, el que empieza antes, el que tiene menos conflictos... Todas suenan bien y todas fallan en algún caso. La correcta es menos intuitiva: el que termina antes.

Explicación línea a línea:

• sorted(..., key=lambda t: t[2]): materializa la función de selección. Coste O(n log n), que dominará el total (02-01).
• fin_ultimo: el estado mínimo que necesitamos recordar — cuándo queda libre el autobús. Nota el uso de una sola variable: espacio auxiliar O(1) más la salida (02-02).
• if inicio >= fin_ultimo: el test de factibilidad. Un trayecto es compatible si empieza cuando el autobús ya está libre.
• El append es la decisión irrevocable: nunca reconsideramos un trayecto aceptado ni recuperamos uno rechazado.
• El bucle recorre los candidatos una vez: O(n). Total: O(n log n), frente al coste exponencial de probar todos los subconjuntos de trayectos.

Resultado: 3 trayectos. Ninguna combinación logra 4 — y esto no es casualidad, como vamos a argumentar.

El argumento clásico se llama argumento de intercambio (exchange argument) y conviene interiorizarlo, porque es la herramienta estándar para justificar un greedy:

1. Sea g el primer trayecto que elige el greedy: el que termina antes de todos.
2. Toma cualquier solución óptima OPT. Si OPT no contiene g, mira el primer trayecto de OPT (llámalo x). Como g termina antes o igual que cualquier trayecto — también antes que x —, podemos sustituir x por g en OPT sin crear solapamientos: g deja libre el autobús incluso antes que x, así que todo lo que cabía después de x sigue cabiendo después de g.
3. La solución modificada tiene el mismo tamaño que OPT, luego sigue siendo óptima y empieza como el greedy.
4. Eliminado g y los trayectos incompatibles con él, queda un subproblema idéntico pero más pequeño ("máximo de trayectos que empiezan tras fin_ultimo"), al que se aplica el mismo razonamiento una y otra vez.

Conclusión: la elección voraz nunca nos aleja de un óptimo. Fíjate en la lógica: no decimos que greedy sea la única solución óptima, sino que siempre existe un óptimo que toma la decisión voraz — con eso basta.

Este argumento explica también por qué "el que termina antes" es la clave: terminar pronto deja el máximo margen posible al futuro. Los criterios rivales no tienen esa propiedad: el trayecto más corto puede estar "atravesado" bloqueando a dos largos compatibles, y el que empieza antes puede ser larguísimo y comerse la mañana entera.

Los billetes de recarga de la tarjeta RutaBus valen 1, 3 y 4 euros (un sistema deliberadamente exótico). Queremos abonar una cantidad con el mínimo número de billetes. El greedy natural — "toma siempre el billete más grande que quepa" — falla:

Para 6 €, el greedy toma el 4 (localmente óptimo) y se condena a completar con dos monedas de 1. La decisión irrevocable de coger el 4 destruye la posibilidad de usar 3+3. Con el sistema del euro (1, 2, 5, 10, 20, 50...) el greedy sí es óptimo — se dice que el sistema es canónico —, lo que ilustra algo incómodo: el mismo algoritmo es exacto o incorrecto según los datos del problema. Por eso un greedy sin argumento de optimalidad es una apuesta. (La versión general del cambio de monedas se resuelve garantizadamente con programación dinámica, la estrategia de 03-03.)

En 01-02 escribimos recorrido_supervisor: el supervisor visita todas las paradas yendo siempre a la más cercana no visitada. Ahora tenemos vocabulario para diagnosticarlo: es un greedy de manual — candidatos: paradas no visitadas; selección: mínima distancia; factibilidad: no repetir parada. Y ya dijimos entonces que es una heurística: da rutas razonables, no la ruta más corta.

Verlo fallar es fácil con paradas en línea recta (posiciones en km): el supervisor parte del km 0 y debe visitar las paradas de los km 1, 2 y −1,5.

• Greedy (vecino más cercano): la más cercana al 0 es la del km 1 → luego la del 2 (a 1 km) → y por último la del −1,5 (a 3,5 km). Total: 1 + 1 + 3,5 = 5,5 km.
• Óptimo: ir primero "a contracorriente": 0 → −1,5 (1,5 km) → 1 (2,5 km) → 2 (1 km). Total: 5 km.

El greedy pierde por ir primero a lo cómodo y dejar para el final el desplazamiento largo de vuelta: cada elección local fue impecable y el total, subóptimo.

La moraleja es doble. Primera: greedy falla cuando una decisión cómoda ahora crea un sobrecoste inevitable después. Segunda: un greedy no óptimo no es basura — como heurística, recorrido_supervisor da soluciones decentes en O(n²) para un problema (el del viajante) cuya solución exacta es exponencial. Saber que no es óptimo, y decidir si nos vale, es exactamente el tipo de juicio profesional que este curso entrena.

No hay receta infalible, pero sí dos propiedades que los problemas "greedy-compatibles" exhiben (las enunciamos de manera informal; su tratamiento riguroso pertenece a textos avanzados):

• Propiedad de elección voraz: existe una elección localmente óptima que forma parte de alguna solución global óptima — es decir, decidir ya, sin mirar el futuro, no cierra la puerta al óptimo. Se comprueba típicamente con un argumento de intercambio como el de la sección anterior.
• Subestructura óptima: tras tomar la decisión voraz, lo que queda es un subproblema del mismo tipo cuya solución óptima, unida a la decisión tomada, da el óptimo global. (Esta propiedad reaparecerá en 03-03: la programación dinámica también la exige. La diferencia: PD explora varias decisiones posibles y greedy se juega todo a una.)

Lista de comprobación práctica antes de confiar en un greedy:

1. ¿Puedo formular una función de selección clara?
2. ¿Tengo un argumento de intercambio, aunque sea informal, de que la elección voraz no descarta el óptimo?
3. ¿He buscado activamente contraejemplos pequeños (3-6 elementos, casos extremos)?
4. Si no logro 2 y 3: ¿me vale como heurística, o el problema exige el óptimo exacto (→ PD en 03-03 o backtracking en 03-04)?

Dijkstra merece una nota: es la prueba de que "greedy" no significa "aproximado". Elegir siempre la parada no procesada más cercana al origen es óptimo para caminos mínimos — lo demostraremos e implementaremos en 04-05, cuando la red de RutaBus sea por fin un grafo con pesos.

• Asumir optimalidad sin argumento. "Suena razonable" no es una demostración. El cambio de monedas con (1, 3, 4) suena igual de razonable y falla. Exige siempre un argumento de intercambio o contraejemplos agotados.
• Elegir la función de selección equivocada. En el problema de trayectos, tres criterios plausibles fallan y solo "termina antes" funciona. Prueba cada criterio candidato contra ejemplos pequeños diseñados con mala idea.
• Olvidar la ordenación en el análisis. El bucle greedy es O(n), pero el sorted previo lo hace O(n log n). No anuncies costes que tu propio código desmiente (02-01).
• Confundir "greedy falla" con "greedy inútil". Una heurística voraz con garantías empíricas puede ser la mejor opción de ingeniería cuando el exacto es exponencial. Documenta que es heurística y punto.
• Modificar la solución ya construida. Si te descubres "quitando" elementos aceptados, ya no estás escribiendo un greedy: estás improvisando un backtracking sin control. Replantea la estrategia (03-04).

RutaBus quiere instalar el mínimo número de puntos de recarga en una avenida de modo que toda parada tenga un punto a menos de 500 m. Las posiciones de las paradas (en metros) están en una lista ordenada, p. ej. [100, 300, 850, 900, 1800]. Diseña un greedy: indica candidatos, función de selección y test de factibilidad, e impleméntalo. Pista: procesa las paradas de izquierda a derecha y coloca cada punto lo más a la derecha posible.

Para el problema de los trayectos, demuestra con un contraejemplo concreto (3-4 trayectos con horas) que la función de selección "el trayecto más corto primero" no es óptima.

El autobús de refuerzo tiene un depósito para 300 km. En la ruta hay gasolineras en los km [90, 150, 230, 350, 480] y la ruta mide 520 km. Escribe un greedy que calcule el mínimo número de repostajes (partiendo con el depósito lleno) y razona informalmente por qué su elección voraz es segura.

Solución 1

• Candidatos: posiciones posibles de puntos de recarga. Selección: para la parada descubierta más a la izquierda, colocar el punto en parada + 500 (lo más a la derecha que aún la cubre). Factibilidad: cada parada debe quedar a ≤ 500 m de algún punto.

Con [100, 300, 850, 900, 1800]: el punto en 600 cubre 100, 300, 850 y 900 (todas a ≤ 500 de 600... 100 está a 500 justos, dentro); el punto en 2300 cubre 1800. Total: 2 puntos. Argumento de intercambio: cualquier solución óptima necesita algún punto que cubra la primera parada; moverlo hasta paradas[0] + 500 no descubre a nadie de la izquierda (no hay nadie) y solo puede cubrir más paradas a la derecha. Coste: O(n).

Solución 2

Trayectos: A = (10:00-12:00), B = (11:45-12:15), C = (12:10-14:00). El más corto es B (30 min); el greedy "corto primero" lo elige, y B se solapa tanto con A (11:45 < 12:00) como con C (12:10 < 12:15): quedan ambos descartados y el total es 1 trayecto. Sin embargo, A y C son compatibles entre sí (A termina a las 12:00 ≤ 12:10): el óptimo es 2. B está "atravesado" bloqueando a dos trayectos compatibles — exactamente el defecto que anticipamos en la lección. Comprueba que el criterio correcto, "termina antes", elige A y luego C y alcanza el óptimo.

Solución 3

Selección voraz: no repostar hasta que sea imprescindible y, entonces, hacerlo en la gasolinera alcanzable más lejana que hayamos dejado atrás.

Traza con autonomía 300: desde el km 0 se alcanza hasta el 300, así que 90, 150 y 230 se pasan de largo; el 350 ya no se alcanza → repostaje imprescindible, y de las alcanzables (90, 150, 230) se elige la más lejana: 230. Desde 230 se alcanza el km 530 ≥ 520, así que se llega al destino pasando de largo 350 y 480. Resultado: 1 repostaje. Argumento de intercambio: cuando repostar es inevitable, cualquier plan óptimo reposta en alguna gasolinera alcanzable; sustituirla por la más lejana no puede dejarnos tirados (también era alcanzable) y deja el depósito lleno más adelante, cubriendo un tramo posterior igual o mayor. La elección voraz nunca aleja del óptimo. (La búsqueda de alcanzables dentro del bucle es O(n); con dos índices se deja en O(n) total — buen refinamiento opcional.)

Los algoritmos greedy construyen la solución con decisiones locales e irrevocables: candidatos + función de selección + test de factibilidad, casi siempre con una ordenación O(n log n) como único coste relevante. Hemos visto la estrategia brillar en la asignación de trayectos — con su argumento de intercambio: elegir lo que antes termina nunca cierra la puerta al óptimo — y fracasar en el cambio de monedas (1, 3, 4) y en nuestro viejo conocido recorrido_supervisor, que hoy hemos rebautizado como lo que siempre fue: un greedy heurístico. La lección de fondo: greedy exige demostrar (o al menos argumentar y buscar contraejemplos), porque su fallo es silencioso. ¿Y qué hacemos cuando el problema tiene subestructura óptima pero la elección voraz falla — cuando 6 € se pagan mejor con 3+3 que empezando por el 4? Necesitamos una estrategia que, en lugar de apostarlo todo a una decisión, explore todas las decisiones posibles reutilizando los cálculos repetidos — la idea de gastar memoria para no repetir trabajo que dejamos apuntada en 02-02 con construir_indice. Esa estrategia tiene nombre propio y es la protagonista de la siguiente lección: la programación dinámica.