Prolog/Retrocesso

Retrocesso ou Backtracking

Retrocesso (em inglês Backtracking) é um procedimento dentro da linguagem Prolog. Uma busca inicial em um programa nesta linguagem segue o padrão Busca em profundidade (depth-first search), ou seja, a árvore é percorrida sistematicamente de cima para baixo e da esquerda para direita. Quando essa pesquisa falha, ou é encontrado um nó 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.

Exemplo:

Considerando uma base de dados família, fazemos a seguinte consulta:

?- pai(roberto,X), mae(vera,X)

O compilador tenta satisfazer o primeiro objetivo. Quando conseguir, tenta satisfazer o segundo. Caso não consiga, ele retorna ao ponto onde encontrou a solução para o primeiro objetivo (backtracking).