PSC¶
Module implementant les algorithmes du backtracking et du forward checking pour la resolution des problemes de contraintes
Chaque algorithme utilise les methodes de consistance pour eviter d’avoir des instanciations de valeurs qui ne sont pas compatibles avec les contraintes. Pour plus de details sur le fonctionnement des PSC, lire le chapitre 8 du livre.
Voir aussi
Chapitre 8 du livre
Fonctions
afficheNbIterations(algo, k) |
Affiche le nombre d’iterations ainsi que quelques informations utiles |
afficheSolution(algo, solution) |
Affiche la solution avec quelques informations utiles |
backtrack(k[, toutesLesSolutions, initialise]) |
Algorithme de backtracking simple |
chercheIndexAvecMinTailleLabel(debutIndex) |
Cherche l’index de la plus petite valeur de label dans la liste des |
consistanceAvecVarsPrecedentes(k) |
Verifie si chaque contrainte portant sur la variable k et sur au moins |
dvo(k) |
Applique l’heuristique DVO sur la liste PSC.VARIABLES |
forwardChecking(k[, toutesLesSolutions, ...]) |
Algorithme de Forward Checking simple avec DVO |
metAJourlabels(labels) |
Met a jour les labels de certaines variables |
propageAuxVarsSuivantes(k) |
Propage l’assignation actuelle de la variable k aux variables suivantes dans PSC.VARIABLES |
retourneLabels(k) |
Retourne le contenu des labels des variables a partir de la position k dans un dictionnaire |
variableOrdering() |
Applique l’algorithme du variable ordering en mettant dans l’ordre croissant de longueur du domaine. |
Classes
Contraintes() |
Classe gerant la liste des contraintes PSC.CONTRAINTES |
Variables() |
Classe gerant la liste des variables PSC.VARIABLES |