Retour sur trace

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Le retour sur trace (appelé aussi backtracking en anglais) est une famille d'algorithmes qui consistent à revenir 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.

Problèmes de satisfaction de contraintes[modifier | modifier le code]

Les problèmes de satisfaction sont des problèmes ayant une solution complète, dans laquelle aucun ordre naturel des éléments n'existe. Ces problèmes se composent d'un ensemble de variables dont les valeurs sont assujetties à des contraintes spécifiques au problème. L'idée maîtresse consiste à essayer chaque possibilité (combinaison) jusqu'à trouver la bonne. Pour cela on examine les possibilités immédiates, puis si aucun blocage n'apparaît on continue sur les possibilités suivantes ; si un blocage apparaît, autrement dit s'il n'y a aucune possibilité, on revient au dernier cas examiné où une autre possibilité existait et on continue à partir de ce cas. Les langages de programmation déclaratifs, comme Prolog, permettent d'exprimer directement ces contraintes et effectuent cette recherche automatiquement.

Jeux[modifier | modifier le code]

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 à un point donné et on envisage un autre mouvement.

Analyse syntaxique[modifier | modifier le code]

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.

Pile[modifier | modifier le code]

La structure de donnée fondamentale du retour sur trace est la pile ou structure « dernier arrivé, premier sorti » (ou LIFO en anglais pour « last in, first out » ; elle stocke (empile) les branchements effectués et les met à jour (dépile) lors d'un blocage.

Voir aussi[modifier | modifier le code]