Session 3 :
Résolution de CSPs


Sommaire de la session 3 :

Présentation de la session
1 - L'algorithme "génère et teste"
2 - Critique de "génère et teste" et notion d'espace de recherche d'un CSP
3 - L'algorithme "simple retour-arrière"
4 - L'algorithme "anticipation"
5 - Intégration d'heuristiques




Présentation de la session

Ce qu'on va voir dans cette session...

Lors de la première session de cours, on a introduit le formalisme des CSPs, formalisme qui offre un cadre structurant pour modéliser des problèmes exprimés en termes de contraintes, et lors de la deuxième session vous vous êtes entrainés à modéliser des problèmes sous la forme de CSPs. On va maintenant étudier quelques algorithmes permettant de résoudre, de façon générique, certains de ces CSPs. On se restreindra aux CSPs sur les domaines finis, c'est-à-dire, les CSPs dont les domaines des variables sont des ensembles finis de valeurs. Le principe commun à tous les algorithmes que nous allons étudier est d'explorer méthodiquement l'ensemble des affectations possibles jusqu'à, soit trouver une solution (quand le CSP est consistant), soit démontrer qu'il n'existe pas de solution (quand le CSP est inconsistant).

...et ce qu'on ne verra pas (entre autres...)


1 - L'algorithme "génère et teste"

1.1 - Principe de l'algorithme "génère et teste"

La façon la plus simple (et très naïve !) de résoudre un CSP sur les domaines finis consiste à énumérer toutes les affectations totales possibles jusqu'à en trouver une qui satisfasse toutes les contraintes. Ce principe est repris dans la fonction récursive "genereEtTeste(A,(X,D,C))" décrite ci-dessous. Dans cette fonction, A contient une affectation partielle et (X,D,C) décrit le CSP à résoudre (au premier appel de cette fonction, l'affectation partielle A sera vide). La fonction retourne vrai si on peut étendre l'affectation partielle A en une affectation totale consistante (une solution), et faux sinon.

fonction genereEtTeste(A,(X,D,C)) retourne un booléen
Précondition :
(X,D,C) = un CSP sur les domaines finis
A = une affectation partielle pour (X,D,C)
Postrelation :
retourne vrai si l'affectation partielle A peut être étendue en une solution pour (X,D,C), faux sinon
début
si toutes les variables de X sont affectées à une valeur dans A alors
/* A est une affectation totale */
si A est consistante alors
/* A est une solution */
retourner vrai
sinon
retourner faux
finsi
sinon /* A est une affectation partielle */
choisir une variable Xi de X qui n'est pas encore affectée à une valeur dans A
pour toute valeur Vi appartenant à D(Xi) faire
si genereEtTeste(A U {(Xi,Vi)}, (X,D,C)) = vrai alors retourner vrai
finpour
retourner faux
finsi
fin

1.2 - Exemple de trace d'exécution de "génère et teste"

Considérons par exemple le CSP (X,D,C) suivant :

L'enchainement des appels successifs à la fonction genereEtTeste (abrégée par GET) est représenté ci-dessous (chaque rectangle correspond à un appel de la fonction, et précise la valeur de l'affectation partielle en cours de construction A).
Arbre de recherche de genereEtTest (GET) pour le CSP ci dessus.

2 - Critique de "génère et teste" et notion d'espace de recherche d'un CSP

L'algorithme "génère et teste" que nous venons de voir énumère l'ensemble des affectations complètes possibles, jusqu'à en trouver une qui soit consistante. L'ensemble des affectations complètes est appelé l'espace de recherche du CSP. Si le domaine de certaines variables contient une infinité de valeurs, alors cet espace de recherche est infini et on ne pourra pas énumérer ses éléments en un temps fini. Néanmoins, même en se limitant à des domaines comportant un nombre fini de valeurs, l'espace de recherche est souvent de taille tellement importante que l'algorithme "génère et teste" ne pourra se terminer en un temps "raisonnable". En effet, l'espace de recherche d'un CSP (X,D,C) comportant n variables ( X = {X1, X2, ..., Xn}) est défini par

E = { {(X1,v1), (X2,v2), ..., (Xn,vn)} / quelquesoit i compris entre 1 et n, vi est un élément de D(Xi) }

et le nombre d'éléments de cet espace de recherche est défini par

| E | = | D(X1) | * | D(X2) | * ... * | D(Xn) |

de sorte que, si tous les domaines des variables sont de la même taille k (autrement dit, | D(Xi) |=k), alors la taille de l'espace de recherche est

| E | = kn

