∑
MathTCG
#194 / 200•Foundations•MathTCG #194 / 500•★Commune•⊦Maths Discrètes•Méthode & Idée

Retour sur trace (backtracking)

Période historique : 1965 (Golomb, Baumert)

L'exploration méthodique avec retour en arrière dès qu'une impasse est constatée : l'art de sortir des labyrinthes.

Contenu & Formulation mathématique

Principe de la démarche
Parcours en profondeur d'un arbre de décisions avec élagage immédiat des branches qui ne peuvent plus mener à une solution valide.
Champs d'application canoniques
Résolution de grilles de Sudoku, problème des huit dames, coloriage de cartes et solveurs SAT pour la vérification de circuits.
Si ¬Valide(eˊtat)  ⟹  Annuler(choix)  ∧  Bifurquer\text{Si } \neg\text{Valide}(\text{état}) \implies \text{Annuler}(\text{choix}) \;\land\; \text{Bifurquer}

Genèse & Portée historique

Technique algorithmique explorant systématiquement l'espace des solutions possibles d'un problème combinatoire sous forme d'arbre. Dès qu'une branche viole une contrainte, l'algorithme fait marche arrière (backtrack) pour tester une alternative, évitant l'exploration inutile.

Cette méthode formalise le légendaire fil d'Ariane de la mythologie grecque permettant à Thésée de retrouver son chemin dans le labyrinthe du Minotaure en revenant sur ses pas.

« Explorer chaque couloir jusqu'au mur, puis reculer d'un pas pour tenter une autre porte. »

Filiations & Relations conceptuelles (0)

Cette notice constitue un axiome autonome sans relations directes enregistrées dans le recueil.

Objet de collection MathTCG

#194
★Commune
⊦

Retour sur trace (backtracking)

Maths Discrètes•MÉTHODE

Principe : Parcours en profondeur d'un arbre de décisions avec élagage immédiat des branches qui ne peuvent plus mener à une solution valide.

Si ¬Valide(eˊtat)  ⟹  Annuler(choix)  ∧  Bifurquer\text{Si } \neg\text{Valide}(\text{état}) \implies \text{Annuler}(\text{choix}) \;\land\; \text{Bifurquer}
1965 (Golomb, Baumert)

Dans l'édition physique et numérique de MathTCG, cette carte appartient à l'extension Foundations.

Extension : Foundations (#194 / 200)
Numéro global MathTCG : MathTCG #194 / 500
Rareté officielle : Commune (★)
Domaine théorique : Maths Discrètes
Identifiant pérenne : retour-sur-trace-backtracking
Consulter mon classeurExplorer tout le recueil