Problèmes de satisfaction de contraintes (CSP)
4. Résolution d'un CSP
4.2. Approche simple retour arrière (backstracking)
Le retour en arrière est l'action de retourner vers une variable précédant la variable courante dans la sous-séquence d'instanciation, de modifier la valeur affectée à celle-ci et de poursuivre la résolution par la suite.
L'algorithme de BT est donc un algorithme à deux phases.
- Premièrement, une phase permettant d'avancer vers une prochaine variable à instancier et permettant d'étendre la sous-séquence et,
- Deuxièmement, une phase de retour en arrière consistant à choisir la variable vers laquelle sera fait le retour en arrière dans la sous-séquence.
Inconvénients:
- Pas d’identification des causes de conflit
- Redondance
- Détection tardive des conflits
