Backtracking
Backtracking é a técnica que resolve problemas em que a resposta não se calcula, se procura: sudoku, n rainhas, todos os subconjuntos de um array, todos os caminhos de um labirinto. A ideia cabe em três palavras (escolher, explorar, desfazer) e a terceira é a que dá nome a ela e a que todo mundo esquece de escrever.
Tentar, falhar, e desfazer
Imagine percorrer um labirinto sem mapa. Você anda até bater numa parede, volta até a última bifurcação, e tenta o outro caminho. Se ele também acaba em parede, volta de novo. Você não é esperto, você é sistemático: nenhum caminho fica sem ser tentado, e nenhum é tentado duas vezes.
Isso é backtracking, e o nome vem justamente do movimento de voltar. O algoritmo tem três passos, sempre os mesmos:
Pegue uma das opções disponíveis e acrescente-a à solução parcial.
Chame o algoritmo de novo, agora com essa escolha feita, e resolva o resto.
Tire a escolha da solução parcial, para poder tentar a próxima opção do mesmo ponto.
O terceiro passo é o que separa backtracking de uma busca qualquer. Sem ele, a solução parcial acumula lixo das tentativas anteriores e o algoritmo passa a explorar combinações que nunca existiram. E ele é uma linha só, o que o torna fácil de esquecer e difícil de depurar quando falta.
Todo nó da árvore é uma resposta, inclusive a raiz (o conjunto vazio). Repare que o algoritmo registra a solução na ENTRADA de cada chamada, antes de olhar as opções, e por isso são 2^3 = 8 respostas para 8 nós.
Subconjuntos de 1, 2, 3. A solução parcial começa vazia e o algoritmo vai fazer sempre a mesma coisa: escolher uma opção, explorar tudo que sai dela, e desfazer a escolha para poder tentar a próxima.
Rode os três até o fim e compare nós visitados com soluções encontradas: 8 e 8 nos subconjuntos, 16 e 6 nas permutações, 10 e 6 nas combinações. Nas permutações, dez dos dezesseis nós são caminho e não resposta, e é esse desperdício que faz o custo do backtracking ser exponencial. O número de retrocessos é sempre igual ao de arestas da árvore: todo escolher tem exatamente um desfazer.
←→ passo · espaço roda
A árvore de decisão não existe
Todo material sobre backtracking desenha uma árvore, e a árvore ajuda muito. Ela também engana, porque dá a impressão de que existe uma árvore sendo construída na memória.
Não existe. O que existe é:
- uma lista com a solução parcial, que cresce quando você escolhe e encolhe quando você desfaz;
- a pilha de chamadas da recursão, que guarda em que ponto cada chamada parou.
A árvore é o desenho do caminho que o algoritmo percorreu, feito depois. Dá para conferir isso no visualizador acima: no passo de retrocesso, a árvore não perde nenhum nó (ela é histórico), a lista encolhe um elemento e a pilha desempilha um quadro. Três coisas que parecem uma só andando em ritmos diferentes.
Essa distinção não é preciosismo. Ela é o que permite entender o consumo de memória: um backtracking sobre 20 elementos pode visitar milhões de nós e nunca guardar mais do que 20 elementos na lista e 20 quadros na pilha.
A semelhança com DFS é real e vale explorar: os dois vão fundo até não dar mais e voltam. A diferença é que o DFS percorre um grafo que existe e marca o que já visitou, enquanto o backtracking percorre um espaço de possibilidades que ele gera enquanto anda, e desfaz em vez de marcar.
O template, e as três peças que mudam
Praticamente todo problema de backtracking cabe neste molde:
def backtrack(parcial, opcoes):
if completo(parcial):
solucoes.append(parcial[:]) # cópia, e isso importa
return
for opcao in opcoes:
if valido(opcao, parcial):
parcial.append(opcao) # 1. escolher
backtrack(parcial, ...) # 2. explorar
parcial.pop() # 3. desfazerTrocar de problema é trocar três peças: quais são as opções, o que é válido e o que é uma solução completa. O esqueleto não muda.
| Problema | opções | válido | completo |
|---|---|---|---|
| Subconjuntos | os elementos do índice atual em diante | tudo é válido | todo estado é resposta |
| Permutações | todos os elementos ainda não usados | ainda não usado | usou todos |
| Combinações de k | do índice atual em diante | tudo é válido | tamanho igual a k |
| Sudoku | os dígitos de 1 a 9 | não repete na linha, coluna e quadrante | não sobrou célula vazia |
| N rainhas | as colunas da linha atual | nenhuma rainha ataca | pôs n rainhas |
Vale marcar a diferença entre os três primeiros, porque ela confunde bastante e cai em entrevista. Permutação usa todos os elementos e a ordem importa (1 2 3 e 3 2 1 são respostas diferentes): são n!. Combinação escolhe alguns e a ordem não importa (1 2 e 2 1 são a mesma): são C(n, k). Subconjunto é qualquer seleção mantendo a ordem original, inclusive a vazia: são 2ⁿ. Se essa distinção ainda embaralhar, vale passar em Os 4 "sub".
Os números do visualizador mostram o custo de cada um com três elementos: subconjuntos visitam 8 nós e devolvem 8 respostas, permutações visitam 16 nós e devolvem 6. Nas permutações, dez dos dezesseis nós são caminho e não resultado, e é esse desperdício que faz o backtracking custar caro.
Existe uma invariante bonita para conferir se o seu backtracking está correto: o número de retrocessos é sempre igual ao número de arestas da árvore, e no fim a solução parcial tem que voltar exatamente ao estado inicial. Se ela terminar com sobras, faltou um pop.
A cópia que salva as respostas
Aquele parcial[:] do template é o detalhe que mais causa bug em backtracking, e o motivo é sutil.
A solução parcial é uma lista só, a mesma da primeira à última chamada. Quando você encontra uma resposta e faz solucoes.append(parcial), você não guarda a resposta: guarda uma referência para a lista que continua sendo modificada. No fim da execução, a lista voltou a ficar vazia (porque todo escolher teve o seu desfazer), e todas as respostas guardadas apontam para ela.
O resultado é um dos bugs mais desconcertantes de depurar: a função encontra as soluções certas, você vê cada uma delas passando no depurador, e o retorno é uma lista com o número certo de elementos, todos vazios.
solucoes.append(parcial) # errado: guarda a lista viva
solucoes.append(parcial[:]) # certo: guarda uma foto dela
solucoes.append(list(parcial))# idemA mesma armadilha existe em Java, C#, JavaScript e qualquer linguagem em que listas sejam objetos passados por referência. E ela não aparece em teste pequeno com uma solução só, porque com uma resposta o momento da leitura pode ser antes de a lista mudar.
Sudoku é o mesmo algoritmo
Sudoku parece um problema de outra natureza, e é o mesmo template com as três peças trocadas: as opções são os dígitos de 1 a 9, a validade é a regra do jogo (sem repetir na linha, na coluna e no quadrante), e desfazer é apagar a célula.
def resolver(grade):
pos = primeira_vazia(grade)
if pos is None: return True # completo
for d in range(1, 10): # as opções
if valido(grade, pos, d): # a validade
grade[pos] = d # 1. escolher
if resolver(grade): # 2. explorar
return True
grade[pos] = VAZIO # 3. desfazer
return False # nenhum dígito serviuAs mesmas regras num tabuleiro que cabe na cabeça: dígitos de 1 a 4, sem repetir na linha, na coluna e no quadrante 2x2. Acompanhe uma célula específica e conte quantas vezes ela é escrita e apagada antes de ficar.
Tabuleiro 4x4 com 11 lacunas. As opções de cada célula são os dígitos de 1 a 4, a validade é a regra do sudoku (linha, coluna e quadrante) e o desfazer é apagar. O algoritmo é o mesmo de sempre.
Rode o preset de 48 lacunas até o fim, na velocidade 2x, e compare os cards: 882 dígitos testados para 48 lacunas, com 120 escritas e 72 retrocessos. São 18 tentativas por célula, e o algoritmo escreve e apaga a mesma posição várias vezes; cada apagada é a descoberta de que uma escolha feita lá atrás não levava a lugar nenhum. É o mesmo template do visualizador anterior, com três peças trocadas: as opções viraram os dígitos, a validade virou a regra do sudoku, e o desfazer virou apagar a célula.
←→ passo · espaço roda
Duas coisas ficam visíveis rodando isso que nenhum texto transmite bem.
A primeira é que caber não é estar certo. Quando o algoritmo escreve um dígito, ele só verificou que aquele valor não conflita com o que já está no tabuleiro agora. É uma aposta, e ela pode ser desmentida vinte células adiante.
A segunda é o preço. No tabuleiro com 48 lacunas, o algoritmo testa 882 dígitos para preencher 48 células, com 120 escritas e 72 retrocessos: cerca de 18 tentativas por célula. Ele escreve e apaga a mesma posição várias vezes, e cada apagada é a descoberta de que uma escolha feita lá atrás não levava a lugar nenhum.
Repare no que o algoritmo faz quando o tabuleiro tem várias soluções válidas: ele para na primeira que encontrar, não na "certa", porque para ele não existe uma certa. Se você precisa de todas, tire o return True e deixe a recursão continuar depois de registrar; se você precisa da melhor por algum critério, precisa comparar todas ou usar uma técnica diferente.
Poda: a mesma resposta por uma fração do trabalho
A otimização mais importante do backtracking não muda o algoritmo, muda quando a validade é conferida. Comparar as duas versões no problema das n rainhas deixa isso quantitativo.
O problema: pôr 6 rainhas num tabuleiro 6x6 sem que nenhuma ataque outra, ou seja, sem duas na mesma linha, coluna ou diagonal. As duas versões abaixo são o mesmo backtracking, e a única diferença é quando a validade é conferida.
As duas versões devolvem 4 soluções, e são as mesmas soluções, uma a uma. A poda não troca a resposta por uma aproximação, ela só evita descer por caminhos que já são impossíveis: com 6 rainhas, ela corta 742 escolhas antes de virarem ramo e visita 153 nós contra 55.987, 365.9 vezes menos. É a diferença entre perguntar "isto ainda pode dar certo?" a cada passo e perguntar só no fim.
Repare em como a razão cresce com o tabuleiro: 20x com 4 rainhas, 366x com 6 e 1.741x com 7. Podar não muda a classe de complexidade (as duas continuam exponenciais) e muda o expoente na prática, que é o que separa um algoritmo que roda de um que não termina. Com 8 rainhas a versão sem poda visitaria 19.173.961 nós, e é por isso que ela não está aqui: desenhar essa barra custaria segundos de CPU do seu navegador. É a mesma ideia que aparece depois em programação dinâmica, com um nome diferente: em vez de cortar o ramo impossível, guardar o resultado do ramo já calculado.
Sem poda, o algoritmo monta todas as disposições possíveis de rainhas e só no fim pergunta se aquela disposição é válida. Com 7 rainhas, isso significa visitar 960.800 nós.
Com poda, antes de descer ele pergunta se a rainha nova já é atacada por alguma das que estão no tabuleiro. Quando é, o ramo inteiro que sairia daquela escolha deixa de existir. Mesmas 40 soluções, 552 nós, 1.741 vezes menos trabalho.
E a diferença cresce com o tamanho: 20 vezes com 4 rainhas, 366 com 6, 1.741 com 7. Com 8 rainhas, a versão sem poda visitaria (8⁹ - 1) / 7 = 19.173.961 nós para achar as 92 soluções, contra 2.057 da versão com poda.
Podar não muda a classe de complexidade. As duas continuam exponenciais, e existe entrada capaz de fazer a poda não cortar nada. O que ela muda é o expoente na prática, que costuma ser a diferença entre um algoritmo que roda e um que não termina.
O custo, e para onde isso vai
O custo do backtracking se descreve por O(b^d), onde b é o fator de ramificação (quantas opções existem em cada ponto) e d é a profundidade da solução. Os dois vêm do problema, não do código.
| Problema | quantas respostas | ordem de grandeza |
|---|---|---|
| Subconjuntos de n | 2ⁿ | exponencial |
| Permutações de n | n! | fatorial |
| Combinações de k entre n | C(n, k) | polinomial em n, para k fixo |
| N rainhas | não tem fórmula fechada | exponencial |
A diferença entre exponencial e fatorial não é acadêmica: com 10 elementos são 1.024 subconjuntos e 3.628.800 permutações; com 20, são cerca de um milhão contra 2,4 × 10¹⁸. Vale revisitar Big O para dimensionar isso antes de escrever o código, e não depois de o processo travar.
Isso põe o backtracking num lugar específico do repertório. Ele é a resposta quando:
- o problema pede todas as soluções, e não uma medida sobre elas;
- o espaço de busca é grande mas as restrições cortam muito (é o caso do sudoku);
- não existe estrutura melhor conhecida, e uma resposta correta e lenta vale mais que nenhuma.
E ele é o ponto de partida de quase toda otimização seguinte. O caminho usual é: escreva o backtracking, veja que ele estoura o tempo, e então observe que muitos ramos recalculam a mesma coisa. Guardar esses resultados em vez de recalculá-los é memoização, e é a porta de entrada da programação dinâmica. A relação entre as duas técnicas é simples de dizer e difícil de enxergar na primeira vez: backtracking explora todas as soluções, programação dinâmica quebra o problema em subproblemas que se repetem. Quando o seu backtracking repete subproblemas, ele está pedindo para virar programação dinâmica.
Daqui, Recursão é a base que sustenta tudo isto (o backtracking é uma recursão com um passo de desfazer), e DFS e BFS mostram o mesmo movimento de descer e voltar sobre uma estrutura que já existe.
Vídeo da aula
Direto do canal da comunidade Craft & Code Club · 2:08:38.
Problemas para praticar
Na ordem em que recomendamos resolver. Marque os que você já fez, fica salvo aqui.
Referências
Artigos e materiais externos para se aprofundar.
Travou em algum passo? Traga sua questão para o Discord da comunidade ou para os encontros semanais.
EntrarEste tópico faz parte de
Ver todos →Backtracking aparece num percurso com objetivo próprio. O conteúdo é o mesmo; o que muda é a pergunta que ele responde ali, e o que vem antes e depois.