Ramificación y poda
De Wikipedia, la enciclopedia libre
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 algortimo se encarga de detectar en que 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.
[editar] 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.
- optimo 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.
