Il modo migliore per creare disegni con limiti

-1

Sto scrivendo un programma per fare automaticamente il sorteggio per una competizione. Ci sono quattro oggetti: Debate Judge School Team Ogni dibattito ha due squadre e un giudice. Ogni squadra partecipa a tre dibattiti.

Con questo, ci sono le seguenti regole: 1) Una squadra non può affrontare qualcuno della stessa scuola 2) Una squadra non può affrontare un'altra squadra della stessa scuola (Come se giocassero una squadra da una scuola, non posso giocare di nuovo contro qualcuno di quella scuola) 3) Un giudice non può venire dalla stessa scuola di una squadra che sta giudicando.

Quindi, come potrei creare un pareggio? Un pareggio sembra un tavolo (ho solo bisogno dei dati, ma quando lo scrivi sembra questo) con una colonna per i giudici e poi altre tre colonne per ogni round di dibattiti (i tre dibattiti a cui ogni squadra partecipa).

In questo momento sto praticamente scegliendo una squadra a caso, trovando una squadra avversaria che non ha ancora giocato la scuola della prima squadra e non viene dalla stessa scuola e quindi non trova un giudice da nessuna di quelle scuole. Poi faccio la stessa cosa fino a quando ho tutti i dibattiti. Il problema è che il programma a volte entra nei solchi dove non c'è nessun altro team / giudice adatto. Un essere umano dovrebbe quindi spostare le cose intorno e cercare di trovare un modo per spostare altri giudici in giro per capirlo, ma come posso farlo con un programma. Se eseguo nuovamente il programma, lo capisco solo perché è casuale quali squadre sceglie per cosa. Fondamentalmente, mi chiedo quale sia la soluzione migliore per il problema?

    
posta sinθ 27.04.2013 - 20:20
fonte

3 risposte

2

Penso che tu sia vicino. Il trucco è iniziare con la prima squadra (il "primo" può essere definito in qualsiasi modo, anche casuale) e creare un elenco di tutte le altre squadre disponibili, in un certo ordine. Accoppia la prima squadra con la prima delle altre squadre disponibili. Ora guarda a fare una lista dei giudici disponibili (di nuovo in un certo ordine), e scegli il primo giudice disponibile.

Ripeti il precedente per il prossimo set. Ad un certo punto non avrai nessuna seconda squadra da scegliere, o sarai fuori dai giudici. A quel punto devi "tornare indietro" - srotolare una delle tue decisioni precedenti e passare a quella successiva.

Ad esempio, quando selezioni la squadra A, le tue scelte sono (B e C). Seleziona B e vai avanti. Più tardi scopri che B è stata una scelta sfortunata, quindi rivisita quella scelta e seleziona C invece.

L'idea è chiamata Prima ricerca di profondità . È molto più semplice di quanto la pagina di Wikipedia sia in realtà.

Gestire la tua sfida assegnando a ogni squadra un numero casuale, quindi utilizzare quel numero per selezionarli ogni volta che cerco il "prossimo disponibile" team o arbitro. In questo modo otterrai i tuoi accoppiamenti casuali e un modo per tornare indietro e rilassarti. (L'obiettivo è selezionare correttamente le squadre e i giudici corretti in un ordine tale da ottenere tutti gli abbinamenti necessari, soggetti ai vincoli delle regole del concorso).

L'unica volta che usi Random () è quando stai configurando i dati. L'algoritmo non dovrebbe usarlo.

    
risposta data 28.04.2013 - 00:22
fonte
3

Sembra un buon candidato per l'utilizzo del algoritmo del problema dello zaino . Potresti volere una delle estensioni multi-variante (anch'essa elencata in quel riferimento su Wikipedia), ma alla fine è lo stesso algoritmo. Potresti dare un'occhiata a una delle mie risposte recenti per un dominio problematico molto simile.

La cattiva notizia è che si tratta di un problema NP-difficile. Traduzione libera: non troverai mai un algoritmo perfetto per risolvere il problema. Tuttavia, se sei disposto a utilizzare alcuni "cheat", puoi generare un algoritmo che verrà completato in modo affidabile. I trucchi non sono un grosso problema in questo caso; è sufficiente limitare i parametri di partenza per consentire all'algoritmo di convergere su una soluzione. E non è che tu abbia bisogno della vera casualità per impostare il sorteggio, devi soltanto assicurarti che i partecipanti siano in grado di competere come una vasta gamma di altri partecipanti nel modo più ragionevole possibile.

    
risposta data 28.04.2013 - 00:22
fonte
-1

Dato che è sabato, e il mio pensatore è attualmente distrutto, prenderò la via pigra. Contare le iterazioni senza trovare una corrispondenza. Se superano un numero arbitrario, scarica il set di risultati e ricomincia da capo.

È una correzione di kludge, ma affronterà il problema della carreggiata senza fine.

    
risposta data 27.04.2013 - 23:26
fonte

Leggi altre domande sui tag