Retour sur trace
Un article de Freepedia.
| Image:Symbole-ordinateur.png | Cet article est une ébauche à compléter concernant l'informatique, vous pouvez partager vos connaissances en le modifiant. |
Le retour sur trace, appelé aussi backtracking en anglais, est une stratégie pour trouver des solutions à des problèmes de satisfaction de contraintes, en utilisant par exemple un langage de programmation déclaratif, comme Prolog et dans d'autres situations comme la décomposition analytique de texte.
Ce sont des problèmes ayant une solution complète, dans laquelle peu importe l'ordre des éléments. Ils (ces problèmes) se composent d'un ensemble de variables dont à chacune une valeur est assignée, sujette aux contraintes particulières du problème. L'idée maîtresse est d'essayer chaque possibilité (combinaison) jusqu'à trouver la bonne. C'est une recherche de profondeur première sur l'ensemble des solutions.
Pendant la recherche, si vous essayez une alternative qui ne fonctionne pas, vous faite un retour sur trace au point choisi, la place qui se présente à vous avec différentes alternatives, et vous essayez la possibilité suivante. Si vous n'avez plus de points la recherche échoue. La force du backtracking est que beaucoup de ses réalisations évitent d'essayer beaucoup de combinaisons partielles, accélèrant de ce fait le temps d'exécution.
Le backtracking est étroitement lié à l'analyse combinatoire (Cf. Combinatorial_search en Anglais).
