Backtracking
Le retour sur trace explore systématiquement toutes les solutions candidates, annulant les choix (en revenant en arrière) quand une branche devient infaisable ; il sert aux problèmes de satisfaction de contraintes.
Objectif
Résoudre des problèmes de recherche combinatoire et de satisfaction de contraintes tels que le problème des N reines ou le Sudoku.
Mécanisme
Il parcourt en profondeur l'arbre de l'espace des solutions, étendant un candidat à chaque étape et revenant en arrière quand une contrainte est violée. L'élagage (propagation de contraintes, bornage) réduit l'espace de recherche. Classiques : N reines, coloration de graphes, somme de sous-ensembles.
Cas d’usage
- Satisfaction de contraintes
- Recherche combinatoire
- Résolution de casse-têtes