1. Modelo do Problema & Espaço de Busca
- Que tipo de problemas o backtracking resolve
- Como as soluções candidatas são modeladas
- Por que o espaço de busca forma uma árvore
- O papel das restrições na poda
- O objetivo preciso do método
O backtracking costuma ser introduzido informalmente como um método que tenta possibilidades e desfaz decisões quando elas falham.
Essa intuição é útil, mas para compreender a técnica de forma rigorosa precisamos primeiro definir o modelo do problema e o espaço de busca que ela explora.
1.1 Por que começar pelo modelo?
Backtracking não está ligado a um único problema específico. Ele é uma estratégia geral para explorar um conjunto estruturado de possibilidades sob restrições.
Portanto, antes de discutir recursão ou detalhes de implementação, precisamos responder:
- O que é uma solução candidata?
- Como uma solução parcial é representada?
- Quando devemos parar de explorar um ramo?
1.2 Soluções candidatas
Uma solução candidata normalmente é construída incrementalmente como uma sequência de decisões:
Cada variável xᵢ representa uma escolha feita no passo i, normalmente selecionada de um domínio de valores possíveis.
Uma atribuição completa pode representar uma solução final, enquanto um prefixo (x₁, …, xᵢ) representa uma solução parcial.
1.3 O espaço de busca
O conjunto de todas as soluções candidatas define o espaço de busca.
Esse espaço é naturalmente modelado como uma árvore:
- A raiz representa a solução vazia
- Cada nível corresponde a uma nova decisão
- Cada aresta representa uma escolha
- Cada nó representa uma solução parcial
Em termos abstratos, um nó pode ser escrito como (x₁, …, xᵢ).
1.4 Restrições
Nem toda solução parcial vale a pena explorar.
Um problema de backtracking é definido juntamente com restrições que determinam se uma atribuição parcial ainda pode ser estendida para uma solução completa válida.
Se a atribuição parcial atual viola a estrutura do problema, o algoritmo interrompe a exploração daquele ramo.
1.5 Soluções viáveis vs. completas
É útil distinguir dois conceitos:
- Solução parcial viável: não viola as restrições
- Solução completa: satisfaz todos os requisitos do problema
O backtracking passa a maior parte do tempo explorando soluções parciais viáveis e verificando se elas podem ser estendidas.
A viabilidade é uma condição local, enquanto a completude é global.
1.6 O objetivo do backtracking
Dependendo do problema, o objetivo pode ser:
- Encontrar uma solução válida
- Encontrar todas as soluções válidas
- Contar quantas soluções existem
- Encontrar uma solução ótima segundo algum critério
Em todos os casos, o método explora sistematicamente a árvore de busca enquanto poda ramos impossíveis.
1.7 Por que isso é importante
Esse modelo aparece em vários problemas clássicos:
- N-Rainhas
- Sudoku
- Geração de permutações
- Geração de subconjuntos
- Coloração de grafos
- Busca de caminho Hamiltoniano
Em todos eles a ideia central é a mesma: construir soluções incrementalmente, testar restrições cedo e voltar atrás quando um ramo se torna impossível.
Próximo: Parte 2 — A Ideia Central (Explorar + Desfazer)
Agora que definimos a estrutura do espaço de busca, o próximo passo é entender o mecanismo que o explora.
Na Parte 2 estudaremos como a exploração recursiva funciona, por que as escolhas são desfeitas e como esse processo percorre sistematicamente a árvore de busca.