PDF de programación - Tema 3. Algoritmos voraces - Parte I. Estructuras de Datos

Programa de teoría
Parte I. Estructuras de Datos.

1. Abstracciones y especificaciones.
2. Conjuntos y diccionarios.
3. Representación de conjuntos mediante árboles.
4. Grafos.

Parte II. Algorítmica.

1. Análisis de algoritmos.
2. Divide y vencerás.
3. Algoritmos voraces.
4. Programación dinámica.
5. Backtracking.
6. Ramificación y poda.

A.E.D.

Tema 3. Algoritmos voraces.

PARTE II: ALGORÍTMICA

Tema 3. Algoritmos voraces.
3.1. Método general.
3.2. Análisis de tiempos de ejecución.
3.3. Ejemplos de aplicación.

3.3.1. Problema de la mochila.
3.3.2. Planificación de tareas.

3.4. Heurísticas voraces.

3.4.1. El problema del viajante.
3.4.2. Coloración de grafos.

A.E.D.

Tema 3. Algoritmos voraces.

1

2

1

3.1. Método general.

• Los algoritmos voraces, ávidos o de avance

rápido (en inglés greedy) se utilizan normalmente
en problemas de optimización.
– El problema se interpreta como: “tomar algunos
elementos de entre un conjunto de candidatos”.

– El orden el que se cogen puede ser importante o no.

• Un algoritmo voraz funciona por pasos:
– Inicialmente partimos de una solución vacía.
– En cada paso se escoge el siguiente elemento para

añadir a la solución, entre los candidatos.

– Una vez tomada esta decisión no se podrá deshacer.
– El algoritmo acabará cuando el conjunto de elementos

seleccionados constituya una solución.

A.E.D.

Tema 3. Algoritmos voraces.

3

3.1. Método general.

• Ejemplo: “el viejo algoritmo de comprar patatas en

el mercado”.

¿Sí o no?

2 Kg.

A.E.D.

Tema 3. Algoritmos voraces.

4

2

3.1. Método general.

Características básicas del algoritmo:

• Inicialmente empezamos con una solución “vacía”,

sin patatas.

• Función de selección: seleccionar la mejor patata

del montón o la que “parezca” que es la mejor.

• Examinar la patata detenidamente y decidir si se

coge o no.

• Si no se coge, se aparta del montón.
• Si se coge, se mete a la bolsa (y ya no se saca).
• Una vez que tenemos 2 kilos paramos.

A.E.D.

Tema 3. Algoritmos voraces.

5

3.1. Método general.

• Se puede generalizar el proceso intuitivo a un

esquema algorítmico general.

• El esquema trabaja con los siguientes conjuntos

de elementos:
– C: Conjunto de elementos candidatos,

pendientes de seleccionar (inicialmente todos).
– S: Candidatos seleccionados para la solución.
– R: Candidatos seleccionados pero rechazados

después.

• ¿Qué o cuáles son los candidatos? Depende de

cada problema.

A.E.D.

Tema 3. Algoritmos voraces.

6

3

3.1. Método general.

• Esquema general de un algoritmo voraz:

voraz (C: CjtoCandidatos; var S: CjtoSolución)

S:= Ø
mientras (C ≠ Ø) Y NO solución(S) hacer

x:= seleccionar(C)
C:= C - {x}
si factible(S, x) entonces

insertar(S, x)

finsi

finmientras
si NO solución(S) entonces

devolver “No se puede encontrar solución”

finsi

A.E.D.

Tema 3. Algoritmos voraces.

7

3.1. Método general.

Funciones genéricas

• solución (S). Comprueba si un conjunto de candidatos es
una solución (independientemente de que sea óptima o no).

• seleccionar (C). Devuelve el elemento más “prometedor” del

conjunto de candidatos pendientes (no seleccionados ni
rechazados).

• factible (S, x). Indica si a partir del conjunto S y añadiendo

x, es posible construir una solución (posiblemente añadiendo
otros elementos).

• insertar (S, x). Añade el elemento x al conjunto solución.

