6. Problemas Clássicos
- Por que o backtracking aparece em muitos problemas clássicos
- Como diferentes problemas compartilham a mesma estrutura de busca
- O que muda de um problema para outro
- Como as restrições definem estratégias de poda
- Por que esses exemplos são importantes em algoritmos e entrevistas
Backtracking não é um truque específico de um único problema.
É uma estratégia geral de busca que aparece em muitos problemas clássicos de combinatória, teoria dos grafos e satisfação de restrições.
O objetivo desta parte é conectar o algoritmo genérico com aplicações concretas e bem conhecidas.
6.1 Geração de Permutações
Uma das aplicações mais simples de backtracking é gerar todas as permutações de um conjunto.
Em cada nível, o algoritmo escolhe um elemento que ainda não foi utilizado.
- Solução parcial = prefixo da permutação
- Escolhas = elementos não utilizados
- Objetivo = permutação completa
Este costuma ser o primeiro problema usado para introduzir backtracking.
6.2 Geração de Subconjuntos
Outro exemplo clássico é gerar todos os subconjuntos de um conjunto.
Cada decisão responde a uma pergunta binária: incluir ou não incluir um elemento.
- Cada nível corresponde a um elemento
- Cada nó gera dois ramos
- As folhas representam subconjuntos completos
Isso torna a árvore de busca muito clara e fácil de visualizar.
6.3 N-Queens
O problema das N-Rainhas é um dos exemplos mais famosos de backtracking.
O objetivo é posicionar n rainhas em um tabuleiro n × n sem que elas se ataquem.
- Solução parcial = rainhas já posicionadas
- Escolhas = colunas possíveis na próxima linha
- Restrições = sem conflito em coluna ou diagonal
6.4 Sudoku
Sudoku também pode ser resolvido com backtracking.
O algoritmo preenche as células vazias uma a uma, verificando se cada escolha respeita as regras.
- Escolhas = números possíveis para a célula
- Restrições = linha, coluna e subgrade
- Objetivo = preencher todo o tabuleiro
Esse é um ótimo exemplo de poda baseada em restrições.
6.5 Coloração de Grafos
Na coloração de grafos, atribuímos cores aos vértices de forma que vértices adjacentes tenham cores diferentes.
O backtracking atribui cores vértice por vértice.
- Solução parcial = cores atribuídas
- Escolhas = cores disponíveis
- Restrição = vértices adjacentes não podem ter a mesma cor
Esse problema conecta backtracking diretamente à teoria dos grafos.
6.6 Caminho Hamiltoniano
O problema do caminho Hamiltoniano busca um caminho que visita cada vértice exatamente uma vez.
O backtracking explora sequências possíveis de vértices, descartando aquelas inválidas.
- Solução parcial = caminho atual
- Escolhas = próximos vértices válidos
- Objetivo = visitar todos os vértices
6.7 Estrutura Comum
Apesar das diferenças, todos esses problemas compartilham a mesma estrutura:
- construir solução incrementalmente
- gerar escolhas
- testar restrições
- recursão
- desfazer (backtrack)
O que muda não é o algoritmo, mas a definição de estado, escolhas e restrições.
Próximo: Parte 7 — Complexidade
Agora que vimos aplicações reais, o próximo passo é analisar o custo computacional.
Na Parte 7, estudamos fator de ramificação, profundidade e comportamento no pior caso.