Gibt es einen bekannten Algorithmus zum Planen von Turniermatchups?

10

Ich frage mich nur, ob es bereits einen Turnierplanungsalgorithmus gibt, den ich verwenden oder sogar leicht anpassen könnte.

Hier sind meine Anforderungen:

  • Eine variable Anzahl von Gegnern, die zu einer variablen Anzahl von Teams / Vereinen gehören, muss mit einem Gegner gepaart werden
  • Zwei Gegner können nicht aus demselben Verein stammen
  • Wenn es eine ungerade Anzahl von Spielern gibt, wird 1 von ihnen zufällig ausgewählt, um ein Tschüss zu erhalten

Alle Algorithmen, die sich auf diese Art von Anforderungssatz beziehen, wären willkommen.

BEARBEITEN: Ich muss dies nur maximal einmal ausführen und Matchups für die erste "Runde" des Turniers erstellen.

algorithms Barfoon
quelle
Vielleicht möchten Sie die maximale Übereinstimmung untersuchen .
Svick

Antworten:

10

Wie ich sehen kann, möchten Sie die maximale Übereinstimmung in der Grafik finden. Tatsächlich sind Knoten Spieler, sie sind miteinander verbunden, wenn sie nicht im selben Verein sind. Jetzt sollten Sie die maximale Anzahl von Kanten finden, die nicht denselben Scheitelpunkt haben. Siehe Edmonds Maximum Matching-Algorithmus .

Saeed
quelle
1

Aus meiner kurzen Zeit bei Wikipedia vor zwanzig Sekunden geht hervor, dass Sie sich zunächst für eine Eliminierungsstrategie entscheiden müssen. Siehe Wikipedia:

  1. Schweizer System
  2. Single-Elimination_Turnament
  3. Doppelausscheidungsturnier

Der Artikel zur Einzeleliminierung beschrieb Seeding-Techniken (den Algorithmus, nach dem Sie suchen) ziemlich allgemein und sah hilfreich aus, obwohl er kein richtiger Algorithmus ist.

Chris Pfohl
quelle
Ich bevorzuge Swiss, die im Gegensatz zur Doppel- / Einzelausscheidung eine mittlere Platzierung erreicht und die besten N-Spieler in der gleichen Anzahl von Runden wie ein N-Ausscheidungsturnier findet.
Mooing Duck
1

Wenn ich das nachdenke, scheint es, als sei ein anfänglicher Matching-Algorithmus ganz einfach:

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

Wenn eine Person übrig bleibt, handelt es sich mit einer Ausnahme um eine zufällige Person. Wenn ein Verein mehr Mitglieder hat als alle gegnerischen Spieler zusammen, stammen die Reste immer von diesem Verein. Realistisch gesehen ist das eine sehr seltene Situation, und wenn Sie einen Kauf bei einem anderen Verein tätigen, bleiben noch mehr Menschen übrig.

Mooing Duck
quelle