Backtracking

Este texto continua o de Recursão: tudo aqui parte da mesma ideia de caso base e passo recursivo, aplicada a um tipo específico de problema, aquele em que precisamos procurar uma resposta entre muitas possibilidades.

O assunto é construído em camadas. Primeiro, a forma mais simples de resolver esse tipo de problema: gerar e testar todas as possibilidades (força bruta). Depois, como abandonar cedo os caminhos que claramente não vão dar certo (poda). Com esses dois ingredientes chegamos à definição de backtracking e a um estudo de caso: encontrar a saída de um labirinto.

Força bruta

Sequências binárias

Começando do jeito mais simples possível: gerar todas as sequências de bits. Para são sequências: 000, 001, 010, ..., 111.

Um vetor vet de tamanho é preenchido posição por posição. Em cada posição i existem exatamente duas escolhas, 0 ou 1, e a função tenta as duas, uma de cada vez. Quando todas as posições estão preenchidas (i == n), a sequência está completa e é impressa.

A árvore abaixo mostra as chamadas para : cada nível decide um bit e cada folha é uma sequência completa. Toda combinação de bits é válida, então nenhum ramo é cortado: a árvore inteira é percorrida.

Subconjuntos

Agora, em vez de 0 e 1, interprete cada escolha como deixar de fora ou incluir um elemento. O mesmo código passa a gerar todos os subconjuntos de um conjunto de elementos. Pense em arrumar uma mochila: para cada item candidato, você decide se ele vai ou não.

Compare a árvore abaixo com a das sequências binárias: é a mesma árvore, só com rótulos diferentes ("sem A" e "com A" no lugar de 0 e 1). No fundo, os dois problemas são um só, interpretado de duas formas.

Poda

Soma de subconjuntos

Considere agora o problema de listar todos os subconjuntos de valores não negativos cuja soma não ultrapassa um limite (a mochila aguenta um peso máximo).

A solução direta seria gerar os subconjuntos e conferir a soma de cada um no final. Mas, se a soma de um subconjunto parcial já passou do limite, não faz sentido continuar incluindo elementos nele: qualquer continuação só aumenta a soma. A resposta para aquele ramo já está decidida bem antes da folha. Conferir essa condição a cada chamada e abandonar o ramo assim que ela falha é o que chamamos de poda.

Esta função tenta primeiro incluir o elemento e depois deixá-lo de fora, por isso a árvore abaixo tem a inclusão à esquerda: as folhas, da esquerda para a direita, aparecem na mesma ordem da saída.

Repare que geraSubconjuntos recebe a soma como parâmetro. Uma primeira versão poderia recalculá-la a cada chamada, percorrendo pertence do início:

long long calculaSoma(int ate) {
    long long soma = 0;
    for (int j = 0; j < ate; j++)
        if (pertence[j])
            soma += valores[j];
    return soma;
}

void geraSubconjuntos(int i) {
    if (calculaSoma(i) > limite)
        return;
    /* ... resto igual, sem o parâmetro soma ... */
}

As duas versões fazem exatamente as mesmas chamadas: é a mesma árvore, com a mesma poda. A diferença é o trabalho de cada chamada.

As duas continuam exponenciais, mas eliminar o recálculo tira um fator do total. Passar adiante o que a chamada anterior já sabe é um truque que aparece em quase todo backtracking.

Backtracking

O que backtracking não é

Antes da definição, um contraexemplo: o Fibonacci recursivo também se ramifica em duas chamadas, como geraSequencias e geraSubconjuntos.

int fib(int n) {
    if (n == 0 || n == 1)
        return n;
    return fib(n - 1) + fib(n - 2);
}

Mas fib não gera soluções distintas para listar, contar ou escolher a melhor: ela combina (soma) os resultados das duas chamadas em um único valor. Não há um espaço de soluções sendo percorrido, nem escolhas a fazer e desfazer. Ter várias chamadas recursivas não basta para ser busca exaustiva, muito menos backtracking.

Definição

