5. Poda
- Por que a poda é essencial
- Como restrições reduzem o espaço de busca
- Poda antecipada vs tardia
- Limites (bounding) e otimização
- Impacto na complexidade
Backtracking sem poda geralmente é impraticável.
A árvore de busca cresce exponencialmente, e explorar todos os ramos rapidamente se torna inviável.
A poda é o que torna o backtracking eficiente.
5.1 Por que a poda é importante
Em muitos problemas, a árvore de busca completa é enorme.
No entanto, a maioria dos ramos não leva a soluções válidas.
A poda permite que o algoritmo ignore subárvores inteiras que não podem produzir uma solução válida.
5.2 Poda baseada em restrições
A forma mais básica de poda vem das restrições.
Se uma solução parcial viola restrições, paramos imediatamente a exploração.
Isso é chamado de poda antecipada.
5.3 Poda antecipada vs tardia
A poda pode ocorrer em diferentes momentos:
- Poda antecipada: rejeitar o mais cedo possível
- Poda tardia: rejeitar após explorar mais profundamente
5.4 Limites (Bounding) em problemas de otimização
Em problemas de otimização, podemos usar limites para podar.
Se uma solução parcial não pode superar a melhor solução conhecida, ela pode ser descartada.
Essa ideia é a base do Branch and Bound.
5.5 Impacto na complexidade
Em teoria, backtracking é exponencial.
Mas com poda eficiente, o número real de nós explorados pode ser drasticamente menor.
- Pior caso: exponencial
- Com poda: frequentemente muito mais rápido na prática
5.6 Intuição
Sem poda:
explorar tudo → lento
Com poda:
explorar apenas caminhos promissores → rápido
5.7 Resumo
- A poda elimina ramos inúteis
- Restrições permitem poda antecipada
- Limites permitem poda em otimização
- A eficiência depende fortemente da qualidade da poda
Próximo: Parte 6 — Problemas Clássicos
Agora que entendemos como o backtracking funciona e como torná-lo eficiente, podemos estudar problemas reais.
Na Parte 6, aplicamos backtracking em problemas clássicos como N-Queens, permutações e problemas em grafos.