2. A Ideia Central (Explorar + Desfazer)
- Por que o backtracking é um método de exploração incremental
- Como o algoritmo avança por meio de escolhas
- Por que ramos inválidos são abandonados cedo
- O que significa desfazer uma escolha
- Como a recursão corresponde à estrutura da árvore de busca
Uma vez que o espaço de busca é modelado como uma árvore de soluções parciais, a questão central passa a ser: como percorremos essa árvore de forma eficiente?
A ideia essencial do backtracking é simples: explorar uma escolha, continuar recursivamente e desfazê-la se necessário.
2.1 Construção incremental
O backtracking não gera soluções completas de uma só vez. Ele as constrói passo a passo.
Em cada etapa, o algoritmo estende uma solução parcial fazendo uma nova decisão.
Essa estrutura incremental é o que torna a poda possível: podemos rejeitar uma direção ruim antes de completar toda a atribuição.
2.2 Explorar
Explorar significa: escolher uma possível extensão da solução parcial atual e descer para o ramo correspondente da árvore de busca.
Se o nó atual é (x₁, …, xᵢ), então explorar corresponde a selecionar um valor para xᵢ₊₁.
Na linguagem de árvores, isso significa mover-se de um nó para um de seus filhos.
2.3 Testar cedo
Depois de fazer uma escolha, o algoritmo verifica se a nova solução parcial ainda é viável.
Se as restrições já foram violadas, não há motivo para continuar aprofundando nesse ramo.
2.4 Becos sem saída
Um ramo se torna um beco sem saída quando a solução parcial atual não pode ser estendida para nenhuma solução completa válida.
Isso pode acontecer porque:
- uma restrição é violada imediatamente
- não resta nenhuma próxima escolha válida
- a estrutura do ramo torna a conclusão impossível
Nesse ponto, o algoritmo para de descer e retorna.
2.5 Desfazer
Desfazer uma escolha significa remover a decisão mais recente e restaurar o estado anterior da busca.
Conceitualmente:
É por isso que a técnica se chama backtracking: o algoritmo volta ao nível anterior e tenta outra opção.
2.6 Por que a recursão se encaixa naturalmente
O espaço de busca tem uma estrutura de árvore, e a recursão é o mecanismo natural para percorrer árvores.
Cada chamada recursiva corresponde a:
- um nó na árvore de busca
- uma solução parcial
- um nível ativo de tomada de decisão
Retornar da recursão corresponde exatamente a desfazer a última escolha.
2.7 A intuição completa
O mecanismo completo pode ser resumido assim:
- Construir uma solução parcial
- Tentar uma possível próxima escolha
- Testar se o ramo ainda é viável
- Se sim, continuar recursivamente
- Se não, desfazer a escolha e tentar outra
Próximo: Parte 3 — Algoritmo Genérico de Backtracking
Agora que o mecanismo central está claro, podemos passar da intuição para a estrutura formal.
Na Parte 3, escreveremos o algoritmo genérico de backtracking e identificaremos seus componentes padrão: estado, geração de escolhas, teste de viabilidade, recursão e etapa de desfazer.