Page 149 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
P. 149
INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
Ramificación y acotamiento (branch and bound)
INtroduccIóN
El método de diseño de algoritmos ramificación y acotamiento (también llamado ramificación y poda)
es una variante del backtracking mejorado sustancialmente. El término (del inglés, branch and bound)
se aplica mayoritariamente para resolver cuestiones o problemas de optimización.
La técnica de ramificación y acotamiento se suele interpretar como un árbol de soluciones, donde
cada rama lleva a una posible solución posterior. La característica de esta técnica con respecto a
otras anteriores (y a la que debe su nombre) es que el algoritmo se encarga de detectar en qué ra-
mificación las soluciones dadas ya no están siendo óptimas para “podar” esa rama del árbol y no
continuar malgastando recursos y procesos en casos que se alejan de la solución óptima.
deScrIpcIóN geNeral
Nuestra meta será encontrar el valor mínimo (o máximo) de una función f(x) (un ejemplo puede ser
el coste de manufacturación de un determinado producto), para lo que se fijan x rangos sobre un
determinado conjunto S de posibles soluciones. Un procedimiento de ramificación y poda requiere
dos herramientas:
• La primera es la de un procedimiento de expansión, que dado un conjunto
fijo S de candidatos, devuelva dos o más conjuntos más pequeños S , S ,…,
1 2
S cuya unión cubra a S. Nótese que el mínimo de f(x) sobre S es min{ V , V ,…}
n 1 2
donde cada v es el mínimo de f(x) sin S. Este paso es llamado ramificación; como
i i
su aplicación es recursiva, esta definirá una estructura de árbol cuyos nodos serán
subconjuntos de S.
• La segunda es el procedimiento de poda. La idea clave del algoritmo de ramifi-
cación y acotamiento es la siguiente: si estamos buscando un mínimo, y para una
rama de algún árbol (conjunto de candidatos), una hoja A del árbol tiene un punto
factible con un valor mayor a otro nodo hijo B de otra rama, entonces A debe ser
descartada con seguridad de la búsqueda. Algo equivalente sucede cuando se
busca un máximo. Este paso es llamado poda, y usualmente es implementado
manteniendo una variable global m que graba el mínimo nodo padre visto en-
tre todas las subregiones examinadas hasta entonces. Cualquier nodo hoja cuyo
valor es mayor que m puede ser descartado. La recursión se detiene cuando el
143
