Backtracking
Neste artigo vamos explorar o fascinante mundo de Backtracking. Quer você seja um fã de história, um entusiasta da ciência, um amante da moda ou apenas alguém curioso por natureza, Backtracking tem algo para todos. Desde o seu impacto na sociedade até à sua evolução ao longo do tempo, este tema deixou uma marca indelével no mundo que nos rodeia. Junte-se a nós nesta jornada enquanto descobrimos os mistérios e maravilhas que Backtracking tem a oferecer.
 |
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; /* 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 = c;
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
e_uma_solucao(int a, int k, int n) {
return (k == n);
}
construir_candidatos(int a, int k, int n, int c, int *ncandidatos) {
c = TRUE;
c = FALSE;
*ncandidatos = 2;
}
processar_solucao(int a, int k) {
int i; /* Contador */
printf("{");
for (i=1; i<=k; i++)
if (a == 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
construir_candidatos(int a, int k, int n, int c, int *ncandidatos) {
int i; /* Contador */
bool in_perm; /* Quem já está na permutação? */
for (i=1; i<NMAX; i++) in_perm = FALSE;
for (i=1; i<k; i++) in_perm ] = TRUE;
*ncandidatos = 0;
for (i=1;i<=n;i++)
if (in_perm == FALSE) {
c = i;
*ncandidatos = *ncandidatos+1;
}
}
processar_solucao(int a, int k) {
int i; /* Contador */
for (i=1; i<=k; i++)
printf(" %d", a);
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)