Ainsi, le nombre d'affectations à générer croit de façon exponentielle en fonction du nombre de variables du problème. Considérons plus précisément un CSP ayant n variables, chaque variable pouvant prendre 2 valeurs (k=2 ). Dans ce cas, le nombre d'affectations totales possibles pour ce CSP est 2n. En supposant qu'un ordinateur puisse générer et tester un milliard d'affectations par seconde (ce qui est une estimation vraiment très optimiste !), le tableau suivant donne une idée du temps qu'il faudrait pour énumérer et tester toutes les affectations en fonction du nombre de variables n.

Nombre de variables n
Nombre d'affectations totales 2^n
Temps (si on traitait 10^9 affectations par seconde)
10
environ 10^3
environ 1 millionième de seconde
20
environ 10^6
environ 1 millième de seconde
30
environ 10^9
environ 1 seconde
40
environ 10^12
environ 16 minutes
50
environ 10^15
environ 11 jours
60
environ 10^18
environ 32 ans
70
environ 10^21
environ 317 siècles

Les améliorations de "génère et teste" que nous allons étudier dans la suite...

La conclusion de ce petit exercice de dénombrement est que, dès lors que le CSP a plus d'une trentaine de variables, on ne peut pas appliquer "bêtement" l'algorithme "génère et teste". Il faut donc chercher à réduire l'espace de recherche. Pour cela, on peut notamment :

... et celles que nous n'étudierons pas (entre autres...)

Il existe encore bien d'autres façons de (tenter de) réduire la combinatoire, afin de rendre l'exploration exhaustive de l'espace de recherche possible, que nous ne verrons pas dans ce cours. Par exemple, lors d'un échec, on peut essayer d'identifier la cause de l'échec (quelle est la variable qui viole une contrainte) pour ensuite "retourner en arrière" directement là où cette variable a été instanciée afin de remettre en cause plus rapidement la variable à l'origine de l'échec. C'est ce que l'on appelle le "retour arrière intelligent" ("intelligent backtracking").

Une autre approche particulièrement séduisante consiste à exploiter des connaissances sur les types de contraintes utilisées pour réduire l'espace de recherche.

considérons par exemple le CSP (X,D,C) suivant :
- X={a,b,c},
- D(a)=D(b)=D(c)={0,1,2,3,4, ..., 1000},
- C={4*a - 2*b = 6*c + 3}

L'espace de recherche de ce CSP comporte 1 milliard d'affectations ; pour résoudre ce CSP, on peut énumérer toutes ces combinaisons, en espérant en trouver une qui satisfasse la contrainte 4*a - 2*b = 6*c + 3... c'est long et si on remplace la borne supérieure 1000 par l'infini, ça devient carrément impossible. En revanche un simple raisonnement permet de conclure très rapidement que ce CSP n'a pas de solution : la partie gauche de l'équation "4*a - 2*b" donnera toujours un nombre pair, quelles que soient les valeurs affectées à a et b, tandis que la partie droite "6*c + 3" donnera toujours un nombre impair, quelle que soit la valeur affectée à c ; par conséquent, on ne peut trouver d'affectation qui satisfasse la contrainte, et il est inutile d'énumérer toutes les affectations possibles pour s'en convaincre !

Ce genre de raisonnement demande de l'intelligence, ou pour le moins des connaissances. De fait, l'homme est capable de résoudre des problèmes très combinatoires en raisonnant (en utilisant son "expérience" et des connaissances plus ou moins explicitées). Un exemple typique est le jeu d'échec : les grands joueurs d'échecs n'envisagent pour chaque coup à jouer que très peu de combinaisons (les meilleures évidemment !), éliminant par des raisonnements souvent difficiles à expliciter un très grand nombre de combinaisons moins intéressantes. Cela explique le fait que, malgré leur capacité à envisager un très grand nombre de combinaisons, les ordinateurs sont encore (bien souvent) moins forts que ces grands joueurs.


3 - L'algorithme "simple retour-arrière"

3.1 - Principe de l'algorithme "simple retour-arrière"

Une première façon d'améliorer l'algorithme "génère et teste" consiste à tester au fur et à mesure de la construction de l'affectation partielle sa consistance : dès lors qu'une affectation partielle est inconsistante, il est inutile de chercher à la compléter. Dans ce cas, on "retourne en arrière" ("backtrack" en anglais) jusqu'à la plus récente instanciation partielle consistante que l'on peut étendre en affectant une autre valeur à la dernière variable affectée.
Par exemple, sur la trace d'exécution décrite en 1.2, on remarque que l'algorithme génère tous les prolongements de l'affectation partielle A={(a,0),(b,0)}, en énumérant toutes les possibilités d'affectation pour les variables c et d, alors qu'elle viole la contrainte a ≠ b. L'algorithme "simple retour-arrière" ne va donc pas chercher à étendre cette affectation, mais va "retourner en arrière" à l'affectation partielle précédente A={(a,0)}, et va l'étendre en affectant 1 à b , ...

