8. Branch & Bound vs Backtracking vs Programação Dinâmica
- Como Branch & Bound difere de Backtracking
- Como difere de Programação Dinâmica
- Quando os três métodos se sobrepõem
- Quando cada método é mais apropriado
- Como escolher a ferramenta certa para um problema
Branch & Bound é frequentemente apresentado junto com Backtracking porque ambos exploram árvores de busca.
Ele também é frequentemente comparado com Programação Dinâmica porque os três métodos são usados para resolver problemas combinatórios difíceis.
Mas seus objetivos, hipóteses e mecanismos são diferentes.
8.1 Branch & Bound vs Backtracking
Backtracking está principalmente relacionado à viabilidade.
Ele explora uma árvore de busca e poda ramos quando restrições são violadas ou quando nenhuma solução válida é possível.
Branch & Bound vai além: ele também pode podar ramos que ainda são viáveis, mas que não podem levar a uma solução melhor que a atual.
- Backtracking: poda porque o ramo é inválido
- Branch & Bound: poda porque o ramo não é competitivo
8.2 Branch & Bound vs Programação Dinâmica
Programação Dinâmica é baseada em subproblemas sobrepostos e subestrutura ótima.
Em vez de explorar uma árvore de busca com poda, ela resolve subproblemas sistematicamente e armazena seus resultados para reutilização.
Branch & Bound, por outro lado, explora uma árvore de soluções parciais e reduz trabalho por meio de poda, não memoização.
- Programação Dinâmica: evita recomputação
- Branch & Bound: evita explorar regiões irrelevantes
8.3 Onde eles se sobrepõem
Esses métodos nem sempre são completamente separados.
Para alguns problemas de otimização:
- Backtracking pode ser estendido para Branch & Bound
- Programação Dinâmica pode resolver o mesmo problema de forma mais eficiente quando suas hipóteses são satisfeitas
- Branch & Bound ainda pode ser preferido quando DP é inviável por memória ou tamanho de estado
Portanto, a escolha depende não apenas do problema, mas da estrutura disponível para explorar.
8.4 Quando usar Backtracking
Backtracking é uma escolha natural quando:
- o objetivo é encontrar qualquer solução válida,
- ou enumerar todas as soluções válidas,
- e a poda é baseada principalmente em restrições.
Exemplos típicos incluem:
- N-Queens
- Sudoku
- Geração de permutações
- Problemas de satisfação de restrições
8.5 Quando usar Branch & Bound
Branch & Bound é apropriado quando:
- o problema é de otimização,
- o espaço de busca é combinatório,
- e existem bounds capazes de eliminar grandes partes da árvore.
É especialmente útil quando a solução ótima exata é necessária, mas a busca exaustiva completa é inviável.
8.6 Quando usar Programação Dinâmica
Programação Dinâmica é a melhor escolha quando:
- existem subproblemas sobrepostos,
- há subestrutura ótima,
- e o espaço de estados pode ser armazenado.
Nesses casos, DP pode superar Branch & Bound pois transforma busca exponencial em computação estruturada com reutilização de estados.
8.7 Resumo comparativo
- Backtracking: busca + poda por viabilidade
- Branch & Bound: busca + poda por otimalidade
- Programação Dinâmica: reutilização de estados + recorrência
Em resumo:
- Backtracking pergunta: esse ramo ainda é válido?
- Branch & Bound pergunta: esse ramo ainda pode vencer?
- Programação Dinâmica pergunta: já resolvemos esse estado antes?
8.8 Resumo
- Backtracking trata de validade
- Branch & Bound trata de otimalidade
- Programação Dinâmica trata de reutilização de trabalho
- Os três métodos podem resolver problemas relacionados
- A escolha depende da estrutura do problema
Série concluída
Agora cobrimos toda a série de Branch & Bound: desde modelagem de problemas e árvores de busca até bounding functions, estratégias de exploração, complexidade e comparação com outros paradigmas.
O próximo passo natural é estudar uma implementação concreta, geralmente começando com Mochila 0/1 ou TSP.