Matemática Discretapara Engenheiros

3. Algoritmo Genérico de Backtracking

Agora que entendemos a intuição por trás do backtracking, podemos formalizar a técnica como um algoritmo genérico.

Muitos problemas clássicos compartilham a mesma estrutura, mesmo que suas restrições e espaços de busca sejam diferentes.

Por esse motivo, o backtracking é melhor compreendido por meio de um template algorítmico genérico.

3.1 Representação do estado

Em qualquer ponto do algoritmo, mantemos uma solução parcial.

Essa sequência representa as decisões tomadas até o momento.

Portanto, o estado do algoritmo consiste em:

• a atribuição parcial atual
• a profundidade na árvore de busca
• as possíveis escolhas restantes

3.2 Geração de escolhas

A partir de uma solução parcial (x₁, …, xᵢ), o algoritmo gera possíveis extensões para a próxima variável de decisão.

Esses valores normalmente vêm de um domínio de candidatos viáveis.

Cada candidato corresponde a um nó filho na árvore de busca.

3.3 Teste de viabilidade

Antes de explorar um ramo mais profundamente, o algoritmo verifica se a nova solução parcial ainda satisfaz as restrições.

Se o teste de restrição falhar, o ramo é podado imediatamente.

3.4 Detectando uma solução completa

Uma solução completa é obtida quando todas as variáveis de decisão foram atribuídas.

Em outras palavras, quando a profundidade da árvore de busca atinge o nível necessário.

Nesse momento, o algoritmo pode:

• registrar a solução
• imprimir a solução
• atualizar um valor ótimo
• interromper a busca (se apenas uma solução for necessária)

3.5 Template genérico de backtracking

A estrutura geral de um algoritmo de backtracking pode ser escrita da seguinte forma:

BACKTRACK(state):

    if state is a complete solution:
        report solution
        return

    for each candidate choice c:
        
        if c is feasible:
            apply choice c
            
            BACKTRACK(updated state)
            
            undo choice c

Esse template captura todo o mecanismo: explorar uma escolha, chamar recursivamente, e desfazer a escolha em seguida.

3.6 Estrutura da árvore de busca

O algoritmo explora implicitamente uma estrutura de árvore.

• Cada nó representa uma solução parcial
• Cada aresta representa uma decisão
• As folhas correspondem a atribuições completas

O poder do backtracking vem da capacidade de podar grandes partes dessa árvore antes de explorá-las completamente.

3.7 Por que esse template é importante

Muitos algoritmos clássicos são instâncias diretas desse template.

• N-Queens
• Resolução de Sudoku
• Geração de permutações
• Geração de subconjuntos
• Coloração de grafos
• Busca de caminho Hamiltoniano

Em todos esses casos, as diferenças estão nos testes de restrição e na geração de candidatos, e não na estratégia de busca subjacente.