O que Branch & Bound resolve
Branch & Bound é uma técnica geral para resolver problemas de otimização combinatória explorando um espaço de busca e podando ramos que não podem levar a uma solução ótima.
Conceitualmente, ele estende a busca combinatória ao associar cada solução parcial a um limite (bound) que estima o melhor resultado possível a partir daquele estado.
Em vez de explorar todas as possibilidades, o algoritmo foca em regiões promissoras e descarta aquelas que não podem melhorar a melhor solução atual.
Referência:
a apresentação segue o tratamento clássico utilizado em
projeto de algoritmos e otimização combinatória,
conectando árvores de busca, limites e estratégias de poda.
Partes
- Parte 1 — Modelo do Problema & Espaço de Busca
- Parte 2 — Ideia Central (Branch + Bound + Poda)
- Parte 3 — Algoritmo Genérico de Branch & Bound
- Parte 4 — Funções de Limite (Bounding)
- Parte 5 — Estratégias de Seleção de Nós
- Parte 6 — Problemas Clássicos
- Parte 7 — Complexidade
- Parte 8 — Branch & Bound vs Backtracking vs Programação Dinâmica