Discussion :

[Jeffboj]

Bonjour,
Access 2000
Dur, dur les Maths
Je cherche un algorithme qui me permette de résoudre la situation suivante :
J'ai une saison de 33 semaines
J'ai 10 Équipes
J'ai 10 allées répartie en 5 paires 1 et 2, 3 et 4, 5 et 6, etc..
Sachant que chaque équipe doit jouer chaque semaine contre une équipe différente et sur une paire d'allée différente.
Donc j'aimerai obtenir :
semaine 1
Equipe 1 -> Equipe 2 sur allée 1 et 2
Equipe 3 -> Equipe 4 sur allée 3 et 4
etc pour les 10 équipes
Semaine 2
Equipe 1 -> Equipe 3 sur allée 4 et 5
Equipe 2 -> Equipe 4 sur allée 5 et 6
etc..
Toutes les 9 semaines on rencontre la même équipe sur une paire d'allée différent à la premiére fois
Quelqu'un peut-il m'aider ?
merci
Jeff

[Adjanakis]

euh.... et tu dois faire ça sous access? Sinon, si j'étais à ta place, je tenterais de déléguer la calendrier des matchs à un moteur de résolution de contraintes. Mais avec Access 2000 c'est chaud. Sinon un algo existe peut etre... mais moi je sèche!

[Jeffboj]

re,

un moteur de résolution de contraintes

je trouve ça ou ?
pas très hot en algo
merci jeff

[Médiat]

Il y a déjà eu plusieurs discussions sur ce sujet dans ce même forum, avec une recherche sur "match" tu devrais trouver plusieurs matches (comme on dit en anglais )

[SuperCed]

Regarde du coté des CSP. C'est exactement fait pour ce genre de problèmes.

[Adjanakis]

re,

un moteur de résolution de contraintes

je trouve ça ou ?
pas très hot en algo
merci jeff

Résolution de contraintes, CSP, Programmation Par Contrainte ... tu l'auras compris, la méthode dont on parle n'est pas de l'algorithmique ordinaire. Il s'agit de réfléchir en émettant des contraintes. Par exemple, pour chaque match entre deux équipe, tu associe une journée de championnat et un terrain. Après tu donne des contraintes telles que:
- un terrain ne recoit qu'un match par journée
- une équipe n'a qu'un match par semaine.

Maintenant, pour trouver un outil te permettant de faire ça, j'ai personnelement bossé avec CHIP qui est une bibliothèque payante et Sat4J qui est un système de contraintes qui ne t'embrouillerait trop. Mais il y a plein d'autre moteurs, mais je ne les connais pas par coeur.

Sinon tu peux simuler tout ça avec un langage comme prolog, ou en retrouvant un algorithme procédural en recherchant sur le site.

[Nemerle]

http://www.developpez.net/forums/vie...11009&start=14

[ceugniet]

Salut,

J'ai fait un petit programme pour résoudre ton problème (en partie, car je n'ai pas tenu compte des allées différentes).
Ce programme s'arrête à la première solution. La voici :

Semaine 1 : ( 1- 2) ( 3- 4) ( 5- 6) ( 7- 8) ( 9-10)
Semaine 2 : ( 1- 3) ( 2- 4) ( 5- 7) ( 6- 9) ( 8-10)
Semaine 3 : ( 1- 4) ( 2- 3) ( 5- 8) ( 6-10) ( 7- 9)
Semaine 4 : ( 1- 5) ( 2- 6) ( 3- 7) ( 4-10) ( 8- 9)
Semaine 5 : ( 1- 6) ( 2- 5) ( 3- 8) ( 4- 9) ( 7-10)
Semaine 6 : ( 1- 7) ( 2- 8) ( 3- 9) ( 4- 6) ( 5-10)
Semaine 7 : ( 1- 8) ( 2- 9) ( 3-10) ( 4- 5) ( 6- 7)
Semaine 8 : ( 1- 9) ( 2-10) ( 3- 5) ( 4- 7) ( 6- 8)
Semaine 9 : ( 1-10) ( 2- 7) ( 3- 6) ( 4- 8) ( 5- 9)

Je tiens mon programme en C à ta disposition si tu le souhaites. Le principe est simple :

1 - Faire la liste des 45 matches
2 - Etablir successivement la liste des cinq matchs d'une semaine en évitant de réutiliser les matches déjà faits depuis le début, et à chaque fois, de refaire jouer les équipes participant aux matchs déjà choisis de cette semaine-là.
3 - En cas de blocage (ça arrive lorsque des équipes restent sur le carreau une semaine car elles se sont déjà rencontrées), remettre en cause le choix précédent (le match précédent de cette semaine) et recommencer.
4 - J'ai prévu, sans avoir besoin d'aller jusque là, de développer le cas de figure où cette procédure (remettre en cause le choix du match précédent) serait impossible, c'est-à-dire qu'on arriverait au premier match à choisir dans cette semaine-là. Si ce type de blocage était survenu, il aurait alors fallu remettre en cause les choix de la semaine précédente. Mais cela n'a pas été nécessaire : le programme a trouvé cette solution.

En ce qui concerne les allées, est-ce que tu veux que chaque équipe utilise successivement toutes les paires (5) d'allées (dans ce cas nécessairement toujours dans le même ordre), ou est-ce que tu voudrais simplement qu'une équipe ne joue pas deux fois de suite sur la même paire d'allées ? (Il était évident que chaque équipe devait rencontrer toutes les autres ; il l'est moins que chaque équipe doive utiliser toutes les paires d'allées !)

