Backtracking – Wikipédia, a enciclopédia livre

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

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

↑ Eitan Gurari (1999). «CIS 680: Data Structures: Capítulo 19: Algoritmos de Backtracking» (em inglês)

Este artigo sobre programação de computadores é um esboço. Você pode ajudar a Wikipédia expandindo-o.

[1] Eitan Gurari (1999). «CIS 680: Data Structures: Capítulo 19: Algoritmos de Backtracking» (em inglês)

[1]