Backtracking – Wikipédia a enciclopédia livre

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Backtracking sem backjumping.
Backtracking com backjumping.
Backtracking
Origem: Wikipédia, a enciclopédia livre.
Backtracking é um tipo de algoritmo que representa um
refinamento da busca por força bruta, 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
[1]
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[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
construir_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
1. ↑ Eitan Gurari (1999). CIS 680: Data Structures: Capítulo 19: Algoritmos de Backtracking
(http://www.cse.ohio-state.edu/~gurari/course/cis680/cis680Ch19.html#QQ1-51-128) (em inglês).
Obtida de "http://pt.wikipedia.org/w/index.php?title=Backtracking&oldid=32777293"
Categoria: Algoritmos de busca
Esta página foi modificada pela última vez à(s) 11h56min de 29 de outubro de 2012.
Este texto é disponibilizado nos termos da licença Atribuição-Partilha nos Mesmos Termos 3.0 não
Adaptada (CC BY-SA 3.0); pode estar sujeito a condições adicionais. Consulte as condições de uso
para mais detalhes.