4. Funções de Bounding
- O que uma função de bounding deve fazer
- A diferença entre limites apertados e frouxos
- Limites superiores vs. limites inferiores
- Trade-offs entre a qualidade do limite e o custo de computação
- Por que funções de bounding determinam o desempenho na prática
No Branch & Bound, a busca não é guiada apenas por força bruta. Ela é guiada por estimativas.
Essas estimativas vêm das funções de bounding, que nos dizem quão promissora é uma solução parcial e se ainda vale a pena explorá-la.
4.1 O que é uma função de bounding?
Uma função de bounding mapeia uma solução parcial para uma estimativa numérica de sua melhor conclusão possível.
A interpretação exata depende do problema de otimização:
- em maximização, frequentemente é um limite superior
- em minimização, frequentemente é um limite inferior
Em ambos os casos, o propósito é o mesmo: determinar se o nó ainda pode produzir uma solução melhor do que a melhor solução atual.
4.2 Limites seguros
Uma função de bounding deve ser segura.
Isso significa que ela nunca deve subestimar o que é possível em maximização, e nunca deve superestimar o que é possível em minimização, se for usada para poda.
Caso contrário, o algoritmo pode descartar incorretamente um ramo que de fato contém a solução ótima.
4.3 Limites apertados vs. frouxos
Nem todos os limites válidos são igualmente úteis.
- Um limite apertado permanece próximo do verdadeiro melhor valor alcançável.
- Um limite frouxo é válido, mas otimista ou conservador demais.
Limites apertados permitem mais poda porque distinguem nós promissores de nós fracos de forma mais precisa.
Limites frouxos preservam a corretude, mas frequentemente deixam muitos ramos ativos.
4.4 Qualidade do limite vs. custo de computação
Um limite melhor nem sempre é melhor na prática.
Existe um trade-off:
- um limite barato pode ser fraco, mas rápido de calcular
- um limite forte pode podar mais, mas custar mais por nó
O design prático de Branch & Bound frequentemente depende de equilibrar esses dois efeitos.
4.5 Bounding em maximização e minimização
A regra de poda depende da direção da otimização.
Em maximização:
Em minimização:
Essas regras expressam o mesmo princípio: descartar nós que não podem melhorar a melhor solução conhecida.
4.6 De onde vêm os limites
Funções de bounding são específicas do problema.
Elas são frequentemente derivadas de:
- relaxações do problema original
- aproximações gulosas
- subproblemas simplificados
- desigualdades matemáticas
Por exemplo, no problema da mochila 0/1, um limite superior comum vem de permitir itens fracionários, o que torna o problema mais fácil e fornece uma estimativa otimista segura.
4.7 Por que funções de bounding importam tanto
Em teoria, Branch & Bound é definido por branching, bounding e pruning. Na prática, seu desempenho é frequentemente dominado pela qualidade do limite.
Dois algoritmos com a mesma estrutura de branching podem se comportar de forma muito diferente se um usa um limite forte e o outro usa um limite fraco.
É por isso que funções de bounding são frequentemente a decisão de projeto mais importante em uma implementação de Branch & Bound.
4.8 Resumo
- Limites estimam a melhor conclusão possível de uma solução parcial
- Eles devem ser seguros para preservar a corretude
- Limites apertados melhoram a poda
- Limites fortes podem custar mais para calcular
- O desempenho prático depende fortemente do design do limite
Próximo: Parte 5 — Estratégias de Seleção de Nós
Uma vez que os limites estão disponíveis, a próxima questão não é apenas quais nós ainda estão ativos, mas também qual nó ativo deve ser explorado primeiro.
Na Parte 5, estudaremos as principais estratégias de seleção de nós e como elas afetam o uso de memória, a descoberta da melhor solução atual, e a eficácia geral da poda.