7. Complexidade
- A complexidade no pior caso do Branch & Bound
- Por que a poda pode ajudar drasticamente na prática
- A diferença entre complexidade teórica e prática
- O papel dos bounds e da seleção de nós no desempenho
- Por que a análise de complexidade é sutil nesse método
Branch & Bound é frequentemente muito mais rápido do que força bruta na prática, mas isso não significa que sua complexidade no pior caso desapareça.
Para entender corretamente o método, devemos distinguir entre complexidade teórica no pior caso e redução prática da busca através de poda.
7.1 Complexidade no pior caso
No pior caso, Branch & Bound ainda pode explorar toda a árvore de busca.
Isso significa que sua complexidade de tempo permanece exponencial:
onde:
- b é o fator de ramificação
- d é a profundidade da árvore de busca
Em problemas binários, isso é frequentemente escrito como:
7.2 Por que ainda é útil
Se o pior caso ainda é exponencial, por que usar Branch & Bound?
Porque, em muitos casos práticos, o algoritmo evita explorar grande parte da árvore.
Bounds fortes e boas soluções incumbentes podem eliminar grandes porções do espaço de busca antes mesmo de serem exploradas.
7.3 O efeito da poda
Quanto mais nós são podados, menor se torna a árvore de busca efetiva.
Isso significa que o tempo de execução prático depende de:
- a qualidade da função de bound,
- a rapidez em encontrar boas soluções incumbentes,
- e a estratégia de seleção de nós.
Portanto, duas implementações de Branch & Bound para o mesmo problema podem ter a mesma complexidade teórica, mas comportamentos práticos muito diferentes.
7.4 Complexidade de espaço
A complexidade de espaço depende fortemente da estratégia de seleção de nós.
- DFS: geralmente baixo uso de memória, pois mantém apenas um caminho e uma pequena fronteira
- BFS: pode exigir muita memória, pois muitos nós no mesmo nível permanecem armazenados
- Best-first: frequentemente requer bastante memória, já que muitos nós ativos ficam na fila de prioridade
Na prática, memória pode ser tão importante quanto tempo ao avaliar um algoritmo de Branch & Bound.
7.5 Custo de cálculo dos bounds
A complexidade não depende apenas do número de nós visitados.
Cada nó pode exigir trabalho adicional para calcular seu bound.
Assim, o tempo total depende de:
- o número de nós visitados,
- e o custo por nó.
Por isso, um bound mais forte nem sempre é melhor: ele pode reduzir a árvore, mas aumentar o custo por nó.
7.6 Dependência da instância
Branch & Bound é altamente dependente da instância.
Em alguns casos, a poda é extremamente eficiente. Em outros, quase nenhuma poda ocorre.
Isso torna difícil prever a complexidade com precisão.
7.7 Visão prática da complexidade
Na prática, Branch & Bound é avaliado por:
- número de nós expandidos,
- número de nós podados,
- uso de memória,
- tempo total de execução em instâncias representativas.
Essa perspectiva prática é especialmente importante em engenharia de otimização e desenvolvimento de solvers.
7.8 Resumo
- O tempo no pior caso permanece exponencial
- A poda pode reduzir drasticamente a busca na prática
- O espaço depende fortemente da estratégia de exploração
- O custo total inclui nós visitados e cálculo de bounds
- O desempenho depende fortemente da instância
Próximo: Parte 8 — Branch & Bound vs Backtracking vs Programação Dinâmica
Agora que entendemos a complexidade do Branch & Bound, o próximo passo é compará-lo com outras técnicas importantes.
Na Parte 8, iremos comparar Branch & Bound com Backtracking e Programação Dinâmica, destacando quando cada abordagem é mais adequada.