Lab 7 : 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 -------- - :download:`libPSCTemplate.py <../../exercises/hw7/libPSCTemplate.py>` - :download:`PSCTemplate.py <../../exercises/hw7/PSCTemplate.py>` - :download:`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 :py:func:`~PSC.Contraintes.consistanceDesNoeuds` et :py:func:`~PSC.Contraintes.consistanceDesArcs` ne sont pas remplies. Complétez ces fonctions. .. note:: la fonction ``consistanceDesArcs`` doit appeler la méthode :py:func:`~libPSC.ContrainteBinaire.reviser` de la classe :py:class:`~libPSC.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 ``testPSC.py``. Exercice 2 : Algorithme de Backtrack ------------------------------------ Le backtrack est un algorithme de recherche en profondeur d'abord : - nœud de recherche = instanciation de variables x\ :sub:`1` = v\ :sub:`1`, x\ :sub:`2` = v\ :sub:`2`, ..., x\ :sub:`k` = v\ :sub:`k` (où k est la profondeur du nœud dans l'arbre de recherche) - fonction de successeur = instanciation de la variable x\ :sub:`k+1` = v\ :sub:`k+1` de manière à respecter toutes les contraintes pour les variables x\ :sub:`1`, ..., x\ :sub:`k` - nœud initial = instanciation vide - nœud but = instanciation de toutes les variables x\ :sub:`1`, ..., x\ :sub:`n` 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 ``testPSC.py``. .. -------------- .. Copyright LIA - 2006. Author: vincent.schickel-zuber@epfl.ch - le 28 .. Avril 2006 - Last modified 31st MArch 2011 by Florent Garcin