Ing Industrial

Algoritmo Branch-and-Bound
Introducción
Branch-and-Bound (B&B) es una técnica eficiente para la búsqueda de soluciones donde su objetivo es encontrar no solamente una solución, más si la óptima solución. El algoritmo B&B interactua y crea un árbol de búsqueda con el problema representado en un nodo, donde este nodo – problema – sufre una descomposición del problema en subproblemas,buscando la falseabilidad de soluciones no óptimas. Casi todas las otras técnicas de búsquedas son distintas del método B&B porque encuentran soluciones no óptimas o soluciones subóptimas. El problema debe ser representado con un grafo de estados, donde el estado inicial significa el problema propuesto y el estado final es el objetivo a alcanzar. Ha variaciones como búsqueda con retroceso,programación dinámica, los árboles de decisión Y/O y otros.
En este estudio, será presentado en la primera sección algunas definiciones, conceptos y funcionamiento de lo algoritmo Branch-and-Bound, en la segunda sección el paralelismo e distribución de carga para algoritmos paralelos; y en la tercera sección la orientación a objetos para eses algoritmos, conclusiones y bibliografía.

I –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 una buena solución.
Para comprenderemos mejor como el algoritmoB&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 nodode 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 como diferencia de generar todos los hijos del nodo en curso antesde elegir el próximo nodo.
* MINIMO COSTE: Se utiliza una cola con prioridades para implementar la LNV. Ahora, cada nodo de la LNV tiene un 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 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 es la misma que a poda realizada por el método. La podarealizada por el método es para evitar una duplicación de los estados en el árbol, evitando, así, que un mismo nodo sea explorado más de una vez.
Acotación
Significa usar una función U para podar en el árbol del espacio de estados de los nodos que se ajusten a una regla de poda.
La función U tiene, inicialmente, valor máximo determinado por una heurística basada en información extra del problema,siendo que U nunca podrá ser menor que la solución de mínimo coste.
Eliminación
Significa podar los nodos que lo límite es mayor que la solución encontrada hasta ahora.
Selección
Generalmente, la función de selección está determinada por una función de prioridad heurística. Los subproblemas están almacenados en la estructura de datos en un orden parcial o total, que no es decreciente de...