Retour sur trace
Un article de Wikipédia, l'encyclopédie libre.
 |
Cet article est une ébauche concernant l’informatique.
Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).
|
Le retour sur trace, appelé aussi backtracking en anglais, consiste à revenir légèrement en arrière sur des décisions prises afin de sortir d'un blocage. La méthode des essais et erreurs constitue un exemple simple de backtracking.
Le terme est surtout utilisé en programmation, où il désigne une stratégie pour trouver des solutions à des problèmes de satisfaction de contraintes.
Sommaire |
[modifier] Problèmes de satisfaction de contraintes
Ce sont des problèmes ayant une solution complète, dans laquelle peu importe l'ordre des éléments. Ces problèmes se composent d'un ensemble de variables avec une valeur assujettie aux contraintes particulières du problème chacune. L'idée maîtresse est d'essayer chaque possibilité (combinaison) jusqu'à trouver la bonne. C'est une recherche en profondeur sur l'ensemble des solutions. Les langages de programmation déclaratifs, comme Prolog, permettent d'exprimer directement ces contraintes, et effectuent cette recherche automatiquement.
Pendant la recherche, si vous essayez une alternative qui ne satisfait plus une contrainte, vous effectuez un retour sur trace à un point où d'autres alternatives s'offraient à vous, et vous essayez la possibilité suivante. Si vous n'avez plus de tels points la recherche échoue. La force du backtracking est que beaucoup de ses réalisations évitent d'essayer beaucoup de combinaisons partielles, diminuant ainsi le temps d'exécution.
[modifier] Jeux
On peut dans un jeu que l'on programme envisager un mouvement donné et ses suites. Il se peut que l'une des suites ne soit pas heureuse. On remonte alors et on envisage un autre mouvement.
[modifier] Analyse syntaxique
Les espaces ne comptaient pas dans la première version du langage FORTRAN. Au moment de l'analyse syntaxique, le début de certaines instructions posait des problèmes d'interprétation :
- GO TO 100
- est-ce une instruction GO TO ou une variable dont le nom commence par GOTO ?
- DO 10 I =
- est-ce une boucle DO ou une variable nommée DO10I que l'on va affecter ?
Il fallait donc effectuer une hypothèse (latch) que l'on confirmait si la syntaxe était correcte (clamp), et sur laquelle on revenait dans le cas contraire.
