Retour sur trace

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche
Depth first search.svg

Le retour sur trace ou retour arrière[1] (appelé aussi backtracking en anglais) est une famille d'algorithmes pour résoudre des problèmes algorithmiques, notamment de satisfaction de contraintes (optimisation ou décision). Ces algorithmes permettent de tester systématiquement l'ensemble des affectations potentielles du problème. Ils consistent à sélectionner une variable du problème, et pour chaque affectation possible de cette variable, à tester récursivement si une solution valide peut-être construite à partir de cette affectation partielle. Si aucune solution n'est trouvée, la méthode abandonne et revient sur les affectations qui auraient été faites précédemment (d'où le nom de retour sur trace).

En d'autres termes, le retour sur trace est un parcours en profondeur sur l'arbre de décision du problème.

Exemples de contextes d'utilisation[modifier | modifier le code]

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 et casse tête[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 pile est une structure de donnée fondamentale pour le retour sur trace, elle permet de stocker (empiler) les branchements effectués et de les mettre à jour (dépiler) lors d'un retour. L'implémentation la plus naturelle de l'algorithme utilise des appels récursifs et donc la pile d'exécution.

Notes et références[modifier | modifier le code]

  1. Office québécois de la langue française, « retour arrière », sur gdt.oqlf.gouv.qc.ca, (consulté le 10 novembre 2019)

Voir aussi[modifier | modifier le code]

Sur les autres projets Wikimedia :