Publicado el 20 de Mayo del 2018
1.075 visualizaciones desde el 20 de Mayo del 2018
503,8 KB
50 paginas
Creado hace 10a (04/03/2015)
Programa de teoría
Algoritmos y Estructuras de Datos II
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. II
Tema 3. Algoritmos voraces
1
ALGORITMOS Y E. D. II
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. II
Tema 3. Algoritmos voraces
2
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. II
Tema 3. Algoritmos voraces
3
3.1. Método general
• Ejemplo: “el viejo algoritmo de comprar patatas en el mercado”.
• 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.
• ¿Cuál o cuáles son los candidatos? Depende de
cada problema.
A.E.D. II
Tema 3. Algoritmos voraces
4
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. II
Tema 3. Algoritmos voraces
5
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. II
Tema 3. Algoritmos voraces
6
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. II
Tema 3. Algoritmos voraces
7
3.1. Método general
SON 1,11 EUROS
AHÍ VAN 5 EUROS
TOMA EL CAMBIO,
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. II
Tema 3. Algoritmos voraces
8
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. II
Tema 3. Algoritmos voraces
9
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. II
Tema 3. Algoritmos voraces
10
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. II
Tema 3. Algoritmos voraces
11
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;
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)
seleccionar(C,P,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]
finmientras
insertar(X,j)
A.E.D. II
Tema 3. Algoritmos voraces
12
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. II
Tema 3. Algoritmos voraces
13
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) u 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. II
Tema 3. Algoritmos voraces
14
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. II
Tema 3. Algoritmos voraces
15
3.3. Ejemplos de aplicación
3.3.1. Problema de la mochila no 0/1
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. II
Tema 3. Algoritmos voraces
16
3.3.1. Problema de la mochila no 0/1
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 fracción escogida del objeto i.
Formulación matemática:
• Maximizar xi bi, sujeto a la restricción xi pi ≤ M, y 0 ≤ xi ≤ 1
i=1..n
i=1..n
A.E.D. II
Tema 3. Algoritmos voraces
17
3.3.1. Problema de la mochila no 0/1
• Ejemplo: n = 3; M = 20
p = (18, 15, 10)
b = (25, 24, 15)
20 Kg.
18 kg
15 kg
PVP 25
PVP 24
10 kg
PVP 15
• Solución 1: S = (1, 2/15, 0)
18 kg
Beneficio total = 25 + 24*2/15 = 28,2
2 kg
PVP 25
PVP 24
• Solución 2: S = (0, 2/3, 1)
Beneficio total = 15 + 24*2/3 = 31
10 kg
PVP 24
10 kg
PVP 15
A.E.D. II
Tema 3. Algoritmos voraces
18
3.3.1. Problema de la mochila no 0/1
• El problema se ajusta bien a la idea de algoritmo voraz.
• Diseño de la solución:
– Candidatos: cada uno de los n objetos de partida.
– Función solución: tendremos una solución si hemos
introducido en la mochila el peso máximo M, o si se han
acabado los objetos.
– Función seleccionar: escoger el objeto más prometedor.
– Función factible: será siempre cierta (podemos añadir trozos
de objetos).
– Añadir a la solución: añadir el objeto entero si cabe, o en otro
caso la proporción del mismo que quede para completarla.
– Función objetivo: suma de los beneficios de cada candidato
por la proporción seleccionada del mismo.
• Queda por definir la función de selección. ¿Qué criterio
podemos usar para seleccionar el objeto más prometedor?
A.E.D. II
Tema 3. Algoritmos voraces
19
3.3.1. Problema de la mochil
Comentarios de: Tema 3. Algoritmos voraces - Algoritmos y Estructuras de Datos II (0)
No hay comentarios