Backtracking é busca exaustiva: no pior caso, ainda pode visitar o espaço de busca inteiro. A diferença é cortar os ramos que já se mostraram inúteis. Por isso o nome tentativa e erro, às vezes usado como sinônimo, descreve bem o mecanismo: tenta, e se não der certo, desfaz e tenta a próxima.

O template

Os detalhes mudam de problema para problema, mas o esqueleto é sempre este:

backtrack(estado):
    se estado é solução:
        registra a solução
        retorna

    para cada escolha possível a partir do estado:
        se a escolha é válida:
            aplica a escolha            (muda o estado)
            backtrack(novo estado)      (tenta continuar daqui)
            desfaz a escolha            (volta ao estado anterior)

Cada chamada de backtrack é um nó de uma árvore, como nas figuras anteriores. A diferença é que alguns ramos terminam antes de chegar ao fundo: ou porque a poda os cortou, ou porque uma solução foi encontrada.

Estudo de caso: o labirinto

Agora o espaço de busca não é mais um vetor de escolhas binárias, e sim um mapa.

Um exemplo de entrada (8 linhas, 10 colunas):

8 10
..........
.#####.##.
.S...#..E.
.###.#.##.
.#...#....
.#.#######
.#........
..........

Repare que a borda é livre: o mapa não é cercado por paredes, e um caminho pode passar por ela. Isso tem uma consequência importante no código, como veremos no passo 2.

No vocabulário do template:

Construindo caminha() passo a passo

O mapa fica em uma matriz alocada linha por linha, como visto em Alocação de memória. A função caminha(l, c) tenta continuar o caminho a partir da posição .

1. 1

   Poda: já achou a saída?#

   Se outro ramo já encontrou a saída, não há o que fazer aqui. Não é um caso base no sentido usual: é uma poda que corta tudo o que ainda estava na pilha.

   if (achouSaida)
       return;

2. 2

   Poda: a posição é válida?#

   Fora do mapa, parede ou já visitada: retorna. Como a borda pode ser livre, o algoritmo vai tentar andar para fora do mapa, e a checagem de limites é obrigatória. Ela também precisa vir antes do acesso a mapa[l][c].

   if (l < 0 || c < 0 || l >= nl || c >= nc)
       return;
   if (mapa[l][c] != '.' && mapa[l][c] != 'S' && mapa[l][c] != 'E')
       return;

3. 3

   Aplica a escolha. É a saída?#

   Marca a posição como visitada. Se ela era o E, achou. O teste é feito antes de marcar, porque a marca apaga o E.

   bool eSaida = (mapa[l][c] == 'E');
   mapa[l][c] = 'v';
   if (eSaida) {
       achouSaida = true;
       return;
   }

4. 4

   Tenta as 4 direções e desfaz#

   Tenta continuar por cada vizinha. Se nenhuma levou à saída, desmarca a posição: ela não faz parte do caminho.

   caminha(l, c - 1);    /* esquerda */
   caminha(l, c + 1);    /* direita  */
   caminha(l - 1, c);    /* cima     */
   caminha(l + 1, c);    /* baixo    */
   
   if (!achouSaida)
       mapa[l][c] = '.';

A main lê o mapa, procura o S e chama caminha a partir dele. No final, as células marcadas com v formam o caminho encontrado.

Vendo o backtracking acontecer

A versão abaixo imprime cada passo, com um recuo por nível de recursão: visita quando uma célula é marcada e recua quando a marca é desfeita. O mapa é menor, com um beco sem saída logo à direita do S.

O algoritmo tenta a esquerda (fora do mapa), depois a direita, entra no beco, chega ao fim dele e recua célula por célula até o S. Só então tenta subir, que é a direção que leva à saída.

Complexidade

Como as marcas são desfeitas na volta, uma mesma célula pode ser visitada várias vezes, uma para cada caminho diferente que chega até ela. No pior caso (por exemplo, quando E não é alcançável), caminha percorre todos os caminhos sem repetição de células que partem de S.

