Round robin, bilanciato casa / fuori, più posizioni con opzioni multi-team

0

Questa è la mia prima domanda su questo forum, ho cercato di esaurire ogni possibile opzione di ricerca che potrei pensare o trovare. In realtà questa è la prima volta che ho inviato aiuto per questo ovunque, quindi forse avrei dovuto iniziare qui ...:)

Sto cercando di creare una soluzione di pianificazione automatica per un pool league, in questo momento il processo è interamente manuale. Farò del mio meglio per cercare di descrivere la mia situazione:

Di solito ci sono circa 20 squadre che giocano in questo campionato, ma devono accettare situazioni in cui ci possono essere solo 5 squadre e fino a 50 squadre. Oltre al numero di squadre, questa è una lega itinerante, quindi ci sono più sedi, alcune delle quali possono ospitare una sola partita (due squadre) e alcune che possono ospitare fino a 6 partite (12 squadre). Se c'è un numero dispari di squadre, posso aggiungere un bye, naturalmente, ma vorrei davvero limitarlo a un singolo bye se posso, a meno che non sia assolutamente necessario aggiungere più byte.

Ho bisogno di concepire un sistema di pianificazione che permetta ai team di giocare tra loro sulla base di una formula round robin, cercando il meglio possibile per consentire una casa alternata equilibrata e lontana, e senza superare i limiti sul numero di partite che possono essere giocato in una sede. Se ci sono un paio di casi in cui una squadra gioca a casa o fuori due volte di seguito per sistemare i limiti della sede o le squadre che giocano nello stesso luogo per giocare, va bene, a patto che non sia frequente (si spera non più di una volta per squadra per non più di 3 o 4 squadre in un programma). Posso essere flessibile su questo se l'algoritmo richiede.

Ho trovato soluzioni simili, incluso un algoritmo equilibrato di torneo round / robin casalingo / esterno, ma questo non consente di vedere luoghi che possono giocare più partite ma li limita.

Se qualcuno può indicarmi una direzione o fornire qualche intuizione, lo apprezzerei molto. Sto sperando in una soluzione asp.net/vb.net a questo, ma se qualcuno ha una formula che aiuti con questo posso fare del mio meglio per programmarlo su asp.net.

Dovrei menzionare che le informazioni sulla sede / squadra verranno archiviate in un database MSSQL (incluso il limite di match per sede), così come questo programma una volta che sarà stato creato, e dovrà essere richiamato in coda anche.

Grazie mille per il tuo tempo e impegno!

Modifica

Non credo di essere stato abbastanza specifico su questo elemento:

Ogni squadra deve scegliere una sede da cui giocare, e questo fa parte del requisito di casa e di via alternata; se una squadra può tenere 4 squadre di casa, almeno 2 di quelle squadre devono giocare e 2 di quelle squadre possono giocare a casa ogni settimana. La ragione per cui dico che 2 di quelle squadre devono giocare è assicurarsi che non più di 2 squadre giochino a casa in quella sede e superino i limiti di quella venu. E le squadre possono giocare l'una con l'altra, una come casa e una come "fuori".

    
posta user277561 10.07.2017 - 20:45
fonte

1 risposta

-1

In questi giorni, i computer sono così potenti che non è necessario essere preziosi. Puoi forzare il problema con la forza e utilizzare i criteri di ottimizzazione per scegliere l'opzione migliore.

Ecco come farei al riguardo:

  1. Definisci una rappresentazione dei dati di una pianificazione completata, ad es. una struttura o classe c # o un blob XML possibile. La cosa importante è che puoi attraversare la struttura in codice con relativa facilità.

  2. Definisci una serie di vincoli hard e soft. Un vincolo rigido rappresenta una regola che non deve essere violata, ad es. "Venue X può supportare un massimo di 6 squadre simultanee." Un vincolo soft è una regola che può essere violata ma che sarebbe meno favorevole, ad es. "Riduci il numero di byte".

  3. Scrivi il codice per riempire il tuo modello di dati in modo casuale.

  4. Scrivi il codice per segnare il programma. Se viola un vincolo rigido, ottiene un punteggio pari a 0. Se non viola assolutamente nessun vincolo morbido, ottiene un punteggio di 100. Se viola alcuni vincoli non rigidi, dovrebbe ottenere un punteggio da qualche parte nel mezzo, che è possibile modificare in base alla tua conoscenza di ciò che è accettabile. Ad esempio, se una squadra finisce per giocare una partita in casa due volte di seguito, forse puoi detrarre 2 punti dal punteggio per ogni squadra che finisce così.

  5. Esegui il programma 10.000 volte e genera e segna 10.000 programmi.

  6. Segui la pianificazione con il punteggio più alto.

Potrebbe essere che 10.000 iterazioni non siano abbastanza, ma puoi probabilmente eseguirlo per 100.000 iterazioni o anche 1.000.000 di iterazioni in un ragionevole lasso di tempo.

In questo modo non devi davvero preoccuparti di creare un algoritmo intelligente, ed è abbastanza semplice cambiare le regole in seguito, se pensi a più vincoli.

    
risposta data 11.07.2017 - 03:01
fonte

Leggi altre domande sui tag