PDF de programación - Capítulo 7 - RAMIFICACIÓN Y PODA

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 para resolver 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 de descendientes 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 en principio 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 ser necesariamente 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, necesitaremos
almacenar 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 un algoritmo 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 el proceso 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 sumo, igual que ella), es peor que una solución ya
obtenida por otra rama, podemos podar esa rama pues no es interesante seguir por
ella. Evidentemente no podremos realizar ninguna poda hasta que hayamos
encontrado alguna solución. Por supuesto, las funciones de coste han de ser
crecientes respecto a la profundidad del árbol, es decir, si h es una función de coste
entonces h(n) ≤ h(n’) para todo n’ nodo descendiente de n.
En consecuencia, y a la vista de todo esto, podemos afirmar que lo que le da
valor a esta técnica es la posibilidad de disponer de distintas estrategias de
exploración del árbol y de acotar la búsqueda de la solución, que en definitiva se
traduce en eficiencia. La dificultad está en encontrar una buena función de coste
para el problema, buena en el sentido de que garantice la poda y que su cálculo no
sea muy costoso. Si es demasiado simple probablemente pocas ramas puedan ser
excluidas. Dependiendo de cómo ajustemos la función de coste mejor algoritmo se
deriva.

Inicialmente, y antes de proceder a la poda de nodos, tendremos que disponer
del coste de la mejor solución encontrada hasta el momento que permite excluir de
futuras expansiones cualquier solución parcial con un coste mayor. Como muchas
veces no se desea esperar a encontrar la primera solución para empezar a podar, un
buen recurso para los problemas de optimización es tomar como mejor solución
inicial la obtenida con un algoritmo ávido, que como vimos no encuentra siempre
la solución óptima, pero sí una cercana a la óptima.
Por último, sólo comentar una ventaja adicional que poseen estos algoritmos: 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, nada impide tener más de un proceso trabajando sobre este conjunto,
extrayendo nodos, expandiéndolos y realizando la poda. El disponer de algoritmos
paralelizables (y estos algoritmos, así como los de Divide y Vencerás lo son) es
muy importante en muchas aplicaciones en las que es necesario abordar los
problemas de forma paralela para resolverlos en tiempos razonables, debido a su
complejidad intrínseca.

RAMIFICACIÓN Y PODA



257

Sin embargo, todo tiene un precio, sus requerimientos de memoria son mayores
que los de los algoritmos Vuelta Atrás. Ya no se puede disponer de una estructura
global en donde ir construyendo la solución, puesto que el proceso de construcción
deja de ser tan “ordenado” como antes. Ahora se 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.

7.2 CONSIDERACIONES DE IMPLEMENTACIÓN
Uno de las dificultades que suele plantear la técnica de Ramificación y Poda es
la implementación de los algoritmos que se obtienen. Para subsanar este problema,
en esta sección presentamos una estructura general de tales algoritmos, basada en
tres módulos (en el sentido de Modula-2) principales:
1. De un

lado dispondremos del módulo que contiene el esquema de

funcionamiento general de este tipo de algoritmos.

2. Por otro se encuentra el módulo que maneja la estructura de datos en donde se
almacenan los nodos que se van generando, y que puede tratarse de una pila,
una cola o un montículo (según se siga una estrategia LIFO, FIFO o LC).

3. Finalmente, necesitamos un módulo que describa e implemente las estructuras

de datos que conforman los nodos.

El primero de los tres módulos no se modifica a lo largo del capítulo, pues es
válido para todos los algoritmos que siguen la técnica de Ramificación y Poda, y lo
presentamos a continuación:


MODULE Esquema;
FROM IO IMPORT WrStr, WrCard, WrLn;
FROM Estruc IMPORT Estructura,Crear,Anadir,Extraer,EsVacia,
Tamano,Destruir;
FROM Nodos IMPORT nodo,NodoInicial,MAXHIJOS,Expandir,EsAceptable,
EsSolucion,h,Eliminar,NoHaySolucion,Imprimir,PonerCota;
VAR numgenerados, (* numero total de nodos generados *)
numanalizados, (* numero total de nodos analizados *)
numpodados:CARDINAL; (* numero total de nodos podados *)

PROCEDURE RyP_una():nodo; (* encuentra la primera solucion *)
VAR E:Estructura; (* estructura para almacenar los nodos *)
n:nodo; (* nodo vivo en curso *)
hijos:ARRAY [1..MAXHIJOS] OF nodo; (* hijos de un nodo *)
numhijos,i,j:CARDINAL;
BEGIN
E:=Crear(); (* inicializamos las estructuras *)
n:=NodoInicial(); Anadir(E,n,h(n)); (*h es la funcion de coste*)
WHILE NOT EsVacia(E) DO
n:=Extraer(E); INC(numanalizados);
numhijos:=Expandir(n,hijos); INC(numgenerados,numhijos);
Eliminar(n);

258

TÉCNICAS DE DISEÑO DE ALGORITMOS

FOR i:=1 TO numhijos DO
IF EsAceptable(hijos[i]) THEN
IF EsSolucion(hijos[i]) THEN (* Eureka! *)
FOR j:=1 TO numhijos DO (*eliminamos resto de hijos*)
IF i<>j THEN Eliminar(hijos[j]) END;
END;
Destruir(E);
RETURN hijos[i] (* devolvemos la solucion *)
ELSE
Anadir(E,hijos[i],h(hijos[i]))
END;
ELSE
Eliminar(hijos[i]); INC(numpodados)
END;
END;
END;
Destruir(E);
RETURN NoHaySolucion();
END RyP_una;

(* programa principal del esquema *)
VAR n:nodo;
BEGIN
numgenerados:=0; numanalizados:=0; numpodados:=0;
n:=RyP_una();
WrStr("Nodos Generados: "); WrCard(numgenerados,4); Wr