Algoritmo voraz

En ciencias de la computación, un algoritmo voraz (también conocido como codicioso, goloso, ávido, devorador o greedy) es una estrategia de búsqueda por la cual se sigue una heurística consistente en elegir la opción óptima en cada paso local con la esperanza de llegar a una solución general óptima.

Este esquema algorítmico es el que menos dificultades plantea a la hora de diseñar y comprobar su funcionamiento.

Se utilizan generalmente para resolver problemas de optimización (obtener el máximo o el mínimo).

Toman decisiones en función de la información que está disponible en cada momento.

Una vez tomada la decisión, ésta no vuelve a replantearse en el futuro.

Por lo tanto, siempre habrá que estudiar la corrección del algoritmo para demostrar si las soluciones obtenidas son óptimas o no.

Se elimina ese elemento del conjunto de candidatos (

En caso de que así sea, se incluye ese elemento en

Un algoritmo voraz determina el mínimo número de monedas que debe devolverse en el cambio . En la figura se muestran los pasos que un ser humano debería seguir para emular a un algoritmo voraz para acumular 36 céntimos usando solamente monedas de valores nominales de 1, 5, 10 y 20. La moneda del mayor valor menor que el resto debido es el óptimo local en cada paso. Nótese que en general el problema de devolución del cambio requiere programación dinámica o programación lineal para encontrar una solución óptima. Sin embargo, muchos sistemas monetarios, incluyendo el euro y el dólar estadounidense , son casos especiales donde la estrategia del algoritmo voraz da con la solución óptima.