Branch and Bound

Definição

Branch and Bound é uma técnica de busca usada para resolver problemas de otimização combinatória, onde o objetivo é encontrar a melhor solução possível (não apenas uma solução válida). Ao contrário do backtracking, que visa encontrar qualquer solução válida, o Branch and Bound busca sempre a melhor — e evita caminhos improdutivos com base em limites.

Ela combina:

Branching: divisão do problema em subproblemas menores (como no backtracking);
Bounding: cálculo de limites (bounds) para evitar explorar caminhos que não podem levar à solução ótima.

Se um ramo não puder melhorar a melhor solução já encontrada, ele é descartado — isso reduz drasticamente o espaço de busca.

Por que usar

Ideal para problemas em que todas as combinações possíveis são muito numerosas (exponenciais);
Mais eficiente que backtracking puro em problemas de otimização;
Garante a melhor solução, sem precisar testar todas as possibilidades.

Exemplos clássicos

Problema do Caixeiro Viajante (TSP);
Mochila Inteira (0/1);
Alocação de tarefas com custo mínimo;
Programação inteira.

Complexidade

Pode chegar a tempo exponencial, mas melhora muito com bons limites (bounds);
Depende de estratégias de poda e heurísticas para eficiência.

Exemplo prático (Python) — Mochila 0/1 com poda

Este código resolve o problema da mochila 0/1, buscando o maior valor possível de itens que caibam na mochila. Usa a técnica de Branch and Bound para evitar caminhos que não podem levar à melhor solução.

# Classe que representa um item com valor e peso
class Item:
    def __init__(self, valor, peso):
        self.valor = valor
        self.peso = peso
        self.densidade = valor / peso

# Resolve o problema da mochila 0/1 com Branch and Bound
def mochila_branch_and_bound(capacidade, itens):
    itens.sort(key=lambda x: x.densidade, reverse=True)
    melhor_valor = 0

    # Função recursiva que explora as decisões
    def explorar(indice, valor_atual, peso_atual):
        nonlocal melhor_valor

        if peso_atual > capacidade:
            return  # Excede a capacidade, descarta

        if valor_atual > melhor_valor:
            melhor_valor = valor_atual

        if indice >= len(itens):
            return  # Todos os itens foram considerados

        # Cálculo do limite otimista (bound)
        restante = capacidade - peso_atual
        estimativa = valor_atual
        i = indice
        while i < len(itens) and restante > 0:
            if itens[i].peso <= restante:
                estimativa += itens[i].valor
                restante -= itens[i].peso
            else:
                estimativa += itens[i].densidade * restante
                break
            i += 1

        if estimativa < melhor_valor:
            return  # Poda: não vale a pena continuar

        # Explora com e sem incluir o item atual
        explorar(indice + 1, valor_atual + itens[indice].valor, peso_atual + itens[indice].peso)
        explorar(indice + 1, valor_atual, peso_atual)

    explorar(0, 0, 0)
    return melhor_valor

# Exemplo
itens = [
    Item(valor=60, peso=10),
    Item(valor=100, peso=20),
    Item(valor=120, peso=30)
]

capacidade = 50
resultado = mochila_branch_and_bound(capacidade, itens)
print("Melhor valor possível:", resultado)  # Saída esperada: 220

Saída

Melhor valor possível: 220