Backtracking

Conteúdo referente à aula de 10 de junho de 2009, por Eduardo.

Recursão

Antes de falarmos de backtracking, é importante uma rápida revisada em recursão.

Funções recursivas são funções que chamam a si mesmas. Assim como qualquer outra função, sua execução é interrompida quando ocorre esta chamada, e prossegue quando a chama retorna. Entretanto, por se tratar da mesma função, muitas vezes isso pode dar um pequeno nó na cabeça.

É comum abstrair a chamada recursiva e imaginá-la como uma função mágica ou um oráculo que retorna sempre a resposta correta para uma dada chamada.

Outra característica importante é que se não houver um critério de parada (que chamamos de caso base), a recursão continua indefinidamente, causando erros de execução. O caso base deve ser a primeira coisa testada em uma chamada recursiva, garantindo que não haverão outras chamadas se chegarmos ao caso base.

Vejamos, por exemplo, o cálculo da função fatorial de forma recursiva:

int fatorial(int n) {
    if (n == 0) return 1;
    return n * fatorial (n-1);
}

Repare que nosso caso base é quando n == 0, pois é o valor mais simples que sabemos calcular diretamente. Todos os outros podem ser reconstruídos a partir dele. Reparem na definição matemática de fatorial, e como ela é similar ao código escrito:

(1)
\begin{align} n! = \begin{cases} 1 & \mbox{se } n = 0 \\ n \cdot (n-1)! & \mbox{se } n > 0 \\ \end{cases} \end{align}

Backtracking

Backtracking é uma técnica recursiva, comumente utilizada como alternativa mais eficiente que a força bruta, pois permite abortar soluções possíveis assim que se percebe que esta não é viável.

Um exemplo interessante provavelmente é o Sudoku:

364px-Sudoku-by-L2G-20050714.svg.png

Sudoku é um puzzle que consiste em preencher todos os quadradinhos de um tabuleiro 9x9 com número de 1 a 9, respeitando as seguintes restrições:

  • um número não pode aparecer duas vezes na mesma linha
  • um número não pode aparecer duas vezes na mesma coluna
  • um número não pode aparecer duas vezes no mesmo quadrante (um quadrante é definido como subtabuleiros 3x3, que podemos perceber pelas linhas mais grossas na imagem acima — existem ao todo 9 quadrantes)

Reparem na solução abaixo, como todas as restrições são respeitadas:

330px-Sudoku-by-L2G-20050714_solution.svg.png

Um pseudo-código para a resolução do Sudoku seria algo como:

bool completa_sudoku (void) {
    if (tabuleiro_completo()) return true;
 
    for (...) { // procura célula não preenchida
        for (int n=1; n <= 9; n++) {
            if (...) { // cabe o número n nesta célula
                // coloca n na célula
 
                if (completa_sudoku()) {
                    // conseguimos completar com n nesta célula
                    return true;
                }
 
                // tira n da célula, não deu certo!
            }
        }
    }
    return false;
}

Repare que se nenhum número de 1 a 9 é viável em uma dada célula, não faz sentido continuar preenchendo o tabuleiro e podemos abortar. Assim, voltamos a recursão e mudamos um dos números das células preenchidas anteriormente, na tentativa de achar um número que encaixe nas células seguintes.

Exercício

Faça um programa que lê diversas linhas da entrada padrão, cada uma contendo dois números: N (1 <= N <= 10) e K (1 <= K <= N). Em seguida, imprima todas as permutações de K elementos da seqüência de números 1,…,N em ordem crescente (primeiro as permutações que iniciam com 1, depois 2, …).

Cada seqüência deve vir em um linha, e os números devem ser separado por espaços. Após cada caso de teste, imprima uma linha em branco. Seu programa deve parar quando N e K forem iguais a 0, e esta linha não deve ser processada.

Entrada de exemplo

3 3
5 2
0 0

Saída de exemplo

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

1 2
1 3
1 4
1 5
2 1
2 3
2 4
2 5
3 1
3 2
3 4
3 5
4 1
4 2
4 3
4 5
5 1
5 2
5 3
5 4
 
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License