O que o Backtracking Resolve
Backtracking é uma técnica geral para explorar um espaço de busca combinatório construindo soluções candidatas de forma incremental e abandonando estados parciais que não podem levar a uma resposta final válida.
Conceitualmente, o backtracking realiza uma exploração em profundidade de uma árvore de busca, em que cada nó representa uma solução parcial, cada aresta representa uma escolha, e ramos fracassados são desfeitos para que o algoritmo possa tentar outra possibilidade.
Referência:
a apresentação segue o tratamento clássico usado em
projeto de algoritmos e busca combinatória,
conectando exploração recursiva, poda e árvores de busca.
Partes
- Parte 1 — Modelo do Problema & Espaço de Busca
- Parte 2 — A Ideia Central (Explorar + Desfazer)
- Parte 3 — Algoritmo Genérico de Backtracking
- Parte 4 — Árvore de Busca & Estrutura de Recursão
- Parte 5 — Poda
- Parte 6 — Problemas Clássicos
- Parte 7 — Complexidade
- Parte 8 — Backtracking vs DFS vs Programação Dinâmica