Algortimos Voraces

Programación II
Bloque temático 1. Lenguajes de programación
Bloque temático 2. Metodología de programación
Bloque temático 3. Esquemas algorítmicos
Tema 4. Introducción a los Algoritmos
Tema 5. Algoritmos voraces, heurísticos y aproximados
Tema 6. Divide y Vencerás
Tema 7. Ordenación
Tema 8. Programación dinámica
Tema 9. Vuelta atrás
Tema 10.Ramificación y poda
Tema 11.Introducción a losAlgoritmos Genéticos
Tema 12.Elección del esquema algorítmico
Programación II

© Mario Aldea Rivas
05/04/11

1

Tema 5. Algoritmos voraces, heurísticos y aproximados

Tema 5. Algoritmos voraces, heurísticos y
aproximados
5.1. Introducción
5.2. Características generales
5.3. Eficiencia de los algoritmos voraces
5.4. Cuándo usar algoritmos voraces
5.5. El problema de la mochila
5.6. Árbol de recubrimientomínimo
5.7. Caminos mínimos (Dijkstra)
5.8. Algoritmos heurísticos y aproximados
5.9. Heurístico para coloreado de grafos
5.10. Heurístico para el problema del viajante
5.11. Aproximado para el problema del viajante
5.12. Aproximado para el llenado de cajas
5.13. Bibliografía
Programación II

© Mario Aldea Rivas
05/04/11

2

Tema 5. Algoritmos voraces, heurísticos y aproximados
5.1 Introducción5.1 Introducción
Los algoritmos voraces (Greedy) se utilizan típicamente para
resolver problemas de optimización:
• minimizar o maximizar, bajo determinadas condiciones, el valor
de una función del tipo: f(x1,x2,..,xn)=c1x1+c2x2+..+cnxn
La solución se va construyendo en etapas:
• en cada etapa se añade un nuevo elemento a la solución parcial
- el que nos parece el mejor candidato en ese momento
•las decisiones tomadas nunca se revisan
- voracidad: se consume el mejor elemento lo antes posible sin
pensar en futuras consecuencias
• al final de cada etapa se verifica si la solución parcial ya
constituye una solución total para el problema
Ejemplo: “dar cambio utilizando el mínimo número de monedas”
Programación II

© Mario Aldea Rivas
05/04/11

3

Tema 5. Algoritmos voraces, heurísticos yaproximados
5.1 Introducción

Algoritmo voraz para “dar cambio”
Solución: vamos incluyendo secuencialmente la moneda de
mayor valor posible de forma que todavía no superemos la
cantidad a devolver
método daCambio(cent : entero) retorna monedas
cambio := ∅
suma := 0
mientras suma != cent hacer
x := mayor moneda que verifique suma+x ≤ cent
si no existe x entonces
retorna no hay solución
fsi
añade x acambio
suma := suma + x
fhacer
retorna cambio
fmétodo
Programación II

© Mario Aldea Rivas
05/04/11

4

Tema 5. Algoritmos voraces, heurísticos y aproximados
5.2 Características generales

5.2 Características generales
Los algoritmos voraces suelen tener las siguientes propiedades:
• Se trata de resolver un problema de forma óptima
- normalmente se imponen algunas restricciones
• Para construir lasolución se dispone de un conjunto de
candidatos
• Durante el desarrollo del algoritmo se van formando dos
conjuntos: los candidatos seleccionados y los rechazados
• Función solución: comprueba si los candidatos seleccionados
hasta el momento constituyen una solución al problema
• Función factible: comprueba si un conjunto de candidatos
podría llegar a convertirse en solución
• Función deselección: selecciona en cada etapa el mejor
candidato para incluirle en la solución parcial
Programación II

© Mario Aldea Rivas
05/04/11

5

Tema 5. Algoritmos voraces, heurísticos y aproximados
5.2 Características generales

Esquema genérico de un algoritmo voraz
método voraz retorna conjunto
C := candidatos
S := ∅ // irá guardando la solución
mientras no_es_solución(S) hacer
si C == ∅ entonces
retornano hay solución
fsi
x := selecciona(C)
elimina x de C // no se vuelve a considerar
si factible(S+x) entonces
añade x a S
fsi
fhacer
retorna S // retorna la solución alcanzada
fmétodo
Programación II

© Mario Aldea Rivas
05/04/11

6

Tema 5. Algoritmos voraces, heurísticos y aproximados
5.2 Características generales

Análisis del algoritmo “dar cambio”
• Función a optimizar (en este caso...