Ramificación y poda

Branch&bound.jpg

El método de diseño de algoritmos Ramificación y poda (también llamado Ramificación y Acotación) 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 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 (y a la que debe su nombre) 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.

Descripción General

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 , , … , cuya unión cubre S. Nótese que el mínimo de f(x) sobre S es min{ , , … } donde cada es el mínimo de f(x) en . 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)
 while ( no vacio(P) )
    x(k) = extraer(P)
    if esFactible(x,k) y G(x,k) < optimo
        si esSolucion(x)
             Almacenar(x)
        else
             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.
  • NOTA: Usamos un menor que (<) para los problemas de minimización y un mayor que (>) para problemas de maximización.
Other Languages
فارسی: شاخه و حد
日本語: 分枝限定法
한국어: 분기 한정법
português: Branch and bound
srpskohrvatski / српскохрватски: Separacija i evaluacija
српски / srpski: Separacija i evaluacija
українська: Метод гілок і меж