Retour sur trace

Carte Commune · n° 283682

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.

Lire sur Wikipédia