« Retour sur trace » : différence entre les versions
m (Remplacement de texte — « <!--Vocabulaire2 --> » par « ») |
Aucun résumé des modifications Balise : Éditeur de wikicode 2017 |
||
| Ligne 1 : | Ligne 1 : | ||
==Définition== | ==Définition== | ||
Le retour sur trace (appelé aussi ''backtracking'' en anglais) est une famille d'algorithmes pour résoudre des problèmes algorithmiques, notamment de satisfaction de contraintes (optimisation ou décision). 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). | Le retour sur trace (appelé aussi ''backtracking'' en anglais) est une famille d'algorithmes pour résoudre des problèmes algorithmiques, notamment de satisfaction de contraintes (optimisation ou décision). 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). | ||
==Français== | ==Français== | ||
'''retour sur trace''' | '''retour sur trace''' <small> loc. nom. masc. </small> | ||
==Anglais== | ==Anglais== | ||
| Ligne 18 : | Ligne 10 : | ||
<small> | <small> | ||
[https://fr.wikipedia.org/wiki/Retour_sur_trace Source: Wikipedia IA] | |||
[ | [[Catégorie:Apprentissage automatique]] | ||
[[Catégorie:Algorithme de recherche]] | |||
[[Category:GRAND LEXIQUE FRANÇAIS]] | |||
Version du 8 mai 2020 à 09:50
Définition
Le retour sur trace (appelé aussi backtracking en anglais) est une famille d'algorithmes pour résoudre des problèmes algorithmiques, notamment de satisfaction de contraintes (optimisation ou décision). 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).
Français
retour sur trace loc. nom. masc.
Anglais
backjumping
Contributeurs: Jacques Barolet, wiki
