2. A Ideia Central (Branch + Bound + Poda)
- O que significa “branch” no processo de busca
- O que é um bound e por que ele importa
- Como decisões de poda são tomadas
- O papel da melhor solução atual
- Por que Branch & Bound continua sendo exato mesmo com poda
Na Parte 1, modelamos o problema como uma árvore de decisões parciais. Isso nos deu a estrutura.
Agora estudamos o mecanismo que torna o Branch & Bound poderoso: ele não explora a árvore cegamente. Em vez disso, expande regiões promissoras e corta regiões que não podem melhorar a melhor solução atual.
2.1 O que é “branch”?
O termo branch refere-se ao ato de dividir um problema em subproblemas menores ao tomar uma nova decisão.
Em forma de árvore:
- cada nó é uma solução parcial,
- cada aresta representa uma escolha possível,
- cada nó filho representa um refinamento do estado atual.
Por exemplo, na Mochila 0/1, ramificar em um item significa:
- incluir o item, ou
- não incluir o item.
2.2 O que é um bound?
Um bound é uma estimativa do melhor resultado que ainda pode ser obtido a partir de uma solução parcial.
Como um nó ainda não é uma solução completa, geralmente não conhecemos seu valor final exato. Em vez disso, calculamos um limite que indica quão promissor ele é.
onde B estima a melhor continuação possível da solução parcial (x₁, …, xᵢ).
2.3 Limites superiores e inferiores
O significado do bound depende do tipo de problema.
- Maximização: usamos um limite superior
- Minimização: usamos um limite inferior
O princípio é o mesmo: o bound indica se o nó ainda pode superar a melhor solução atual.
2.4 A melhor solução atual
O algoritmo mantém a melhor solução encontrada até o momento, chamada de incumbent.
- se um nó pode superar o incumbent → explorar
- se não pode → podar
Se B(node) ≤ best, o nó pode ser podado (maximização).
2.5 O que é poda?
Poda significa interromper a exploração de um ramo antes do fim.
- ramo inviável
- ramo não competitivo
2.6 Lógica central
- Gerar solução parcial
- Verificar viabilidade
- Calcular bound
- Comparar com o incumbent
- Expandir ou podar
2.7 Por que continua exato?
Branch & Bound é um algoritmo exato.
Só poda quando é matematicamente impossível melhorar a solução.
2.8 Diferença para backtracking
- Backtracking → poda por viabilidade
- Branch & Bound → poda por qualidade
Próximo: Parte 3 — Algoritmo Genérico de Branch & Bound
Na próxima parte, veremos a estrutura geral do algoritmo.