Backtracking

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

Ce document provient de « Retour sur trace ».

Wikimedia Foundation. 2010.

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

Regardez d'autres dictionnaires:

  • Backtracking — is a type of algorithm that is a refinement of brute force search. [cite web | url=http://www.cse.ohio state.edu/ gurari/course/cis680/cis680Ch19.html#QQ1 51 128 Backtracking algorithms | title=CIS 680: DATA STRUCTURES: Chapter 19: Backtracking… …   Wikipedia

  • Backtracking — Der Begriff Rücksetzverfahren oder englisch Backtracking (deut. Rückverfolgung) bezeichnet eine mathematische Problemlösungsmethode innerhalb der Algorithmik. Backtracking arbeitet nach dem Prinzip der Tiefensuche Inhaltsverzeichnis …   Deutsch Wikipedia

  • Backtracking — Trial and Error Verfahren; Rücksetzalgorithmus * * * Back|tra|cking 〈[bæ̣ktrækıŋ] n.; od. s; unz.; EDV〉 Programmier bzw. Suchstrategie, die von bestimmten Problempunkten ausgehend Lösungswege entwickelt, wobei der bis dahin aktuelle (Daten… …   Universal-Lexikon

  • backtracking — grįžimų metodas statusas T sritis informatika apibrėžtis Algoritmavimo metodas, kai sprendimas grindžiamas variantų tikrinimu ir, pasiekus aklavietę, grįžimu vienu žingsniu atgal. Grįžimų metodas labiausiai taikomas sprendžiant labirinto tipo… …   Enciklopedinis kompiuterijos žodynas

  • backtracking — The backwards movement of RNA polymerase along the DNA template to a state more stable than that encountered when some base pairs disrupt the attachment of the 3′ end from the active transcription site …   Medical dictionary

  • Backtracking — Back|tra|cking 〈[bæ̣ktrækıŋ] n.; Gen.: od. s; Pl.: unz.; EDV〉 Programmier bzw. Suchstrategie, die von bestimmten Problempunkten ausgehend Lösungswege entwickelt, wobei der bis dahin aktuelle (Daten )Bestand gesichert (u. gegebenenfalls… …   Lexikalische Deutsches Wörterbuch

  • Backtracking — Suchmethode. 1. Prinzip: An denjenigen Punkten des Suchvorgangs, an denen zur Fortsetzung der Suche eine Auswahlentscheidung zwischen mehreren Möglichkeiten getroffen werden muss, wird zunächst der aktuelle Zustand festgehalten, bevor man die… …   Lexikon der Economics

  • backtracking — v. go backwards; retrace one s footsteps or path …   English contemporary dictionary

  • backtracking — backˈtracking noun • • • Main Entry: ↑back …   Useful english dictionary

  • Backtracking-Verfahren —   [ bæktrækɪȖ , englisch »sich zurückziehen«], Versuch und Irrtum …   Universal-Lexikon

Share the article and excerpts

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