AlgoritmosVoraces

Algoritmos Voraces
(ávidos, glotones, “greedy”)

Análisis y Diseño de Algoritmos

Algoritmos Voraces

Los algoritmos voraces suelen ser bastante simples. Se
empleansobre todo para resolver problemas de
optimización, como por ejemplo, hallar el camino mínimo de
un grafo o devolver cambio.

Análisis y Diseño de Algoritmos

AlgoritmosVoraces

•

•

Habitualmente los elementos que intervienen son: un
conjunto o lista de candidatos (vértices del grafo,
denominaciones).!
Un conjunto de decisiones yatomadas (candidatos ya
escogidos).

Análisis y Diseño de Algoritmos

Algoritmos Voraces

•
•

•
•
•

Para resolver el problema, los algoritmos voraces proceden
por pasos. !
Segeneran los posibles candidatos y en cada paso se elige si
un candidato cumple con la solución a una parte de ella
(función de selección).!
Si hay un candidato que nocumple, se rechaza y nunca más
se vuelve a elegir.!
Cada vez que ingresa un nuevo candidato a la lista de
decisiones, se comprueba si tal conjunto resuelve el problema.!Generalmente se ordenan los candidatos de mayor a menor
para ir devorando del más grande al más pequeño.

Análisis y Diseño de Algoritmos

Algoritmos Voraces

•
•
•
•

Sonalgoritmos de órdenes bajos.!
Se basan en hacer elecciones a partir de un conjunto de
opciones.!
La función selección determina la mejor opción del conjunto
deopciones.!
Ejemplo de este tipo de algoritmos: Kruskal, Dijskstra, Prim

Análisis y Diseño de Algoritmos

Programa

Implementar un algoritmo voraz, el cual devuelva
cambio de unamáquina despachadora de refresco,
la cual contiene las siguientes denominaciones:!
!

$50

$20

$10

$5

$2

$1

10

10

5

5

10

10

Análisis y Diseño de Algoritmos