À retenir
- C'est une technique d'exploration systématique de toutes les solutions possibles.
- Elle repose souvent sur la récursivité (une fonction qui s'appelle elle-même).
- Elle permet de trouver une solution sans avoir à tester bêtement toutes les combinaisons imaginables grâce aux retours intelligents.
C'est une méthode de résolution de problèmes qui fonctionne par essais et erreurs. Si un choix mène à une impasse, l'ordinateur revient à l'étape précédente pour essayer une autre option, comme un explorateur qui ferait demi-tour dans un labyrinthe après avoir rencontré un cul-de-sac.
Étymologie
Traduction littérale de l'anglais backtracking. Le terme évoque l'action de suivre ses propres traces en sens inverse (track back) pour revenir à un point de décision connu afin d'explorer une nouvelle voie.
Exemples d'usage
- Résolution de Sudoku : placer un chiffre, continuer, et si une règle est violée, effacer les chiffres jusqu'à l'erreur pour recommencer.
- Le problème des huit dames : placer des reines sur un échiquier sans qu'elles ne se menacent mutuellement.
- Génération de labyrinthes : construire des chemins et revenir en arrière pour créer des bifurcations.
Cas d'usage
Ce concept est utilisé en intelligence artificielle, dans les jeux de réflexion, pour la planification de tâches complexes, en cryptographie ou encore dans les outils de vérification de preuves mathématiques.
Bonnes pratiques
Pour éviter que l'algorithme ne mette trop de temps, il est crucial d'implémenter l'élagage (pruning) : cela consiste à abandonner une piste dès que l'on sait qu'elle ne peut mathématiquement pas mener à la solution, sans attendre d'arriver au bout.
Synonymes
Antonymes
Conseil
Pour bien comprendre le retour sur trace, essayez de le dessiner sous forme d'arbre : chaque branche est un choix, et chaque fois que vous remontez vers le tronc pour prendre une autre branche, vous faites un retour sur trace.
Questions fréquentes
Est-ce la même chose que la force brute ?
Pas tout à fait. La force brute teste tout sans réfléchir, alors que le retour sur trace élimine des pans entiers de mauvaises solutions dès qu'il détecte un blocage.
Pourquoi utilise-t-on souvent la récursion ?
Parce que la récursion permet de mémoriser naturellement 'l'état' du problème à chaque choix, facilitant le retour en arrière vers l'état précédent.