Además, puede ser necesario hacer otras cosas.

• Función objetivo (S). Dada una solución devuelve el coste

asociado a la misma (resultado del problema de
optimización).

A.E.D.

Tema 3. Algoritmos voraces.

8

4

3.1. Método general.

• Algunos algoritmos ya estudiados usan la técnica de

avance rápido...

• Ejemplo 1. Algoritmo de Dijkstra:

– Cjto. de candidatos: todos los nodos del grafo.
– Función de selección: escoger el nodo candidato con

camino especial más corto.

– Función insertar: recalcular los caminos especiales.
– Solución: cuando se acaben los candidatos.

• Ejemplo 2. Algoritmo de Kruskal:

– Cjto. de candidatos: el conjunto de aristas con sus pesos.
– Función de selección: escoger la arista con menor coste.
– Función factible: que no forme un ciclo en la solución actual.
– Solución: cuando hayamos seleccionado n – 1 aristas.

• Ejemplo 3. Algoritmo de Prim: ¿?

A.E.D.

Tema 3. Algoritmos voraces.

9

3.2. Análisis de tiempos de ejecución.

3.1. Método general.

• El orden de complejidad depende del número de
candidatos, de las funciones básicas a utilizar, del
número de elementos de la solución.

• n: número de elementos de C. m: número de elementos

de una solución.

• Repetir, como máximo n veces y como mínimo m:

– Comprobar si el valor actual es solución: f(m).

Normalmente O(1) ó O(m).

– Selección de un elemento entre los candidatos: g(n).

– La función factible es parecida a solución, pero con una

Entre O(1) y O(n).

solución parcial h(n).

– La unión de un nuevo elemento a la solución puede

requerir otras operaciones de cálculo, j(n, m).

A.E.D.

Tema 3. Algoritmos voraces.

10

5

3.1. Método general.

SON 1,11 EUROS
SON 1,11 EUROS

AHÍ VAN 5 EUROS
AHÍ VAN 5 EUROS

TOMA EL CAMBIO,
TOMA EL CAMBIO,

3,89 EUROS
3,89 EUROS

• Problema del cambio de monedas.
Construir un algoritmo que dada una cantidad P devuelva esa
cantidad usando el menor número posible de monedas.

Disponemos de monedas
con valores de 1, 2, 5, 10,
20 y 50 céntimos de euro,
1 y 2 euros (€).

A.E.D.

Tema 3. Algoritmos voraces.

11

3.1. Método general.

• Caso 1. Devolver 3,89 Euros.

1 moneda de 2€, 1 moneda de 1€, 1 moneda de 50 c€, 1
moneda de 20 c€, 1 moneda de 10 c€ , 1 moneda de 5 c€ y
2 monedas de 2 c€. Total: 8 monedas.

• El método intuitivo se puede entender como un

algoritmo voraz: en cada paso añadir una moneda
nueva a la solución actual, hasta llegar a P.

A.E.D.

Tema 3. Algoritmos voraces.

12

6

3.1. Método general.
Problema del cambio de monedas

• Conjunto de candidatos: todos los tipos de monedas

disponibles. Supondremos una cantidad ilimitada de
cada tipo.

• Solución: conjunto de monedas que sumen P.
• Función objetivo: minimizar el número de monedas.

Representación de la solución:

• (x1, x2, x3, x4, x5, x6, x7, x8), donde xi es el número de

monedas usadas de tipo i.

• Suponemos que la moneda i vale ci.
• Formulación: Minimizar Σ xi, sujeto a Σ xi·ci = P, xi≥0

i=1..8

i=1..8

A.E.D.

Tema 3. Algoritmos voraces.

13

3.1. Método general.

Funciones del esquema:

• inicialización. Inicialmente xi= 0, para todo i= 1..8
• solución. El valor actual es solución si Σ xi·ci = P
• seleccionar. ¿Qué moneda se elige en cada paso

de entre los candidatos?

