1. No category

Algoritmos Voraces
Algoritmos Avanzados
Introducción
Las personas glotonas (voraces) intentan coger
tanto como pueden en cada momento.
Los algoritmos voraces intentar “coger” la
solución que parece más adecuada en ese mismo
momento.
Los buenos algoritmos voraces pueden resolver
correctamente los problemas.
Esquema Voraz
En cada paso se toma una decisión de la que
estamos seguros.
Las decisiones tomadas nunca se
reconsideran
el algoritmo termina cuando no quedan
decisiones por tomar.
el algoritmo es correcto si podemos
garantizar que la solución encontrada es
siempre óptima;
Introducción (cont ...)
SU SOLUCION
SOLO ACEPTA
COMO RESPUESTA
SI
NO
Conjunto de algoritmos que toman decisiones basándose en la
información disponible inmediatamente
Sin tener en cuenta los efectos de las decisiones
Algoritmo general
Elementos
Conjunto de candidatos: dará lugar a seleccionados y
rechazados
Función de solución: comprueba si el conjunto de
seleccionados es ya una solución
Función de factibilidad: comprueba si el conjunto de
candidatos seleccionados es factible (si es posible completar
la solución)
Función de selección: candidato más prometedor de los
no seleccionados
Función objetivo: devuelve la solución al problema
El problema del cambio
Se trata de devolver una
cantidad de dinero con el menor
número posible de monedas.
Debemos adaptar el problema al
algoritmo general e introducir mejoras
Elementos
Monedero
200 100 50
20
10
5
2
1
0.5 0.2
5
1
2
8
9
1
2
1
Cambio:
3
180.70
4
Función factibilidad
M(1,i)<=cambio
M(2,i)>0
¿Existen monedas de éste corte?
Función objetivo
Σ(M(1,i)*M(2,i))=cambio
Conjunto Solución
200 100 50
20
10
0
1
1
1
1
5
2
Al final mostrar el monedero
1
0.5 0.2
1
1
El problema no siempre tiene solución,
en tal caso se debe mostrar el monedero
como al inicio y el conjunto solución
cereado
El problema de la mochila
Sean:
Cargar una mochila de
capacidad W maximizando el
valor de su carga
n objetos fraccionables.
(p1,...,pn), pesos.
(b1,...,bn), beneficios.
mochila con capacidad C.
Cuando los objetos se pueden fraccionar
Ejemplo del problema de la
mochila
n=3
C=17
(b1, b2, b3)=(40, 36, 22)
(p1, p2, p3)=(15, 12, 8)
Tres soluciones factibles:
(i) (1,1/6,0)
(ii) (0,3/4,1)
(iii) (0,1,5/8)
46
49
49,75
Σ bixi
1≤i≤3
Elección del criterio correcto
1ª estrategia: elegir el objeto con mayor beneficio total (el
primero).
Sin embargo, la mochila se llena muy rápidamente con poco
beneficio total.
2ª estrategia: elegir el objeto que llene menos la mochila,
para acumular beneficios de un número mayor de objetos.
Sin embargo, es posible que se elija un objeto con poco
beneficio simplemente porque pesa poco.
3ª estrategia, que es la óptima, es tomar siempre el objeto
que proporcione mayor beneficio por unidad de peso.
Formulación:
Variables:
X=(x1,x2,...,xn),
0 ≤ xi ≤ 1 “porción que tomo del objeto i”
Σ xi
Restricciones:
Función objetivo:
pi ≤ C
F(X) = Σ xi bi
función mochila(benef,peso,cap)
variables resto:real; i:entero;
sol:vectReal
principio
para todo i en 1..n hacer
sol[i]:=0.0 {inicializar solución}
fpara;
resto:=cap; {capacidad restante}
i:=1;
mq (i≤n) and (peso[i]≤resto) hacer
sol[i]:=1;
resto:=resto-peso[i];
i:=i+1
fmq;
si i≤n entonces sol[i]:=resto/peso[i] fsi;
devuelve sol
Fin función
Fin