Metodo Branch And Bound
Páginas: 12 (2910 palabras)
Publicado: 13 de diciembre de 2012
MÉTODO BRANCH AND BOUND
Ensayo.
Fundación universitaria Tecnológico Comfenalco
Cartagena D, T, H Y C.
2012
Método Branch and Bound
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 oproblemas 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 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 yprocesos en casos que se alejan de la solución óptima.
Al igual que los métodos de búsqueda con retroceso:
* Se aplica a problemas 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
Un procedimiento de ramificación y poda requiere dos herramientas,
Laprimera 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 S. Este paso es llamado ramificación; como su aplicación es recursiva, esta definirá una estructura de árbol cuyos nodos seránsubconjuntos 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. Cualquier nodo cuyonodo hijo es mayor que m puede ser descartado.
Definiciones y Conceptos
El funcionamiento general de lo algoritmo B&B consiste en reducir el espacio de búsqueda del problema podando las zonas del árbol aún no exploradas que no pueden crear mejores soluciones que la solución en curso. Para tanto, el método de ramificación y acotación B&B busca siempre la óptima solución y, nunca unabuena solución.
Para comprenderemos mejor como el algoritmo B&B funciona, algunos conceptos deben ser descritos.
Ramificación
Significa elegir el próximo nodo en curso de la lista de nodos vivos, siendo el nodo vivo eliminado da lista y la continuación ocurre generando sus hijos. Para elegir el próximo nodo en curso hay 3 estrategias:
* FIFO: Se utiliza una cola para implementar lalista de nodos vivos, tiendo el nodo en curso el primero nodo de la lista de nodos vivos (LNV) y sus hijos se añaden al final de la lista. El recorrido aquí es por niveles.
* LIFO: Se utiliza una pila para implementar la LNV. Aquí el próximo nodo vivo será el primero de la LNV y sus hijos se añaden al inicio de la lista. Esta estrategia es muy similar al recorrido en profundidad, tiendo comodiferencia de generar todos los hijos del nodo en curso antes de elegir el próximo nodo.
* MINIMO COSTO: Se utiliza una cola con prioridades para implementar la LNV. Ahora, cada nodo de la LNV tiene una prioridad o coste, de forma que siempre el nodo con mayor prioridad será elegido. Un problema de optimización con restricciones puede ser transformado en un problema de encontrar la solución demínimo coste. Así, crease una función de estimación. Encontrar una función de estimación fácil de calcular no es una tarea fácil. Hay propiedades que la función debe cumplir. Se no se cumplen el algoritmo se detén al encontrar la primera solución, la cual pude no ser la óptima.
En la fase de ramificación es posible emplear poda para que el tamaño del árbol de estados sea reducido. Esta poda no...
Ensayo.
Fundación universitaria Tecnológico Comfenalco
Cartagena D, T, H Y C.
2012
Método Branch and Bound
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 oproblemas 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 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 yprocesos en casos que se alejan de la solución óptima.
Al igual que los métodos de búsqueda con retroceso:
* Se aplica a problemas 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
Un procedimiento de ramificación y poda requiere dos herramientas,
Laprimera 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 S. Este paso es llamado ramificación; como su aplicación es recursiva, esta definirá una estructura de árbol cuyos nodos seránsubconjuntos 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. Cualquier nodo cuyonodo hijo es mayor que m puede ser descartado.
Definiciones y Conceptos
El funcionamiento general de lo algoritmo B&B consiste en reducir el espacio de búsqueda del problema podando las zonas del árbol aún no exploradas que no pueden crear mejores soluciones que la solución en curso. Para tanto, el método de ramificación y acotación B&B busca siempre la óptima solución y, nunca unabuena solución.
Para comprenderemos mejor como el algoritmo B&B funciona, algunos conceptos deben ser descritos.
Ramificación
Significa elegir el próximo nodo en curso de la lista de nodos vivos, siendo el nodo vivo eliminado da lista y la continuación ocurre generando sus hijos. Para elegir el próximo nodo en curso hay 3 estrategias:
* FIFO: Se utiliza una cola para implementar lalista de nodos vivos, tiendo el nodo en curso el primero nodo de la lista de nodos vivos (LNV) y sus hijos se añaden al final de la lista. El recorrido aquí es por niveles.
* LIFO: Se utiliza una pila para implementar la LNV. Aquí el próximo nodo vivo será el primero de la LNV y sus hijos se añaden al inicio de la lista. Esta estrategia es muy similar al recorrido en profundidad, tiendo comodiferencia de generar todos los hijos del nodo en curso antes de elegir el próximo nodo.
* MINIMO COSTO: Se utiliza una cola con prioridades para implementar la LNV. Ahora, cada nodo de la LNV tiene una prioridad o coste, de forma que siempre el nodo con mayor prioridad será elegido. Un problema de optimización con restricciones puede ser transformado en un problema de encontrar la solución demínimo coste. Así, crease una función de estimación. Encontrar una función de estimación fácil de calcular no es una tarea fácil. Hay propiedades que la función debe cumplir. Se no se cumplen el algoritmo se detén al encontrar la primera solución, la cual pude no ser la óptima.
En la fase de ramificación es posible emplear poda para que el tamaño del árbol de estados sea reducido. Esta poda no...
Leer documento completo
Regístrate para leer el documento completo.