Définition - Que signifie le retour en arrière?
Le backtracking est un algorithme pour capturer certaines ou toutes les solutions à des problèmes de calcul donnés, en particulier pour les problèmes de satisfaction des contraintes. L'algorithme ne peut être utilisé que pour des problèmes qui peuvent accepter le concept de «solution candidate partielle» et permet un test rapide pour voir si la solution candidate peut être une solution complète. Le retour en arrière est considéré comme une technique importante pour résoudre les problèmes de satisfaction des contraintes et les énigmes. Il est également considéré comme une excellente technique d'analyse syntaxique et constitue également la base de nombreux langages de programmation logique.
Definir Tech explique le retour en arrière
Le retour en arrière aide à résoudre un problème global en trouvant une solution au premier sous-problème, puis en tentant de manière récursive de résoudre d'autres sous-problèmes en fonction de la solution du premier problème. Si le problème actuel ne peut pas être résolu, l'étape est rétrogradée et la solution possible suivante est appliquée aux étapes précédentes, puis continue. En fait, l'un des éléments clés du retour en arrière est la récursivité. Il est également considéré comme une méthode de recherche exhaustive utilisant diviser pour conquérir. Un algorithme de retour en arrière se termine lorsqu'il n'y a plus de solutions au premier sous-problème.
Le backtracking est un algorithme qui peut aider à réaliser l'implémentation du non-déterminisme. Il faut d'abord rechercher en profondeur un espace de problèmes donné. Il est principalement utilisé dans les langages de programmation logique comme Prolog. Partout où le retour en arrière peut être appliqué, il est plus rapide que la technique de la force brute, car il élimine un grand nombre de candidats avec un seul test.