Un algoritmo greedy realiza la elección localmente óptima en cada paso, esperando que conduzca a un óptimo global. Es simple y rápido, pero solo es correcto cuando el problema tiene la propiedad greedy-choice y la subestructura óptima.
Nunca reconsideres elecciones pasadas — comprométete con la mejor opción inmediata y continúa.
def greedy_coins(amount, coins=(25, 10, 5, 1)):
result = []
for coin in coins: # largest first
while amount >= coin:
amount -= coin # take as many as possible
result.append(coin)
return result
greedy_coins(36) # -> [25, 10, 1]
Esto es óptimo para monedas estadounidenses, pero falla para conjuntos como {1, 3, 4} donde greedy da 4+1+1 para 6 en lugar de 3+3.
Ejemplos que funcionan: Dijkstra, Kruskal/Prim (MST), Huffman coding, interval scheduling.
Usualmente rápido — a menudo O(n log n) después de ordenar.
Greedy no siempre es correcto. Prueba la propiedad greedy-choice o pruébalo contra una línea de base brute-force/DP antes de confiar en él.
Cuando greedy se aplica, es mucho más simple y rápido que DP o brute force.
Saber cuándo es válido — y cuándo silenciosamente da respuestas incorrectas — es una marca de madurez algorítmica.
Muchos algoritmos de grafos fundamentales son greedy en el corazón.