PDF de programación - Programación II - 5. Algoritmos voraces, heurísticos y aproximados

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 los Algoritmos Genéticos
Tema 12.Elección del esquema algorítmico

Programación II

© Mario Aldea Rivas

05/04/11

Tema 5. Algoritmos voraces, heurísticos y aproximados

Tema 5. Algoritmos voraces, heurísticos y

aproximados



1



Introducción

5.1.
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 recubrimiento mí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

Tema 5. Algoritmos voraces, heurísticos y aproximados

© Mario Aldea Rivas

05/04/11

2

5.1 Introducción
Los algoritmos voraces (Greedy) se utilizan típicamente para
resolver problemas de optimización:

5.1 Introducció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 y aproximados

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 a cambio
suma := suma + x
fhacer
retorna cambio
fmétodo

Programación II

© Mario Aldea Rivas

05/04/11

Tema 5. Algoritmos voraces, heurísticos y aproximados

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

5.2 Características generales

• Para construir la solució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 de selección: selecciona en cada etapa el mejor

candidato para incluirle en la solución parcial

Programación II

© Mario Aldea Rivas

05/04/11

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
retorna no 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

4

5

6

Tema 5. Algoritmos voraces, heurísticos y aproximados

Análisis del algoritmo “dar cambio”

5.2 Características generales

• Función a optimizar (en este caso minimizar):

f(x1,x2, ..,xn)=x1+x2+..+xn
Verificándose que Σxivi=c
- donde: xi es el número de monedas de la clase “i”, vi su
valor y c la cantidad a devolver

• Candidatos:

• Las monedas disponibles (p.e. 50, 20, 10, 5, 2 y 1 céntimos)
• Función solución: Σxivi=c
• Función de selección: la mayor de las monedas que verifican
Σxivi≤c
• Función factible: comprobar si la función de selección encuentra

alguna moneda

Programación II

Tema 5. Algoritmos voraces, heurísticos y aproximados

© Mario Aldea Rivas

05/04/11

7

5.3 Eficiencia de los algoritmos voraces

5.3 Eficiencia de los algoritmos voraces

Por lo general los algoritmos voraces son muy eficientes
Su eficiencia depende de:

• el número de iteraciones, que viene determinado por el tamaño

de la solución

• la eficiencia de las funciones “solución”, “factible” y

“selección”
- “solución” y “factible” suelen ser operaciones de tiempo

constante o dependientes de la longitud de la solución

- “selección” depende de la longitud del conjunto de

candidatos
- muchas veces es la causante de la mayor parte de la complejidad del

algoritmo

- en ocasiones convendrá preordenar el conjunto de candidatos, para que

la función de selección sea más rápida

Programación II

© Mario Aldea Rivas

05/04/11

Tema 5. Algoritmos voraces, heurísticos y aproximados

Eficiencia del algoritmo “dar cambio”

5.3 Eficiencia de los algoritmos voraces

Iteraciones

solución
factible
selección

cuando n es muy grande el número de

monedas tiende a n
suma == cent

existe x

mayor moneda que verifique

suma+x ≤ cent

Complejidad

O(n)

O(1)
O(1)
O(m)

Donde:
• n es la cantidad que se desea cambiar
• m es el número de monedas distintas

Complejidad del algoritmo: O(n)·O(m) = O(n) (ya que n>>m)

Programación II

© Mario Aldea Rivas

05/04/11

8

9

Tema 5. Algoritmos voraces, heurísticos y aproximados

5.4 Cuándo usar algoritmos voraces

5.4 Cuándo usar algoritmos voraces

Los algoritmos voraces suelen ser eficientes y fáciles de diseñar e
implementar
Pero no todos los problemas se pueden resolver utilizando
algoritmos voraces:

• a veces no encuentran la solución óptima
• o incluso no encuentran ninguna solución cuando el problema

sí la tiene

Ejemplo de problema para él que no funciona el algoritmo voraz:

• Dar cambio con el antiguo sistema monetario ingles

- corona (30p), florín (24p), chelín (12p), 6p, 3p, penique

• Solución del algoritmo voraz para 48p: 30p+12p+6p

- solución óptima: 24p+24p

Programación II

Tema 5. Algoritmos voraces, heurísticos y aproximados

Necesidad de prueba matemática

© Mario Aldea Rivas

05/04/11

10

5.4 Cuándo usar algoritmos voraces

Si queremos utilizar un algoritmo voraz para encontrar soluciones
óptimas

• debe probarse que el algoritmo encuentra la solución óptima en

todos los casos

• la prueba puede ser muy complicada

Un algoritmo que no garantice encontrar la solución óptima puede
ser útil en algunos casos para encontrar una solución aproximada

• los algoritmos voraces no óptimos a menudo encuentran

soluciones bastante aproximadas a las óptimas

• hablaremos de ellos al tratar los algoritmos heurísticos y

aproximados (apartado 5.8)

Programación II

Tema 5. Algoritmos voraces, heurísticos y aproximados

© Mario Aldea Rivas

05/04/11

11

5.4 Cuándo usar algoritmos voraces

Principio de optimalidad
Un problema verifica el principio de optimalidad si:

• en una secuencia óptima de decisiones toda subsecuencia ha

de ser también óptima

• P.e. el cálculo del camino más corto entre ciudades:

- el camino más corto SantanderMadrid pasa por Burgos

- unión de los caminos más cortos SantanderBurgos, BurgosMadrid

• No pasa igual con el camino más rápido:

- ir rápido en un tramo puede obligar a repostar en el siguiente
La mayoría de los problemas que verifican este principio pueden
resolverse utilizando algoritmos voraces

• puesto que es posible que exista una función de selección que

conduzca a la solución óptima

• pero no hay garantía de que se vaya a encontrar esa función (ni

siquiera de que exista)

Programación II

© Mario Aldea Rivas

05/04/11

12

Tema 5. Algoritmos voraces, heurísticos y aproximados

5.4 Cuándo usar algoritmos voraces

Principio de optimalidad (cont.)

Dar el cambio cumple el principio de optimalidad

• la vuelta óptima de 74 cent. es igual a la vuelta óptima de 50

cent. más la vuelta óptima de 24 cent.

• pero no es igual a la vuelta óptima de 43 cent. más la vuelta

óptima de 31 cent.
- de ahí la importancia de una buena función de selección
• el algoritmo para el sistema monetario inglés funcionaría

correctamente con una función de selección apropiada

Programación II

Tema 5. Algoritmos voraces, heurísticos y aproximados

5.5 El problema de la mochila
Descripción (the knapsack problem):

© Mario Aldea Rivas

05/04/11

13

5.5 El problema de la mochila

• disponemos de una mochila que soporta un
peso máximo P
• existen n objetos que podemos cargar en la
mochila, cada objeto tiene un peso pi y un valor vi
• el objetivo es llenar la mochila maximizando el valor de los
objetos que transporta
- suponemos que los objetos se pueden romper, de forma que
podemos llevar una fracción xi (0≤xi≤1) de un objeto

Matemáticamente:
• Maximizar Σxivi con la restricción Σxipi≤P
• donde vi>0, pi>0 y 0≤xi≤1 para 1≤i≤n
Aplicaciones: empresa de transporte, ...

Programación II

Tema 5. Algoritmos voraces, heurísticos y aproximados

© Mario Aldea Rivas

05/04/11

14

5.5 El problema de la mochila
El problema de la mochila (cont.)

El problema cumple el principio de optimalidad

• intentaremos resolverlo utilizando un algoritmo voraz
• el problema será encontrar la función de selección adecuada

retorna real[1..n]

El pseudocódigo de nuestro algoritmo será:
método mochila(real[1..n