Un algoritmo voraz toma en cada paso la elección que parece mejor y nunca vuelve atrás. Es rápido y sencillo, pero solo es correcto cuando el problema tiene la estructura adecuada.
Un clásico que funciona: selección de actividades
Supón que tienes una lista de reuniones con hora de inicio y de fin, y quieres programar el mayor número posible sin solapamientos. Se ordenan por hora de fin, se toma la primera y luego se toma siempre la siguiente reunión que empiece después de que termine la anterior. Elegir el fin más temprano deja más espacio para el resto.
Un clásico que falla: algunos sistemas de monedas
Con monedas de 1, 3 y 4 y un objetivo de 6, el algoritmo voraz toma 4 + 1 + 1, es decir, tres monedas. La mejor respuesta es 3 + 3, con dos. El enfoque voraz funciona con muchas monedas reales, pero no con todos los conjuntos de monedas.
Cómo comprobar si es seguro
Importan dos propiedades. La propiedad de elección voraz dice que alguna solución óptima comienza con la elección voraz. La subestructura óptima dice que lo que queda tras esa elección es un problema más pequeño del mismo tipo. Una técnica de demostración habitual es el argumento de intercambio: mostrar que sustituir la primera elección de una solución óptima por la elección voraz no la empeora.
Algoritmos voraces que ya conoces
Los algoritmos de Kruskal y Prim para árboles de expansión mínima son voraces y correctos. El algoritmo de Dijkstra para caminos mínimos también lo es, y es correcto cuando los pesos de las aristas no son negativos.
Consejo práctico
Prueba las ideas voraces con contraejemplos pequeños antes de confiar en ellas. Si aparece uno, el problema suele requerir programación dinámica.
Continúa con el libro
Consulta el tratamiento completo, los ejemplos y los ejercicios en Algoritmos explicados con claridad.
Adaptado de Algoritmos explicados con claridad, publicado por Choral Software. Texto del artículo y ejemplos originales © 2026 Choral Software. Todos los derechos reservados.