La ramificación y poda algoritmo

Introducción

El método de diseño de algoritmos Ramificación y poda (también conocido  Ramificación y Acotación) es una variante del Backtracking mejorado sustancialmente. El término se aplica mayoritariamente para resolver cuestiones o problemas de optimización.

La técnica de Ramificación y poda se suele interpretar como un árbol de soluciones, donde cada rama nos lleva a una posible solución posterior a la actual. La característica de esta técnica con respecto a otras anteriores es que el algoritmo se encarga de detectar en qué ramificació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.

Descipción del algoritmo

Nuestra meta será encontrar el valor mínimo de una función f(x) (un ejemplo puede ser el coste de manufacturación de un determinado producto) donde fijamos 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, devuelve dos o más conjuntos más pequeños S1, S2, …, Sn cuya unión cubre S. Nótese que el mínimo de f(x) sobre S es min{v1, v2, … } donde cada vi es el mínimo de f(x) sin Si. Este paso es llamado ramificación; como su aplicación es recursiva, esta definirá una estructura de árbol cuyos nodos serán subconjuntos de S.

La idea clave del algoritmo de ramificación y poda es: si la menor rama para algún árbol nodo(conjunto de candidatos) A es mayor que la rama padre para otro nodo B, entonces A debe ser descartada con seguridad de la búsqueda. Este paso es llamado poda, y usualmente es implementado manteniendo una variable global m que graba el mínimo nodo padre visto entre todas las subregiones examinadas hasta entonces. Cualquier nodo cuyo nodo hijo es mayor que m puede ser descartado. La recursión para cuando el conjunto candidato S es reducido a un solo elemento, o también cuando el nodo padre para el conjunto S coincide con el nodo hijo. De cualquier forma, cualquier elemento de S va a ser el mínimo de una función dentro de S.

Pseudocódigo

El pseudocódigo del algoritmo de Ramificación y poda es el siguiente:

Funcion RyP {
P = Hijos(x,k)
mientras ( no vacio(P) )
x(k) = extraer(P)
si esFactible(x,k) y G(x,k) < optimo
si esSolucion(x)
Almacenar(x)
sino
RyP(x,k+1)
}

Donde:

• G(x) es la función de estimación del algoritmo.
• P es la pila de posibles soluciones.
• esFactible es la función que considera si la propuesta es válida.
• esSolución es la función que comprueba si se satisface el objetivo.
• óptimo es el valor de la función a optimizar evaluado sobre la mejor solución encontrada hasta el momento.