Algoritmos voraces

Los algoritmos voraces suelen ser bastante simples. Se emplean sobre todo para resolver problemas de optimización, como por ejemplo, encontrar la secuencia óptima para procesar un conjunto de tareas por un computador, hallar el camino mínimo de un grafo, etc. Habitualmente, los elementos que intervienen son: Para resolver el problema de optimización hay que encontrar un conjunto de candidatos que optimiza la función objetivo. Los algoritmos voraces proceden por pasos. Inicialmente el conjunto de candidatos es vacío. A continuación, en cada paso, se intenta añadir al conjunto el mejor candidato de los aún no escogidos, utilizando la función de selección. Si el conjunto resultante no es completable, se rechaza el candidato y no se le vuelve a considerar en el futuro. En caso contrario, se incorpora al conjunto de candidatos escogidos y permanece siempre en él. Tras cada incorporación se comprueba si el conjunto resultante es una solución del problema. Un algoritmo voraz es correcto si la solución así encontrada es siempre óptima. El esquema genérico del algoritmo voraz es:
funcion voraz(C:conjunto):conjunto
{ C es el conjunto de todos los candidatos }
S <= vacio    { S es el conjunto en el que se construye la solucion}
mientras  ¬solucion(S) y C <> vaciohacer
x <= el elemento de C que maximiza seleccionar(x)
C <= C \ {x}
si completable(S U {x}) entonces S <= S U {x}
si solucion(S)
entonces devolver S
si no devolver no hay solucion
El nombre voraz proviene de que, en cada paso, el algoritmo escoge el mejor "pedazo" que es capaz de "comer" sin preocuparse del futuro. Nunca deshace una decisión ya tomada: una vez incorporado un candidato a la solución permanece ahí hasta el final; y cada vez que un candidato es rechazado, lo es para siempre.
 

Ejemplo:

    Se desea pagar una cantidad de dinero a un cliente enmpleando el menor número posible de monedas. Los elementos del esquema anterior se convierten en: