PSC.forwardChecking

PSC.forwardChecking(k, toutesLesSolutions=None, initialise=None)

Algorithme de Forward Checking simple avec DVO

Le forward checking a pour but d’eviter autant que possible les backtracks en detectant a l’avance des instanciations inconsistantes et en appliquant le critere de la consistance des arcs pendant la recherche.

Il exige qu’on ajoute un label l[i] a chaque variable, qui sera initialement egal a son domaine. Le forward checking met a jour ces labels en appliquant la regle suivante:

A chaque instanciation d’une variable xk, eliminer toutes les valeurs inconsistantes avec xk des labels des variables qui ne sont pas encore instanciees.

Paramètres:

• k – la pronfondeur de la recherce (commence a 0)
• toutesLesSolutions – si True alors cherche TOUTES les solutions, sinon s’arrete a la premiere (valeur par defaut)
• initialise – initialise les variables globales ITERATIONS et SOLUTIONS, et le labels des noeuds

Retourne:

instances contenant la solution OU echec si aucune solution trouvee

Voir aussi

Chapitre 8.4.1 du livre