Modélisation d'un problème CSP
Bonjour je dois faire un programme qui selon un fichier défini comme ceci :
Code:
1
2
3
4
5
6
7
| nom_domaine1 val_11 val_12 ... //domaine et valeurs du domaine
nom_domaine2 val_21 val_22 ...
...
xi xj // variables en contraintes
val_i1 val_j1 // liste des couples autorisés
val_i2 val_j2
... |
doit détermininer si le problème est consistant.A savoir associer une valeur à chaque variable tout en satisfaisant les contraintes entre variables.Donc dès qu'on a une solution,on s'arrête et on répond oui le problème a une solution.
Je veux utiliser l'algorithme Backtrack,je l'ai bien compris maintenant reste à savoir l'implémenter.
J'aimerai avoir votre avis sur les structures de données à utiliser pour représenter un tel problème.
Pour les contraintes et les domaines j'ai pensé à un tableau de listes.
Après pour la liste des couples autorisés pour 2 variables en contraintes je ne sais pas trop.
Enfin pour associer une valeur à mes variables un tableau d'entiers semblerait suffire !
Si vous avez déjà eu affaire à ce genre de programme et que vous voulez m'aider je vous en remercie d'avance.