Si c'est ce dernier cas, je pense qu'on peut facilement à la main arranger les colonnes du tableau ci-dessus ligne par ligne (chaque colonne représentant une paire d'allées) pour respecter cette contrainte, par exemple, comme ceci :

Semaine 1 : ( 1- 2) ( 3- 4) ( 5- 6) ( 7- 8) ( 9-10)
Semaine 2 : ( 6- 9) ( 8-10) ( 1- 3) ( 2- 4) ( 5- 7)
Semaine 3 : ( 2- 3) ( 1- 4) ( 5- 8) ( 7- 9) ( 6-10)
Semaine 4 : ( 1- 5) ( 2- 6) ( 3- 7) ( 4-10) ( 8- 9)
Semaine 5 : ( 3- 8) ( 2- 5) ( 4- 9) ( 1- 6) ( 7-10)
Semaine 6 : ( 1- 7) ( 3- 9) ( 2- 8) ( 5-10) ( 4- 6)
Semaine 7 : ( 2- 9) ( 4- 5) ( 3-10) ( 6- 7) ( 1- 8)
Semaine 8 : ( 6- 8) ( 1- 9) ( 4- 7) ( 2-10) ( 3- 5)
Semaine 9 : ( 2- 7) ( 3- 6) ( 5- 9) ( 4- 8) ( 1-10)

Ensuite, une fois que le tableau de neuf lignes et 5 colonnes est fait, on fait un copier-coller sur ce tableau pour les 9 semaines suivantes en effectuant une rotation sur les colonnes (la colonne anciennement en 1 passe en 2, celle qui était 2 devient 3,...celle qui était 5 devient 1). La seule contrainte à vérifier est qu'une équipe ne joue pas sur la même paire d'allées en semaine 9 et en semaine 10.

Semaine 1 : ( 1- 2) ( 3- 4) ( 5- 6) ( 7- 8) ( 9-10)
Semaine 2 : ( 6- 9) ( 8-10) ( 1- 3) ( 2- 4) ( 5- 7)
Semaine 3 : ( 2- 3) ( 1- 4) ( 5- 8) ( 7- 9) ( 6-10)
Semaine 4 : ( 1- 5) ( 2- 6) ( 3- 7) ( 4-10) ( 8- 9)
Semaine 5 : ( 3- 8) ( 2- 5) ( 4- 9) ( 1- 6) ( 7-10)
Semaine 6 : ( 1- 7) ( 3- 9) ( 2- 8) ( 5-10) ( 4- 6)
Semaine 7 : ( 2- 9) ( 4- 5) ( 3-10) ( 6- 7) ( 1- 8)
Semaine 8 : ( 6- 8) ( 1- 9) ( 4- 7) ( 2-10) ( 3- 5)
Semaine 9 : ( 2- 7) ( 3- 6) ( 5- 9) ( 4- 8) ( 1-10)
Semaine 10 : ( 9-10) ( 1- 2) ( 3- 4) ( 5- 6) ( 7- 8)
Semaine 11 : ( 5- 7) ( 6- 9) ( 8-10) ( 1- 3) ( 2- 4)
Semaine 12 : ( 6-10) ( 2- 3) ( 1- 4) ( 5- 8) ( 7- 9)
Semaine 13 : ( 8- 9) ( 1- 5) ( 2- 6) ( 3- 7) ( 4-10)
Semaine 14 : ( 7-10) ( 3- 8) ( 2- 5) ( 4- 9) ( 1- 6)
Semaine 15 : ( 4- 6) ( 1- 7) ( 3- 9) ( 2- 8) ( 5-10)
Semaine 16 : ( 1- 8) ( 2- 9) ( 4- 5) ( 3-10) ( 6- 7)
Semaine 17 : ( 3- 5) ( 6- 8) ( 1- 9) ( 4- 7) ( 2-10)
Semaine 18 : ( 1-10) ( 2- 7) ( 3- 6) ( 5- 9) ( 4- 8)

Et ainsi de suite...
Semaine 19 : ( 7- 8) ( 9-10) ( 1- 2) ( 3- 4) ( 5- 6)
...

Si c'est le premier cas (chaque équipe utilise successivement toutes les paires (5) d'allées), alors il faudrait intégrer le problème des allées au programme, et je te laisserai ce soin...

Bon courage

[Jeffboj]

Merci beaucoup

Salut,

J'ai fait un petit programme pour résoudre ton problème (en partie, car je n'ai pas tenu compte des allées différentes).
Ce programme s'arrête à la première solution. La voici :

Bon courage

En ce qui concerne les allées, est-ce que tu veux que chaque équipe utilise successivement toutes les paires (5) d'allées (dans ce cas nécessairement toujours dans le même ordre), ou est-ce que tu voudrais simplement qu'une équipe ne joue pas deux fois de suite sur la même paire d'allées ? (Il était évident que chaque équipe devait rencontrer toutes les autres ; il l'est moins que chaque équipe doive utiliser toutes les paires d'allées !)

La deuxième solution est plus que satisfaisante!


je n'ai pas encore tout étudier mais il me semble que cela ressemble à ce que je voulais.
Je te tiens au courant et encore merci pour ton aide
Jeff