J'ai un problème d'algorithme concernant la planification des équipes en rotation aussi équitablement que possible

Question

J'ai un projet pour l'école où je dois trouver un algorithme pour programmer 4 équipes pour jouer au volleyball sur un terrain, de sorte que chaque équipe devient aussi proche de la même quantité de temps que possible pour jouer.

Si vous avez toujours les gagnants qui restent et qui font le tour du perdant, alors l'équipe classée 4ème ne jouera jamais et l'équipe # 1 le fera toujours. L'objectif est que tout le monde joue le même temps. La réponse la plus simple est l'équipe de jeu 1 de l'équipe 1, puis l'équipe 3 joue l'équipe 4 et continue de changer, mais l'équipe 1 ne peut jamais jouer l'équipe 3 ou 4 et ainsi de suite. Donc, j'essaie de trouver un algorithme qui permettra à tout le monde de jouer à tout le monde à un moment ou à un autre sans avoir une équipe à s'asseoir beaucoup plus que n'importe quelle autre équipe.

Suggestions?

Answer 1

bien vous devrait jouer 1-2 3-4, 1-3 2-4, 1-4 2-3 et recommencer à zéro.

Answer 2

faire semblant que c'est une petite ligue de sport, et répéter les « saisons » ... (dans la plupart des ligues sportives en Europe, toutes les équipes jouent contre toutes les autres équipes deux ou trois fois au cours d'une saison)

Answer 3

S'il y a N équipes et que vous voulez que toutes les paires soient jouées une fois, alors il y a "N choisissez 2" = N*(N-1)/2 jeux que vous devez exécuter. Pour les énumérer, placez les équipes dans une liste ordonnée et demandez à la première équipe de jouer toutes les deux équipes, puis demandez à la deuxième équipe de jouer toutes les équipes qui se trouvent en dessous dans la liste, et ainsi de suite. Si vous voulez répartir les parties de façon à ce que les équipes aient des intervalles de repos similaires entre les parties, voyez Knuth.

Answer 4

Que diriez-vous ceci: Faire une table de hachage H de taille NC2, dans ce cas, 6. Il ressemble à:

H[12] = 0 
H[13] = 0 
H[14] = 0 
H[23] = 0 
H[24] = 0 
H[34] = 0 

Je suppose que ce serait trivial pour générer les clés.

Maintenant, pour planifier un jeu, parcourez le hash et sélectionnez la clé avec la valeur la plus basse (une passe). Les équipes désignées par la touche jouent au jeu et vous incrémentez la valeur de un.

EDIT: Pour ajouter une autre contrainte qu'aucune équipe ne devrait attendre trop longtemps, faire une autre hachage W:

W[1] = 0 
W[2] = 0 
W[3] = 0 
W[4] = 0 

Après chaque jeu augmenter la valeur de W pour l'équipe qui n'a pas joué, par un.

Maintenant, lorsque vous prenez l'équipe la moins jouée s'il y a plus d'un combo d'équipe avec un score de jeu faible, prenez l'aide de ce hash pour déterminer quelle équipe doit jouer ensuite.

Answer 5

Vérifiez l'entrée de la wikipedia sur round robin scheduling.

Answer 6

Les exigences pour l'ÉQUILIBRÉ POULE algorithme, pour la programmation du championnat de l'équipe se trouvent ici: Constellation Algorithm - Balanced Round Robin Les exigences de l'algorithme peuvent être définis par ces quatre contraintes:

1) Tous contre tous Chaque L'équipe doit se rencontrer exactement une fois, et une fois seulement, les autres équipes de la division/ligue. Si la division est composée de n équipes, le championnat se déroule dans les n-1 tours.

2) Alternances Règle HOME/AWAY La séquence d'alternances HOME/AWAY pour chaque équipe de la ligue de division doit être conservée si possible. Pour toute équipe dans la ligue de division au plus une fois dans la séquence des matchs consécutifs HAHA, se produit la PAUSE du rythme, c'est-à-dire HH ou AA dans les deux tours consécutifs.

3) La règle du dernier numéro d'emplacement L'équipe ayant le numéro d'emplacement le plus élevé doit toujours être positionnée dans la dernière rangée de la grille. Pour chaque itération suivante, le numéro de créneau le plus élevé alterne les positions gauche et droite; colonne de gauche (home) et droite (away). Le système utilisé pour composer le calendrier de la ligue est "circuit anti-horaire". Dans la construction de matches dans un tour du championnat, une division avec un nombre pair d'équipes. Si dans une division est présent un nombre impair d'équipes, il sera inséré une équipe BYE/Dummy dans le numéro d'emplacement le plus élevé de la grille/anneau. 4) HH et AA non terminal et non initial La cadence HH ou AA ne doit jamais se produire au début ou à la fin de la partie des matches pour une équipe de la division.