AlgoritmosVoraces

Análisis y Diseño de Algoritmos

Ernesto Cárdenas Cangahuala

Semana 3: Algoritmos Voraces

Recordando:
¿Que haríamos si tenemos que
efectuar búsquedas u
ordenamientos?

Logro de aprendizaje
•

Al finalizar la sesión el estudiante:
• Explicará los algoritmos voraces, sus
alcances y limitaciones, mediante su
implementación y discusión con sus
compañeros

Algoritmo voraz (greedy)
• Seleccionanla opción de solución
(solución local) que tenga un costo
menor en la etapa de solución en la que
se encuentran, sin considerar si esa
opción es parte de una solución óptima
para el problema completo (solución
global)

Características
• 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
• Suelen ser rápidos y fáciles de implementar

“Greed, for lack of a better word, is good”

El termino greedy
es sinónimo de
voraz, codicioso,
ávido, glotón, ...

Elementos
• Para poder resolver un problema usando el enfoque voraz,
tendremos que considerar, tendremos que considerar 6
elementos:
1.Conjunto de candidatos (elementos seleccionables).
2. Solución parcial (candidatos seleccionados).
3. Función de selección (determina el mejor candidato del conjunto de
candidatos seleccionables).
4. Función de factibilidad (determina si es posible completar la solución parcial
para alcanzar una solución del problema).
5. Criterio que define lo que es una solución (indica si la solución parcialobtenida resuelve el problema).
6. Función objetivo (valor de la solución alcanzada).

Funcionamiento de un algoritmo voraz
• Un algoritmo Greedy procede siempre de la
siguiente manera:
• Se parte de un conjunto de candidatos seleccionados vacío: S =
∅
• De la lista de candidatos C que hemos podido identificar, con la
función de selección, se coge el mejor candidato posible,
• Vemos si con eseelemento podríamos llegar a constituir una
solución: Si se verifican las condiciones de factibilidad en S se
añade y se borra de C
• Si el candidato anterior no es válido, lo borramos de la lista de
candidatos posibles, y nunca mas es considerado
• Utilizamos la función solución. Si todavía no tenemos una solución
seleccionamos con la función de selección otro candidato y

Funcionamiento de unalgoritmo voraz
• Voraz(C : conjunto de candidatos) : conjunto solución
S=Ø
mientras C ≠Ø y no Solución(S) hacer
x = Seleccion(C)
C = C – {x}
si factible(S U {x}) entonces
S = S U {x}
fin si
fin mientras
si Solución(S) entonces
Devolver S
en otro caso
Devolver “No se encontró una solución”
fin si

Siempre habrá que analizar la
corrección del algoritmo para
demostrar si las soluciones son
validaso no

Escenario general
• Este esquema se aplica normalmente a
problemas de decisión y optimización
• Procede por pasos:
• En cada paso se toma una decisión de la que se
esta seguro
• Las decisiones tomadas nunca se reevalúan
• Se termina cuando no hay decisiones por tomar
• El algoritmo es correcto si se puede garantizar
que la solución encontrada siempre es optima

Algunos casos dealgoritmo
voraz

Cambio de moneda
• Se trata de devolver una cantidad de dinero con el menor
número posible de monedas.
• Se parte de:
• un sistema monetario (v1,v2,...,vn), y suficientes monedas de cada tipo
• un importe a devolver C.

• Formulación:
• Variables: X=(x1,x2,...,xn),
•

xi {0,1,..,C}

número de monedas de tipo i

• Restricciones: xi vi = C
• Función objetivo: xi

• Criterio voraz:
•Tomar el máximo de monedas (sin sobrepasar C) en orden decreciente de valor

Cambio de moneda
•
•

tipo moneda=(M25,M10,M5,M1)
función cambia(importe:nat; valor:vector[moneda] de nat)
devuelve vector[moneda] de nat
variable mon:moneda;
cambio:vector[moneda] de nat
principio
para todo mon en moneda hacer
cambio[mon]:=0
fin para;
para mon:=M25 hasta M1 hacer
mientras valor[mon]≤importe hacer...