4 devorador
Post on 14-Apr-2016
24 Views
Preview:
DESCRIPTION
TRANSCRIPT
Algoritmos devoradores
Juan Ramón Pérez Pérez
jrpp@uniovi.es
AlgoritmiaGrado en Ingeniería Informática del Software
Escuela de Ingeniería Informática – Universidad de Oviedo
Cómo cargar el barco para transportar el mayor valor
Problema de la mochila
n objetos / tipos y una “mochila” para transportarlos.
Para cada objeto i= 1,2, ...n tiene un peso wi y un valor vi.
La mochila puede llevar un peso que no sobrepase W.
Objetivo: maximizar valor de los objetos transportados respetando la limitación de peso.
Algoritmos voraces 3
Mochila con fragmentación
Suponemos que se pueden dividir los objetos.
Podemos asignar a la mochila una fracción xi del objeto i, con 0<= xi <= 1.
Algoritmos voraces 4
Correspondencia con la carga del barco
n tipos de minerales y el buque de carga es la “mochila” para transportarlos.
Para cada tipo i= 1,2, ...n tenemos un peso wi y un valor vi.
El carguero puede llevar un peso que no sobrepase W.
Objetivo: maximizar valor de los objetos transportados respetando la limitación de peso.
Algoritmos voraces 5
Algoritmos voraces
• Los algoritmos voraces se utilizan en problemas de
optimización.
• La solución se construye paso a paso.
• Basan la búsqueda de la solución óptima al problema en buscar en cada paso la solución localmente óptima.
• Para buscarla suelen emplear heurísticos, reglas basadas en algún tipo de conocimiento sobre el problema.
Elementos que se deben identificar en el problema
Conjunto de candidatos, las n entradas del problema.
Función de selección que en cada momento determine el candidato idóneo para formar la solución de entre los que aún no han sido seleccionados ni rechazados.
Función que compruebe subconjunto de candidatos es prometedor. Que sea posible encontrar una solución.
Función objetivo que determine el valor de la solución hallada.
Función que compruebe si un subconjunto es solución.
Toma de decisiones en algoritmos voraces
Estos algoritmos toman decisiones basándose en la
información que tienen disponible localmenteConfiando en que estas decisiones conduzcan a la solución buscada.
Nunca se reconsidera una decisión
No hay necesidad de emplear procedimientos de seguimiento para deshacer las decisiones.
Datos del problema concreto
n=5, W=100
Mineral 1 2 3 4 5
w (Tm) 10 20 30 40 50
v (x1000€) 20 30 66 40 60
Algoritmos voraces 9
• Candidatos: los n objetos.
• Estado del problema: vector X=(x1,x2,x3..xn).
• Función para comprobar si una solución es factible:
• Función de selección de un nuevo elemento.
Concretando esquema general para este problema
n
i
i Ww1
Algoritmos voraces 10
Heurístico para la función de selección (I)
• Tres posibilidades:
• Seleccionar objeto más valioso.
• Seleccionar objeto menos pesado.
• Seleccionar objeto cuyo valor por unidad de peso sea el mayor posible.
Decreciente vi 0 0 1 0,5 1 146
Creciente wi 1 1 1 1 0 156
Algoritmos voraces 11
Objetos 1 2 3 4 5 Valor
Heurístico para la función de selección (II)
• El último heurístico nos proporciona la solución óptima.
• Estos datos han servido de contraejemplo para demostrar que los dos primeros heurísticos no proporcionan la solución óptima.
Decreciente v/w 1 1 1 0 0,8 164
Objetos 1 2 3 4 5 Valor
Valor / peso 2 1,5 2,2 1 1,2
Algoritmos voraces 12
Código problema de la mochila// Se suponen los objetos ordenados por sus valores
static int resolverMochila ()
{
int n=peso.length; // Número de objetos / tipos
int cabe=m; // Límite de la mochila
int indice=0;
int valor=0;
while (cabe>0 && indice<n )
{
if (cabe>=peso[indice] ) //cabe entero
{
valor= valor+peso[indice]*beneficio[indice];
cabe= cabe-peso[indice];
indice++;
}
else // no cabe entero
{
valor=valor+cabe*beneficio[indice];
cabe=0;
indice++;
}
}
System.out.println("SE HAN CARGADO UN TOTAL DE "+(m-cabe)+" kg.");
return valor;
}Algoritmos voraces 13
Mochila 0/1
Mochila sin fragmentación
En la variante mochila 0/1 NO se pueden dividir los objetos.
Podemos asignar a la mochila un objeto i o no asignarlo, con xi = (0 | 1).
Algoritmos voraces 15
Contraejemplo para demostrar algoritmo NO óptimo
n=3, W=20
Heurístico v/w - v= 36
Valor óptimo= 40
Mineral 1 2 3
w (Tm) 10 10 12
v (x1000€) 20 20 36
v/w 2 2 3
Algoritmos voraces 16
Esquema general algoritmos voraces
public Estado realizarVoraz(List candidatos)
{
Estado estadoActual= new Estado();
while (!candidatos.esVacio() && !estadoActual.esSolucion())
{
/* Elige la primera componente
* que cumple un determinado heurístico */
Object x= SeleccionarCandidato(candidatos); // heurístico
if (estadoActual.esPrometedor(x))
estadoActual.add(x);
}
if (estadoActual.esSolucion())
return estadoActual;
else
return null; // No se ha encontrado una solución
}
Características algoritmos voraces
• La principal característica de estos algoritmos:
• Son rápidos y fáciles de implementar,
• Dependen totalmente de la calidad del heurístico
• Un heurístico de baja calidad podría proporcionar soluciones no óptimas
• En el extremo podría no proporcionar soluciones, aunque el problema las tenga.
• Son adecuados para aquellos casos en que:
• por la calidad del heurístico se encuentra la solución óptima,
• no se dispone de tiempo para aplicar otras técnicas que la encuentren.
• Hay muchos problemas que no se pueden resolver correctamente con este enfoque.
Algoritmos voraces 18
Ejemplos de algoritmos voraces
El problema del cambio (I)
• Diseñar un algoritmo para pagar una cierta cantidad, utilizando el menor número posible de monedas.
• Ejemplo:• Tenemos que pagar 2,89 €. Sistema monetario euro.
• Solución: 1 moneda de 2 €, 1 moneda de 50 cent, 1 moneda de 20 cent, 1 moneda de 10 cent, 1 moneda de 5 cent, 2 monedas de 2 cent. Solución óptima.
• Heurístico: Dar la moneda de mayor valor posible sin que exceda a lo que nos queda por devolver.
El problema del cambio (II)
• Dependiendo del sistema monetario y la disponibilidad de monedas, el heurístico no siempre nos proporciona una solución óptima.
• Lo demostramos con un contraejemplo:• Pagar 0,60 €.
• Monedas disponibles: 0,50 €, 0,20 €, 0,02 €.
• Solución heurístico: 0,50 € + 5· 0,02 € 6 monedas.
• Solución óptima: 3· 0,20 € 3 monedas.
• Este problema se podría resolver con backtracking, desarrollando todas las soluciones o cambios posibles.
Implementación del problema del cambio
public void calcularCambio(int cantidad)
{
int numMon= 0;
while (cantidad>0 && numMon<monedas.length)
{
// Estado es valido
if (cantidad-monedas[numMon]>=0)
{
// nueva moneda en el conjunto solución
solucion[numMon]++;
cantidad-= monedas[numMon];
}
else
// pasa a comprobar la moneda de valor inferior
numMon++;
}
}
Problema del viajante de comercio
• Dado un grafo no dirigido, ponderado y completo (sin ciclos), encontrar un ciclo simple que incluya todos los nodos (ciclo de Hamilton) y cuyo coste sea mínimo.
• Al ser completo se podría demostrar que el camino mínimo es un ciclo simple y, además, no depende del nodo de partida.
• Se supone que hay arista entre cualquier par de nodos.
• Cálculo del coste de cada arista: distancia euclídea entre los nodos.
Ejemplo del problema del viajante de comercio (I)
• 6 nodos situados en las coordenadas indicadas.
a=(0,0)
b=(4,3)
c=(1,7) d=(15,7)
e=(15,4)
f=(18,0)
Ejemplo del problema del viajante de comercio (II)
• Ordenamos todas las aristas de menor a mayor coste.
• Selección de una arista:
• La de menor coste.
• Un nodo no puede tener más de 2 aristas.
• No pueden formarse ciclos.
Posible Arista Coste
(d,e) 3
(a,b) 5
(b,c) 5
(e,f) 5
(a,c) 7,07
(d,f) 7,62
(b,e) 11,05
(b,d) 11,70
(c,d) 14,00
... ...
SI
NO
SI
SI
SI
SI
NO
NO
NO
Ejemplo del problema del viajante de comercio (II)
• Solución mediante un algoritmo voraz. Coste = 50.
a=(0,0)
b=(4,3)
c=(1,7) d=(15,7)
e=(15,4)
f=(18,0)
Pseudocódigo problema del viajante
public void calcularCamino()
{
int numAristas= 0;
// Inserta aristas de menor a mayor coste
for (Iterador iter= g.crearIterador(); iter.hayMas(); iter.siguiente())
colaPrioridad.insertar(iter.getActual());
while (numAristas<n-1) // Buscamos n-1 aristas
{
// Selecciona arista más corta de las que quedan
arista= colaPrioridad.extraer();
// No debe formar ciclos ni nodos con más de 2 aristas
if (!hayCiclos(arista) && !hayNodosConMas2(arista))
{
// Añade a las aristas seleccionadas
aristasSeleccionadas.insertar(arista);
numAristas++;
}
}
}
Ejemplo del problema del viajante de comercio (III)
• Solución óptima: Coste = 48,39.
a=(0,0)
b=(4,3)
c=(1,7) d=(15,7)
e=(15,4)
f=(18,0)
Otros problemas
• Árbol de búsqueda por algoritmo D.• Heurístico: “coger como raíz de la rama el nodo con
mayor probabilidad de acceso” solución no óptima.
• Árboles de recubrimiento mínimo para grafos:• Kruskal. Heurístico: “coger como siguiente arista la de
menor coste que quede por escoger” solución óptima.
• Prim. Heurístico: “se selecciona la arista de menor coste que parta del nodo” solución óptima.
top related