LOGARITMO DE BRANCH

LOGARITMO DE BRANCH
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 (delinglé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 ramanos lleva a una posible solución posterior a la actual.
La característica de esta técnica 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.
Al igual que los métodos de búsqueda con retroceso:
* Se aplica aproblemas de optimización con restricciones (algunas veces también a probabilidad. de decisión)
* Se genera el espacio de soluciones, organizándolo en un árbol.
Se podan subárboles inútiles

La idea básica deeste método es responder a la pregunta ¿Se puede dividir el problema en problemas más pequeños para obtener la solución”?. Esta técnica se utiliza para resolver problemas tipo enteros, por lo que lasolución es del mismo tipo. Se sabe que es muy difícil resolver esta situación, por lo que el problema se relaja, es decir, el problema entero se convierte en uno del tipo continuo (Xi ≥0, ∀i) y lassoluciones dejan de ser puntos y se transforman en una “región factible”. Así, con este método se pretende ir reduciendo este espacio de soluciones factibles, agregando nuevas restricciones yobteniendo problemas más pequeños y más fáciles de resolver. Encontramos la solución óptima cuando la solución óptima de los problemas relajados cumple con las restricciones del problema original.

El nombreviene del proceso de usar un árbol donde se ramifica para examinar subregiones (y sus relajaciones) de la región factible y cotas para mantener el crecimiento del árbol bajo control y lograr...