Download Ramificar-acotar - Elisa Schaeffer

Técnicas de diseño de algoritmos
Ramificar-acotar
Dra. Elisa Schaeffer
elisa.schaeffer@gmail.com
PISIS / FIME / UANL
Ramificar-acotar– p. 1
Optimización combinatorial
Solución ingenua: hacer una lista completa de todas las
soluciones factibles y evaluar la función objetivo para cada
una, eligiendo al final la solución cual dio el mejor valor.
Ramificar-acotar– p. 2
Optimización combinatorial
Solución ingenua: hacer una lista completa de todas las
soluciones factibles y evaluar la función objetivo para cada
una, eligiendo al final la solución cual dio el mejor valor.
La complejidad de ese tipo de solución es por lo menos
Ω (|F |) donde F es el conjunto de soluciones factibles.
Ramificar-acotar– p. 2
Optimización combinatorial
Solución ingenua: hacer una lista completa de todas las
soluciones factibles y evaluar la función objetivo para cada
una, eligiendo al final la solución cual dio el mejor valor.
La complejidad de ese tipo de solución es por lo menos
Ω (|F |) donde F es el conjunto de soluciones factibles.
El número de soluciones factibles suele ser algo como
Ω (2n ), por lo cual el algoritmo ingenuo tiene complejidad
asintótica exponencial.
Ramificar-acotar– p. 2
Opciones
Si uno tiene un método eficiente para generar en una
manera ordenada soluciones factibles y rápidamente
decidir sí o no procesarlos (en el sentido de podar-buscar),
no es imposible utilizar un algoritmo exponencial.
Otra opción es buscar por soluciones aproximadas, o
sea, soluciones cerca de ser óptima sin necesariamente
serlo.
Ramificar-acotar– p. 3
Heurísticas
Una manera de aproximación es utilizar métodos
heurı́sticos, donde uno aplica una regla simple para
elegir candidatos.
Si uno siempre elije el candidatos que desde el punto de
vista de evaluación local se ve el mejor, la heurística es
voraz.
Ramificar-acotar– p. 4
Solución inicial factible
Muchos problemas de optimización combinatorial
consisten de una parte de construcción de cualquier
solución factible.
Ramificar-acotar– p. 5
Solución inicial factible
Muchos problemas de optimización combinatorial
consisten de una parte de construcción de cualquier
solución factible.
Esta construcción tiene la misma complejidad que el
problema de decisión de la existencia de una solución
factible.
Ramificar-acotar– p. 5
Solución inicial factible
Muchos problemas de optimización combinatorial
consisten de una parte de construcción de cualquier
solución factible.
Esta construcción tiene la misma complejidad que el
problema de decisión de la existencia de una solución
factible.
No es posible que sea más fácil solucionar el problema de
optimización que el problema de decisión a cual está
basado.
Ramificar-acotar– p. 5
Ejemplo: M ST
Meta: Encontrar un árbol cubriente mínimo en un grafo
ponderado no dirigido.
Para construir un árbol cubriente cualquiera – o sea, una
solución factible — podemos empezar de cualquier vértice,
elegir una arista, y continuar al vecino indicado,
asegurando al añadir aristas que nunca regresamos a un
vértice ya visitado con anterioridad.
Ramificar-acotar– p. 6
¡Fácil!
Logramos a encontrar la solución óptima con una
heurística voraz:
Siempre elige la arista con menor peso para añadir en el
árbol que está bajo construcción.
Ramificar-acotar– p. 7
Algoritmo de Prim
Empezamos por incluir en el árbol la arista de peso
mı́nimo y marcando los puntos finales de esta arista.
En cada paso, se elige entre los vecinos de los vértices
marcados el vértice que se puede añadir con el menor
peso entre los candidatos.
Ramificar-acotar– p. 8
Implementación simple
Se guarda el “costo” de añadir un vértice en un arreglo
auxiliar c[v] y asignamos c[v] = ∞ para los que no son
vecinos de vértices ya marcados.
Para saber cuales vértices fueron visitados, se necesita
una estructura de datos.
Con montículos normales se obtiene complejidad de
O (m log n) y con montículos de Fibonacci complejidad de
O (m + n log n).
Ramificar-acotar– p. 9
Algoritmo de Kruskal
Empezar a añadir aristas, de la menos pesada a la más
pesada, cuidando a no formar ciclos por marcar vértices al
haberlos tocado con una arista.
El algoritmo termina cuando todos los vértices están en el
mismo árbol, por lo cual una estructura tipo unir-encontrar
resulta muy útil.
La complejidad es
O (m log m) + O (m · ( unir-encontrar )) = O (m log m) =
O (m log n).
Ramificar-acotar– p. 10
¿Cómo guiar la búsqueda?
En los algoritmos de optimización combinatorial que
evaluan propiedades de varios y posiblemente todos los
candidatos de solución, es esencial saber “guiar” la
búsqueda de la solución y evitar evaluar “candidatos
malos”.
Un ejemplo de ese tipo de técnica es el método
podar-buscar.
Algoritmos que avancen siempre en el candidato
localmente óptimo se llaman voraces.
Ramificar-acotar– p. 11
Backtracking
En el método de “vuelta atrás” se aumenta una solución
parcial utilizando candidatos de aumento.
En cuanto una solución está encontrada, el algoritmo
vuelve a examinar un ramo de aumento donde no todos
los candidatos han sido examinados todavía.
Ramificar-acotar– p. 12
Ramificar-acotar
Cuando uno utiliza cotas para decidir cuáles ramos dejar
sin explorar, la técnica se llama ramificar-acotar (inglés:
branch and bound).
Es recomendable utilizar métodos tipo ramificar-acotar
solamente en casos donde uno no conoce un algoritmo
eficiente y no basta con una aproximación.
Ramificar-acotar– p. 13
El procedimiento
Los ramos de la computación consisten de soluciones
factibles distintas y la subrutina para encontrar una cota
(superior para maximización y inferior para minimización)
debería ser rápida.
Normalmente el recorrido del árbol de soluciones factibles
se hace en profundidad.
Cada hoja del árbol corresponde a una solución factible,
mientras los vértices internos son las operaciones de
aumento que construyen las soluciones factibles.
El algoritmo tiene que recordar el mejor resultado
visto para poder eliminar ramos que por el valor de su
cota no pueden contener soluciones mejores a la ya
conocida.
Ramificar-acotar– p. 14
Problema de viajante
En la versión de optimización del problema de viajante
(T SP), uno busca por el ciclo de menor costo/peso en un
grafo ponderado.
En el caso general, podemos pensar que el grafo sea no
dirigido y completo.
Utilizamos un método tipo ramificar-acotar para buscar la
solución óptima. Suponemos que el orden de
procesamiento de las aristas es fijo.
Ramificar-acotar– p. 15
Espacio de soluciones
El árbol de
soluciones consiste en decicir para cada uno
de los n2 aristas del grafo sı́ o no está incluida en el
ciclo.
Para el largo L(R) de cualquier ruta R aplica que
L(R) =
n
X
1
2
(L(vi−1 , vi ) + L(vi , vi+1 )) ,
i=1
donde los vértices de la ruta han sido numerados según
su orden de visita en la ruta así que el primer vértice tiene
dos números v1 y vn+1 y el último se conoce como vn y v0
para dar continuidad a la ecuación.
Ramificar-acotar– p. 16
Cota inferior al costo
Para cualquier ruta R el costo de la arista incidente a cada
vértice es por lo menos el costo de la arista más barata
incidente a ese vértice.
=⇒ Para la ruta más corta Rmı́n aplica que
L(R
Xmı́n ) ≥
1
2
los largos de las 2 aristas más baratas incidentes a v.
v∈V
Ramificar-acotar– p. 17
Ramificación
Al procesar la arista {v, w}, el paso “ramificar” es el
siguiente:
1. Si al excluir {v, w} resultaría que uno de los vértices
v o w tenga menos que dos aristas incidentes para la
ruta, ignoramos el ramo de excluirla.
2. Si al incluir {v, w} resultaría que uno de los vértices
v o w tenga más que dos aristas incidentes para la
ruta, ignoramos el ramo de inclusión.
3. Si al incluir {v, w} se generaría un ciclo en la ruta
actua sin haber incluido todos los vértices todavía,
ignoramos el ramo de inclusión.
Ramificar-acotar– p. 18
Uso de la cota
Después de haber eliminado o incluído aristas así,
computamos un nuevo valor de Rmı́n para las elecciones
hechas y lo utilizamos como la cota inferior.
Si ya conocemos una solución mejor a la cota asi
obtenida, ignoramos el ramo.
Al cerrar un ramo, regresamos por el árbol (de la manera
D FS) al nivel anterior que todavía tiene ramos sin
considerar.
Cuando ya no queda ninguno, el algoritmo termina.
Ramificar-acotar– p. 19
Tarea para entregar el martes
Diseña y explica en nivel de pseudocódigo un algoritmo de
ramificar-acotar para la versión de optimización del
problema de la mochila.
Muestra cómo funciona su el algoritmo con una instancia
pequeña de tu elección.
Ramificar-acotar– p. 20