Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Retour sur trace
Résumé
En informatique, plus précisément en algorithmique, le retour sur trace ou retour arrière (appelé aussi backtracking en anglais) est une famille d'algorithmes pour trouver des solutions à des problèmes algorithmiques, notamment de satisfaction de contraintes. Contrairement à une recherche exhaustive, un algorithme de retour sur trace construit incrémentalement des solutions candidates. Il abandonne la construction lorsqu'il ne peut compléter le candidat courant en solution valide. Il revient alors sur ses choix (d'où le nom de retour sur trace) et en prend d'autres pour construire d'autres solutions candidates.
Le retour sur trace est utilisé pour résoudre des problèmes algorithmiques difficile à résoudre, typiquement NP-complets.
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).
Fichier:Sudoku solved by bactracking.gif|Grille de Sukodu résolue grâce au retour sur trace.
Fichier:Eight-queens-animation.gif|Placement de huit reines sur un échiquier sans qu'elles s'attaquent.
La figure ci-dessus de gauche montre l'application du retour sur trace sur la recherche d'une solution pour le jeu du Sudoku. L'algorithme affecte une valeur possible dans une case puis poursuit la construction d'une solution. En cas d'impossibilité, l'algorithme revient sur les affectations déjà faites puis essait avec d'autres valeurs. La figure de droite montre l'application du retour sur trace pour le problème des huit reines. Il s'agit de placer 8 reines sur un échiquier sans qu'elles s'attaquent.
vignette|Ordre du parcours en profondeur. C'est l'ordre dans lequel les nœuds de l'arbre de recherche sont visités par le backtracking.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Proximité ontologique