teoria de algoritmos

Teoría de Algoritmos
Tema 1. Planteamiento General
Tema 2. La Eficiencia de los Algoritmos
Tema 3. Algoritmos “Divide y Vencerás”
Tema 4. Algoritmos Voraces (“Greedy”)
Tema 5. Algoritmos para la Exploración de Grafos
(“Backtraking”, “Branch and Bound”)
Tema 6. Algoritmos basados en Programación Dinámica
Tema 7. Algoritmos Probabilísticos
1

Autor: Rafael Alcalá

Tema 4: AlgoritmosVoraces
(“Greedy”)

Bibibliografía:
G. BRASSARD, P. BRATLEY. Fundamentos de Algoritmia. Prentice Hall (1997).
T.H. CORMEN, C.E. LEISERSON, R.L. RIVEST. Introduction to Algorithms. The MIT Press
(1992)
E. HOROWITZ, S. SAHNI, S. RAJASEKARAN. Computer Algorithms. Computer Science
Press (1998).
J.L. VERDEGAY. Curso de Teoría de Algoritmos. Universidad de Granada (2004).

Autor: Rafael AlcaláObjetivos
„

Comprender la filosofía de diseño de algoritmos
voraces

„

Conocer las características de un problema
resoluble mediante un algoritmo voraz

„

Resolución de diversos problemas

„

Heurísticas voraces: Soluciones aproximadas a
problemas

Índice
„

EL ENFOQUE GREEDY

„

ALGORITMOS GREEDY EN GRAFOS

„

HEURÍSTICA GREEDY

Índice
EL ENFOQUE GREEDY„

„

Características Generales

„

Elementos de un Algoritmo Voraz

„

Esquema Voraz

„

Ejemplo: Problema de Selección de Actividades

„

Ejemplo: Almacenamiento Optimal en Cintas

„

Ejemplo: Problema de la Mochila Fraccional

„

ALGORITMOS GREEDY EN GRAFOS

„

HEURÍSTICA GREEDY

Características generales de
los algoritmos voraces
„

Se utilizangeneralmente para resolver problemas de
optimización: máximo o mínimo

„

Un algoritmo “greedy” toma las decisiones en función
de la información que está disponible en cada momento.

„

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

„

Suelen ser rápidos y fáciles de implementar.

„

No siempre garantizan alcanzar la solución óptima.

Características generales delos algoritmos voraces
¡Comete siempre todo
lo que tengas a mano!

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

Elementos de un algoritmo
voraz
Para poder resolver un problema con un enfoque greedy,
ha de reunir las 6 siguientes características, que no son
necesarias, pero si suficientes:

1. Conjunto de candidatos a seleccionar.
2. Conjunto de candidatosseleccionados
3. Función Solución: determina si los candidatos seleccionados
han alcanzado una solución.

Elementos de un algoritmo
voraz
4. Función de Factibilidad: determina si es posible completar el
conjunto de candidatos seleccionados con el siguiente
elemento seleccionado para alcanzar una solución al
problema.
5. Función Selección: determina el mejor candidato del conjunto
a seleccionar.6. Función Objetivo: da el valor de la solución alcanzada.

Esquema 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 ese elemento podríamosllegar 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 repetimos el procesoanterior hasta alcanzar la
solución.

Esquema de un algoritmo
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

El enfoque Greedy suele
proporcionar soluciones
óptimas, pero no hay
garantía de ello....