Por vezes não há alternativa a ter de procurar por todo o espaço de soluções.
No entanto podemos ser inteligentes e ir construíndo as soluções passo a passo, e de cada vez que uma solução parcial não for viável (feasible), podemos abandonar esse ramo da pesquisa, voltando para trás (backtracking) para outras soluções parciais. Esta é a essência da pesquisa por retrocesso.
Claro que só poderemos usar esta técnica em problemas que:
Com a possibilidade de parar a meio da construção de uma solução, o backtracking pode ser muito mais rápido que uma pesquisa que enumere todas as soluções, incluindo soluções não viáveis.
Outra questão importante é saber criar soluções parciais de modo a que estas se tornem inviáveis o mais rápido possível, dado que é melhor voltar para trás no início do que no fim do processo de construção uma solução.
Existe muita literatura sobre esta técnica, mas para nós interessa-nos como técnica de pesquisa que permite encontrar soluções em problemas onde temos de pesquisar por todas as soluções viáveis possíveis.
Um àparte: a programação dinâmica evita calcular todas as soluções, permitindo ganhos exponenciais de desempenho ao escolher o que calcular, mas é uma técnica menos geral, nem sempre podendo ser implementada.
O backtracking pode ser usado em problemas combinatóricos, como encontrar uma solução do Sodoku, ou encontrar uma saída de um labirinto.
Um exemplo clássico é resolver o problema das oito rainhas do Xadrez: colocar oito rainhas no tabuleiro de xadrez de forma a que nenhuma ataque as restantes. A forma de resolver este problema por retrocesso é ir colocando a i-ésima rainha em todas as linhas da i-ésima coluna. Quando uma linha funciona (ie, não entra em conflito com as restantes rainhas já no tabuleiro), tentar colocar a rainha seguinte pelo mesmo algoritmo. Se não for possível colocar a rainha, voltar para trás (porque encontrámos uma solução parcial inviável) e experimentar a rainha anterior numa nova linha. E assim por diante...
O seguinte código (baseado neste) usa esta técnica:
public class Queens {
static final int SIZE = 4; // board size
// is it feasible to place the n-th queen there?
public static boolean isFeasible(int[] queen_positions, int n) {
for (int i=0; i<n; i++)
if ((queen_positions[i] == queen_positions[n]) || // same row
(queen_positions[i] - queen_positions[n]) == (n - i) || // same major diagonal
(queen_positions[n] - queen_positions[i]) == (n - i)) // same minor diagonal
return false;
return true;
}
O método isFeasible testa se uma solução parcial é viável. Como referimos isto é uma componente essencial para que o backtracking seja eficiente.
Já o seguinte método contém o algoritmo de retrocesso:
public static void backtrack(int[] queen_positions, int k) {
if (k == SIZE) {
showResult(queen_positions);
return;
}
for (int i=0; i<SIZE; i++) {
queen_positions[k] = i;
if (isFeasible(queen_positions, k))
backtrack(queen_positions, k+1);
}
}
O condicional inicial verifica se teremos concluído uma solução (colocámos todas as rainhas). Se assim for, imprime a solução. Se a solução ainda é parcial, continua a construi-la.
Neste exemplo, a classe vai imprimir todas as soluções possíveis.
Segue o resto da classe:
public static void showResult(int[] queen_positions) {
for (int i = 0; i < SIZE; i++) { // for each row
for (int j = 0; j < SIZE; j++) // for each column
System.out.print(queen_positions[i] == j ? "Q ": ". ");
System.out.println();
}
System.out.println();
}
public static void main(String[] args) {
backtrack(new int[SIZE], 0);
}
}
Se executarmos o main vamos obter as soluções para tabuleiros 4x4 (foi o valor dado à constante SIZE):
. Q . .
. . . Q
Q . . .
. . Q .
. . Q .
Q . . .
. . . Q
. Q . .