CAP7 RamificacionyPoda

Capítulo 7
RAMIFICACIÓN Y PODA

7.1 INTRODUCCIÓN
Este método de diseño de algoritmos es en realidad una variante del diseño Vuelta
Atrás estudiado en el capítulo anterior. Sin embargo, su particular importancia y
extenso uso hace que nosotros le dediquemos un capítulo aparte.
Esta técnica de diseño, cuyo nombre en castellano proviene del término inglés
Branch and Bound, se aplica normalmente pararesolver problemas de
optimización. Ramificación y Poda, al igual que el diseño Vuelta Atrás, realiza una
enumeración parcial del espacio de soluciones basándose en la generación de un
árbol de expansión.
Una característica que le hace diferente al diseño anterior es la posibilidad de
generar nodos siguiendo distintas estrategias. Recordemos que el diseño Vuelta
Atrás realiza la generación dedescendientes de una manera sistemática y de la
misma forma para todos los problemas, haciendo un recorrido en profundidad del
árbol que representa el espacio de soluciones. El diseño Ramificación y Poda en su
versión más sencilla puede seguir un recorrido en anchura (estrategia LIFO) o en
profundidad (estrategia FIFO), o utilizando el cálculo de funciones de coste para
seleccionar el nodo que enprincipio parece más prometedor (estrategia de mínimo
coste o LC).
Además de estas estrategias, la técnica de Ramificación y Poda utiliza cotas
para podar aquellas ramas del árbol que no conducen a la solución óptima. Para
ello calcula en cada nodo una cota del posible valor de aquellas soluciones
alcanzables desde ése. Si la cota muestra que cualquiera de estas soluciones tiene
que sernecesariamente peor que la mejor solución hallada hasta el momento no
necesitamos seguir explorando por esa rama del árbol, lo que permite realizar el
proceso de poda.
Definimos nodo vivo del árbol a un nodo con posibilidades de ser ramificado, es
decir, que no ha sido podado. Para determinar en cada momento que nodo va a ser
expandido y dependiendo de la estrategia de búsqueda seleccionada, necesitaremosalmacenar todos los nodos vivos en alguna estructura que podamos recorrer.
Emplearemos una pila para almacenar los nodos que se han generado pero no han
sido examinados en una búsqueda en profundidad (LIFO). Las búsquedas en
amplitud utilizan una cola (FIFO) para almacenar los nodos vivos de tal manera
que van explorando nodos en el mismo orden en que son creados. La estrategia de
mínimo coste (LC)utiliza una función de coste para decidir en cada momento qué
nodo debe explorarse, con la esperanza de alcanzar lo más rápidamente posible una

256

TÉCNICAS DE DISEÑO DE ALGORITMOS

solución más económica que la mejor encontrada hasta el momento. Utilizaremos
en este caso una estructura de montículo (o cola de prioridades) para almacenar los
nodos ordenados por su coste.
Básicamente, en unalgoritmo de Ramificación y Poda se realizan tres etapas.
La primera de ellas, denominada de Selección, se encarga de extraer un nodo de
entre el conjunto de los nodos vivos. La forma de escogerlo va a depender
directamente de la estrategia de búsqueda que decidamos para el algoritmo. En la
segunda etapa, la Ramificación, se construyen los posibles nodos hijos del nodo
seleccionado en el paso anterior.Por último se realiza la tercera etapa, la Poda, en
la que se eliminan algunos de los nodos creados en la etapa anterior. Esto
contribuye a disminuir en lo posible el espacio de búsqueda y así atenuar la
complejidad de estos algoritmos basados en la exploración de un árbol de
posibilidades. Aquellos nodos no podados pasan a formar parte del conjunto de
nodos vivos, y se comienza de nuevo por elproceso de selección. El algoritmo
finaliza cuando encuentra la solución, o bien cuando se agota el conjunto de nodos
vivos.
Para cada nodo del árbol dispondremos de una función de coste que nos estime
el valor óptimo de la solución si continuáramos por ese camino. De esta manera, si
la cota que se obtiene para un nod, que por su propia construcción deberá ser mejor
que la solución real (o a lo...