5. Estratégias de Seleção de Nós
- Por que a seleção de nós importa em Branch & Bound
- As principais estratégias de exploração
- Como DFS, BFS e Best-first diferem
- Os trade-offs entre memória, velocidade e poda
- Por que a ordem de exploração afeta o desempenho na prática
Em Branch & Bound, a poda depende dos limites, mas o desempenho também depende de qual nó é explorado a seguir.
Mesmo com a mesma estrutura de branching e a mesma função de bounding, diferentes estratégias de seleção de nós podem levar a comportamentos muito diferentes na busca.
5.1 Por que a seleção de nós importa
Em qualquer momento do algoritmo, vários nós ativos podem permanecer na fronteira. O algoritmo deve decidir qual deles expandir a seguir.
Essa decisão importa porque:
- afeta a rapidez com que uma boa solução atual é encontrada,
- influencia a quantidade de memória necessária,
- e altera o quão cedo a poda se torna eficaz.
5.2 A fronteira de nós ativos
O algoritmo mantém um conjunto de nós que foram gerados mas ainda não foram expandidos.
Esses nós são chamados de nós ativos, e o conjunto completo é chamado de fronteira.
Uma estratégia de seleção de nós é essencialmente uma regra para escolher um nó dessa fronteira.
5.3 Busca em profundidade (DFS)
Em uma estratégia de profundidade, o algoritmo sempre continua pelo ramo mais recentemente gerado.
Isso normalmente é implementado com uma pilha.
- Vantagem: baixo uso de memória
- Vantagem: frequentemente encontra uma solução completa rapidamente
- Desvantagem: pode passar muito tempo em regiões pouco promissoras
DFS é especialmente atrativo quando a memória é limitada ou quando encontrar uma solução inicial cedo é útil.
5.4 Busca em largura (BFS)
Em uma estratégia de largura, o algoritmo explora os nós nível por nível.
Isso normalmente é implementado com uma fila.
- Vantagem: exploração sistemática por níveis
- Vantagem: útil para certas análises estruturais
- Desvantagem: pode exigir muita memória
Em problemas combinatórios grandes, BFS costuma ser caro na prática porque a fronteira pode crescer muito rapidamente.
5.5 Busca Best-first
Em uma estratégia best-first, o algoritmo escolhe o nó ativo com o limite mais promissor.
Isso normalmente é implementado com uma fila de prioridade.
- Vantagem: frequentemente encontra boas soluções cedo
- Vantagem: pode melhorar significativamente a poda
- Desvantagem: exige manutenção de prioridades ordenadas
Best-first é uma das estratégias mais comuns em implementações práticas de Branch & Bound.
5.6 Comparando as estratégias principais
- DFS: baixa memória, exploração profunda
- BFS: exploração ampla, alta memória
- Best-first: exploração guiada pela qualidade do limite
A melhor estratégia depende do problema, da qualidade do limite, e dos recursos computacionais disponíveis.
5.7 Interação com a solução atual
A seleção de nós afeta a rapidez com que a melhor solução atual melhora.
Se uma estratégia tende a encontrar boas soluções completas cedo, então a solução atual se torna forte mais rapidamente, tornando a poda mais agressiva depois.
Esse é um dos motivos pelos quais best-first costuma ter bom desempenho na prática: ele prioriza nós com maior chance de gerar boas soluções.
5.8 Resumo
- A seleção de nós determina a ordem de exploração
- DFS usa pilha
- BFS usa fila
- Best-first usa fila de prioridade
- A estratégia afeta memória, qualidade da solução e eficiência da poda
Próximo: Parte 6 — Problemas Clássicos
Agora que vimos como a seleção de nós afeta o processo de busca, o próximo passo é estudar os tipos de problemas onde Branch & Bound é aplicado.
Na Parte 6, analisaremos exemplos clássicos como Mochila, Caixeiro Viajante e outros problemas de otimização onde branching, bounding e seleção de nós trabalham juntos.