X1 = 5 X2 = 14 X3 = 3 X4 = 12
On se place dans le cas de contraintes binaires.
Les contraintes sont exprimées en intention.
Le langage de programmation utilisé est Common Lisp.
Le projet consiste en :
Il s'agit uniquement de variables entières.
On donne pour chaque variable une liste comprenant le nom de la variable puis son domaine.
Celui-ci est explicité soit sous forme d'un intervalle,
par exemple (toto 0 10) pour l'intervalle fermé de 0 à 10,
soit sous forme énumérée grâce à une sous-liste, par exemple (var1 (1 14 52 66)).
Cette syntaxe a été implémentée, en saisie au clavier, ou à partir d'un fichier.
Deux variantes, dont la détection est automatique, sont prévues :
(X4 (2 3))
(X3 1 4)
((X4 (2 3)) (X3 1 4))
Il s'agit de contraintes unaires (pour éliminer les valeurs particulières dans un intervalle) ou binaires.
Elles n'utilisent que les opérateurs arithmétiques +, −, *, /, <, <=, =, /=, >, >=.
On donne pour chaque contrainte une liste décrivant une expression infixée et parenthèsée (si nécessaire).
Exemples :
(toto /= 5) (x1 >= x3) (((3 * x * x) + (4 * x * y) - 3) = 0)
Nous avons tout de suite pensé le système en n-aire.
Cela nous a semblé plus simple de le traiter au départ,
plutôt que d'avoir à adapter le programme plus tard.
De même, dès l'origine, nous avons prévu la possibilité de saisir les contraintes en préfixé
ou infixé, là aussi avec détection automatique.
Les contraintes sont analysées puis parenthèsées et transformées si nécessaire en préfixé,
de manière à ce qu'elles puissent facilement être évaluées par LISP.
Exemple de contraintes valides pour notre interface :
(X1 < X2) (< X1 X2) ((X1 + 4 + X2 + X3) <= (X4 * X5)) (<= (+ X1 (+ 4 (+ X2 X3))) (* X4 X5))
Nous avons divisé le programme LISP en différents fichiers spécialisés :
Ce fichier est la bibliothèque principale du programme.
C'est elle qui contient les fonctions permettant de gérer le stockage, les accès et les modifications des contraintes.
Ce stockage est organisé autour d'une PListe (SYMBOL-PLIST)
car sa structure était déjà proche de celle dont nous avions besoin.
Ce fichier gère l'interface entre le noyau du programme et le monde extérieur.
Il permet :
Ce fichier est le point d'entrée de notre programme.
C'est lui qui charge les autres bibliothèques.
Il lance en boucle les différents menus, afin de pouvoir faire plusieurs actions consécutives,
jusqu'à la sortie, où il ferme LISP complètement.
Voici les fichiers contenant les algorithmes qui nous ont été demandé d'implémenter. Tous contiennent leurs méthodes propres.
Voici le backtrack.
Il fonctionne sur la base d'une seule fonction récursive,
qui teste successivement pour chaque variable les différentes valeurs de son domaine.
Faisant toutes les combinaisons, l'algorithme est assuré de trouver une solution si elle existe.
Il n'y a aucune mémoire des combinaisons testées, ni fonction d'élagage.
Notre structure de donnée est optimisée au niveau des contraintes.
Celles-ci ne sont stockées q'au niveau de la variable testée le plus tard dans l'algorithme.
ie: les contraintes ne sont pas stockées de manière symétrique. Si (A < B),
la contrainte ne sera stockée qu'au niveau de B,
car il faut que l'une des deux variables ait pris une valeur avant de pouvoir tester la contrainte.
Ce fichier contient le filtre utilisé pour AC3.
C'est un filtre partiel de type partial look future, au cours duquel on parcourt toutes les variables,
pour lesquelles on essaye de réduire leur domaine, en fonction des contraintes qu'elles ont avec les autres variables.
Au cours du traitement d'une variable, on ne modifie pas les domaines des autres variables.
Ce fichier contient une fonction qui boucle sur toutes les variables,
et parcours leurs contraintes pour élaguer leur domaine.
Ce fichier contient le filtre utilisé pour FC.
C'est un filtre exécuter lors du backtrack.
Lorsqu'on se trouve sur une variable, il essaye d'élaguer les domaines des variables avec lesquelles elle a des contraintes.
Nous avons essayé notre programme sur plusieurs problèmes, où l'efficacité des algorithmes c'est montrée variable.
Il s'agit de placer n dames sur un échiquier de taille n×n
sans que deux dames ne soient sur la même colonne, ni sur la même ligne,
ni sur la même diagonale.
X1 à Xn sont les positions des dames sur un échiquier dont les cases
sont numérotées en ligne de 1 à n2.
Nous avons fait un script de génération de contraintes.
Voici le fichier de contraintes pour n=5 :
(D (4 8 12 16)) (C (3 7 11 15)) (B (2 6 10 14)) (A (1 5 9 13)) (B /= (A + 1)) (B /= (A + 5)) (B /= (A - 3)) (C /= (A + 2)) (C /= (B + 1)) (C /= (A + 10)) (C /= (B + 5)) (C /= (A - 6)) (C /= (B - 3)) (D /= (A + 3)) (D /= (B + 2)) (D /= (C + 1)) (D /= (A + 15)) (D /= (B + 10)) (D /= (C + 5)) (D /= (A - 9)) (D /= (B - 6)) (D /= (C - 3)) NIL
Et voilà la solution trouvée par le backtrack.
|
X1 = 5 X2 = 14 X3 = 3 X4 = 12 |
Voici le problème résolu pour n=20.
X1 = 1 X2 = 42 X3 = 83 X4 = 24 X5 = 65 X6 = 246 X7 = 287 X8 = 228 X9 = 349 X10 = 390 X11 = 331 X12 = 172 X13 = 313 X14 = 374 X15 = 155 X16 = 196 X17 = 137 X18 = 278 X19 = 119 X20 = 220
Le temps de calcul pour n=20 a été raisonnable (~10mn) avec le backtrack.
On constate un gain avec FC (2 min 12 avec n=17 en backtrack, 1 min 15 en FC).
Par contre, le AC3 ne filtre rien sur ce problème, il n'est donc qu'une perte de temps.
Le problème a été résolu jusqu'à n=25.
Ce projet a permis de prendre contact avec LISP et avec les problèmes à satisfaction de contraintes.
Accés aux sources (ZIP 25.6Ko)