Ce principe est repris dans la fonction récursive "simpleRetourArrière(A,(X,D,C))" décrite ci-dessous. Dans cette fonction, A contient une affectation partielle et (X,D,C) décrit le CSP à résoudre (au premier appel de cette fonction, l'affectation partielle A sera vide). La fonction retourne vrai si on peut étendre l'affectation partielle A en une affectation totale consistante (une solution), et faux sinon.

fonction simpleRetourArrière(A,(X,D,C)) retourne un booléen
Précondition :
A = affectation partielle
(X,D,C) = un CSP sur les domaines finis
Postrelation :
retourne vrai si A peut être étendue en une solution pour (X,D,C), faux sinon
début
si A n'est pas consistante alors retourner faux finsi
si toutes les variables de X sont affectées à une valeur dans A alors
/* A est une affectation totale et consistante = une solution */
retourner vrai
sinon /* A est une affectation partielle consistante */
choisir une variable Xi de X qui n'est pas encore affectée à une valeur dans A
pour toute valeur Vi appartenant à D(Xi) faire
si simpleRetourArrière(A U {(Xi,Vi)}, (X,D,C)) = vrai alors retourner vrai
finpour
retourner faux
finsi
fin

3.2 - Exemple de "trace d'exécution" de SimpleRetourArrière

Considérons le problème du placement de 4 reines sur un échiquier 4x4, et sa deuxième modélisation proposée au point 3 de la première session de cours :

L'enchainement des appels successifs à la fonction SimpleRetourArrière peut être représenté par l'arbre suivant (chaque noeud correspond à un appel de la fonction ; l'échiquier dessiné à chaque noeud décrit l'affectation partielle en cours) :
Arbre de recherche de simpleRetourArrière pour le problème des 4 reines

Cette image est empruntée au "Guide to Constraint Programming" de Roman Bartak.



4 - L'algorithme "anticipation"

4.1 - Notions de filtrage et de consistance locale

Pour améliorer l'algorithme "simple retour-arrière", on peut tenter d'anticiper ("look ahead" en anglais) les conséquences de l'affectation partielle en cours de construction sur les domaines des variables qui ne sont pas encore affectées : si on se rend compte qu'une variable non affectée Xi n'a plus de valeur dans son domaine D(Xi) qui soit "localement consistante" avec l'affectation partielle en cours de construction, alors il n'est pas nécessaire de continuer à développer cette branche, et on peut tout de suite retourner en arrière pour explorer d'autres possibilités.

Pour mettre ce principe en oeuvre, on va, à chaque étape de la recherche, filtrer les domaines des variables non affectées en enlevant les valeurs "localement inconsistantes", c'est-à-dire celles dont on peut inférer qu'elles n'appartiendront à aucune solution. On peut effectuer différents filtrages, correspondant à différents niveaux de consistances locales, qui vont réduire plus ou moins les domaines des variables, mais qui prendront aussi plus ou moins de temps à s'exécuter : considérons un CSP (X,D,C), et une affectation partielle consistante A,

4.2 - Principe de l'algorithme "anticipation"

Le principe général de l'algorithme "anticipation" reprend celui de l'algorithme "simple retour-arrière", en ajoutant simplement une étape de filtrage à chaque fois qu'une valeur est affectée à une variable. Comme on vient de le voir au point 4.1, on peut effectuer différents filtrages plus ou moins forts, permettant d'établir différents niveaux de consistance locale (noeud, arc, chemin, ...). Par exemple, la fonction récursive "anticipation/noeud(A,(X,D,C))" décrite ci-dessous effectue un filtrage simple qui établit à chaque étape la consistance de noeud. Dans cette fonction, A contient une affectation partielle consistante et (X,D,C) décrit le CSP à résoudre (au premier appel de cette fonction, l'affectation partielle A sera vide). La fonction retourne vrai si on peut étendre l'affectation partielle A en une affectation totale consistante (une solution), et faux sinon.

fonction anticipation/noeud(A,(X,D,C)) retourne un booléen
Précondition :
A = affectation partielle consistante
(X,D,C) = un CSP sur les domaines finis
Postrelation :
retourne vrai si A peut être étendue en une solution pour (X,D,C), faux sinon
début
si toutes les variables de X sont affectées à une valeur dans A alors
/* A est une affectation totale et consistante = une solution */
retourner vrai
sinon /* A est une affectation partielle consistante */
choisir une variable Xi de X qui n'est pas encore affectée à une valeur dans A
pour toute valeur Vi appartenant à D(Xi) faire
/* filtrage des domaines par rapport à A U {(Xi,Vi)} */
pour toute variable Xj de X qui n'est pas encore affectée faire
Dfiltré(Xj) <- { Vj élément de D(Xj) / A U {(Xi,Vi),(Xj,Vj)} est consistante }
si Dfiltré(Xj) est vide alors retourner faux
finpour
si anticipation(A U {(Xi,Vi)}, (X,Dfiltré,C))=vrai alors retourner vrai
finpour
retourner faux
finsi
fin

Nous n'étudierons pas dans le cadre de ce cours l'algorithme de filtrage qui établit la consistance d'arc (algorithme AC).

4.3 - Exemple de "trace d'exécution" de "anticipation"

Considérons de nouveau le problème du placement de 4 reines sur un échiquier 4x4. L'enchainement des appels successifs à la fonction "Anticipation/noeud" peut être représenté par l'arbre suivant (les valeurs supprimées par le filtrage sont marquées d'une croix) :

Arbre de recherche pour l'algorithme anticipation (consistance de noeud) pour le problème des 4 reines
Cette image est empruntée au "Guide to Constraint Programming" de Roman Bartak.

Si on appliquait un filtrage plus fort, qui rétablirait à chaque étape la consistance d'arc, l'enchainement des appels successifs à la fonction "Anticipation/arc" correspondante serait le suivant (les valeurs supprimées par le filtrage sont marquées d'une croix) :

Arbre de recherche de l'algorithme anticipation (consistance d'arc) pour le problème des 4 reines
Cette image est empruntée au "Guide to Constraint Programming" de Roman Bartak.

Ainsi, on constate sur le problème des 4 reines que le filtrage des domaines permet de réduire le nombre d'appels récursifs : on passe de 27 appels pour "simple retour-arrière" à 8 appels pour l'algorithme d'anticipation avec filtrage simple établissant une consistance de noeud. En utilisant des filtrages plus forts, comme celui qui établit la consistance d'arc, on peut encore réduire la combinatoire de 8 à 3 appels récursifs. Cependant, il faut noter que plus le filtrage utilisé est fort, plus cela prendra de temps pour l'exécuter...

De façon générale, on constate que, quel que soit le problème considéré, l'algorithme "anticipation/noeud" est généralement plus rapide que l'algorithme "simple retour-arrière" car le filtrage utilisé est vraiment peu coûteux. En revanche, si l'algorithme "anticipation/arc" envisage toujours moins de combinaisons que l'algorithme "anticipation/noeud", il peut parfois prendre plus de temps à l'exécution car le filtrage pour établir une consistance d'arc est plus long que celui pour établir la consistance de noeud.


5 - Intégration d'heuristiques

Les algorithmes que nous venons d'étudier choisissent, à chaque étape, la prochaine variable à instancier parmi l'ensemble des variables qui ne sont pas encore instanciées ; ensuite, une fois la variable choisie, ils essayent de l'instancier avec les différentes valeurs de son domaine. Ces algorithmes ne disent rien sur l'ordre dans lequel on doit instancier les variables, ni sur l'ordre dans lequel on doit affecter les valeurs aux variables. Ces deux ordres peuvent changer considérablement l'efficacité de ces algorithmes : imaginons qu'à chaque étape on dispose des conseils d'un "oracle-qui-sait-tout" qui nous dise quelle valeur choisir sans jamais se tromper ; dans ce cas, la solution serait trouvée sans jamais retourner en arrière... Malheureusement, le problème général de la satisfaction d'un CSP sur les domaines finis étant NP-complet, il est plus qu'improbable que cet oracle fiable à 100% puisse jamais être "programmé". En revanche, on peut intégrer des heuristiques pour déterminer l'ordre dans lequel les variables et les valeurs doivent être considérées : une heuristique est une règle non systématique (dans le sens où elle n'est pas fiable à 100%) qui nous donne des indications sur la direction à prendre dans l'arbre de recherche.

Les heuristiques concernant l'ordre d'instanciation des valeurs sont généralement dépendantes de l'application considérée et difficilement généralisables. En revanche, il existe de nombreuses heuristiques d'ordre d'instanciation des variables qui permettent bien souvent d'accélérer considérablement la recherche. L'idée générale consiste à instancier en premier les variables les plus "critiques", c'est-à-dire celles qui interviennent dans beaucoup de contraintes et/ou qui ne peuvent prendre que très peu de valeurs. L'ordre d'instanciation des variables peut être :