Definição – o que significa retrocesso?
Backtracking é um algoritmo para capturar algumas ou todas as soluções para determinados problemas computacionais, especialmente para problemas de satisfação de restrição. O algoritmo só pode ser usado para problemas que aceitem o conceito de “solução candidata parcial” e permite um teste rápido para ver se a solução candidata pode ser uma solução completa. O retrocesso é considerado uma técnica importante para resolver problemas e quebra-cabeças de satisfação de restrições. Também é considerada uma ótima técnica para análise e também constitui a base de muitas linguagens de programação lógica.
Definirtec explica Backtracking
O retrocesso ajuda a resolver um problema geral, encontrando uma solução para o primeiro subproblema e, em seguida, tentando resolver outros subproblemas com base na solução do primeiro problema. Se o problema atual não puder ser resolvido, a etapa é retrocedida e a próxima solução possível é aplicada às etapas anteriores e, em seguida, prossegue. Na verdade, uma das coisas principais no retrocesso é a recursão. Também é considerado como um método de pesquisa exaustiva usando dividir para conquistar. Um algoritmo de retrocesso termina quando não há mais soluções para o primeiro subproblema.
Backtracking é um algoritmo que pode ajudar a alcançar a implementação do não determinismo. É necessária uma pesquisa aprofundada de um determinado espaço temático. É usado principalmente em linguagens de programação lógica como Prolog. Onde quer que o retrocesso possa ser aplicado, ele é mais rápido do que a técnica de força bruta, pois elimina um grande número de candidatos com um único teste.