Técnicas de branch and bound

Centro de Ensino Unificado de Teresina
Nome: Guilherme Cássio Oliveira Holanda
Disciplina: Projeto e Análise

TÉCNICAS DE BRANCH AND BOUND

02 de junho de 2012

IDÉIA BÁSICA

O algoritmo roda sob a árvore de enumeração das soluções possíveis. No pior caso, todas as soluções serão exploradas. Na prática, frequentemente vários ramos são podados com o uso de limites.

INTRODUÇÃO

O princípio do Branch and Bound (BB) é a enumeração de todas as soluções viáveis de um problema de otimização combinatorial, diga-se um problema de minimização, tal que propriedades ou atributos não compartilhados por qualquer solução ótima são detectados tão cedo quanto possível. Um atributo (ou ramo da árvore de enumeração) define um subconjunto do conjunto de todas as soluções viáveis do problema original onde cada elemento do subconjunto satisfaz este atributo.
O método Branch and Bound é um algoritmo que busca por uma solução ótima através do exame de somente uma pequena parte do número total de possíveis soluções. Ele trabalha quebrando o espaço de soluções viáveis em subproblemas menores até que uma solução ótima seja alcançada. Para cada subproblema gerado o custo total ou lucro é calculado. Subproblemas com pior custo ou lucro são descartados até que não se possa criar mais subproblemas.
O termo Branch and Bound refere-se a todos os métodos de busca no espaço de estados na qual todas as crianças do E-node (nó expandido) são gerados antes que qualquer outro nó vivo possa se tornar o E-node. A técnica Branch and Bound trabalha basicamente usando uma das duas estratégias, busca em largura (BFS) ou busca em profundidade (D-search). Na terminologia BB, uma busca BFS será chamada busca FIFO (primeiro que entra primeiro que sai) porque a lista de nós vivos é uma fila. Uma busca D-search será chamada busca LIFO(último que entra primeiro que sai) porque a lista de nós vivos é uma pilha. Como no caso de backtracking, funções de limitação (bounding functions) são usadas para