Algoritmos exactos
Algoritmo exacto:
Algoritmos aproximados
Algoritmo que siempre calcula una solucin
ptima para un problema de optimizacin
Tcnicas para disear algoritmos exactos:
Tcnica voraz
Tcnicas de bsqueda:
Vuelta atrs
Ramificacin y poda
Programacin dinmica
Heursticas
Algoritmos no exactos:
Algoritmos que no siempre calculan una solucin
ptima (slo para algunos datos)
Algoritmos basados en una funcin de
seleccin:
Diseo similar a los voraces, pero no exactos:
Heursticas:
Algoritmos sencillos y eficientes, a menudo basados en el sentido
comn
Algoritmos aproximados:
Calculan una solucin cercana a la ptima y acotada
Coloreado de un grafo
Nmero mnimo de colores para colorear
los nodos de un grafo de forma que los
nodos adyacentes tengan colores
distintos
3
Ejemplo:
1
5
4
Coloreado de un grafo
Algoritmo heurstico:
Se ordenan los nodos y los colores
Se toma un color y se intentan colorear todos
los nodos posibles con el primer color
Se toma en siguiente color y se intentan
colorear todos los nodos posibles an no
coloreados
As sucesivamente hasta colorear todos los
nodos
Coloreado de un grafo
Casos extremos:
Orden que permite encontrar el nmero
mnimo n de colores:
Se disponen en primer lugar los nodos coloreados
en la solucin ptima con el color 1, despus los
nodos coloreados con el color 2 y as
sucesivamente hasta el ltimo color n
Coloreado de un grafo
Ejemplo:
3
1
5
4
Orden 1-3-4-2-5: 2 colores
Orden 1-5-2-3-4: 3 colores
Coloreado de un grafo
Casos extremos:
Dado un grafo bipartito, orden que hace que
esta heurstica necesite 2 colores: 1, 3, ,
2n-1, 2, 4, , 2n
Coloreado de un grafo
Problema del viajante
Casos extremos:
Ciclo hamiltoniano ms corto
Ejemplo:
Dado un grafo bipartito, orden que hace que
esta heurstica necesite n colores: 1, 2, ,
2n-1, 2n
1
2
Solucin ptima: 1-2-3-6-4-5-1,
3+8+20+15+5+7 = 58
Tomar siempre el arco de longitud menor a algn nodo
no visitado
25
10
7 11
26
20 4
18
Problema del viajante
Ejemplo:
26 9 12
15
Algoritmo heurstico:
10
7 11
25
Problema del viajante
Ejemplo:
12
20 4
15
3
10
7 11
20 4
25
3
9
6
4
Solucin heurstica: 1-2-3-5-4-6-1,
=
5
18 3+8+4+5+15+25
5
60
26 9 12
15
18
3
9
Solucin heurstica: 1-2-3-5-4-6-1,
3+8+4+5+15+25 = 60
Solucin ptima: 1-2-3-6-4-5-1, 3+8+20+15+5+7
= 58
Problema del viajante
Algoritmos aproximados
Justificacin:
Haciendo la distancia entre el primer y el
ltimo nodo arbitrariamente larga,
tenemos una solucin arbitrariamente
mala
Problema del viajante mtrico:
Problemas para los que slo hay algoritmos
ineficientes
Si es aceptable una solucin subptima pero buena
Clases de algoritmos aproximados:
Algoritmo aproximado c-absoluto:
d(i,j) d(i,k) + d(k,j)
La solucin calculada dista de la ptima en un valor mximo
de c
Esta propiedad permite sustituir dos arcos
(i,k) y (k,j) por otro (i,j) igual o menor
Algoritmo aproximado -relativo:
La solucin calculada dista de la ptima en un error relativo
mximo de
Problema del viajante
Problema del viajante
Algoritmo aproximado:
Algoritmo aproximado:
rbol de recubrimiento de
coste mnimo (ARM):
3+7+4+5+15 = 34
Long. ARM Long. ciclo
hamiltoniano ptimo
Un recorrido del rbol de
recubrimiento de coste
mnimo tiene el doble de
longitud:
1-2-1-5-3-5-4-6-4-5-1, 68
7
4
4
15
Pueden suprimirse las
visitas a nodos ya
visitados, que equivale
a sustituir dos arcos
por uno menor o igual
1
9
7
4
25
18
5
4
15
Problema del viajante
Problema del viajante
Algoritmo aproximado:
Resulta el recorrido en
preorden del ARM:
1-2-5-3-4-6-1,
3+9+4+9+15+25 = 65
Algoritmo aproximado:
3
1
25
9
5
9
Algoritmo aproximado 1-relativo:
Long. recorrido en preorden de ARM [Link]
[Link].
Como mximo tiene el doble de coste que la
solucin ptima
15
Problema del viajante
Formulacin para su resolucin por bsqueda o
por programacin dinmica:
Sea h(i,S) la longitud del camino mnimo desde el
nodo i hasta 1 que pase exactamente una vez por
cada nodo de S:
Ecuaciones:
Problema de la mochila 0/1
Algoritmos heursticos o aproximados:
Algoritmo heurstico:
El algoritmo voraz (B/P) ptimo en 81% casos
No proporciona ninguna cota en la diferencia o
proporcin con respecto a la solucin ptima
Ejemplo:
p1=1, b1=2
p2=x, b2=x, para un valor x arbitrariamente grande
Llamada inicial: h(1,S-{1})
i{1..n}, Spartes de N-{1} de tamao 2 n-1!
Podemos probar otras heursticas con GreedEx:
El algoritmo voraz B ptimo en 85% casos!
Problema de la mochila 0/1
Algoritmos heursticos o aproximados:
Algoritmo aproximado:
Tomar el mximo entre la solucin voraz y el
objeto de mayor beneficio absoluto
Algoritmo aproximado -relativo:
Como mnimo calcula la mitad de beneficio de la
solucin ptima
Vase clase Mochilas_0_1
Sistema OptimEx
Tabla de resumen:
Nmero de ejecuciones
Porcentajes de casos en que se han obtenido resultados
ptimos, subptimos o superptimos
Desviacin, como porcentaje, de los resultados no ptimos con
respecto a las soluciones ptimas
Sistema OptimEx
Sistema para la experimentacin y comparacin de
algoritmos de optimizacin:
Parecido a GreedEx, pero:
Genrico
Sin visualizaciones
Sin explicaciones
Gua de uso
Problema de seleccin de
actividades
Implementado en GreedEx
Existen algoritmos voraces ptimos:
Orden creciente de fin de actividad
Orden decreciente de comienzo de actividad
Algoritmo aproximado:
Orden creciente de duracin de actividad
Diferencia relativa la mitad (1-relativo)
Sin embargo:
Calcula la solucin ptima en ms del 95% de los casos
En la mayor parte de los casos subptimos slo difiere en 1
actividad
Problema del llenado de cajas (a)
Problema de maximizacin
Sean objetos de pesos ps={2,3,4,5} y 2
cajas de capacidad c=7:
Nmero mximo de objetos que pueden
meterse: 4, {2,5},{3,4}
Problema del llenado de cajas (a)
Algoritmo aproximado para k cajas:
Se ordenan los objetos en orden creciente de
peso y se van metiendo en cada caja y en
orden todos los objetos que se pueda:
Solucin ej. anterior, objetos de pesos ps={2,3,4,5}
y 2 cajas de capacidad c=7: 3 objetos, {2,3},{4}
Algoritmo aproximado 1-absoluto
Vase versiones masObjetos
de clase LlenadoCajas
Problema del llenado de cajas (b)
Problema de minimizacin
Sean objetos de pesos ps={5,2,4,1,8} y
capacidad de cada caja c=10:
Nmero mnimo de cajas para meter los
objetos: 2, {5,4,1}, {2,8}
Problema del llenado de cajas (b)
Algoritmo de vuelta atrs:
rbol de bsqueda creado, ps={5,2,4,1,8},c=10:
Vase versin menosCajasBack
de clase LlenadoCajas
Problema del llenado de cajas (b)
Algoritmos aproximados:
Igual a la funcin de seleccin de la versin anterior
del problema
Se ordenan los objetos en orden creciente de peso y
se van metiendo en cada caja y en orden todos los
objetos que se pueda:
Sean objetos de pesos {2,3,4,5} y cajas de capacidad 7.
Solucin: 3 cajas, {2,3},{4},{5}. Solucin ptima: 2, {2,5},
{3,4}
Algoritmo aproximado con un valor menor o igual que
Vase versin menosCajasAprox1
2+opt17/10
de clase LlenadoCajas
Problema del equilibrado de carga
Problema de minimizacin
Sean tareas de tiempos ts={2,3,4,6,2,2} y
3 procesadores:
Se desea repartir las tareas entre los
procesadores de forma equilibrada
Mxima carga de algn procesador: 7, {6},
{4,2},{3,2,2}
Problema del llenado de cajas (b)
Algoritmos aproximados:
Se ordenan los objetos en orden decreciente de peso
y se va metiendo cada uno en la primera caja donde
cabe:
Solucin ejemplo anterior, cajas de capacidad 7: 2 cajas,
{5,2},{4,3}
Contraejemplo: sean objetos de pesos {6,5,3,2,2,2} y cajas
de capacidad 10. Solucin: 3 cajas, {6,3},{5,2,2},{2}.
Solucin ptima: 2 cajas, {6,2,2},{5,3,2}
Algoritmo aproximado con un valor menor o igual que
4+opt11/9
Vase versin menosCajasAprox2
de clase LlenadoCajas
Problema del equilibrado de carga
Algoritmos de aproximacin:
Cada tarea se asigna a la mquina que tiene menos
carga:
Sean tareas de tiempos ts={2,3,4,6,2,2} y 3 procesadores.
Solucin: mxima carga 8, {6,2},{3,2},{4,2}. Solucin ptima:
7, {6},{4,2},{3,2,2}
Algoritmo aproximado con una diferencia relativa del doble
(1-relativo)
Vase versin equilibrarCargaAprox1
de clase EquilibradoCargas
Problema del equilibrado de carga
Algoritmos de aproximacin:
Las tareas se ordenan en orden decreciente de
duracin y se van asignando a la mquina que tiene
menos carga:
Sean tareas de tiempos ts={2,3,4,6,2,2} y 3 procesadores.
Solucin (ptima): mxima carga 7, {6},{4,2},{3,2,2}
Sean tareas de tiempos ts={3,3,3,4,5} y 5 procesadores.
Solucin: mxima carga 10, {5,3},{4,3,3}. Solucin ptima: 9,
{5,4},{3,3,3}
Algoritmo aproximado con una diferencia relativa de 3/2
(-relativo)
Vase versin equilibrarCargaAprox2
de clase EquilibradoCargas
