Algorithmes backtrack basiques

Algorithme itératif affichant une seule solution

Entrée: X la liste des variables, de leur valeurs, de leurs domaines et d'un sous ensemble des contraintes les concernant

Code:

début
   Xi = premiereVariable(X);
   tant que Xi != NULL{
       tant que booléen = affecter_valeur(Xi){
           booléen = vérifier_les_contraintes(Xi);
           si booléen == true
               break;
       }
       si booléen == true
           Xi = suivant(Xi);
       sinon
           Xi = précédent(Xi);
   }
   si booléen == true
       afficher_valeurs(X);
   sinon
       printf("pas de solution");
fin

principe de l'algo:
X est une liste doublement chainée terminée par NULL des deux côtés
il y a deux cas d'arrêts de la première boucle:
- car on tombe sur le pointeur NULL après la dernière variable: cela veut dire qu'on a affecté chaque variable, et que le résultat de vérifier_les_contraintes(Xi) à toujours donné true, donc on a une solution
- car on tombe sur le pointeur NULL avant la première variable: cela veut dire qu'on a testé toutes les valeurs possibles pour la première variable mais que ça fonctionnais pas donc qu'il n'y a aucune solution

dans la deuxième boucle, la fonction affecter_valeur renvoi 1 si elle réussit à mettre dans Xi->valeur une valeur, 0 si il n'y a plus de valeur à affecté (on peut par exemple savoir s'il ne reste plus de valeur en les affectant par ordre croissant et en regardant la valeur actuelle de Xi->valeur)

il y a deux manière de quitter cette deuxième boucle:
-les contraintes avec la valeur sont respectées et on emprunte le break et le booléen vaut true
-la fonction n'arrive affecter_valeur n'arrive pas à affecter une autre valeur et le booléen vaut false

en sortant de la boucle incluse, si le booléen vaut true, il faut passer à la variable suivante
si le booléen vaut false, c'est qu'aucune valeur ne satisfait les contraintes étant donnée les affectations actuelle des variable. il faut donc tenter d'affecter une valeur différente à la variable précédente

en sortant de la boucle principale, le booléen indique toujours si la dernière affectation à vérifier les contraintes ou non, donc cela indique si on a dans les variables une solution du CSP si c'est true, ou alors qu'il n'en existe pas si c'est false



Algorithme itératif affichant toutes solutions

Entrée: X la liste des variables, de leur valeurs, de leurs domaines et d'un sous ensemble des contraintes les concernant

Code:

début
   Xi = premiereVariable(X);
   dernier = derniereVariable(X);
   existeSolution = true;
   tant que existeSolution{
       tant que Xi != NULL{
           tant que existeSolution = affecter_valeur(Xi){
               existeSolution = vérifier_les_contraintes(Xi);
               si existeSolution == true
                   break;
           }
           si existeSolution == true
               Xi = suivant(Xi);
           sinon
           Xi = précédent(Xi);
       }
       si existeSolution == true{
           afficher_valeurs(X);
           Xi = dernier;
       }
       sinon
           printf("plus de solution");
   }
fin

le principe est pareil que l'algo précédent
en plus ici, dès qu'on trouve une solution, c'est à dire que notre booléen vaut true, alors notre Xi qui vaut NULL redevient la dernière variable pour continuer la recherche de solution

Suite aux remarques de Monsieur Marc Bernard, j'ai pensé que faire un algorithme récursif permet plus facilement de gérer la sauvegarde des domaines, et évite en plus d'utiliser une liste doublement chainé pour la liste des variables.
Du coup, Anthony et moi avons réfléchi à un algorithme et voila le fruit de notre dur labeur:

Code:

resolution(LX,LC,0);
void resolution(listeVariable LX, ListeContrainte LC, int k)
{
  if(k>nbVariable(LX))
      affiche_LX(LX);
else
{
  LX = reduction_domaine(LX,LC);
  variable X = recup_var(LX,k);
  for(i=0;i<longueurDomaine(X);i++)
    {
      X = associer_valeur(i,X);
      resolution(ajouter(X,LX),LC,k+1);
    }
}
}

Comment fonctionne-t-il ? Un algo récursif avec un type de retour void c'est possible ? On nous aurait menti ? Et bien c'est très simple:

les arguments: la liste des variables en premier (avec leur domaines et possiblement leur valeur déjà instancié), la liste des contraintes, et un entier pour déterminer combien de variable nous avons déjà instancié (d'où l'appel de la fonction juste au dessus ce fait avec le paramètre 0).

Ensuite: si nous avons déjà instancié toutes les variables du domaines (k>nbVariable) ça veut donc dire que l'on a réussi à atteindre une solution sans conflit de contrainte, on peut donc afficher la solution (ou, si l'on veut récupérer la liste de variable instancié, le plus simple serait sans doute de créer un objet global qui contienne des listes de variables déjà instancié et d'ajouter notre liste de variable instancié à cette étape au lieu d'afficher)

Sinon, ça veut dire qu'il nous reste encore du pain sur la planche: On va tout d'abord réduire le domaine de toutes les variables restantes en ce basant sur les k-1emes qu'on a déjà affecté (une première ébauche de cette fonction a déjà été bossé par Romain).

Ensuite On récupère la kième variable (du coup, tableau pas tableau ? je ne sais pas, c'est pas mon boulot) elle n'est pas instancié (puisqu'on a déjà instancié les k-1iemes précédentes) qu'on stocke dans X (on suppose ici que le type variable contienne aussi le domaine de la variable)

Puis: Pour toutes les valeurs de X du domaine de définition de cette variable (j'ai supposé qu'elles étaient indicé de i à longueurDomaine(X), mais on peut peut-être tourné la boucle différemment) ne pas oublié que le domaine de la variable a pu être réduit au préalable et qu'il ne peut contenir aucune valeur, dans ce cas la boucle ne s’exécute pas et aucun résultat ne sera retourné pour cette instanciation.

Enfin, dans la boucle, s'il y a des valeurs possible pour X, on passe à X la valeur i, puis on récure les toilettes sur résolution en ajoutant l'instanciation de X à LX (d'où la commande ajouter(X,LX) ), on passe les mêmes contraintes et on incrémente k.

Dites-nous si vous voyez un soucis et on voit quel solution on envisage

Cordialement,

void forward_check(variable X_instanciee){
variables V = suivante(X_instanciee);
listeContrainte l;
while( !fin_de_liste(V)){
l = V->contraintes;
while(l!= NULL){
if(l.presenceVariable[X_instanciee.id]=='1') {
domaine D;
while(affecter_valeur(V)){
if (evalue_contrainte(l->a))
ajouter(D,V->valeur);
empiler(V->domaines, D) ;
}
}
l = l->suivant;
}
}
V->suivante(V);
}

Le forward checking implique une modification de la fonction precedente(variable* var), qui doit depiler les nouveaux domaines des variables non initialisées.

Voici la modification que l'on peut vous proposer :


variable* precedente(variable* var){
var->valeur = (float)(var->domaines->dom->valeur - 1);
variables V = suivante(var);
listeContrainte l;
while( !fin_de_liste(V)){
l = V->contraintes;
while(l!= NULL){
if(l.presenceVariable[X_instanciee.id]=='1') {
depiler(V->dom);
}
l = l->suivant;
}
}
V->suivante(V);
return var->precedent;
}