Session 4 :
Réalisation de solveurs de contraintes en Prolog


Sommaire de la session 4 :

Présentation de la session
1 - Description de CSPs binaires en Prolog
2 - Programmation de l'algorithme "génère et teste" en Prolog
3 - Programmation de l'algorithme "simple retour-arrière en Prolog"
4 - Programmation de l'algorithme "anticipation/noeud" en Prolog
5 - Intégration de l'heuristique "échec d'abord"
6 - Comparaison expérimentale des quatre solveurs




Présentation de la session

Lors des sessions de cours précédentes, vous avez appris ce qu'est un CSP, et vous avez étudié un certain nombre d'algorithmes permettant de résoudre ces CSPs. Aujourd'hui, vous allez implémenter en Prolog ces algorithmes : vous allez écrire votre propre solveur de contraintes pour résoudre des CSPs sur les domaines finis. L'objectif est d'une part de vous faire mieux comprendre le fonctionnement de ces algorithmes en les programmant, et d'autre part de vous entrainer un peu plus à la programmation en Prolog.

Pour simplifier la phase de vérification de la consistance d'une affectation, on se limitera aux CSPs binaires, c'est à dire les CSPs dont toutes les contraintes portent sur 2 variables exactement. Le premier point de cette session de cours propose un formalisme pour décrire en Prolog les CSPs binaires que l'on souhaite résoudre ; les points suivants vous permettront d'écrire progressivement les programmes Prolog implémentant les différents algorithmes étudiés au cours de la troisième session.

A chaque fois que l'on vous décrira un prédicat, ou que vous aurez à écrire un prédicat, on utilisera les conventions suivantes. Par ailleurs, à chaque fois que l'on vous donnera un exemple d'exécution sous l'interprète Prolog, on utilisera la fonte courier, et on encadrera la séquence d'exécution.


1 - Description de CSPs binaires en Prolog

Pour concevoir un solveur de contraintes, la première chose à faire est de décider d'une convention pour décrire le CSP à résoudre. On se limite ici à des CSPs binaires, c'est à dire des CSPs dont toutes les contraintes portent sur 2 variables exactement, et on propose de décrire un CSP binaire (X,D,C) en définissant les 2 prédicats Prolog suivants :

Nous vous donnons les codes Prolog décrivant le CSP des 4 reines, le CSP du coloriage d'une carte, et le CSP des mariages stables. Vous pourrez utiliser ces descriptions de CSPs pour tester les solveurs de contraintes que vous allez maintenant écrire.


2 - Programmation de l'algorithme "génère et teste" en Prolog

2.1 - Génération d'affectations totales

Pour implémenter l'algorithme "génère et teste" étudié au point 1 de la session de cours 3, il s'agit tout d'abord de définir un prédicat qui, étant donné une liste de variables du CSP (chaque variable étant suivie de son domaine) génère une affectation totale. Pour cela, vous devez écrire le prédicat genere/2 suivant :
Une fois que vous avez programmé le rédicat genere/2, vérifiez qu'il est bien défini en le testant sur l'exemple d'exécution ci-dessus. Vous pouvez également le tester sur le CSP des 4 reines. Pour cela, chargez le code Prolog décrivant le CSP des 4 reines et demandez à l'interprète Prolog de générer toutes les affectations totales pour le problème des 4 reines de la façon suivante :
| ?- variables(V), genere(V,A).
Prolog doit alors vous énumérer toutes les affectations totales (il y en a 4 puissance 4...).
A = [(x(1),1),(x(2),1),(x(3),1),(x(4),1)] ? ;
A = [(x(1),1),(x(2),1),(x(3),1),(x(4),2)] ? ;
A = [(x(1),1),(x(2),1),(x(3),1),(x(4),3)] ? ;
A = [(x(1),1),(x(2),1),(x(3),1),(x(4),4)] ? ;
A = [(x(1),1),(x(2),1),(x(3),2),(x(4),1)] ? ;
A = [(x(1),1),(x(2),1),(x(3),2),(x(4),2)] ? ;
A = [(x(1),1),(x(2),1),(x(3),2),(x(4),3)] ? ;
etc...

2.2 - Test de consistance d'une affectation

Une fois le prédicat genere/2 écrit, il s'agit ensuite de définir un prédicat qui, étant donnée une affectation, teste sa consistance. Pour cela, vous devez écrire le prédicat teste/1 suivant :
Vérifiez que votre prédicat est bien défini en le testant sur l'exemple d'exécution ci-dessus (n'oubliez pas de charger auparavant le code Prolog décrivant le CSP des 4 reines).

2.3 - Génère et teste

En utilisant les prédicats genere/2 et teste/1, vous pouvez maintenant écrire le prédicat genereEtTeste/1 suivant :

Correction de genereEtTeste


3 - Programmation de "simple retour-arrière" en Prolog

3.1 - Test incrémental de consistance

Pour implémenter l'algorithme "simple retour arrière" étudié au point 3 de la session 3, on peut s'inspirer du prédicat genere/2 que l'on vient d'écrire : il suffit d'intégrer au cours de la génération des affectations un test qui vérifie, à chaque fois que l'on instancie une nouvelle variable, que cette instanciation est consistante avec les affectations déjà effectuées. Pour cela, vous devez tout d'abord écrire le prédicat teste/2suivant :
Vérifiez que votre prédicat est bien défini en le testant sur l'exemple d'exécution ci-dessus (n'oubliez pas de charger auparavant le code Prolog décrivant le CSP des 4 reines).

3.2 - Simple retour-arrière

En utilisant le prédicat teste/2, et en vous inspirant du prédicat genere/2, vous pouvez ensuite écrire le prédicat simpleRetourArrière/3 suivant :

Vérifiez que votre prédicat est bien défini en le testant sur les exemples d'exécution ci-dessus (n'oubliez pas de charger auparavant le code Prolog décrivant le CSP des 4 reines).

Enfin, en utilisant ce prédicat simpleRetourArriere/3, vous pouvez écrire le prédicat simpleRetourArriere/1 tel que simpleRetourArriere(A) unifie A avec une solution du CSP décrit par les prédicats variables/1 et consistants/2.

Correction de simpleRetourArrière.


4 - Programmation de l'algorithme "anticipation/noeud" en Prolog

4.1 - Filtrage des domaines des variables

Pour implémenter la fonction "anticipation/noeud" étudiée au point 4 de la session 3, on peut s'inspirer du prédicat simpleRetourArriere/3 que l'on vient d'écrire : il suffit d'intégrer une étape de filtrage qui, à chaque fois que l'on instancie une nouvelle variable, enlève des domaines des variables non affectées les valeurs incompatibles avec cette instanciation. Pour cela, vous devez tout d'abord écrire le prédicat filtre/4 suivant :
Vérifiez que votre prédicat est bien défini en le testant sur l'exemple d'exécution ci-dessus (n'oubliez pas de charger auparavant le code Prolog décrivant le CSP des 4 reines).

4.2 - Anticipation

En utilisant le prédicat filtre/4, et en vous inspirant du prédicat simpleRetourArriere/3, vous pouvez ensuite écrire le prédicat anticipation/3 suivant :
Enfin, en utilisant ce prédicat anticipation/3, vous pouvez écrire le prédicat anticipation/1 tel que anticipation(A) unifie A avec une solution du CSP décrit par les prédicats variables/1 et consistants/2.

Correction de Anticipation.


5 -Intégration de l'heuristique "échec d'abord"

Les solveurs que vous venez de programmer instancient les variables dans l'ordre dans lequel elles sont définies par le prédicat variables/1. Pour améliorer ces solveurs, on peut intégrer des heuristiques déterminant l'ordre dans lequel les variables doivent être instanciées. On va maintenant intégrer l'heuristique "échec d'abord", décrite au point 5 de la session 3, à l'algorithme anticipation/noeud que nous venons de programmer. Rappelons que le principe de cette heuristique est de choisir, à chaque étape, la variable dont le domaine a le plus petit nombre de valeurs localement consistantes avec l'affectation partielle en cours. Dans le cas de l'algorithme anticipation, cette heuristique est mise en oeuvre en choisissant la variable qui a le plus petit domaine après filtrage.

5.1 - Extraction de la variable ayant le plus petit domaine

Pour implémenter cette heuristique, vous trouverez ici le code Prolog définissant le prédicat extraitMin/3 suivant :

5.2 - Anticipation/noeud avec l'heuristique "échec d'abord"

En utilisant le prédicat extraitMin/3, et en vous inspirant du prédicat anticipation/3, vous pouvez maintenant écrire le prédicat echecDabord/3 qui choisit à chaque étape d'instancier la variable ayant le plus petit domaine, puis filtre les domaines des variables non encore instanciées pour rétablir la consistance de noeud :
Enfin, en utilisant ce prédicat echecDabord/3, vous pouvez écrire le prédicat echecDabord/1 tel que echecDabord(A) unifie A avec une solution du CSP décrit par les prédicats variables/1 et consistants/2 .

Correction de echecDabord


6 - Comparaison expérimentale des quatre solveurs

On peut maintenant comparer l'efficacité des quatre solveurs que l'on vient de programmer en les exécutant sur le problème du placement de n reines sur un échiquier nxn.

Pour cela, commencez par récupérer le fichier solveurs.pl contenant le code Prolog pour les 4 solveurs, et le fichier reinesN.pl contenant le code Prolog permettant de générer le CSP des n reines... et chargez ces deux fichiers sous l'interprète GNU-Prolog :

| ?- [solveurs,reinesN].
compiling solveurs.pl for byte code...
solveurs.pl compiled, 76 lines read - 10671 bytes written, 54 ms
compiling reinesN.pl for byte code...
reinesN.pl compiled, 20 lines read - 2588 bytes written, 10 ms

yes
Pour générer le code Prolog définissant le CSP des n reines pour une valeur de n donnée, vous devez appeler le prédicat genereReines/1. Par exemple, l'exécution de
| ?- genereReines(6).
génère le code Prolog décrivant le CSP des n reines lorsque n=6. On peut alors résoudre ce CSP en faisant appel à un des 4 prédicats genereEtTeste/1, simpleRetourArriere/1, anticipation/1 ou echecDabord/1. Par exemple :
| ?- anticipation(A).
A = [(x(1),2),(x(2),4),(x(3),6),(x(4),1),(x(5),3),(x(6),5)] ? ;
A = [(x(1),3),(x(2),6),(x(3),2),(x(4),5),(x(5),1),(x(6),4)] ? ;
A = [(x(1),4),(x(2),1),(x(3),5),(x(4),2),(x(5),6),(x(6),3)] ? ;
A = [(x(1),5),(x(2),3),(x(3),1),(x(4),6),(x(5),4),(x(6),2)] ? ;
(10 ms) no

Pour comparer l'efficacité des 4 solveurs, il est plus significatif de comparer les temps mis pour calculer toutes les solutions (en effet, la première solution est souvent trouvée quasiment instantanément pour les petites valeurs de n).

Pour calculer toutes les solutions à une question, vous pouvez utiliser le prédicat bagof/3 : l'exécution de bagof(A,But,L) a pour effet de calculer tous les termes A pour lesquels But réussit (But étant un atome logique à prouver contenant la variable A), et de collecter la liste de ces termes dans L. Ainsi, pour déterminer le temps mis par le solveur genereEtTeste pour calculer toutes les solutions aux CSP des n reines lorsque n=6, on exécutera la séquence suivante :

| ?- genereReines(6).

yes
| ?- bagof(A,genereEtTeste(A),L).

L = [[(x(1),2),(x(2),4),(x(3),6),(x(4),1),(x(5),3),(x(6),5)],...]

(730 ms) yes
Le temps d'exécution étant indiqué par l'interprète à la fin (ici, 730 ms). Si vous ne souhaitez pas que Prolog affiche la liste L, vous pouvez remplacer L par la variable anonyme '_'.

| ?- bagof(A,genereEtTeste(A),_).

(730 ms) yes

On peut ainsi comparer les temps d'exécution des 4 solveurs que nous avons écrits sur le problème des n reines, pour différentes valeurs de n. On obtient des temps d'exécution de l'ordre des suivants (ces temps dépendent bien évidemment de votre machine !!!) :

nb de reines
"génère et teste"
"simple retour-arrière"
"anticipation/noeud"
"anticipation/noeud + échec d'abord"
6
730 ms
10 ms
10 ms
10 ms
8
288 530 ms
210 ms
140 ms
130 ms
10
-
5 880 ms
2 520 ms
2 310 ms
12
-
183 110 ms
62 820 ms
52 240 ms

Sur ce problème, on peut constater que "simple retour-arrière" est considérablement plus efficace que "génère et teste" ; "anticipation/noeud" est environ 2 fois plus rapide que "simple retour-arrière", et enfin l'heuristique d'ordonnancement des variables "échec d'abord" améliore légèrement les temps d'exécution de "anticipation/noeud".

Sur le problème du coloriage de la carte (avec 14 pays), on obtient des résultats similaires : pour calculer simplement la première solution, "génère et teste" prend 794 670 ms, tandis que pour trouver toutes les solutions (il y en a 1968), "simple retour-arriere" prend 7 230 ms, "anticipation/noeud" prend 1 310 ms et "anticipation/noeud" couplé avec l'heuristique "échec d'abord" prend 580 ms.