3. Algoritmo Genérico de Branch & Bound
Roteiro (o que você vai aprender nesta parte):
- A estrutura geral do algoritmo
- Como os nós são armazenados e selecionados
- Onde os bounds são calculados
- Como a poda se integra ao fluxo
- Diferentes estratégias de busca (DFS, BFS, Best-first)
Na Parte 2, introduzimos as ideias centrais: branching, bounding e poda.
Agora organizamos essas ideias em um algoritmo genérico que pode ser aplicado a uma ampla variedade de problemas de otimização.
3.1 Estrutura de Alto Nível
Branch & Bound explora uma árvore de busca mantendo um conjunto de nós candidatos à expansão.
Em alto nível, o algoritmo repete:
- Selecionar um nó
- Avaliar seu bound
- Decidir entre podar ou expandir
- Atualizar a melhor solução, se necessário
3.2 Pseudocódigo Genérico
Inicializar best ← −∞ (ou +∞ para minimização)
Inicializar conjunto de nós com a raiz
enquanto o conjunto de nós não estiver vazio:
selecionar um nó N
se N for solução completa:
atualizar best se for melhor
senão:
calcular bound B(N)
se B(N) for promissor:
ramificar e adicionar filhos ao conjunto
senão:
podar N
Inicializar conjunto de nós com a raiz
enquanto o conjunto de nós não estiver vazio:
selecionar um nó N
se N for solução completa:
atualizar best se for melhor
senão:
calcular bound B(N)
se B(N) for promissor:
ramificar e adicionar filhos ao conjunto
senão:
podar N
Essa estrutura captura a essência do Branch & Bound: exploração sistemática guiada por bounds.
3.3 Estratégia de Seleção de Nós
- DFS (profundidade): baixo uso de memória
- BFS (largura): explora por níveis
- Best-first: escolhe o nó mais promissor
3.4 Conjunto de Nós (Fronteira)
- Pilha → DFS
- Fila → BFS
- Fila de prioridade → Best-first
3.5 Atualização do Incumbent
- atualiza a melhor solução
- torna a poda mais agressiva
3.6 Onde ocorre a poda
Se o bound não supera o incumbent → descartar nó
3.7 Propriedades
- Exploração sistemática
- Guiada por bounds
- Poda eficiente
- Garantia de otimalidade
Próximo: Parte 4 — Funções de Bounding
Continue:
Parte 4 — Funções de Bounding →