retour sur trace

retour arrière
algorithme de backtracking

COMBINATOIRE
INFORMATIQUE

Le retour sur trace, ou algorithme de retour arrière, ou en anglais backtracking, est une famille d’algorithmes permettant de résoudre des problèmes en programmation, notamment des problèmes de satisfaction de contraintes. Cela est comparable à l’observation d’un arbre binaire.
On peut prendre l’exemple de la résolution d’un sudoku par ordinateur. On remplit la grille au fur et à mesure, en vérifiant constamment qu’elle reste toujours potentiellement valide, on arrive vite à des blocages.
Le backtracking consiste à remonter d’un rang seulement et d’explorer toutes les possibilités, puis au besoin de remonter à nouveau d’un rang, etc. Cela est moins coûteux que de parcourir tous les chemins à partir de la racine de l’arbre.
On peut schématiser le retour sur trace par « un pas en arrière, deux pas en avant »