Ramificacion y corte

Ramificación y acotación
v v v v v v v v

Introducción: (1) Ramificación… Un primer ejemplo: El juego del 15 Aplicación a problemas de optimización Introducción: (2) … y acotación Un problema de planificación de tareas a plazo fijo El problema de la mochila 0-1 El problema del viajante de comercio Consideraciones finales sobre eficiencia

2 7 19 24 28 43 55 73

J. Campos - C.P.S.Esquemas algorítmicos - Ramificación y acotación Pág. 1

Introducción: (1) Ramificación…
v

Al igual que los métodos de búsqueda con retroceso:
– se aplica a problemas de optimización con restricciones, – se genera el espacio de soluciones, organizándolo en un árbol (en general en un grafo), – no se genera el espacio de soluciones completo, sino que se podan bastantes estados.

vTerminología:
– Nodo vivo: nodo del espacio de soluciones del que no se han generado aún todos sus hijos. – Nodo muerto: nodo del que no se van a generar más hijos porque: u no hay más u no es completable, i.e., viola las restricciones u no producirá una solución mejor que la solución en curso – Nodo en curso (o en expansión): nodo del que se están generando hijos

J. Campos - C.P.S.

Esquemasalgorítmicos - Ramificación y acotación Pág. 2

Introducción: (1) Ramificación…
v

Diferencia fundamental con el método de búsqueda con retroceso:
– Búsqueda con retroceso: Tan pronto como se genera un nuevo hijo del nodo en curso, este hijo pasa a ser el nodo en curso. – Ramificación y acotación: Se generan todos los hijos del nodo en curso antes de que cualquier otro nodo vivo pase a ser el nuevonodo en curso.

v

En consecuencia:
– Búsqueda con retroceso: Los únicos nodos vivos son los que están en el camino de la raíz al nodo en curso. – Ramificación y acotación: Puede haber más nodos vivos. Se deben almacenar en una estructura de datos auxiliar: lista de nodos vivos.

J. Campos - C.P.S.

Esquemas algorítmicos - Ramificación y acotación Pág. 3

Introducción: (1) Ramificación…v

Diferentes estrategias de elegir el siguiente nodo de la lista de nodos vivos ⇒ Distintos órdenes de recorrido del árbol de soluciones

– FIFO: la lista de nodos vivos es una cola ⇒ recorrido por niveles (en anchura) – LIFO: la lista de nodos vivos es una pila ⇒ ≈ recorr. en profundidad (D–búsqueda) – Mínimo coste: la lista es una cola con prioridades ⇒ recorrido “extraño” La prioridad deun nodo se calcula de acuerdo con una función de estimación que mide cuánto de “prometedor” es un nodo.

J. Campos - C.P.S.

Esquemas algorítmicos - Ramificación y acotación Pág. 4

Introducción: (1) Ramificación…
v

Primer punto clave de los métodos de ramificación y acotación: Encontrar un buen orden de recorrido (o ramificación) de los nodos, es decir, definir una buena función deprioridad de los nodos vivos, para que las soluciones buenas se encuentren rápidamente.

J. Campos - C.P.S.

Esquemas algorítmicos - Ramificación y acotación Pág. 5

Introducción: (1) Ramificación…
v

El esquema es el siguiente:
repetir repetir expandir el nodo vivo más prometedor; expandir el nodo vivo más prometedor; generar todos sus hijos; generar todos sus hijos; una vez generados, elpadre se mata; una vez generados, el padre se mata; para cada hijo hacer para cada hijo hacer si tiene un coste esperado peor que si tiene un coste esperado peor que el de la mejor solución en curso el de la mejor solución en curso entonces se mata sino entonces se mata sino si tiene un coste esperado mejor si tiene un coste esperado mejor que el de la mejor solución en que el de la mejorsolución en curso y no es solución curso y no es solución entonces se pasa a la lista de entonces se pasa a la lista de nodos vivos nodos vivos sino {tiene un coste esperado mejor que sino {tiene un coste esperado mejor que
el de la mejor solución en curso el de la mejor solución en curso y es solución (el coste no es y es solución (el coste no es estimado sino real)} estimado sino real)}

pasa a...