[ALGORITMI] Quando il BMX da i numeri ...
Buongiorno a tutti, mi chiamo Bruno e non sono né un informatico, ne’ tantomeno un matematico, mi occupo di fotografia e BMX.
Mi rivolgo a voi per un problema che soverchia le mie scarse attitudini in quello che credo sia invece il vostro campo.
Con un gruppo di volontari sto lavorando ad un nuovo software per la gestione di gare di BMX Racing, una disciplina che si pratica con bici bmx (ovviamente) su piste in terra battuta e che ricorda il motocross. Il mio apporto riguarda la parte a monte del programma cioè la conoscenza del funzionamento di un gara e delle norme sportive a cui bisogna attenersi. La persona che sta sviluppando il programma utilizza una piattaforma LAMP (Linux, Apache, My Sequel e PHP).
Stiamo cercando un algoritmo che risolva questo problema:
Dato un gruppo di 32 piloti (P1 - P32), bisogna farli gareggiare 5 volte (manche) divisi in 4 sottogruppi (batterie) da 8 piloti e in ognuna di queste manche le batterie devono essere composte rimescolando i 32 piloti. In ogni manche ai piloti viene assegnata una corsia di partenza numerata da 1a 8. Essendo la N° 1 la migliore e la N° 8 la peggiore, è necessario che le corsie di partenza siano attribuite in modo equilibrato cioè che nel complesso delle 5 manche disputate non ci siano piloti che abbiano avuto un vantaggio troppo evidente sugli altri. [Nota: un pilota che partisse sempre in corsia 1 (1,1,1,1,1 somma 5) sarebbe estremamente avvantaggiato su quello che si trovasse a partire sempre in 8 (8,8,8,8,8, somma 40), il valore medio della somma delle posizioni di partenza è 22,5 quindi, non esistendo la “mezza corsia”, in una griglia perfettamente bilanciata ci saranno 4 piloti che avranno la somma delle posizioni di partenza pari a 22 e 4 piloti con somma 23. La griglia bilanciata è già stabilita nei regolamenti per le gare in cui le batterie non cambiano da una manche all’altra, quando cioè sono sempre gli stessi 8 piloti ad affrontarsi nelle 5 manche. Non esiste , ed è proprio quello che stiamo cercando di realizzare, una griglia bilanciata quando i gruppi di 8 piloti devono essere riformati, rimescolandoli ad ogni manche]
Un ulteriore fattore da tenere presente è che i piloti da P1 a P8 sono le teste di serie e quindi, se possibile, è necessario minimizzare gli scontri diretti nel corso delle 5 manche.
Ringrazio anticipatamente chi avesse il tempo di prendere in considerazione questo problema, anche solo per dirmi che non esiste una soluzione . Sarebbe già un grosso aiuto, che mi/ci metterebbe l’animo in pace e giustificherebbe il ricorso ad un rimescolamento casuale e di conseguenza non imparziale.
Bruno
Info aggiuntive sul Bmx.
Ogni fase della gara consiste in un singolo giro di pista. La gara è ad eliminazione e si suddivide in due fasi: manche di qualifica (manches) e turni di finale (ottavi, quarti semi e finali). I piloti si affrontano nelle manche di qualifica in gruppi (detti batterie ) in un numero variabile da 5 a 8 piloti. Le manche di qualifica sono 5, al termine di queste 5 prove si qualificano i 4 piloti con il miglior punteggio così determinato: ad ogni prova viene assegnato 1 punto al primo, 2 al secondo … 8 all’ottavo. In ogni batteria i quattro piloti con il punteggio finale più basso passano ai turni successivi (turni di finale). I turni di finale sono ad eliminazione diretta: i primi quattro avanzano al turno successivo, gli altri quattro sono eliminati.
I piloti corrono suddivisi in categorie di età. Il numero di batterie per ogni categoria e il numero di piloti che compongono dette batterie dipendono dal numero totale di piloti iscritti nella categoria stessa e sono determinati da una tabella emessa dalla Federazione Ciclistica Internazionale (UCI). L’esempio più scontato: 16 iscritti = 2 batterie da 8 piloti. Meno immediato nel caso di 40 iscritti: 8 batterie da 5 piloti, non 5 batterie da 8 piloti. Questo perché un numero dispari di batterie non consente poi la composizione dei turni successivi in gruppi di 8 che sono formati dalle coppie di 4 qualificati per ogni batteria. Dalle 8 batterie da 5 si otterranno 4 batterie da 8 piloti per i quarti di finale, dai quarti si passa alle due semifinali e quindi alla finale, Come detto, il numero massimo di piloti per ogni batteria è 8. Questi 8 concorrenti si dispongono al cancello di partenza su 8 corsie, dove la nr. 1 è interna rispetto alla prima curva, quindi la migliore, la nr. 8 è la corsia esterna quindi il pilota che parte da questa posizione risulta svantaggiato. Per bilanciare questa situazione, esiste una tabella che determina la corsia che un pilota deve occupare in ognuna delle 5 prove, utilizzando tale tabella alla fine delle 5 prove ogni pilota ha avuto nel complesso posizioni di partenza equivalenti, una piccola differenza c’è, ma è trascurabile.
Sequenza posizioni sulla griglia di partenza
pilota manche 1 manche 2 manche 3 manche 4 manche 5
1 P1 8 2 3 4 5
2 P2 7 6 1 5 4
3 P3 6 3 5 7 2
4 P4 5 1 7 6 3
5 P5 4 8 2 3 6
6 P6 3 5 6 1 8
7 P7 2 7 4 8 1
8 P8 1 4 8 2 7
Chiedo scusa se vi ho annoiati e ho invaso il forum con questo post kilometrico, la questione per noi è importante e purtroppo non abbiamo i fondi per finanziare un progetto esterno e quindi dobbiamo arrangiarci con le risorse interne che per quello che mi riguarda, informaticamente parlando sono praticamente un barbone …
Se invece a qualcuno è venuta la curiosità di vedere di cosa si tratta, può togliersela visitando il mio sito d’informazione :http://www.bmxr.it/[/url]
Mi rivolgo a voi per un problema che soverchia le mie scarse attitudini in quello che credo sia invece il vostro campo.
Con un gruppo di volontari sto lavorando ad un nuovo software per la gestione di gare di BMX Racing, una disciplina che si pratica con bici bmx (ovviamente) su piste in terra battuta e che ricorda il motocross. Il mio apporto riguarda la parte a monte del programma cioè la conoscenza del funzionamento di un gara e delle norme sportive a cui bisogna attenersi. La persona che sta sviluppando il programma utilizza una piattaforma LAMP (Linux, Apache, My Sequel e PHP).
Stiamo cercando un algoritmo che risolva questo problema:
Dato un gruppo di 32 piloti (P1 - P32), bisogna farli gareggiare 5 volte (manche) divisi in 4 sottogruppi (batterie) da 8 piloti e in ognuna di queste manche le batterie devono essere composte rimescolando i 32 piloti. In ogni manche ai piloti viene assegnata una corsia di partenza numerata da 1a 8. Essendo la N° 1 la migliore e la N° 8 la peggiore, è necessario che le corsie di partenza siano attribuite in modo equilibrato cioè che nel complesso delle 5 manche disputate non ci siano piloti che abbiano avuto un vantaggio troppo evidente sugli altri. [Nota: un pilota che partisse sempre in corsia 1 (1,1,1,1,1 somma 5) sarebbe estremamente avvantaggiato su quello che si trovasse a partire sempre in 8 (8,8,8,8,8, somma 40), il valore medio della somma delle posizioni di partenza è 22,5 quindi, non esistendo la “mezza corsia”, in una griglia perfettamente bilanciata ci saranno 4 piloti che avranno la somma delle posizioni di partenza pari a 22 e 4 piloti con somma 23. La griglia bilanciata è già stabilita nei regolamenti per le gare in cui le batterie non cambiano da una manche all’altra, quando cioè sono sempre gli stessi 8 piloti ad affrontarsi nelle 5 manche. Non esiste , ed è proprio quello che stiamo cercando di realizzare, una griglia bilanciata quando i gruppi di 8 piloti devono essere riformati, rimescolandoli ad ogni manche]
Un ulteriore fattore da tenere presente è che i piloti da P1 a P8 sono le teste di serie e quindi, se possibile, è necessario minimizzare gli scontri diretti nel corso delle 5 manche.
Ringrazio anticipatamente chi avesse il tempo di prendere in considerazione questo problema, anche solo per dirmi che non esiste una soluzione . Sarebbe già un grosso aiuto, che mi/ci metterebbe l’animo in pace e giustificherebbe il ricorso ad un rimescolamento casuale e di conseguenza non imparziale.
Bruno
Info aggiuntive sul Bmx.
Ogni fase della gara consiste in un singolo giro di pista. La gara è ad eliminazione e si suddivide in due fasi: manche di qualifica (manches) e turni di finale (ottavi, quarti semi e finali). I piloti si affrontano nelle manche di qualifica in gruppi (detti batterie ) in un numero variabile da 5 a 8 piloti. Le manche di qualifica sono 5, al termine di queste 5 prove si qualificano i 4 piloti con il miglior punteggio così determinato: ad ogni prova viene assegnato 1 punto al primo, 2 al secondo … 8 all’ottavo. In ogni batteria i quattro piloti con il punteggio finale più basso passano ai turni successivi (turni di finale). I turni di finale sono ad eliminazione diretta: i primi quattro avanzano al turno successivo, gli altri quattro sono eliminati.
I piloti corrono suddivisi in categorie di età. Il numero di batterie per ogni categoria e il numero di piloti che compongono dette batterie dipendono dal numero totale di piloti iscritti nella categoria stessa e sono determinati da una tabella emessa dalla Federazione Ciclistica Internazionale (UCI). L’esempio più scontato: 16 iscritti = 2 batterie da 8 piloti. Meno immediato nel caso di 40 iscritti: 8 batterie da 5 piloti, non 5 batterie da 8 piloti. Questo perché un numero dispari di batterie non consente poi la composizione dei turni successivi in gruppi di 8 che sono formati dalle coppie di 4 qualificati per ogni batteria. Dalle 8 batterie da 5 si otterranno 4 batterie da 8 piloti per i quarti di finale, dai quarti si passa alle due semifinali e quindi alla finale, Come detto, il numero massimo di piloti per ogni batteria è 8. Questi 8 concorrenti si dispongono al cancello di partenza su 8 corsie, dove la nr. 1 è interna rispetto alla prima curva, quindi la migliore, la nr. 8 è la corsia esterna quindi il pilota che parte da questa posizione risulta svantaggiato. Per bilanciare questa situazione, esiste una tabella che determina la corsia che un pilota deve occupare in ognuna delle 5 prove, utilizzando tale tabella alla fine delle 5 prove ogni pilota ha avuto nel complesso posizioni di partenza equivalenti, una piccola differenza c’è, ma è trascurabile.
Sequenza posizioni sulla griglia di partenza
pilota manche 1 manche 2 manche 3 manche 4 manche 5
1 P1 8 2 3 4 5
2 P2 7 6 1 5 4
3 P3 6 3 5 7 2
4 P4 5 1 7 6 3
5 P5 4 8 2 3 6
6 P6 3 5 6 1 8
7 P7 2 7 4 8 1
8 P8 1 4 8 2 7
Chiedo scusa se vi ho annoiati e ho invaso il forum con questo post kilometrico, la questione per noi è importante e purtroppo non abbiamo i fondi per finanziare un progetto esterno e quindi dobbiamo arrangiarci con le risorse interne che per quello che mi riguarda, informaticamente parlando sono praticamente un barbone …
Se invece a qualcuno è venuta la curiosità di vedere di cosa si tratta, può togliersela visitando il mio sito d’informazione :http://www.bmxr.it/[/url]
Risposte
In che modo i gruppi delle manche verrebbero riformati? C'è una qualche regola da seguire? La tabella deve essere generata durante la gara o al di fuori di essa? È necessario trovare una soluzione o più di una?
Formazione delle batterie
Da un lato abbiamo l’elenco dei concorrenti (P1 -P32) , dall’altro le 4 batterie (b1-b4) e le 5 manche (m1-m5) da formare.
In un formato di gara normale i 32 concorrenti vengono distribuiti a gruppi di 8 nelle 4 batterie minimizzando gli scontri diretti delle teste di serie (da P1 a P8, quindi al massimo 2 teste di serie per batteria, evitando di mettere insieme la 1 con la 2 ecc.) questi gruppi restano invariati e portano a termine le 5 manche. In ogni manche i piloti cambiano la corsia di partenza (1-8) seguendo la tabella che equilibra le posizioni. P.es. il pilota P1 , partirà dalle corsie 8-2-3-4-5; il P2 da 7-6-2-1-5-4, P3 da 6-3-5-7-2 e via dicendo. Riepilogando, abbiamo 4 batterie di 8 piloti ciascuna, gli 8 piloti di ogni batteria si scontrano per 5 manche. Al termine delle manche si redige una classifica per determinare i migliori 4 di ogni batteria, coloro cioè che si qualificano per le fasi successive (turni di finale).
Questo tipo di gara è già gestito dall’attuale programma. Un programma che abbiamo avuto per gentile concessione dalla federazione francese ma che più di un programmatore da noi interpellato ha dichiarato estremamente difficile da modificare.
Il nuovo formato di gara che si vorrebbe mettere in atto, introduce il rimescolamento dei piloti, vale a dire che i gruppi di 8 piloti che compogono le batterie non restano fissi per tutte le 5 manche ma variano ad ogni manche. Quindi un pilota che prima si scontrava per 5 volte con i medesimi 7 avversari, ora si troverà in ogni manche un gruppo di 7 avversari diverso. Nel fare questo però perdiamo l’aggancio con la tabella di compensazione delle posizioni di partenza, non riusciamo più a gestire le posizioni di partenza in modo che ci sia equilibrio tra i piloti. Questo mi sembra lo scoglio maggiore.
Rispondo alle altre tue domande: nel riformaare le batterie non c’è una regola da seguire se non quella di evitare troppi confronti diretti tra le teste di serie e cercare di equilibrare le posizioni di partenza. Le batterie e le 5 manche devono essere determinate e rese note prima dell’inizio della gara, una soluzione è sufficiente (se ho capito il senso della domanda …)
Da un lato abbiamo l’elenco dei concorrenti (P1 -P32) , dall’altro le 4 batterie (b1-b4) e le 5 manche (m1-m5) da formare.
In un formato di gara normale i 32 concorrenti vengono distribuiti a gruppi di 8 nelle 4 batterie minimizzando gli scontri diretti delle teste di serie (da P1 a P8, quindi al massimo 2 teste di serie per batteria, evitando di mettere insieme la 1 con la 2 ecc.) questi gruppi restano invariati e portano a termine le 5 manche. In ogni manche i piloti cambiano la corsia di partenza (1-8) seguendo la tabella che equilibra le posizioni. P.es. il pilota P1 , partirà dalle corsie 8-2-3-4-5; il P2 da 7-6-2-1-5-4, P3 da 6-3-5-7-2 e via dicendo. Riepilogando, abbiamo 4 batterie di 8 piloti ciascuna, gli 8 piloti di ogni batteria si scontrano per 5 manche. Al termine delle manche si redige una classifica per determinare i migliori 4 di ogni batteria, coloro cioè che si qualificano per le fasi successive (turni di finale).
Questo tipo di gara è già gestito dall’attuale programma. Un programma che abbiamo avuto per gentile concessione dalla federazione francese ma che più di un programmatore da noi interpellato ha dichiarato estremamente difficile da modificare.
Il nuovo formato di gara che si vorrebbe mettere in atto, introduce il rimescolamento dei piloti, vale a dire che i gruppi di 8 piloti che compogono le batterie non restano fissi per tutte le 5 manche ma variano ad ogni manche. Quindi un pilota che prima si scontrava per 5 volte con i medesimi 7 avversari, ora si troverà in ogni manche un gruppo di 7 avversari diverso. Nel fare questo però perdiamo l’aggancio con la tabella di compensazione delle posizioni di partenza, non riusciamo più a gestire le posizioni di partenza in modo che ci sia equilibrio tra i piloti. Questo mi sembra lo scoglio maggiore.
Rispondo alle altre tue domande: nel riformaare le batterie non c’è una regola da seguire se non quella di evitare troppi confronti diretti tra le teste di serie e cercare di equilibrare le posizioni di partenza. Le batterie e le 5 manche devono essere determinate e rese note prima dell’inizio della gara, una soluzione è sufficiente (se ho capito il senso della domanda …)
Ignorando per ora il problema degli scontri diretti tra le teste di serie, un metodo semplice per riutilizzare le tabelle attuale potrebbe essere quello di mantenere costante la tabella ma fare una rotazione dei giocatori nelle 4 batterie. P1 partirà cioè sempre dalle posizioni 8-2-3-4-5 ma cambierà batteria di volta in volta e lo stesso faranno gli altri giocatori (usando permutazioni diverse). Immagino che seguendo questa semplice regola si possa costruire una nuova tabella che rispetti le condizioni desiderate.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo