Forward checking¶

from moteur_psc.contrainte import ContrainteBinaire

class ContrainteAvecPropagation(ContrainteBinaire):
    """ Contrainte imposant une restriction sur deux variables avec la méthode\
        ``propage``.

        Exemple: ``x > y``.
    """

    def __init__(self, var1, var2, op):
        """ Exemples d'op: ``lambda x,y: x != y``, ``lambda x,y: x < y``.

            :param var1: première variable concernée par la contrainte.
            :param var2: deuxième variable concernée par la contrainte.
            :param op: fonction ou expression lambda permettant de vérifier la\
            contrainte.
        """

        ContrainteBinaire.__init__(self, var1, var2, op)

    def reviser(self):
        """ Algorithme de révision des domaines.

            Pour chaque variable, vérifie chaque valeur du domaine. Supprime\
            les valeurs qui empêchent la contrainte d'être satisfaite dans le\
            domaine.

            :return: ``True`` si un des domaines a été modifié.
        """

        # Nous appliquons d'abord la méthode reviser() de la classe-mère pour
        # réviser les domaines de chaque variable.
        domaines_modifies = ContrainteBinaire.reviser(self)

        # Puis, s'il y a lieu, nous nous assurons que les labels sont toujours
        # identiques aux domaines.
        if domaines_modifies:
            for var in self.variables:
                var.label = var.domaine[:]

        return domaines_modifies


    def propage(self, var):
        """ Propage l'assignation d'une variable au label de la seconde.

            :param var: la variable fixée.
            :return: ``True`` si la contrainte est toujours satisfaisable avec\
            la valeur fixée.
        """
        var1, var2 = self.variables

        if var == var1:
            fixe = var1
            variable = var2
        elif var == var2:
            variable = var1
            fixe = var2
        else:
            raise ValueError('Var est ' + var.nom + '. ' +
                             'on attendrait ' + var1.nom + ' ou ' + var2.nom)

        # On ne garde que les valeurs du label pour lesquelles variable
        # reste valide.
        for val in variable.label[:]:
            if not self.est_valide(variable, val):
                variable.label.remove(val)

        # S'il existe au moins une valeur possible, l'assignation est consistante.
        return len(variable.label) > 0

from moteur_psc.psc import PSC

class PSCHeuristique(PSC):

    def __init__(self, variables, contraintes):
        """
            :param list variables: les variables du problème.
            :param list contraintes: les contraintes du problème.
        """

        PSC.__init__(self, variables, contraintes)

        self.reinitialise()

    def reinitialise(self):
        """ Réinitialise les attributs du problème.

            Après l'appel à cette méthode, les labels des variables sont à\
            nouveau égaux aux domaines complets, et les variables ont une\
            valeurs indéfinie (égale à ``None``).
        """

        self.initialise_labels()
        self.solutions = []
        self.iterations = 0

    def initialise_labels(self):
        """ Initialise les labels pour les rendre identiques aux domaines. """

        for var in self.variables:
            var.label = var.domaine[:]

    def consistance_noeuds(self):
        """ Applique la consistance des noeuds sur les contraintes unaires du\
            problème.

            L'algorithme consiste à enlever des domaines de définition toutes\
            les valeurs qui violent les contraintes unaires.
        """

        # Nous appelons d'abord la méthode de la classe-mère PSC pour réduire
        # les domaines.
        PSC.consistance_noeuds(self)

        # Puis, nous nous assurons que les labels sont identiques aux domaines.
        self.initialise_labels()

    def variable_ordering(self):
        """ Trie les variables par ordre croissant de taille de domaine."""
        self.variables.sort(key=lambda x: len(x.domaine))

    def dynamic_variable_ordering(self, k):
        """ Place en position ``k`` la variable non instanciée dotée du label le\
            plus restreint.

            :param k: profondeur actuelle de la recherche.
        """
        index = k
        taille_plus_petit_label = len(self.variables[index].label)

        for i in range(k+1, len(self.variables)):
            if len(self.variables[i].label) < taille_plus_petit_label:
                index = i
                taille_plus_petit_label = len(self.variables[i].label)

        if k != index:
            self.variables[k], self.variables[index] = self.variables[index], self.variables[k]

    def propagation_consistante(self, k):
        """ Propage la valeur de la variable actuelle sur les variables\
            suivantes.

            Pour chaque contrainte portant sur la variable courante et sur une\
            ou plusieurs des variables non encore instanciée, appelle la methode\
            ``propage`` de la contrainte pour réduire le label de la deuxième\
            variable.

            :param k: profondeur actuelle de la recherche.
            :return: ``True`` si la valeur de la dernière variable instanciée\
            n'empêche pas l'instanciation des variables suivantes.
        """
        # Pour chaque contrainte portant sur la variable courante,
        for contrainte in self.contraintes:
            if self.variables[k] in contrainte.variables:
                # si la contrainte porte sur une des variables suivantes,
                for i in range(k+1, len(self.variables)):
                    if self.variables[i] in contrainte.variables:
                        # on propage la nouvelle assignation.
                        if contrainte.propage(self.variables[k]):
                            break
                        else:
                            # La contrainte ne peut pas être satisfaite.
                            return False
        return True

    def forward_checking(self, k=0, une_seule_solution=False):
        """ Algorithme du Forward Checking.

            Le Forward Checking essaie de limiter les retours en arrière en\
            restreignant les domaines des variables non instanciées\
            (par application de la consistance des arcs à chaque itération).

            :param une_seule_solution: retourne après avoir trouvé la première\
            solution.
            :param k: la profondeur actuelle de la recherhe.
        """
        if len(self.solutions) == 1 and une_seule_solution:
            return

        self.iterations += 1
        if k >= len(self.variables):
            sol = {}
            for var in self.variables:
                sol[var.nom] = var.val
            self.solutions.append(sol)
        else:
            self.dynamic_variable_ordering(k)
            variable = self.variables[k]

            # Conserve une copie des labels de départ.
            sauvegarde_labels = { var: var.label[:] for var in self.variables }

            for val in sauvegarde_labels[variable]:
                variable.val = val
                variable.label = [val]
                if self.propagation_consistante(k):
                    # Continue l'algorithme sur la variable k+1.
                    self.forward_checking(k=k+1, une_seule_solution=une_seule_solution)
                for var in self.variables:
                    var.label = list(sauvegarde_labels[var])
            variable.val = None