Cada célula tem até 4 vizinhas, o que sugere um limite de para caminhos de passos. O limite é válido, mas frouxo: o algoritmo nunca volta pela célula de onde veio (ela está marcada), então em quase toda chamada há no máximo 3 direções novas, o que dá .

O que o algoritmo enumera, no pior caso, são os caminhos que não repetem células, conhecidos em combinatória como passeios autoevitantes (self-avoiding walks). Em uma grade infinita, a quantidade deles com passos cresce como , onde é a chamada constante conectiva da grade quadrada. Continua exponencial.

Rodando no seu computador

Para testar no terminal, não é preciso digitar o mapa toda vez: salve-o em um arquivo e use redirecionamento. Todo programa nasce ligado a três canais: a entrada padrão (stdin, de onde scanf lê, normalmente o teclado), a saída padrão (stdout, para onde printf escreve, normalmente a tela) e a saída de erro (stderr, também na tela). O terminal permite trocar cada um deles por um arquivo, sem mudar o programa:

O redirecionamento é feito pelo terminal: o programa não sabe (nem precisa saber) se está lendo do teclado ou de um arquivo. Cada scanf simplesmente consome o próximo trecho do arquivo, na ordem, como se ele estivesse sendo digitado.

Com o redirecionamento, dá para ver uma animação do backtracking. A versão abaixo redesenha o mapa a cada célula marcada ou desmarcada, com uma pausa entre um desenho e outro. Ela usa system("clear") e usleep, que não funcionam aqui na página: copie-a para o seu computador, junto com as funções de labirinto.c, e execute com ./labirinto < mapa.txt.

#include <unistd.h>   /* usleep */

void desenhaEPausa(const char *mensagem, int l, int c) {
    system("clear");                  /* no Windows sem WSL: system("cls") */
    printf("%s (%d, %d)\n\n", mensagem, l, c);
    imprime(mapa, nl, nc);
    usleep(150000);                   /* pausa de 150 ms */
}

void caminha(int l, int c) {
    if (achouSaida)
        return;
    if (l < 0 || c < 0 || l >= nl || c >= nc)
        return;
    if (mapa[l][c] != '.' && mapa[l][c] != 'S' && mapa[l][c] != 'E')
        return;

    bool eSaida = (mapa[l][c] == 'E');
    mapa[l][c] = 'v';
    desenhaEPausa("Visitando", l, c);
    if (eSaida) {
        achouSaida = true;
        return;
    }

    caminha(l, c - 1);
    caminha(l, c + 1);
    caminha(l - 1, c);
    caminha(l + 1, c);

    if (!achouSaida) {
        mapa[l][c] = '.';
        desenhaEPausa("Recuando de", l, c);
    }
}

Exercícios

Encontre e corrija o erro

Cada programa tem um erro. Execute, leia a saída e as mensagens, corrija e execute de novo.

Programa 1

Deveria imprimir as 8 sequências de 3 bits.

Programa 2

Deveria listar os subconjuntos com soma no máximo 10.

Programa 3

Programa 4

Programa 5

Implemente

Subconjuntos com soma exata. Conte quantos subconjuntos de um vetor de inteiros positivos têm soma exatamente igual a alvo. Por exemplo, para os valores 5 3 8 2 e alvo 10, a resposta é 2: {5, 3, 2} e {8, 2}. Os testes maiores têm até 50 elementos: a força bruta, com folhas, não termina a tempo. Pense em qual poda usar.

Quantos caminhos? Conte quantos caminhos diferentes, sem repetir células, levam de S até E. Agora a busca não para no primeiro caminho: ao chegar em E, conte e volte para tentar os outros. Por isso o desfazer é obrigatório, e o mapa precisa terminar exatamente como começou (inclusive o S). Em um mapa sem paredes, com S e E em cantos opostos, há 12 caminhos.

Referências

• P. Feofiloff. Algoritmos de enumeração. IME-USP.
• Backtracking. Wikipedia.
• Self-avoiding walk. Wikipedia.