Backtracking
Backtracking é um tipo de algoritmo que representa um refinamento da busca por força bruta,[1] em que múltiplas soluções podem ser eliminadas sem serem explicitamente examinadas. O termo foi cunhado pelo matemático estado-unidense D. H. Lehmer na década de 1950.
O procedimento é usado em linguagens de programação como Prolog. Uma busca inicial em um programa nessa linguagem segue o padrão busca em profundidade, ou seja, a árvore é percorrida sistematicamente de cima para baixo e da esquerda para direita. Quando essa pesquisa falha, ou é encontrado um nodo terminal da árvore, entra em funcionamento o mecanismo de backtracking. Esse procedimento faz com que o sistema retorne pelo mesmo caminho percorrido com a finalidade de encontrar soluções alternativas.
Um exemplo de algoritmo de Backtracking está representado abaixo:
bool acabou = FALSE;
backtrack(int a[], int k, int n) {
int c[MAXCANDIDATOS]; /* Candidatos para a próxima posição */
int ncandidatos; /* Número de candidatos para a próxima posição */
int i; /* Contador */
if (e_uma_solucao(a, k, n)) {
processar_solucao(a, k, n);
} else {
k = k + 1;
construir_candidatos(a, k, n, c, &ncandidatos);
for (i=0; i<ncandidatos; i++) {
a[k] = c[i];
backtrack(a, k, n);
if (acabou) return;
}
}
}
As principais aplicações desse tipo de algoritmo são para a construção de todos os 2^n subconjuntos de um conjunto S, com n elementos e todas as permutações desse conjunto. Abaixo seguem as sub-rotinas para cada situação, na linguagem C:
Construção de todos os subconjuntos
editare_uma_solucao(int a[], int k, int n) {
return (k == n);
}
construir_candidatos(int a[], int k, int n, int c[], int *ncandidatos) {
c[0] = TRUE;
c[1] = FALSE;
*ncandidatos = 2;
}
processar_solucao(int a[], int k) {
int i; /* Contador */
printf("{");
for (i=1; i<=k; i++)
if (a[i] == TRUE)
printf(" %d", i);
printf(" }\n");
}
Agora, é necessário chamar a função backtrack com os argumentos certos, sendo backtrack(a, 0, n).
Construção de todas as permutações
editarconstruir_candidatos(int a[], int k, int n, int c[], int *ncandidatos) {
int i; /* Contador */
bool in_perm[NMAX]; /* Quem já está na permutação? */
for (i=1; i<NMAX; i++) in_perm[i] = FALSE;
for (i=1; i<k; i++) in_perm[ a[i] ] = TRUE;
*ncandidatos = 0;
for (i=1;i<=n;i++)
if (in_perm[i] == FALSE) {
c[ *ncandidatos] = i;
*ncandidatos = *ncandidatos+1;
}
}
processar_solucao(int a[], int k) {
int i; /* Contador */
for (i=1; i<=k; i++)
printf(" %d", a[i]);
printf("\n");
}
e_uma_solucao(int a[], int k, int n) {
return (k == n);
}
Novamente, deve-se chamar a função backtrack da forma backtrack(a, 0, n).
Referências
- ↑ Eitan Gurari (1999). «CIS 680: Data Structures: Capítulo 19: Algoritmos de Backtracking» (em inglês)