Algoritmo per determinare la squadra migliore e la formazione?

Question

Sto cercando algoritmi adatti che potrei usare in un simulatore di gestione di squadre sportive (ad esempio hockey o calcio). Alcune caratteristiche del simulatore:

• La squadra può giocare con diverse formazioni (ad esempio, calcio 4-4-2).
• Ogni giocatore della squadra ha un punteggio numerico per quanto sono bravi per ogni posizione nella formazione.
• c'è una piscina di giocatori della squadra di abilità che variano da cui la squadra può essere selezionato

Cosa algoritmi possono essere utilizzati per determinare a livello di codice e in modo efficiente le squadre e le formazioni più forti?

Answer 1

Se modelliamo il vostro problema da grafico e notando che il numero delle diverse formazioni è piccolo, il problema è maximum weighted bipartite matching, che è risolvibile da Hungarian Algorithm, ....

Ma come modellare il problema con grafi bipartiti? Imposta i giocatori come una parte e posizioni come un'altra parte (ad esempio nel calcio), per formare un gruppo di giocatori e 11 posizioni per loro, collega tutti i giocatori a tutte le posizioni e imposta il peso del bordo corrispondente come corrispondente valutazione del giocatore nella posizione .

Ora tutto quello che devi fare è trovare uno maximum (weighted) matching in questo grafico bipartito completo. (i codici sono disponibili nel link wiki).

Suppongo di avere un numero limitato di formazioni, per ogni formazione possiamo trovare il corrispondente grafico di corrispondenza, e quindi la corrispondenza massima, finalmente assumere il valore massimo su tutte le possibili formazioni (in tutti i grafici).

Answer 2

L'euristica semplice che può essere applicata al problema è l'algoritmo ingordo, la cui spiegazione è disponibile al numero http://en.wikipedia.org/wiki/Greedy_algorithm.

Un'altra soluzione è creare due nodi fittizi (inizio e fine) e considerare il pool di giocatori come un grafico ordinato (prima arriva il portiere, poi il difensore della fascia destra, e così via). I bordi consisteranno nella valutazione dei giocatori per la posizione in esame. In questo scenario, si avrà uno scenario in cui è possibile applicare l'algoritmo A *, la cui descrizione si trova in http://en.wikipedia.org/wiki/A*_search_algorithm (ricorda solo che un problema di massimizzazione è solo una minimizzazione della funzione inversa).

Answer 3

È possibile provare un approccio euristico utilizzando gli strumenti AI esistenti per le ottimizzazioni, ad esempio Genetic Algorithms o Hill Climbing.
Darò più dettagli sull'arrampicata in collina, dato che è il mio preferito.

rappresentare il vostro problema come stati graphG = (V,E) tale che V = {all possible states } e E = {(u,v) | swapping one player you can move from u to v }.
Inoltre, sia u:V->R una funzione di utilità per una formazione.
Dal momento che non vogliamo per generare il grafico, cerchiamo next:V->2^V essere una funzione tale che next(v) = {all possible formation that you can get by changing one player }

L'idea di hill climbing è quello di inizio da una formazione a caso, e avidamente fare il miglior cambio possibile, quando si è bloccato - riavviare l'algoritmo da una nuova formazione casuale.

1. best<- -INFINITY 
2. while there is more time 
3. choose a random matching 
4. NEXT <- next(s) 
5. if max{ u(v) | for each v in NEXT} < u(s): //s is a local maximum 
    5.1. if u(s) > best: best <- u(s) //if s is better then the previous result - store it. 
    5.2. go to 2. //restart the hill climbing from a different random point. 
6. else: 
    6.1. s <- max { NEXT } 
    6.2. goto 4. 
7. return best //when out of time, return the best solution found so far. 

Si noti che questa variazione di hill climbing (collina arrampicata con riavvii casuali) è un any time algorithm - il che significa che diventerà migliore quando viene dato più tempo, e quando viene dato un tempo infinito - si fonda la massima globale .