Esiste un algoritmo noto per pianificare i matchup dei tornei?

9

Mi chiedo solo se esiste già un algoritmo di pianificazione dei tornei che potrei usare o persino adattare leggermente.

Ecco i miei requisiti:

  • Un numero variabile di avversari appartenenti a un numero variabile di squadre / squadre deve essere associato a un avversario
  • Due avversari non possono provenire dallo stesso club
  • Se c'è un numero dispari di giocatori, 1 di essi viene selezionato casualmente per ottenere un bye

Saranno apprezzati tutti gli algoritmi relativi a questo tipo di set di requisiti.

EDIT: ho solo bisogno di eseguirlo al massimo una volta, creando matchup per il primo 'round' del torneo.

    
posta barfoon 03.11.2011 - 20:19
fonte

3 risposte

10

Come posso vedere, vuoi trovare corrispondenza massima nel grafico. Infatti i nodi sono giocatori, si collegano tra di loro se non sono nello stesso club, ora dovresti trovare il numero massimo di bordi che non hanno lo stesso vertice. Vedi Algoritmo di conversione massimo di Edmonds .

    
risposta data 03.11.2011 - 21:49
fonte
1

Dal mio breve tempo su Wikipedia venti secondi fa sembra che dovrai prima decidere una strategia di eliminazione. Vedi Wikipedia:

  1. Swiss-System
  2. Single-elimination_tournament
  3. Double-elimination_tournament

L'articolo sull'eliminazione singola descrive le tecniche di semina (l'algoritmo che stai cercando) in modo abbastanza generico e sembra utile, sebbene non sia abbastanza un algoritmo.

    
risposta data 03.11.2011 - 20:27
fonte
1

Rendendo questo mentre procedo, sembra che un algoritmo di corrispondenza iniziale sia piuttosto semplice:

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

Se una persona rimane, sarà una persona a caso, con un'eccezione. Se un club ha più membri di tutti i giocatori avversari messi insieme, gli avanzi saranno sempre da quel club. Realisticamente, questa è una situazione super-rara, e scegliere un buy da qualsiasi altro club lascerebbe ancora più persone rimanenti.

    
risposta data 03.11.2011 - 22:09
fonte

Leggi altre domande sui tag