rAMIFICACION Y ACOTAMIENTO

Exploración de grafos
Grafos
Recorridos sobre grafos
Búsqueda primero en profundidad
Búsqueda primero en anchura

Backtracking (“vuelta atrás”)
Descripción general
Espacio de soluciones
Implementación
Ejemplos

Branch & Bound (“ramificación y poda”)
Descripción general
Estrategias de ramificación
Implementación
Ejemplos

125

Branch & Bound
“Branch and Bound” (B&B)
Bound”es una generalización de la técnica de backtracking:
backtracking:
Se realiza un recorrido sistemático del árbol de estados
de un problema, si bien ese recorrido no tiene por qué
ser en profundidad, como sucedía en backtracking:
backtracking:
usaremos una estrategia de ramificación.
ramificación.
Además, utilizaremos técnicas de poda para eliminar
todos aquellos nodos que no lleven asoluciones óptimas
(estimando, en cada nodo, cotas del beneficio que
podemos obtener a partir del mismo).
NOTA: Los algoritmos que utilizan B&B suelen ser
de orden exponencial (o peor)en su peor caso.

126

Branch & Bound
Diferencias con backtracking
En bactracking, tan pronto como se genera un nuevo hijo
bactracking,
del nodo en curso, este hijo pasa a ser el nodo en curso.
En B&B, segeneran todos los hijos del nodo en curso
antes de que cualquier otro nodo vivo pase a ser el
nuevo nodo en curso (no se realiza un recorrido en
(no
profundidad).
En consecuencia:
En backtracking, los únicos nodos vivos son los que están
backtracking,
en el camino de la raíz al nodo en curso.
En B&B, puede haber más nodos vivos,
127
que se almacenan en una lista de nodos vivos.

Branch& Bound
Diferencias con backtracking
En bactracking, el test de comprobación realizado por la
bactracking,
funciones de poda nos indica únicamente si un nodo
concreto nos puede llevar a una solución o no.
En B&B, sin embargo, se acota el valor de la solución a la
que nos puede conducir un nodo concreto, de forma que
esta acotación nos permite…
podar el árbol (si sabemos que no nos va allevar a
una solución mejor de la que ya tenemos) y
establecer el orden de ramificación (de modo que
comenzaremos explorando las ramas más
prometedores del árbol).
128

Branch & Bound
Estimación de las cotas
a partir de una solución parcial:
2
Antes de explorar s,
se acota el valor de
la mejor solución M
alcanzable desde s. ................
CI(s) ≤ valor(M) ≤ CS(s)

x1

1
x2
s3
s= (x1, x2)

¿?
(sin explorar)

M= (x1, x2, x3, x4,..., xn)
valor(M) = ¿?

M
129

Branch & Bound
Descripción general
Branch & Bound es un método general de búsqueda
que se aplica de la siguiente forma:
Explora un árbol comenzando a partir de un problema
raíz y su región factible (inicialmente, el problema
original, con su espacio de soluciones completo).
Aplica funciones deacotación al problema raíz, para el
que establece cotas inferiores y/o superiores.
Si las cotas cumplen las condiciones que se hayan
establecido, habremos encontrado la solución óptima
del problema y la búsqueda termina.
130

Branch & Bound
Descripción general
Si se encuentra una solución óptima para un
subproblema concreto, ésta será una solución factible
para el problema completo,pero no necesariamente su
óptimo global.
Cuando en un nodo (subproblema), su cota local es peor
que el mejor valor conocido en la región, no puede existir
un óptimo global en el subespacio de la región factible
asociada a ese nodo y, por tanto, ese nodo puede ser
eliminado (“podado”).
131

Branch & Bound
Descripción general
En B&B, la búsqueda prosigue hasta que…
se examinan o “podan”todos los nodos, o bien
se cumple algún criterio pre-establecido sobre el
mejor valor encontrado y las cotas locales de los
subproblemas aún no resueltos.

132

Branch & Bound
Estimadores y cotas en Branch & Bound
Problema de
maximización

Problema de
minimización

Valor

Beneficio

Coste

Cota local

Cota superior

Cota inferior

CL ≥ Óptimo local

CL ≤ Óptimo local...