Detail des listes

Bon, j'ai essayer de penser à l'organisation des listes et il y a plusieurs points a discuter (notez que, la plupart du temps, je peux pas rester pour les discussion de groupe, donc peut-être que vous avez déjà choisi, bref, vous me direz.)

Je pense qu'il est clair que nous utiliserons deux listes: une pour les variable et une pour les contraintes.
Du coté résolution, ils partent du principe que les listes seront doublement chainé, donc on va partir là dessus.

Première chose: Comment on représente les domaines? Vu qu'il y a un domaine par variable, on peut les mettre dans la liste des variable, mais on peut également en faire des contraintes, vu que ça "contraint" des variable à prendre certaines valeurs.

Deuxième chose: Sur les contraintes, comment on les enregistre? Je me disais qu'on pourrait faire trois variable, genre les deux premières servent de valeur, et la troisième est un char qui sert à indiquer quelle est l'opération de comparaison.
Je vois pas de problème, mais bon, comme je l'ai dit, j'ai pas pu être complètement présent, donc des problème ont pu me passer sous le nez.

Troisième chose: Il faut voir quelles fonctions on intègre avec les listes, et leur effet. (Ex: est-ce que AjouterElement (je suppose qu'on aura une fonction du genre) ajoute un élément à la fin ou au début de la liste? Est-ce qu'elle renvoie quelque chose? Des trucs comme ça.)

les contraintes sont représentés via des arbres semblables à ceux vu en compilation, c'est ce que le prof à proposé et ça permet de faire des contraintes très compliqué et très facilement : dans yacc les arbres sont construit. puis on se fait une seule fonction récursive d'évaluation de l'arbre qui sera un grand switch tout comme en compilation

à partir du fichier de description analysée par lex et yacc, on construit une liste de contraintes

le prof a proposé de faire une fonction qui étant donné une contraintes retourne 3 valeurs: une pour dire contrainte vérifié, une pour dire contraintes non vérifié, une pour dire impossible de vérifier la contraintes car elle fait intervenir au moins une variable non instanciée

j'ai pensé à une méthode permettant de faire une fonction retournant juste vérifiée ou non vérifiée:

plutôt que d'avoir une seule liste de contrainte, chaque variable possède un sous-ensemble de contraintes (éventuellement vide). chaque sous-ensemble est disjoint. dès que la valeur d'une variable est affecté, on vérifie seulement les contraintes de la liste de cette variable
supposons qu'on est un nombre n de variables
la variable i, 1<=i<=n, possède une liste des contraintes la faisant obligatoirement intervenir, et pouvant faire intervenir des variable d'indice j<i
de cette manière, l'évaluation d'une contraintes n'aura pourra jamais à retourner qu'une variable n'est pas affecté.

pour créer ces listes pour chaque variable:
on peut par exemple en début de programme construire une liste de toutes les contraintes
puis on se fixe un ordre d'instanciation des variables qui ne changera plus (on peut le changer juste avant cette étapes mais seulement avant et pas pendant la résolution: par exemple on peut trié par ordre décroissant du nombre d'implications dans les contraintes, ou par ordre croissant de cardinalité de leur domaine (on utilise des domaines fini))

pour chaque variable i de la liste des variables
pour chaque contraintes c dans la grande liste des contraintes
si (c fait intervenir la variable i) && (c ne fait pas intervenir de variable j>i)
enlever c de la grande liste des contraintes
mettre c dans la liste des contraintes de la variable i

normalement, en fin de cette méthode, toutes les contraintes sont dans la liste d'une seules variables
il peut subsister des contraintes ne faisant pas intervenir dans la première liste du genre (5 > 2). on a juste à les supprimer

pour les domaines Dimitri a dit qu'il s'en occupais, normalement il a déjà des idée dessus