1.2.5 Apprentissage : look-back
Dans le cadre des problèmes de satisfaction de
contraintes classiques, le Backtracking (voir la section 1.2.1 pour
une définition) souffre fréquemment d'un phénomène
de « trashing >>, qui se traduit par le fait de redécouvrir
de manière répétitive les mêmes échecs et les
mêmes instanciations partielles durant la recherche.
Les procédures dynamiques d'amélioration de
parcours de l'arbre sont les schémas du type « look-ahead>>
(sélection de variables et de valeurs) et « look-back>>
(Backjumping, apprentissage, Nogood Recording). Le
raisonnement du Backtrack conclut au rejet d'un certain nombre de
choix combinatoires; le Nogood Recording (Schiex et Verfaillie, 1994)
consiste à mémoriser ces choix afin de ne plus les reproduire.
Ainsi, plusieurs techniques d'apprentissage des échecs ont
été proposées.
Le Backjumping a été proposé par
Gaschnig (1979). Supposons qu'un échec est rencontré sur la
variable xi. La technique de Backtrack classique revient sur
la dernière variable instanciée xi_1. Si une
autre valeur est possible pour xi_1 mais qu'aucune
contrainte ne porte sur les variables xi et xi_1,
alors la variable xi_1 ne peut être la source de
l'échec rencontré sur xi. Ainsi, on retrouve
nécessairement un échec sur la variable xi pour chaque
valeur instanciée de xi_1. Gaschnig (1979) propose
d'améliorer ce processus en identifiant la variable coupable de
l'échec et en effectuant le retour dans l'arbre sur cette variable.
L'identification est basée sur la notion d'ensemble en conflit. Un
ensemble en conflit est une instanciation d'un sous-ensemble de variables ne
laissant aucune possibilité pour une certaine variable non encore
instanciée. Une instanciation partielle qui n'apparaît dans aucune
solution est un « NoGood >> (Doyle, 1979).
Ginsberg (1993) a proposé un nouvel algorithme pour
résoudre les problèmes de satisfaction de contraintes. Cet
algorithme, appelé Dynamic Backtracking peut être vu
comme une amélioration du principe de Backjumping, de Graph
Based Backjumping (Dechter, 1990) et de la méthode Conflict
Directed Backjumping algorithms (Prosser, 1993) . La méthode
Conflict Directed Backjumping enregistre à chaque étape
de la recherche et pour chaque variable xi, l'ensemble des variables
assignées qui a conduit à une réduction de domaine de
xi. De tels ensembles sont appelés des ensembles de conflits.
Dynamic Backtracking enregistre le même type d'informations,
mais à un niveau plus fin. À chaque étape de la recherche,
pour chaque variable xi et pour chaque valeur j qui a
été supprimée du domaine courant de xi,
l'algorithme enregistre l'ensemble des variables assignées
précédemment qui sont responsables de cette élimination.
Ces ensembles sont appelés des explications
d'élimination. L'ensemble en conflit d'une variable est alors
défini comme l'union des explications d'élimination des
valeurs de cette variable.
Chvátal (1997) a présenté une
méthode exhaustive pour la résolution de problèmes
linéaires en variables binaires, Resolution Search. Cette
méthode se démarque des procédures arborescentes
classiques par une exploration originale de l'espace de recherche,
censée permettre de rendre la résolution du problème moins
largement dépendante de
la stratégie de branchement invoquée. Celle-ci,
à l'instar des procédés de backtracking intelligents, est
basée sur le principe d'apprentissage qui consiste à identifier
et mémoriser les raisons des échecs qui surviennent tout au long
de la recherche. Lorsqu'un échec est détecté au cours de
l'exploration de l'espace de recherche, l'ensemble des variables, dont
l'instanciation est responsable de l'échec, est déterminé
à partir de la configuration partielle courante. Interdire pour la suite
de la recherche cette instanciation partielle revient à
générer une contrainte additionnelle au problème,
appelée Nogood, afin de couper la recherche en amont du noeud
considéré. Resolution Search propose un schéma
original de gestion de ces nogoods. Celui-ci permet de limiter
l'espace mémoire et le temps de traitement des nogoods. De
plus, il permet d'indiquer rapidement comment poursuivre la recherche à
la suite d'un échec, tout en assurant la convergence de l'algorithme.
Demassey (2003) a appliqué cette méthode sur le problème
d'Ordonnancement de Projet à Contraintes de Ressources (RCPSP). Palpant
(2005) a proposé une utilisation de cette approche pour la
résolution du problème des
Queens_n2.
| 
