Algoritmo per un torneo a round robin con una quantità specifica di partite per round

Question

Algoritmo per un torneo a round robin con una quantità specifica di partite per round

#1 da (1 voti)

1

Attualmente sto cercando di creare un sistema per un torneo specifico ma non riesco a capire come generare la tabella delle partite.

Ho un torneo con <T> team. Ogni squadra deve giocare una contro l'altra esattamente una volta.

La posizione del torneo ha% campi di<M> che possono essere giocati allo stesso tempo (quindi limitare la quantità di partite per round a <M> ).

Una delle soluzioni che conosco è un torneo round robin

Le due soluzioni su wikipedia mostrano tuttavia solo soluzioni per <T> / 2 corrisponde a / campi che non è quello che voglio.

Voglio che la quantità di partite giocate nello stesso momento sia variabile in base all'input (posizione del torneo).

Obvioulsy ci possono essere round in cui squadre specifiche non stanno giocando. Ma l'algoritmo dovrebbe sempre restituire il minor numero possibile di colpi.

Qual è il modo migliore per risolvere questo problema o esistono algoritmi efficienti per questo?

Per chiarire: ogni partita / round richiede lo stesso ammontare di tempo e ogni partita / round inizia allo stesso tempo.

Modifica: ecco un esempio:

Ho 6 squadre:

Quando applichiamo l'algoritmo round robin, genererebbe una tabella come questa:

         Field/Match 1 Field/Match 2 Field/Match 3
Round 1: 1 vs 6     2 vs 5     3 vs 4
Round 2: 1 vs 5     6 vs 4     2 vs 3
Round 3: 1 vs 4     5 vs 3     6 vs 2
Round 4: 1 vs 3     4 vs 2     5 vs 6
Round 5: 1 vs 2     3 vs 6     4 vs 5

Ora sono in un torneo con solo 2 campi disponibili, quindi solo 2 partite possono essere giocate contemporaneamente.

Il modo più semplice per modificare questa tabella è aggiungere tutti i campi che non esistono alla fine del torneo:

         Match 1    Match 2
Round 1: 1 vs 6     2 vs 5
Round 2: 1 vs 5     6 vs 4
Round 3: 1 vs 4     5 vs 3
Round 4: 1 vs 3     4 vs 2
Round 5: 1 vs 2     3 vs 6
Round 6: 3 vs 4
Round 7: 2 vs 3
Round 8: 6 vs 2
Round 9: 5 vs 6
Round 10: 4 vs 5

Questo tuttavia non sarebbe ottimale dal momento che il campo 2 non verrebbe utilizzato affatto.

Ho bisogno di un algoritmo che generi una buona soluzione con l'ottimizzazione di tutti i campi disponibili.

Esempio di una tabella con campi utilizzati in modo ottimale:

         Match 1    Match 2
Round 1: 1 vs 6     2 vs 5
Round 2: 1 vs 5     6 vs 4
Round 3: 1 vs 4     5 vs 3
Round 4: 1 vs 3     4 vs 2
Round 5: 1 vs 2     3 vs 6
Round 6: 3 vs 4     6 vs 2
Round 7: 2 vs 3     5 vs 6
Round 8: 4 vs 5

E non so come potrei convertirlo in un algoritmo che funziona con qualsiasi quantità di partite / campi per round.

algorithms

posta Lyze 04.02.2018 - 18:54

fonte

1 risposta

Leggi altre domande sui tag algorithms

Servizio Windows con autenticazione, è necessaria un'interfaccia utente Come modellare per un'API RESTful che funziona con diversi fornitori di servizi

score 1 · Answer 1

Sei sulla strada giusta. Penso che l'uso di una coda dovrebbe aiutarti. Farei qualcosa del genere:

List<Team> allTeams = getAllTeams(); // Returns the list of all teams
List<Match> allMatches = getAllMatches(allTeams); // Generate all combos of teams - should be n^2 matches
List<Field> allFields = getAllFields(); // Return the list of all possible fields
Queue<Match> remainingMatches(allMatches); // A queue of all the remaining matches - starts with all of them
List<Match, Field> matchesToBePlayed; // initially empty
while (remaininMatches.size() > 0)
{
    Field nextField = getNextAvailableField(allFields);
    if (nextField == NULL)
    {
        // Play all the matches we have
        playMatches(matchesToBePlayed);
        matchesToBePlayed.clear(); // reset it when they've been played
    }
    else
    {
        Match nextMatch = remainingMatches.front();
        remainingMatches.pop_front();
        matchesToBePlayed.addMatch(nextField, nextMatch);
    }
}

Quindi devi semplicemente mettere in coda tutte le partite disponibili. Quindi ti siedi in un loop e ottieni il prossimo campo disponibile, e la prossima corrispondenza disponibile e assegna la corrispondenza al campo. Quando sei fuori dai campi, puoi dormire fino alla fine di una partita. Dal momento che finiscono tutti allo stesso tempo, non ti manca nulla. Quando termina una partita, diventa disponibile un campo.

Questo presuppone alcune cose:

La lista allMatches è ordinata in modo da non finire mai con una squadra in 2 partite allo stesso tempo. Ci sono altri modi in cui puoi farlo, come controllare la variabile nextMatch per assicurarti che nessuna delle squadre coinvolte stia già giocando.
L'oggetto Field ha una bandiera che dice che è in uso e getNextAvailableField() cammina nella lista dei campi ed estrae il successivo che non ha il flag inUse impostato. O forse l'elenco di tutti i campi contiene internamente 2 elenchi in modo da non doverli camminare.