Module projet.solvers.SolverCSP
module pour le solver CSP
Expand source code
""" module pour le solver CSP """
from constraint import *
from projet.outils.GrapheDeLieux import GrapheDeLieux
class SolverCSP :
"""
Implementation du solveur CSP
"""
# attributs
# //////////////////////////////////////////////
# metriques pour comparer les solutions
__problem__ : Problem
""" le problem CSP a resoudre """
__nbCouleurs__ : int
""" le nb de couleurs utilise pour la resolution """
__lesVariables__ : list
""" la liste des variables du CSP """
# constructeur
def __init__ (self, g : GrapheDeLieux, nb : int) :
""" construction du solver
:param g: graphe des lieux (chaque sommet sera une variable et
chaque arete induira une contrainte disant que les
deux extremités doivent etre differentes)
:param nb: nb de valeurs possibles pour les variables (de 1 a nb)
"""
self.__problem__ = Problem()
self.__nbCouleurs__ = nb
self.__lesVariables__ = g.getSommets()
domaine = []
# construction du domaine (le même pour toutes les variables)
for i in range(1,nb+1) :
domaine.append(i)
# ajout des variables avec leur domaine ds le CSP
self.__problem__.addVariables (self.__lesVariables__, domaine)
# construction des contraintes associees
for v1 in self.__lesVariables__ :
for v2 in g.getAdjacents(v1) :
if v2 >= v1 :
l : list = []
l.append(v1)
l.append(v2)
self.__problem__.addConstraint(self.__fcDifferentIfConnected__,l)
# methodes
# //////////////////////////////////
# calcul de la contrainte
def __fcDifferentIfConnected__ (self, s1 : int, s2 : int) :
""" pour construire la contrainte du CSP disant que deux sommets connectes
ne doivent pas avoir la meme valeur
:param s1 : valeur du sommet 1
:param s2 : valeur du sommet 2
"""
return s1 != s2
# affichage des metriques
def __affMetriques__(self, complet : bool, res) :
""" pour afficher le resultat
:param complet: si True le resultat est l'ensemble de toutes les solutions
si False le resultat est une seule solution
:param res: le resultat de la resolution du pb par le solveur CSP
"""
if (res != None and len(res) != 0) :
st = "======== OK avec "+str(self.__nbCouleurs__)+" couleurs !\n\t | "
if complet : # cas ou il y a plusieurs solutions
st = st +" \t (nb de solutions = "+str(len(res)) +")\n\t"
for sol in res :
for cle in self.__lesVariables__ :
st = st + str(cle) +" = "+str(sol[cle])+" | "
st = st +"\n\t"
else : # cas ou il y a une seule solution
for cle in self.__lesVariables__ :
st = st + str(cle) +" = "+str(res[cle])+" | "
else :
st = "======== NOK ! Pas de solution"
print (st)
def solve(self, complet : bool) :
""" execution du solver pour avoir 1 solution
:param complet: False si on veut une seule solution, True si on les veut toutes
"""
# resolution du CSP
if not complet :
res = self.__problem__.getSolution()
else :
res = self.__problem__.getSolutions()
self.__affMetriques__(complet, res)
Classes
class SolverCSP (g: GrapheDeLieux, nb: int)
-
Implementation du solveur CSP
construction du solver
:param g: graphe des lieux (chaque sommet sera une variable et chaque arete induira une contrainte disant que les deux extremités doivent etre differentes)
:param nb: nb de valeurs possibles pour les variables (de 1 a nb)
Expand source code
class SolverCSP : """ Implementation du solveur CSP """ # attributs # ////////////////////////////////////////////// # metriques pour comparer les solutions __problem__ : Problem """ le problem CSP a resoudre """ __nbCouleurs__ : int """ le nb de couleurs utilise pour la resolution """ __lesVariables__ : list """ la liste des variables du CSP """ # constructeur def __init__ (self, g : GrapheDeLieux, nb : int) : """ construction du solver :param g: graphe des lieux (chaque sommet sera une variable et chaque arete induira une contrainte disant que les deux extremités doivent etre differentes) :param nb: nb de valeurs possibles pour les variables (de 1 a nb) """ self.__problem__ = Problem() self.__nbCouleurs__ = nb self.__lesVariables__ = g.getSommets() domaine = [] # construction du domaine (le même pour toutes les variables) for i in range(1,nb+1) : domaine.append(i) # ajout des variables avec leur domaine ds le CSP self.__problem__.addVariables (self.__lesVariables__, domaine) # construction des contraintes associees for v1 in self.__lesVariables__ : for v2 in g.getAdjacents(v1) : if v2 >= v1 : l : list = [] l.append(v1) l.append(v2) self.__problem__.addConstraint(self.__fcDifferentIfConnected__,l) # methodes # ////////////////////////////////// # calcul de la contrainte def __fcDifferentIfConnected__ (self, s1 : int, s2 : int) : """ pour construire la contrainte du CSP disant que deux sommets connectes ne doivent pas avoir la meme valeur :param s1 : valeur du sommet 1 :param s2 : valeur du sommet 2 """ return s1 != s2 # affichage des metriques def __affMetriques__(self, complet : bool, res) : """ pour afficher le resultat :param complet: si True le resultat est l'ensemble de toutes les solutions si False le resultat est une seule solution :param res: le resultat de la resolution du pb par le solveur CSP """ if (res != None and len(res) != 0) : st = "======== OK avec "+str(self.__nbCouleurs__)+" couleurs !\n\t | " if complet : # cas ou il y a plusieurs solutions st = st +" \t (nb de solutions = "+str(len(res)) +")\n\t" for sol in res : for cle in self.__lesVariables__ : st = st + str(cle) +" = "+str(sol[cle])+" | " st = st +"\n\t" else : # cas ou il y a une seule solution for cle in self.__lesVariables__ : st = st + str(cle) +" = "+str(res[cle])+" | " else : st = "======== NOK ! Pas de solution" print (st) def solve(self, complet : bool) : """ execution du solver pour avoir 1 solution :param complet: False si on veut une seule solution, True si on les veut toutes """ # resolution du CSP if not complet : res = self.__problem__.getSolution() else : res = self.__problem__.getSolutions() self.__affMetriques__(complet, res)
Methods
def solve(self, complet: bool)
-
execution du solver pour avoir 1 solution
:param complet: False si on veut une seule solution, True si on les veut toutes
Expand source code
def solve(self, complet : bool) : """ execution du solver pour avoir 1 solution :param complet: False si on veut une seule solution, True si on les veut toutes """ # resolution du CSP if not complet : res = self.__problem__.getSolution() else : res = self.__problem__.getSolutions() self.__affMetriques__(complet, res)