8. Backtracking vs DFS vs Programação Dinâmica
- Por que essas técnicas são frequentemente confundidas
- Como backtracking difere de DFS puro
- Como backtracking difere de Programação Dinâmica
- Que tipo de problema cada método resolve melhor
- Como escolher a ferramenta certa na prática
Backtracking, Busca em Profundidade (DFS) e Programação Dinâmica (DP) são técnicas fundamentais em projeto de algoritmos.
Às vezes elas parecem semelhantes porque as três podem envolver recursão, transições de estado e exploração estruturada.
No entanto, elas resolvem tipos diferentes de problemas e se baseiam em ideias centrais diferentes.
8.1 Backtracking vs DFS
O backtracking frequentemente é implementado como uma travessia em profundidade de uma árvore de busca.
É por isso que ele pode parecer DFS.
- DFS: estratégia de travessia para grafos ou árvores
- Backtracking: método de busca para construir soluções sob restrições
8.2 DFS como mecanismo de travessia
DFS é um padrão genérico de travessia: ir fundo primeiro e depois retornar.
Ele é usado em:
- travessia de grafos
- detecção de ciclos
- ordenação topológica
- componentes conexas
DFS não define, por si só, restrições, escolhas candidatas ou regras de construção de solução.
8.3 Backtracking como busca com restrições
O backtracking usa um padrão em profundidade, mas seu objetivo é diferente.
Ele constrói incrementalmente uma solução candidata, verifica a viabilidade e desfaz escolhas quando necessário.
- construir solução parcial
- testar restrições
- podar ramos inválidos
- desfazer e tentar outra opção
Assim, o backtracking pode ser visto como DFS + restrições + lógica de desfazer.
8.4 Backtracking vs Programação Dinâmica
Backtracking e Programação Dinâmica são frequentemente comparados porque ambos podem resolver problemas combinatórios.
Mas eles se baseiam em ideias muito diferentes:
- Backtracking: explorar possibilidades e podar
- Programação Dinâmica: reutilizar soluções de subproblemas sobrepostos
8.5 Subproblemas sobrepostos
A Programação Dinâmica se torna poderosa quando o mesmo subproblema aparece muitas vezes.
Nesse caso, recalculá-lo é desperdício.
DP evita trabalho repetido por meio de memoização ou tabulação.
8.6 Quando DP substitui o backtracking
Alguns problemas que parecem convidar ao backtracking podem, na verdade, ser resolvidos de forma mais eficiente com DP.
Isso acontece quando:
- há forte sobreposição de subproblemas
- existe subestrutura ótima
- o estado pode ser representado de forma compacta
Nesses casos, DP pode reduzir uma recursão exponencial para tempo polinomial.
8.7 Comparação prática
| Técnica | Ideia principal | Melhor para |
|---|---|---|
| DFS | Explorar em profundidade primeiro | Travessia de grafos e árvores |
| Backtracking | Busca com restrições e desfazer | Satisfação de restrições e busca combinatória |
| Programação Dinâmica | Reutilizar subproblemas repetidos | Otimização e subproblemas sobrepostos |
8.8 Como escolher
Uma regra prática útil é:
- Use DFS quando o problema for principalmente de travessia
- Use Backtracking quando for necessário construir soluções sob restrições
- Use Programação Dinâmica quando subproblemas repetidos puderem ser reutilizados
Conclusão da série
O backtracking é melhor entendido não como “apenas recursão”, mas como um método disciplinado para explorar um espaço de busca com restrições.
Ao longo desta série, estudamos seu modelo de problema, mecanismo recursivo, estrutura da árvore de busca, poda, aplicações clássicas, complexidade e relação com outras técnicas importantes.