## 2.3 ALGORITMOS ÁVIDOS

Los algoritmos ávidos o voraces (Greedy Algorithms) son algoritmos que toman decisiones de corto alcance, basadas en información inmediatamente disponible, sin importar consecuencias futuras.

Suelen ser bastante simples y 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.

El esquema genérico del algoritmo voraz es:

funcion voraz(C:conjunto):conjunto
{ C es el conjunto de todos los candidatos }
S <= vacío { S es el conjunto en el que se construye la solución
mientras ¬solución(S) y C <> vacío hacer
x ← el elemento de C que maximiza seleccionar(x)
C ← C \ {x}
si completable(S U {x}) entonces S ← S U {x}
si solución(S)entonces devolver S
si no devolver no hay solución

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.

###