Ramificación y poda
La técnica genera un árbol de expansión de nodos con soluciones siguiendo distintas estrategias: recorrido de anchura (estrategia LIFO Last Input First Output Ultima Entrada Primera Salida) o en profundidad (estrategia FIFO First Input First Output Primera Entrada Primera Salida) o utilizando el cálculo de funciones de costo para seleccionar el nodo más prometedor.
También utiliza estrategias para las ramas del árbol que no conducen a la solución óptima: calcula en cada nodo una cota del posible valor de aquellas soluciones alcanzables desde ése. Si la cota muestra que cualquiera de estas soluciones no es mejor que solución hallada hasta el momento, no continua explorando esa rama del árbol, lo cuál permite realizar el proceso de poda.
Se conoce como nodo vivo del árbol a aquel nodo con posibilidades de ser ramificado, es decir, que no ha sido podado.
Para determinar en cada momento que nodo va a ser expandido se almacenan todos los nodos vivos en una estructura pila (LIFO) o cola-(FIFO) que podamos recorrer. La estrategia de mínimo costo (LC Low Cost ) utiliza una función de costo para decidir en cada momento qué nodo debe explorarse, con la esperanza de alcanzar lo más rápidamente posible una solución más económica que la mejor encontrada hasta el momento.
En este proceso se realizan tres etapas:
1. Selección: extrae un nodo de entre el conjunto de los nodos vivos.
2. Ramificación: se construyen los posibles nodos hijos del nodo seleccionado en la etapa anterior.
3. Poda: Se eliminan algunos de los nodos creados en la etapa anterior. Aquellos nodos no podados pasan a formar parte del conjunto de nodos vivos, y se comienza de nuevo por el proceso de selección. El algoritmo finaliza cuando encuentra la solución, o bien cuando se agota el conjunto de nodos vivos.
Estos algoritmos tienen la posibilidad de ejecutarlos en paralelo. Debido a que disponen de un conjunto de nodos vivos sobre el que se efectúan las tres etapas del algoritmo antes mencionadas, se puede tener más de un proceso trabajando sobre este conjunto, extrayendo nodos, expandiéndolos y realizando la poda.
Debido a lo anterior, los requerimientos de memoria son mayores que los de los algoritmos Vuelta Atrás. El proceso de construcción necesita que cada nodo sea autónomo, en el sentido que ha de contener toda la información necesaria para realizar los procesos de bifurcación y poda, y para reconstruir la solución encontrada hasta ese momento.
Un ejemplo de aplicación de los algoritmos de ramificación y poda lo encontramos en el problema de las N-reinas, el cuál consiste en colocar 8 reinas en un tablero de ajedrez cuyo tamaño es de 8 por 8 cuadros, las reinas deben de estar distribuidas dentro del tablero de modo que no se encuentren dos o más reinas en la misma línea horizontal, vertical o diagonal. Se han encontrado 92 soluciones posibles a este problema.
Fuente: Apunte Análisis, diseño e implantación de algoritmos de la facultad de contaduría y administración, UNAM
