Existe-t-il un algorithme connu pour planifier les matchs de tournoi?

10

Je me demande simplement s'il existe déjà un algorithme de programmation de tournois que je pourrais utiliser ou même adapter légèrement.

Voici mes exigences:

  • Un nombre variable d'adversaires appartenant à un nombre variable d'équipes / clubs chacun doit être associé à un adversaire
  • Deux adversaires ne peuvent pas appartenir au même club
  • S'il y a un nombre impair de joueurs, 1 d'entre eux est sélectionné au hasard pour obtenir un bye

Tout algorithme lié à ce type d'ensemble d'exigences serait apprécié.

EDIT: J'ai seulement besoin de l'exécuter au maximum une fois, créant des matchs pour le premier «round» du tournoi.

algorithms barfoon
la source
Vous voudrez peut-être examiner la correspondance maximale .
svick

Réponses:

1

Depuis mon bref passage sur Wikipédia il y a vingt secondes, il semble que vous devrez d'abord décider d'une stratégie d'élimination. Voir Wikipedia:

  1. Swiss-System
  2. Tournoi à élimination unique
  3. Tournoi de double élimination

L'article à élimination simple décrit les techniques d'amorçage (l'algorithme que vous recherchez) de manière assez générique et il semble utile, mais pas tout à fait un algorithme.

Chris Pfohl
la source
Je préfère le Suisse, qui donne un classement moyen contrairement à la double / simple élimination, et trouve les meilleurs joueurs N dans le même nombre de tours qu'un tournoi à élimination N.
Mooing Duck
1

En inventant au fur et à mesure, il semble qu'un algorithme de correspondance initial soit assez simple:

While two or more clubs have at least one member not paired  
    select the two clubs with the most unpaired members
    select a random unpaired member from each club
    pair those members

S'il reste une personne, ce sera une personne au hasard, à une exception près. Si un club a plus de membres que tous les joueurs adverses réunis, les restes proviendront toujours de ce club. En réalité, c'est une situation super rare, et choisir un achat dans n'importe quel autre club laisserait encore plus de gens.

Mooing Duck
la source