Metodo branch and bound

Solo disponible en BuenasTareas
  • Páginas : 13 (3179 palabras )
  • Descarga(s) : 0
  • Publicado : 13 de diciembre de 2011
Leer documento completo
Vista previa del texto
Método Branch and Boun
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 cadarama 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 y procesos en casos que se alejan de la solución óptima.
Al igual que los métodos de búsqueda con retroceso:
* seaplica 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.
La primera es la de un procedimiento de expansión, que dado un conjunto fijo S de candidatos, devuelve dos o más conjuntosmá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(conjuntode 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 cuyo nodo hijo es mayor que m puede ser descartado.

Definiciones y Conceptos
El funcionamiento general de lo algoritmoB&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 una buena 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 la lista de nodos vivos, tiendo el nodo en curso el primero nodo de la lista de nodos vivos (LNV) y sus hijos se añaden alfinal 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 como diferencia de generar todos los hijos del nodo en curso antes de elegir el próximo nodo.
* MINIMO COSTO: Se utiliza unacola 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 de mínimo coste. Así, crease una función de estimación. Encontrar una función de estimación fácil de calcular no es una tareafá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 es la misma que a poda realizada por el método. La poda realizada por el método es para evitar una duplicación de los...
tracking img