Backtracking
Origem: 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.
Referências
- ↑
Eitan Gurari (1999). CIS 680: DATA STRUCTURES: Capítulo 19: Algoritmos de Backtracking (inglês).
