Libellé préféré : algorithme utilisant le retour sur trace;
Définition CISMeF : 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 (source https://fr.wikipedia.org/wiki/Retour_sur_trace);
Synonyme CISMeF : algorithme utilisant le retour arrière;
Identifiant d'origine : D000098428;
CUI UMLS : C5940624;
Type(s) sémantique(s)
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 (source https://fr.wikipedia.org/wiki/Retour_sur_trace)