Backtracking

Esta página cita fontes, mas que não cobrem todo o conteúdo. Ajude a inserir referências (Encontre fontes: ABW  • CAPES  • Google (notícias • livros • acadêmico)). (Maio de 2015)

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: