Algorithme de planification pour un tournoi à la ronde?
J'ai récemment fait l'étude de trucs et de rencontre avec Donald Knuth. Mais je n'ai pas trouvé le bon algorithme pour mon problème.
Le Problème Nous avons une ligue avec n joueurs. chaque semaine, ils ont une correspondance avec une autre. en n-1 semaines chaque équipe a combattu les uns contre les autres. il y a des n/2 correspond à un jour. mais une équipe ne peut combattre une fois par semaine. si nous générons un (n/k) la combinaison d'obtenir toutes les combinaisons de... (en supposant que k = 2), mais j'ai besoin de les ramener dans le bon ordre.
Ma première suggestion était... pas le meilleur. je viens de faire un tableau, et ensuite, laissez l'ordinateur, essayez si il trouve le bon chemin. si non, revenir au début, mélangez l'ensemble et le faire à nouveau, eh bien, j'ai programmé en PHP (n=8) et de ce sort fonctionne, mais prendre beaucoup de temps, et pour n=16, il me donne un délai d'attente.
J'ai donc pensé que si peut-être nous trouver un algorithme, ou tout le monde le sait un livre qui traite ce problème.
Et voici mon code:
http://pastebin.com/Rfm4TquY
source d'informationauteur Philipp Spiess
Vous devez vous connecter pour publier un commentaire.
L'algorithme classique fonctionne comme ceci:
Nombre les équipes 1..n. (Ici, je vais prendre n=8.)
Écrire toutes les équipes en deux lignes.
Les colonnes indiquent les équipes qui joueront lors de ce tour (1 vs 8, 2 vs 7, ...).
Maintenant, gardez-en 1 fixe, mais faire tourner toutes les autres équipes. En semaine 2, vous obtenez
et dans la semaine 3, vous obtenez
Cela continue jusqu'à la semaine n-1, dans ce cas,
Si n est impair, faire la même chose, mais ajouter un mannequin de l'équipe. Celui qui est en correspondance avec le mannequin, l'équipe reçoit un au revoir cette semaine.