diff --git a/lab6/PSC.py b/lab6/PSC.py index da2a205..f5883b6 100644 --- a/lab6/PSC.py +++ b/lab6/PSC.py @@ -25,23 +25,23 @@ ##retourne toutes les contraintes unaires pour un noeud donnne ##@param noeud le noeud def retourneContraintesUnaires(noeud): - contraintes=[] - for a in ARCS: - if a.refContrainte.depart==noeud.refVar and a.refContrainte.arrive==noeud.refVar: - contraintes.append(a.refContrainte) - return contraintes + contraintes=[] + for a in ARCS: + if a.refContrainte.depart==noeud.refVar and a.refContrainte.arrive==noeud.refVar: + contraintes.append(a.refContrainte) + return contraintes ##retourne toutes les contraintes binaires pour deux noeuds donnnes ##@param noeud1 le noeud 1 ##@param noeud2 le noeud 2 ##@ret toutes les contraintes bineaires ente n1 et n2 def retourneContraintesBinaires(noeud1,noeud2): - contraintes=[] - for a in ARCS: - if (a.refContrainte.depart==noeud1.refVar and a.refContrainte.arrive==noeud2.refVar) or (a.refContrainte.depart==noeud2.refVar and a.refContrainte.arrive==noeud1.refVar): - if a.refContrainte not in contraintes: - contraintes.append(a.refContrainte) - return contraintes + contraintes=[] + for a in ARCS: + if (a.refContrainte.depart==noeud1.refVar and a.refContrainte.arrive==noeud2.refVar) or (a.refContrainte.depart==noeud2.refVar and a.refContrainte.arrive==noeud1.refVar): + if a.refContrainte not in contraintes: + contraintes.append(a.refContrainte) + return contraintes @@ -49,77 +49,82 @@ ##@param algo le nom de l'algo ##@param solution la solution trouvee def afficheSolution(algo,solution): - print "\t",algo,": SOLUTION TROUVEE en ",ITERATION,"etapes et avec ",libPSC.NBCONTRAINTE," contraintes verifiees; SOLUTION=",solution + print "\t",algo,": SOLUTION TROUVEE en ",ITERATION,"etapes et avec ",libPSC.NBCONTRAINTE," contraintes verifiees; SOLUTION=",solution ##affiche le nombre d'iteration avec queques informations utile ##@param algo le nom de l'algo ##@param k la pronfondeur actuelle def afficheNbIteration(algo,k): - print algo,": Ieration:=",ITERATION," pronfondeur actuelle:=",k ,"et",libPSC.NBCONTRAINTE," contraintes verifiees" - + print algo,": Ieration:=",ITERATION," pronfondeur actuelle:=",k ,"et",libPSC.NBCONTRAINTE," contraintes verifiees" + ##gere tous les noeuds dans NOEUDS class Noeuds: - ##initialise le tableau de noeuds - def __init__(self): - NOEUDS=[] + ##initialise le tableau de noeuds + def __init__(self): + NOEUDS=[] - ##retourne le noeud referencant le variable ayant un nom=nom - ##@param nom le nom de la variable - ##@ret le noeud, -1 si pas trouv�e - def retourneNoeud(self, nom): - for noeud in NOEUDS: - if noeud.refVar.nomEstEgalle(nom): - return noeud - return -1 + ##retourne le noeud referencant le variable ayant un nom=nom + ##@param nom le nom de la variable + ##@ret le noeud, -1 si pas trouv�e + def retourneNoeud(self, nom): + for noeud in NOEUDS: + if noeud.refVar.nomEstEgalle(nom): + return noeud + return -1 - ##ajoute un noeud a la lite - def ajouteNoeud(self,noeud): - NOEUDS.append(noeud) + ##ajoute un noeud a la lite + def ajouteNoeud(self,noeud): + NOEUDS.append(noeud) - ##applique la consitance des noeuds - def consistanceDesNoeuds(self): - for n in NOEUDS: - n.consitanceDuNoeud(A COMPETER); + ##applique la consistance des noeuds + def consistanceDesNoeuds(self): + for n in NOEUDS: + n.consistanceDuNoeud(retourneContraintesUnaires(n)); - ##affiche tous les noeuds - def __str__(self): - str = "Noeuds\n" - for n in NOEUDS: - str+="\t1. "+ n.__str__()+"\n" - return str + ##affiche tous les noeuds + def __str__(self): + str = "Noeuds\n" + for n in NOEUDS: + str+="\t1. "+ n.__str__()+"\n" + return str ##gere tous les noeuds dans ARCS class Arcs: - ##initialise le tableau des ARCS - def __init__(self): - ARCS=[] + ##initialise le tableau des ARCS + def __init__(self): + ARCS=[] - ##ajoute un arc a la lite - def ajouteArc(self,arc): - ARCS.append(arc) + ##ajoute un arc a la lite + def ajouteArc(self,arc): + ARCS.append(arc) - ##retourne tous les arcs unaire pour un noeud donnne - ##@param noeud le noeud - def retourneArcs(noeud): - arcs2 - for a in ARCS: - if a.refContrainte.depart==noeud.refVar and a.refContrainte.arrive==noeud.refVar: - arcs2.append(a) - return arcs2 + ##retourne tous les arcs unaire pour un noeud donnne + ##@param noeud le noeud + def retourneArcs(noeud): + arcs2 + for a in ARCS: + if a.refContrainte.depart==noeud.refVar and a.refContrainte.arrive==noeud.refVar: + arcs2.append(a) + return arcs2 - ##applique la consitance des arcs - def consistanceDesArcs(self): - .... A FAIRE + ##applique la consistance des arcs + def consistanceDesArcs(self): + modified = True + while modified: + modified = False + for a in ARCS: + if a.refContrainte.dimension() == 2 and a.reviser(): + modified = True - ##affiche tous les noeuds - def __str__(self): - str = "Arcs\n" - for n in ARCS: - str+="\t1. "+ n.__str__()+"\n" - return str + ##affiche tous les noeuds + def __str__(self): + str = "Arcs\n" + for n in ARCS: + str+="\t1. "+ n.__str__()+"\n" + return str ## Algorithme de Bactrack simple ## @param instances les n variables; rempli jusqu'a k @@ -127,27 +132,47 @@ ## @param toutesLesSolutions si True alors cherche TOUTES les solutions, sinon s'arrete a la premiere (valeur oar defaut) ## @param initialise initialise les variables gloabl ITEARTION et SOLUTION ## @ret instances contenant la solution OU echec si aucune solution trouv�e -def backtrack(instances, k, touteLesSoltuions=None, initialise=None): - algo="bt" - global ITERATION - global SOLUTION - - if touteLesSoltuions==None: - touteLesSoltuions=False - if initialise==None: - ITERATION=0 - SOLUTION=[] - libPSC.NBCONTRAINTE=0 - initialise=False - - ITERATION=ITERATION+1 +def backtrack(instances, k, touteLesSolutions=None, initialise=None): + algo="bt" + global ITERATION + global SOLUTION + + if touteLesSolutions==None: + touteLesSolutions=False + if initialise==None: + ITERATION=0 + SOLUTION=[] + libPSC.NBCONTRAINTE=0 + initialise=False + + ITERATION=ITERATION+1 - print "....." - afficheSolution(algo,instances) - print "....." + if k >= len(NOEUDS): + if touteLesSolutions: + SOLUTION = SOLUTION + instances + else: + SOLUTION = [instances] + afficheSolution(algo,instances) + return SOLUTION + else: + n = NOEUDS[k] + for x in n.refVar.domaine: + n.refVar.metAJourValeur(x) + consistant = True + for i in range(k): + if not reduce(lambda x,y: x and y.estValide(), retourneContraintesBinaires(n, NOEUDS[i]), True): + consistant = False + if consistant: + instances[k] = x + rest = backtrack(instances, k+1, touteLesSolutions) + if rest != ECHEC: + return rest - return ECHEC + return ECHEC +def initLabelDesVariables(): + for n in NOEUDS: + n.refVar.label = n.refVar.domaine ## Algorithme de Forward Chekcing simple ## @param instances les n variables; rempli jusqu'a k @@ -155,26 +180,52 @@ ## @param toutesLesSolutions si True alors cherche TOUTES les solutions, sinon s'arrete a la premiere (valeur oar defaut) ## @param initialise initialise les variables gloabl ITEARTION et SOLUTION, et le laebl des noeuds ## @ret instances contenant la solution OU echec si aucune solution trouv�e -def forwardChecking(instances, k, touteLesSoltuions=None, initialise=None): - algo="ft" - global ITERATION - global SOLUTION - if touteLesSoltuions==None: - touteLesSoltuions=False - if initialise==None: - ITERATION=0 - SOLUTION=[] - libPSC.NBCONTRAINTE=0 - initLabelDesVarrables() - initialise=False - - ITERATION=ITERATION+1 - afficheNbIteration(algo,k) - print "....." - afficheSolution(algo,instances) - print "....." +def forwardChecking(instances, k, touteLesSolutions=None, initialise=None): + algo="ft" + global ITERATION + global SOLUTION + if touteLesSolutions==None: + touteLesSolutions=False + if initialise==None: + ITERATION=0 + SOLUTION=[] + libPSC.NBCONTRAINTE=0 + initLabelDesVariables() + initialise=False + + ITERATION=ITERATION+1 + afficheNbIteration(algo,k) - return ECHEC + # TODO + if k >= len(NOEUDS): + if touteLesSolutions: + SOLUTION = SOLUTION + instances + else: + SOLUTION = [instances] + afficheSolution(algo,instances) + return SOLUTION + else: + n = NOEUDS[k] + for x in n.refVar.label: + # TODO + n.refVar.metAJourValeur(x) + consistant = True + for i in range(k+1, len(NOEUDS)): + # TODO + if not reduce(lambda x,y: x and y.estValide(), retourneContraintesBinaires(n, NOEUDS[i]), True): + # TODO + consistant = False + if consistant: + instances[k] = x + rest = forwardChecking(instances, k+1, touteLesSolutions, True) + if rest != ECHEC: + return rest + for i in range(k+1, len(NOEUDS)): + # TODO + NOEUDS[i].refVar.label = NOEUDS[i].refVar.domaine -execfile("testConsistance.py") -##execfile("test.py") \ No newline at end of file + + return ECHEC + +#execfile("testConsistance.py") +execfile("test.py") diff --git a/lab6/libPSC.py b/lab6/libPSC.py index 39e7bc0..784ecaa 100644 --- a/lab6/libPSC.py +++ b/lab6/libPSC.py @@ -1,8 +1,5 @@ ################################################################################# print "Chargement du module variable et noeud pour PSC" -print "\t@version: 1.1 date: 24/04/2006 modified by the vincent.schickel-zuber@epfl.ch" -print "\t@author: vincent.schickel-zuber@epfl.ch date: 24/04/2006" -print "\t@copyright: EPFL-IC-IIF-LIA 2006" ################################################################################# import copy @@ -12,209 +9,225 @@ ##Classe modelisant une Variable class Variable: - ##Constructeur de la classe variable - ##INITIALISE valeur = -1 - ##@param nom le nom de la variable; sert d'identifiant - ##@param domaine le domaine de valeur sous fourme [] - def __init__(self, nom, domaine): - self.nom=nom - self.domaine=domaine - self.valeur=-1 - - - ##met a jour la valeur - ##@param valeur la nouvelle valeur - def metAJourValeur(self,valeur): - self.valeur=valeur + ##Constructeur de la classe variable + ##INITIALISE valeur = -1 + ##@param nom le nom de la variable; sert d'identifiant + ##@param domaine le domaine de valeur sous fourme [] + def __init__(self, nom, domaine): + self.nom=nom + self.domaine=domaine + self.valeur=-1 + + + ##met a jour la valeur + ##@param valeur la nouvelle valeur + def metAJourValeur(self,valeur): + self.valeur=valeur - ##Verifie que le nom est egalle a celui passe en parametre - ##@param nom un nom a verifier - ##@ret true <=>self.nom=nom - def nomEstEgalle(self,nom): - return self.nom==nom - - ## retourne la taille du domaine - def tailleDuDomaine(self): - return len(self.domaine) - - ## retourne true <=> le domaine est vide - def domaineEstVide(self): - self.tailleDuDomaine()==0; + ##Verifie que le nom est egalle a celui passe en parametre + ##@param nom un nom a verifier + ##@ret true <=>self.nom=nom + def nomEstEgalle(self,nom): + return self.nom==nom + + ## retourne la taille du domaine + def tailleDuDomaine(self): + return len(self.domaine) + + ## retourne true <=> le domaine est vide + def domaineEstVide(self): + self.tailleDuDomaine()==0; - ##retourne une representation en String de la Variable - def __str__(self): - str = "var : < %s , %s >" %(self.nom, self.domaine) - return str + ##retourne une representation en String de la Variable + def __str__(self): + str = "var : < %s , %s >" %(self.nom, self.domaine) + return str ##class Contrainte: class Contrainte: - ##constructeur - ##@param depart la variable de depart - ##@param arrive la variable d'arrive - def __init__(self,depart,arrive): - self.depart=depart - self.arrive=arrive + ##constructeur + ##@param depart la variable de depart + ##@param arrive la variable d'arrive + def __init__(self,depart,arrive): + self.depart=depart + self.arrive=arrive - ##retournce la dimension - def dimension(self): - return 0 + ##retournce la dimension + def dimension(self): + return 0 - ## verifie que la valeur de la variable 1 et 2 sont valide avec la contrainte - ## @return true <=> valide - def estValide(self): - print "coucou" + ## verifie que la valeur de la variable 1 et 2 sont valide avec la contrainte + ## @return true <=> valide + def estValide(self): + print "coucou" - ##retourne une representation en String de la contrainte - def __str__(self): - str = "contrainte : < %s , %s >" %(self.depart.nom, self.arrive.nom) - return str + ##retourne une representation en String de la contrainte + def __str__(self): + str = "contrainte : < %s , %s >" %(self.depart.nom, self.arrive.nom) + return str ##Classe modelisant une contraite unaire class ContrainteUnaire(Contrainte): - ##constructeur - ##@param ref valeur de reference - ##@param op "<" || "<=" - ##@param refVar reference sur la variable - def __init__(self,refVar,op,ref): - Contrainte.__init__(self,refVar,refVar) - self.ref=ref - self.op=op - self.refVar=refVar + ##constructeur + ##@param ref valeur de reference + ##@param op "<" || "<=" + ##@param refVar reference sur la variable + def __init__(self,refVar,op,ref): + Contrainte.__init__(self,refVar,refVar) + self.ref=ref + self.op=op + self.refVar=refVar - ##retournce la dimension - def dimension(self): - return 1 + ##retournce la dimension + def dimension(self): + return 1 - ## verifie que la valeur de la variable est valide avec la contrainte - ## @param valeur la valeur a verifier - ## @return true <=> valide - def estValide(self): - global NBCONTRAINTE - NBCONTRAINTE+=1 - if (self.op=="<"): - return self.refVar.valeur valide + def estValide(self): + global NBCONTRAINTE + NBCONTRAINTE+=1 + if (self.op=="<"): + return self.refVar.valeur" || "==" - ##@param refVar1 reference sur la variable 1 - ##@param refVar2 reference sur la variable 2 - def __init__(self,refVar1,op,refVar2): - Contrainte.__init__(self,refVar1,refVar2) - self.refVar1=refVar1 - self.op=op - self.refVar2=refVar2 + ##constructeur + ##@param op "<>" || "==" + ##@param refVar1 reference sur la variable 1 + ##@param refVar2 reference sur la variable 2 + def __init__(self,refVar1,op,refVar2): + Contrainte.__init__(self,refVar1,refVar2) + self.refVar1=refVar1 + self.op=op + self.refVar2=refVar2 - ##retournce la dimension - def dimension(self): - return 2 + ##retournce la dimension + def dimension(self): + return 2 - ## verifie que la valeur de la variable 1 et 2 sont valide avec la contrainte - ## @return true <=> valide - def estValide(self): - global NBCONTRAINTE - NBCONTRAINTE+=1 - if (self.op=="<>"): - return self.refVar1.valeur<>self.refVar2.valeur - elif (self.op=="=="): - return self.refVar1.valeur==self.refVar2.valeur - else: - print "|-| Operateur", self.op, "non implemente" - return false + ## verifie que la valeur de la variable 1 et 2 sont valide avec la contrainte + ## @return true <=> valide + def estValide(self): + global NBCONTRAINTE + NBCONTRAINTE+=1 + if (self.op=="<>"): + return self.refVar1.valeur<>self.refVar2.valeur + elif (self.op=="=="): + return self.refVar1.valeur==self.refVar2.valeur + else: + print "|-| Operateur", self.op, "non implemente" + return false - ## verifie que si la valeur de la variable 1 , alors la contrainte n'es pas violee - ## @return true <=> possible - def estPossible(self): - global NBCONTRAINTE - uneVraie = lambda x, y : x or y - results=[] - if len(self.refVar2.domaine)==0 : - return False - for d in self.refVar2.domaine: - NBCONTRAINTE+=1 - self.refVar2.metAJourValeur(d) - if (self.op=="<>"): - results.append(self.refVar1.valeur<>self.refVar2.valeur) - elif (self.op=="=="): - results.append(self.refVar1.valeur==self.refVar2.valeur) - else: - print "|-| Operateur", self.op, "non implemente" - results.append(false) - return reduce(uneVraie,results) + ## verifie que si la valeur de la variable 1 , alors la contrainte n'es pas violee + ## @return true <=> possible + def estPossible(self): + global NBCONTRAINTE + uneVraie = lambda x, y : x or y + results=[] + if len(self.refVar2.domaine)==0 : + return False + for d in self.refVar2.domaine: + NBCONTRAINTE+=1 + self.refVar2.metAJourValeur(d) + if (self.op=="<>"): + results.append(self.refVar1.valeur<>self.refVar2.valeur) + elif (self.op=="=="): + results.append(self.refVar1.valeur==self.refVar2.valeur) + else: + print "|-| Operateur", self.op, "non implemente" + results.append(false) + return reduce(uneVraie,results) - ## verifie que si la valeur de la variable 1 , alors la contrainte n'es pas violee - ## @return true <=> possible - def estPossibleAvecLabel(self): - global NBCONTRAINTE - uneVraie = lambda x, y : x or y - results=[] - if len(self.refVar2.label)==0: - return False - for d in self.refVar2.label: - NBCONTRAINTE+=1 - self.refVar2.metAJourValeur(d) - if (self.op=="<>"): - results.append(self.refVar1.valeur<>self.refVar2.valeur) - elif (self.op=="=="): - results.append(self.refVar1.valeur==self.refVar2.valeur) - else: - print "|-| Operateur", self.op, "non implemente" - results.append(false) - return reduce(uneVraie,results) + ## verifie que si la valeur de la variable 1 , alors la contrainte n'es pas violee + ## @return true <=> possible + def estPossibleAvecLabel(self): + global NBCONTRAINTE + uneVraie = lambda x, y : x or y + results=[] + if len(self.refVar2.label)==0: + return False + for d in self.refVar2.label: + NBCONTRAINTE+=1 + self.refVar2.metAJourValeur(d) + if (self.op=="<>"): + results.append(self.refVar1.valeur<>self.refVar2.valeur) + elif (self.op=="=="): + results.append(self.refVar1.valeur==self.refVar2.valeur) + else: + print "|-| Operateur", self.op, "non implemente" + results.append(false) + return reduce(uneVraie,results) - ##retourne une representation en String de la contrainte - def __str__(self): - str = "contrainte : < %s , %s , %s >" %(self.refVar1.nom, self.op, self.refVar2.nom) - return str + ##retourne une representation en String de la contrainte + def __str__(self): + str = "contrainte : < %s , %s , %s >" %(self.refVar1.nom, self.op, self.refVar2.nom) + return str ##Classe modelisant un Noeud class Noeud: - ##constructeur - ##l'attribut pos est initialise a 0 - ##@param variable la variable referencee - def __init__(self,variable): - self.refVar=variable + ##constructeur + ##l'attribut pos est initialise a 0 + ##@param variable la variable referencee + def __init__(self,variable): + self.refVar=variable - ##fait la consitance du noeud - ##@param contraintes la liste de contraintes unaires pour ce noeud - def consitanceDuNoeud(self,contraintes): - ... A IMPLEMENTER + ##fait la consistance du noeud + ##@param contraintes la liste de contraintes unaires pour ce noeud + def consistanceDuNoeud(self,contraintes): + for x in self.refVar.domaine[:]: + self.refVar.metAJourValeur(x) + for c in contraintes: + if not c.estValide(): + self.refVar.domaine.remove(x) + break + - ##retourne une representation en String de la Variable - def __str__(self): - str = "Noeud -> %s " %(self.refVar) - return str + + ##retourne une representation en String de la Variable + def __str__(self): + str = "Noeud -> %s " %(self.refVar) + return str ##classe modelisant un arc class Arc: - ##constructeur - ##@param contrainte la contrainte referencee - def __init__(self,contrainte): - self.refContrainte=contrainte + ##constructeur + ##@param contrainte la contrainte referencee + def __init__(self,contrainte): + self.refContrainte=contrainte - ##revise la consistance des valeurs de domaine piur la contrainte representee par cet arc - def reviser(self): - ... A IMPLEMENTER - - ##retourne une representation en String de l'arc - def __str__(self): - str = "Arc -> %s " %(self.refContrainte) - return str - \ No newline at end of file + ##revise la consistance des valeurs de domaine pour la contrainte representee par cet arc + def reviser(self): + modified = False + + for x in self.refContrainte.refVar1.domaine[:]: + self.refContrainte.refVar1.metAJourValeur(x) + + if not self.refContrainte.estPossible(): + modified = True + self.refContrainte.refVar1.domaine.remove(x) + + return modified + + ##retourne une representation en String de l'arc + def __str__(self): + str = "Arc -> %s " %(self.refContrainte) + return str + diff --git a/lab6/test.py b/lab6/test.py index 05abe7c..18f35e8 100644 --- a/lab6/test.py +++ b/lab6/test.py @@ -32,11 +32,11 @@ -print "Fait la consitance des noeuds" +print "Fait la consistance des noeuds" noeuds.consistanceDesNoeuds() print noeuds -print "Fait la consitance des arcs" +print "Fait la consistance des arcs" arcs.consistanceDesArcs() print noeuds @@ -44,4 +44,4 @@ print "Solution trouv�e avec bt:=", SOLUTION sol=forwardChecking([-1,-1,-1],0,True) -print "Solution trouv�e avec fc:=", SOLUTION \ No newline at end of file +print "Solution trouv�e avec fc:=", SOLUTION diff --git a/lab6/testConsistance.py b/lab6/testConsistance.py index a80dac5..82e7b42 100644 --- a/lab6/testConsistance.py +++ b/lab6/testConsistance.py @@ -32,10 +32,10 @@ print arcs -print "Fait la consitance des noeuds" +print "Fait la consistance des noeuds" noeuds.consistanceDesNoeuds() print noeuds -print "Fait la consitance des arcs" +print "Fait la consistance des arcs" arcs.consistanceDesArcs() -print noeuds \ No newline at end of file +print noeuds