Outils pour l'Analyse Dynamique et la mise au Point de
Programmes avec Contraintes
Bibliothèque d'exemples,
Exemples classiques
Le golfeur Sociable
Description du problème : n golfeurs désirent
constituer g groupes de s personnes pendant w semaines
de sorte que tous les joueurs ne se rencontrent dans le même groupe
pas plus d'une fois.
Intérêt : le problème comporte un très
grand nombre de symétries (entre les joueurs, entre les semaines,
entre les groupes à l'intérieur d'une semaine, entre les joueurs
au sein d'un groupe, la composition de ces symétries...). Plusieurs
modélisations existent, chacune ayant un nombre différent de
symétries.
Source :
- Modélisation 1: la solution est une liste de semaine, chaque
semaine étant une liste de joueurs qui ont pour valeur le numéro
du groupe dans lequel ils appartiennent. Chaque groupe est donc vu comme
un ensemble et la symétrie à l'intérieur de ce groupe
n'existe pas (code GNU-Prolog).
- Modélisation 2: les données sont représentées
par un tableau joueurIxjoueurJ, chaque case étant une
variable contrainte, la valeur de chacune d'entre elles représentant
la semaine où le joueur I rencontre le joueur J. Pour
définir les groupes on utilise une contrainte de transitivité
fd_transitivity qui n'existe pas dans GNU-Prolog mais qui a été
incluse dans Codeine. Par modélisation les symétries entre
groupes et à l'intérieur d'un groupe sont éliminées.(code GNU-Prolog + librairie pour manipuler les listes).
(Aucune symétries n'a été éliminée, mises
à part celles induites par la modélisation)
Trace :
Modèle 1 :
Modèle 2 :