• Respuesta: elegir en cada paso la moneda de
valor más alto posible, pero sin sobrepasar la
cantidad que queda por devolver.
• factible. Valdrá siempre verdad.
• En lugar de seleccionar monedas de una en una,

usamos la división entera y cogemos todas las
monedas posibles de mayor valor.

A.E.D.

Tema 3. Algoritmos voraces.

14

7

3.1. Método general.

•

Implementación. Usamos una variable local act para
acumular la cantidad devuelta hasta este punto.

• Suponemos que las monedas están ordenadas de menor a

mayor valor.

DevolverCambio (P: entero; C: array [1..n] de entero;

seleccionar(C,P,X)

var X: array [1..n] de entero)
act:= 0
j:= n
para i:= 1,...,n hacer

X[i]:= 0

mientras act ≠ P hacer

inicialización

no solución(X)

mientras (C[j] > (P - act)) AND (j>0) hacer j:= j - 1
si j==0 entonces devolver “No existe solución”
no factible(j)
X[j]:= (P - act) / C[j]
act:= act + C[j]*X[j]
insertar(X,j)

finmientras

A.E.D.

Tema 3. Algoritmos voraces.

15

3.1. Método general.

• ¿Cuál es el orden de complejidad del algoritmo?
• ¿Garantiza siempre la solución óptima?
• Para este sistema monetario sí. Pero no siempre...

• Ejemplo. Supongamos
que tenemos monedas
de 100, 90 y 1. Queremos
devolver 180.
– Algoritmo voraz. 1 moneda de 100 y 80 monedas

de 1: total 81 monedas.

– Solución óptima. 2 monedas de 90: total 2

monedas.

A.E.D.

Tema 3. Algoritmos voraces.

16

8

3.2. Análisis de tiempos de ejecución.

• El orden de complejidad depende de:
– El número de candidatos existentes.
– Los tiempos de las funciones básicas utilizadas.
– El número de elementos de la solución.
– ...

• Ejemplo. n: número de elementos de C. m: número de

elementos de una solución.

• Repetir, como máximo n veces y como mínimo m:
– Función solución: f(m). Normalmente O(1) ó O(m).
– Función de selección: g(n). Entre O(1) y O(n).
– Función factible (parecida a solución, pero con una

solución parcial): h(m).

– Inserción de un elemento: j(n, m).

A.E.D.

Tema 3. Algoritmos voraces.

17

3.2. Análisis de tiempos de ejecución.
• Tiempo de ejecución genérico:

t(n,m) ∈ O(n*(f(m)+g(n)+h(m)) + m*j(n, m))

• Ejemplos:

– Algoritmos de Prim y Dijkstra: n candidatos, la función

de selección e inserción son O(n): O(n2).

– Devolución de monedas: podemos encontrar el

siguiente elemento en un tiempo constante (ordenando
las monedas): O(n).

• El análisis depende de cada algoritmo concreto.
• En la práctica los algoritmos voraces suelen ser

bastante rápidos, encontrándose dentro de
órdenes de complejidad polinomiales.

A.E.D.

Tema 3. Algoritmos voraces.

18

9

3.3. Ejemplos de aplicación.

3.3.1. Problema de la mochila.

20 Kg.

• Tenemos:

– n objetos, cada uno con un peso (pi) y un beneficio (bi)
– Una mochila en la que podemos meter objetos, con una

capacidad de peso máximo M.

• Objetivo: llenar la mochila, maximizando el beneficio de los

objetos transportados, y respetando la limitación de
capacidad máxima M.

• Los objetos se pueden partir en trozos.

A.E.D.

Tema 3. Algoritmos voraces.

19

3.3.1. Problema de la mochila.

Datos del problema:
• n: número de objetos disponibles.
• M: capacidad de la mochila.
• p = (p1, p2, ..., pn) pesos de los objetos.
• b = (b1, b2, ..., bn) beneficios de los objetos.

Representación de la solución:
• Una solución será de la forma S = (x1, x2, ..., xn), con 0≤xi≤1,

siendo cada xi la f