Organizzazione torneo "particolare"
Ciao a tutti,
ho provato a cercare se ci fosse qualcosa di simile alla mia esigenza ma non l'ho trovato... spero di postare nella sezione corretta....
avrei bisogno di organizzare un torneo di un gioco da tavolo, organizzando partite da 6 persone a partita.
Nell'ipotesi di avere un numero di 15 iscritti (per ipotesi), vorrei trovare il modo di organizzare un numero di partite (il minimo possibile) soddisfacendo i seguenti requisiti:
- ogni giocatore deve incontrare almeno una volta tutti gli altri avversari
- ogni giocatore deve giocare lo stesso numero di partite
- minimizzare il numero di sfide "ripetute" o renderlo il più omogeneo possibile. Spiego: il giocatore A sfida B una sola volta, C una volta e D due volte. Quello che non voglio è ahe A sfidi B due volte, C una volta sola e D tre volte. Quindi può andare se il numero di sfide non è uguale tra tutti i partecipanti, ma al massimo vorrei che il numero di sfide differisse al massimo di 1.
Il massimo sarebbe riuscire a trovare un algoritmo che mi permetta di rendere parametrico il calcolo delle sfide, sia sul numero di partecipanti a partita (è 6, ma magari dovremmo passare a 5), sia sul numero di iscritti al torneo.
Qualcuno potrebbe aiutarmi a imbastire una soluzione? O ne esistono già?
Grazie!!
ho provato a cercare se ci fosse qualcosa di simile alla mia esigenza ma non l'ho trovato... spero di postare nella sezione corretta....
avrei bisogno di organizzare un torneo di un gioco da tavolo, organizzando partite da 6 persone a partita.
Nell'ipotesi di avere un numero di 15 iscritti (per ipotesi), vorrei trovare il modo di organizzare un numero di partite (il minimo possibile) soddisfacendo i seguenti requisiti:
- ogni giocatore deve incontrare almeno una volta tutti gli altri avversari
- ogni giocatore deve giocare lo stesso numero di partite
- minimizzare il numero di sfide "ripetute" o renderlo il più omogeneo possibile. Spiego: il giocatore A sfida B una sola volta, C una volta e D due volte. Quello che non voglio è ahe A sfidi B due volte, C una volta sola e D tre volte. Quindi può andare se il numero di sfide non è uguale tra tutti i partecipanti, ma al massimo vorrei che il numero di sfide differisse al massimo di 1.
Il massimo sarebbe riuscire a trovare un algoritmo che mi permetta di rendere parametrico il calcolo delle sfide, sia sul numero di partecipanti a partita (è 6, ma magari dovremmo passare a 5), sia sul numero di iscritti al torneo.
Qualcuno potrebbe aiutarmi a imbastire una soluzione? O ne esistono già?
Grazie!!
Risposte
Questo problema non mi è nuovo... mi sembra di aver letto un problema praticamente uguale qualche mese fa (forse anche un anno). Lo hai mai posto da qualche altra parte? Comunque penso che sia conveniente avere un numero di iscritti pari ad un multiplo dei giocatori (o modificare il numero di giocatori se puoi).
Comunque non è un problema semplice. Appena o tempo ci ragiono su.
Comunque non è un problema semplice. Appena o tempo ci ragiono su.
Ragionandoci un po' con degli amici avevamo concluso che dovrebbe essere un problema np-completo...
Per cui pensavo anch'io di ridurre il modello a casi più "semplici", come per esempio 36 iscritti e sfide da 6 persone a partita, o 25 iscritti con 5 x partita.
Così dovrebbe essere più semplice, ma volevo trovare una soluzione che non fosse una generazione via via di tutte le combinazioni scartando passo passo quelle sbagliate...
Solo che non riesco a trovare il modo giusto di procedere...
Se si trovasse una soluzione al problema "semplificato" sarebbe già sufficiente...
Grazie mille!!
Per cui pensavo anch'io di ridurre il modello a casi più "semplici", come per esempio 36 iscritti e sfide da 6 persone a partita, o 25 iscritti con 5 x partita.
Così dovrebbe essere più semplice, ma volevo trovare una soluzione che non fosse una generazione via via di tutte le combinazioni scartando passo passo quelle sbagliate...
Solo che non riesco a trovare il modo giusto di procedere...
Se si trovasse una soluzione al problema "semplificato" sarebbe già sufficiente...
Grazie mille!!
"Kurjak":su cosa basi tale affermazione? ma non corriamo...non si sa neppure se sia riducibile.
Ragionandoci un po' con degli amici avevamo concluso che dovrebbe essere un problema np-completo...
"vict85":
Questo problema non mi è nuovo... mi sembra di aver letto un problema praticamente uguale qualche mese fa (forse anche un anno). Lo hai mai posto da qualche altra parte?
era su scienzematematiche.it
Infatti mi risuonava familiare pure a me, difatti risposi dall'altra parte. Ricopio la mia risposta, che è una strada ancora percorribile secondo me.
Ciao,
certo che si può formulare con un algoritmo.
La programmazione matematica va bene, ma i vincoli non sono di facile descrizione, cioè non sono immediati. Direi che una versione naturale sarebbe ridurre il problema come di flusso massimo, con un grafo bibartito. Questo perchè:
- ogni giocatore deve incontrare almeno una volta tutti gli altri avversari
questo vincolo mi pare un po' complicato da redigere con programmazione matematica (che sarebbe programmazione intera, non lineare a mio avviso).
Perciò sai cos'è un problema di flusso?
"hamming_burst":
su cosa basi tale affermazione?
Come dicevo, era un'ipotesi venuta fuori una sera con degli amici... ma niente di più di una chiacchierata.
"hamming_burst":
era su scienzematematiche.it
Chiedo scusa, ma non ho più seguito l'altro forum... grazie per la pazienza!!
"hamming_burst":
Direi che una versione naturale sarebbe ridurre il problema come di flusso massimo, con un grafo bibartito. Questo perchè:
- ogni giocatore deve incontrare almeno una volta tutti gli altri avversari
questo vincolo mi pare un po' complicato da redigere con programmazione matematica (che sarebbe programmazione intera, non lineare a mio avviso).
Perciò sai cos'è un problema di flusso?
Ricordo qualcosa di un corso nel quale se ne parlava, ma niente di più...
E onestamente non saprei da dove cominciare per formalizzarlo in questa maniera...
Cioè: come mai un grafo bipartito? Cosa rappresenterebbero a questo punto i nodi? Immagino che i giocatori possano essere i nodi e le partite gli archi, ma a quel punto perché bipartito?
Scusa l'ignoranza... nel frattempo provo ad infarinarmi un po'...
ragionandoci meglio, lasciamo stare flusso massimo incasina più che aiutare. Non ricordo come lo avevo modellato un anno fa quindi, passiamo.
questi due vincoli sono in conflitto.
Non ci potrà mai essere differnza $>0$ se le partite giocate da ogni giocatore sono uguali. Quindi al massimo il secondo vincolo bisogna reiscriverlo tenendo conto del terzo quindi che il numero di partire per ogni giocatore sia differente tra gli altri di massimo $1$ partita.
altra cosa:
quale è la logica di tale fattore? far sì che ci sia un terzo classificato?
- ogni giocatore deve giocare lo stesso numero di partite
- minimizzare il numero di sfide "ripetute" o renderlo il più omogeneo possibile. Spiego: il giocatore A sfida B una sola volta, C una volta e D due volte. Quello che non voglio è ahe A sfidi B due volte, C una volta sola e D tre volte. Quindi può andare se il numero di sfide non è uguale tra tutti i partecipanti, ma al massimo vorrei che il numero di sfide differisse al massimo di 1.
questi due vincoli sono in conflitto.
Non ci potrà mai essere differnza $>0$ se le partite giocate da ogni giocatore sono uguali. Quindi al massimo il secondo vincolo bisogna reiscriverlo tenendo conto del terzo quindi che il numero di partire per ogni giocatore sia differente tra gli altri di massimo $1$ partita.
altra cosa:
minimizzare il numero di sfide "ripetute" o renderlo il più omogeneo possibile. Spiego: il giocatore A sfida B una sola volta, C una volta e D due volte. Quello che non voglio è ahe A sfidi B due volte, C una volta sola e D tre volte.
quale è la logica di tale fattore? far sì che ci sia un terzo classificato?
"hamming_burst":minimizzare il numero di sfide "ripetute" o renderlo il più omogeneo possibile. Spiego: il giocatore A sfida B una sola volta, C una volta e D due volte. Quello che non voglio è ahe A sfidi B due volte, C una volta sola e D tre volte.
quale è la logica di tale fattore? far sì che ci sia un terzo classificato?
Nell'organizzare il torneo, si pensava di fare sì che ognuno avesse se possibile le stesse occasioni contro tutti, quindi di avere il numero di partite contro ognuno degli avversari il più omogeneo possibile... se mi trovo al tavolo 5 volte con un giocatore fortissimo, e 1 sola volta contro una schiappa (oltre agli altri giocatori che fanno parte della partita, naturalmente), è più probabile che i miei risultati siano diversi rispetto a una situazione in cui gioco 5 volte con al tavolo una schiappa e una sola contro un pro.
Comunque, rispetto allo scorso anno pensavo di rilassare un po' i vincoli e pormi in un caso più "comodo", con n giocatori per partita e n^2 iscritti. In questo modo so che ognuno giocherà n+1 partite, né una di più né una di meno, e in questo caso posso garantire che si giochi 1 sola volta contro ognuno degli avversari.
Quale potrebbe essere l'approccio per identificare correttamente la composizione di ogni partita? Provando con 4 giocatori per tavolo (e 16 iscritti) la soluzione l'ho trovata per tentativi, ma non ho trovato uno "schema" che facilitasse l'estensione a numeri maggiori...
Penso anche io che sia il caso migliore.
Riguardo al metodo generale penso si potrebbe ragionare in questi termini.
Prendiamo un giocatore e segniamolo con \(\displaystyle g_{00} \). Segniamo inoltre gli altri giocatore come \(\displaystyle g_{ij} \) dove \(\displaystyle 1\le i\le n-1 \) e \(\displaystyle 0\le j\le n \).
Nella giocata \(\displaystyle j \), \(\displaystyle g_{00} \) giocherà contro la colonna \(\displaystyle g_{ij} \). Ogni altra partita viene fatta scegliendo un elemento per colonna tranne la colonna \(\displaystyle j \).
Indicativamente nella giocata \(\displaystyle 0 \), le partite saranno la colonna \(\displaystyle 0 \) con \(\displaystyle g_{00} \) e le righe \(\displaystyle i \) (senza il giocatore della colonna \(\displaystyle 0 \)).
Nella altre giocate, a parte la colonna \(\displaystyle j \) con \(\displaystyle g_{00} \), basterà partire con il giocatore \(\displaystyle g_{i0} \) e prendere il giocatore della colonna successiva (1, poi 2... ecc.) con l'indice \(\displaystyle i' \) minimo tale che i giocatore nella partita non abbia già giocato con lui e non sia già impegnato in una altra partita.
Mi sembra un metodo abbastanza semplice. Basta dare un indice a tutti i giocatori (eventualmente estraendo a sorte) e poi il tutto viene creato in modo automatico.
Riguardo al metodo generale penso si potrebbe ragionare in questi termini.
Prendiamo un giocatore e segniamolo con \(\displaystyle g_{00} \). Segniamo inoltre gli altri giocatore come \(\displaystyle g_{ij} \) dove \(\displaystyle 1\le i\le n-1 \) e \(\displaystyle 0\le j\le n \).
Nella giocata \(\displaystyle j \), \(\displaystyle g_{00} \) giocherà contro la colonna \(\displaystyle g_{ij} \). Ogni altra partita viene fatta scegliendo un elemento per colonna tranne la colonna \(\displaystyle j \).
Indicativamente nella giocata \(\displaystyle 0 \), le partite saranno la colonna \(\displaystyle 0 \) con \(\displaystyle g_{00} \) e le righe \(\displaystyle i \) (senza il giocatore della colonna \(\displaystyle 0 \)).
Nella altre giocate, a parte la colonna \(\displaystyle j \) con \(\displaystyle g_{00} \), basterà partire con il giocatore \(\displaystyle g_{i0} \) e prendere il giocatore della colonna successiva (1, poi 2... ecc.) con l'indice \(\displaystyle i' \) minimo tale che i giocatore nella partita non abbia già giocato con lui e non sia già impegnato in una altra partita.
Mi sembra un metodo abbastanza semplice. Basta dare un indice a tutti i giocatori (eventualmente estraendo a sorte) e poi il tutto viene creato in modo automatico.
Prendiamo gli \(n^2\) giocatori e posizioniamoli all'interno di un quadrato \(n \times n\). Ad ogni giocatore associeremo quindi due indici \( (i, j) \). A questo punto facciamo \(n\) turni con \(n\) partite per turno e \(n\) giocatori per partita nel seguente modo (tutti gli indici suppongo partino da zero).
1. Nel primo turno facciamo scontrare tra di loro le righe.
2. Nell'\(m-\)esimo turno (escluso il primo quindi) scegliamo come \(k-\)esimo giocatore della \(i\)-esima partita quelli di indici \( ( i + (m \times k) \pmod n , k ). \)
Se pensiamo quindi ai giocatori messi su di una matrice stiamo percorrendo alcune tra le "diagonali" possibili. Tutti i punti che sono allineati lungo una qualche direzione modulo \(n\).
EDIT: Ad una più attenta analisi ho notato che funziona solo con \(n\) primo..
1. Nel primo turno facciamo scontrare tra di loro le righe.
2. Nell'\(m-\)esimo turno (escluso il primo quindi) scegliamo come \(k-\)esimo giocatore della \(i\)-esima partita quelli di indici \( ( i + (m \times k) \pmod n , k ). \)
Se pensiamo quindi ai giocatori messi su di una matrice stiamo percorrendo alcune tra le "diagonali" possibili. Tutti i punti che sono allineati lungo una qualche direzione modulo \(n\).
EDIT: Ad una più attenta analisi ho notato che funziona solo con \(n\) primo..
Mi sono accorto che così come lo scritto non funziona. Ci ragiono sopra e lo scrivo per bene.
Ho provato a implementare l'algoritmo suggerito da apatriarca... funziona perfettamente!!
Grazie mille!!
Grazie a tutti per l'aiuto!!
Grazie mille!!
Grazie a tutti per l'aiuto!!
Scusate se riesumo questo thread, ma dopo aver usato con profitto l'algoritmo per tornei da 25 persone mi sono accorto che per 36 non funzionava, ed infatti ho trovato
... qualcuno ha qualche nuova idea? hamming_burst parlava di qualche idea legata ai problemi di flusso... pur avendogli dato un'occhiata, non riesco a capire come modellizzare il problema...
"apatriarca":
EDIT: Ad una più attenta analisi ho notato che funziona solo con \(n\) primo..
... qualcuno ha qualche nuova idea? hamming_burst parlava di qualche idea legata ai problemi di flusso... pur avendogli dato un'occhiata, non riesco a capire come modellizzare il problema...
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo