Lab 6a : Satisfaction de contraintes
Dans cette série, vous allez programmer des algorithmes de
résolution de satisfaction de contraintes que vous
appliquerez au Sudoku la semaine prochaine (lab 6b).
Durée estimée : 2 heures.
Fichiers
libPSCTemplate.py
PSCTemplate.py
test.py.
Objectifs de la série
- Comprendre la consistance de nœuds et d'arcs.
- Programmer l'algorithme de recherche backtrack.
Satisfaction de contraintes
Le ficher libPSCTemplate.py
implémente une libraire pour la gestion d'une variable et d'une
contrainte (unaire ou binaire), tandis que le
ficher PSCTemplate.py
implémente une libraire pour la gestion d'un ensemble de
variables et de contraintes.
Commencez par lire et comprendre ces fichiers.
Exercice 1 : Consistance des nœuds et des arcs
Comme vous pouvez le constater dans le ficher PSCTemplate.py,
les fonctions consistanceDesNoeuds
et consistanceDesArcs ne sont pas remplies. Complétez
ces fonctions.
Indication : la fonction consistanceDesArcs
doit appeler la méthode reviser de la classe ContrainteBinaire du fichier libPSCTemplate.py, qui implémente
l'algorithme de Walz (consistance d'un arc), et que vous devez aussi
implémenter. Notez bien que, les contraintes binaires
étant bidirectionnelles, vous devez implémenter cette
fonction reviser de telle
sorte que les domaines des deux variables de la contrainte binaire
soient réduits (si possible) par l'appel à la fonction reviser.
Enfin, testez votre programme sur le fichier test.py.
Exercice 2 : Algorithme de Backtrack
Le backtrack est un algorithme de recherche en profondeur d'abord :
- nœud de recherche = instanciation de variables x1 = v1,
x2
= v2, ..., xk = vk
(où k est la
profondeur du nœud dans l'arbre de
recherche)
- fonction de successeur = instanciation de la variable xk+1 = vk+1
de manière à respecter toutes les
contraintes pour les variables x1, ..., xk
- nœud initial = instanciation vide
- nœud but = instanciation de toutes les variables x1,
..., xn
Programmez l'algorithme ci-dessous (similaire à celui de la
Figure 8.7).
SOLUTIONS=[]
VARIABLES=[v1,v2, ...,vn]
Backtrack(k , toutesLesSolutions)
1. IF k >= n THEN
2. IF toutesLesSolutions THEN
3. ajoute la solution actuelle à SOLUTIONS
4. ELSE
5. RETURN SOLUTIONS = [solution actuelle]
6. END IF
7. ELSE
8. var = VARIABLES[k]
9. FOR ALL valeur de domaine d de la variable var DO
10. assigne la valeur d à la variable var
11. vérifie la consistance de var=d avec les variables précédentes
12. IF var=d est consistant THEN
13. reste = backtrack(k+1, toutesLesSolutions)
14. IF reste != echec THEN
15. RETURN reste
16. END IF
17. END IF
18. END DO
19. END IF
20. RETURN echec
END Backtrack
L'algorithme prend 2 paramètres :
- k : la profondeur courante (commence
à 0)
- toutesLesSolutions : si vraie, alors
retourne toutes les solutions possibles ; sinon, retourne la
première
Les solutions seront stockées dans la variable globale SOLUTIONS,
et chaque solution sera représentée par un dictionnaire
qui, à un nom de variable donné, associera la valeur de
cette variable.
Les étapes 11 et 12 de l'algorithme ci-dessus seront
implémentées à l'aide de la fonction consistanceAvecVarsPrecedentes, que
vous devez compléter.
Ensuite, testez votre algorithme sur le fichier test.
Copyright LIA - 2006. Author: vincent.schickel-zuber@epfl.ch -
le 28 Avril 2006 - Last modified 31st MArch 2011 by Florent Garcin