Retour sur trace

Retour sur trace


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

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.

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.

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.

Voir aussi


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Retour sur trace de Wikipédia en français (auteurs)

Игры ⚽ Нужна курсовая?

Regardez d'autres dictionnaires:

  • retour — [ r(ə)tur ] n. m. • retur XIIe; de retourner I ♦ Mouvement en arrière, déplacement vers le point de départ. 1 ♦ Le fait de repartir pour l endroit d où l on est venu. « les vaches, en attendant le retour à l étable, regardaient le soir » (F.… …   Encyclopédie Universelle

  • Sur la route de Madison — Données clés Titre original The Bridges of Madison County Réalisation Clint Eastwood Scénario Richard LaGravenese d après le roman de Robert James Waller Acteurs principaux Meryl Streep …   Wikipédia en Français

  • Sur la route de Madison (film) — Sur la route de Madison Sur la route de Madison (The Bridges of Madison County) est un film américain réalisé et interprété par Clint Eastwood, sorti en 1995. Il s inspire d un roman du même nom écrit par Robert James Waller Sommaire 1 Synopsis 1 …   Wikipédia en Français

  • Sur la route de madison — (The Bridges of Madison County) est un film américain réalisé et interprété par Clint Eastwood, sorti en 1995. Il s inspire d un roman du même nom écrit par Robert James Waller Sommaire 1 Synopsis 1.1 Commentaires 2 …   Wikipédia en Français

  • Retour du religieux — Religion Une religion est un ensemble de rites, croyances généralement théistes[Note 1], composé de règles (éthiques ou pratiques), de récits, de symboles ou de dogmes adoptés comme conviction par une société, un groupe ou une personne. Par… …   Wikipédia en Français

  • sur — 1. sur [ syr ] prép. • 1080; sovre Xe; sore 980; la forme sur vient d un crois. avec sus; lat. super ou supra I ♦ Marquant la position « en haut » ou « en dehors » …   Encyclopédie Universelle

  • sûr — 1. sur [ syr ] prép. • 1080; sovre Xe; sore 980; la forme sur vient d un crois. avec sus; lat. super ou supra I ♦ Marquant la position « …   Encyclopédie Universelle

  • Retour à l'Écriture — Protestantisme Sobriété : le petit temple de Waldersbach, l ancienne paroisse du pasteur Oberlin. Le protestantisme regroupe l ensemble des courants religieux chrétiens issus du catholicisme qui prennent naissance en Europe lors de la… …   Wikipédia en Français

  • Aliens, le retour — Données clés Titre original Aliens Réalisation James Cameron Scénario James Cameron David Giler Walter Hill Acteurs principaux Sigourney Weaver Lance Henriksen …   Wikipédia en Français

  • Massacre D'Oradour-Sur-Glane — Le massacre d’Oradour sur Glane désigne la destruction, le 10 juin 1944, de ce village de la Haute Vienne, situé à environ vingt kilomètres au nord ouest de Limoges, et le massacre de sa population (642 victimes), par un détachement du… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”