Dividere le persone in squadre per più soddisfazione

Question

Solo una domanda curiosità. Ricordate quando in classe lavoro di gruppo il professore sarebbe dividere le persone in gruppi di un certo numero (n)?

Alcuni dei miei professori vorrebbe una lista di persone n uno vuole lavorare con la gente e n uno non vuole lavorare con gli uni dagli studenti, e poi magicamente si rivelano gruppi di n dove gli studenti sarebbero stati abbinati con la gente che preferiscono e evitare di lavorare con le persone che non preferiscono.

Per me questo algoritmo suona molto come un problema di zaino, ma ho pensato di chiedere in giro di quello che sarebbe il tuo approccio a questo tipo di problema.

Modifica : Trovato un articolo ACM descrivere qualcosa esattamente come la mia domanda. Leggete il secondo paragrafo per déjà vu.

Answer 1

A me suona più come una sorta di cricca problema.

Il mio modo di vedere il problema, mi piacerebbe impostare la seguente grafico :

• I vertici sarebbero gli studenti
• Due studenti sarebbero collegati da un bordo se entrambe le seguenti cose sussistono:
  1. Almeno uno dei due studenti vuole lavorare con l'altro.
  2. Nessuno dei due studenti non vuole lavorare con l'altro.

Si tratta allora di suddividere il grafico in cricche di dimensione n. (Supponendo che il numero di studenti è divisibile per n)

Se questo non fosse possibile, probabilmente sarei lasciato che il primo vincolo sui bordi scivolare, e hanno spigoli tra due persone finchè nessuno dei due dice esplicitamente che non vogliono lavorare con l'altro.

Per quanto riguarda un approccio per risolvere questo in modo efficace, non ho idea, ma questo dovrebbe auspicabilmente arrivare più vicino a qualche comprensione del problema.

Answer 2

Si potrebbe modellare questo abbastanza facilmente come un problema di clustering e non si sarebbe nemmeno davvero bisogno di definire uno spazio, si potrebbe in realtà solo di definire le distanze:

Fare due persone molto vicino se entrambi vogliono lavorare insieme. Chiudi se uno di loro vuole lavorare con l'altra. distanza media se c'è solo apatia. Lontano se uno dei due non vuole lavorare con l'altro.

Poi si può solo trovare cluster, yay. Poi dividere i cluster di eccessivamente grande dimensione, con la sicurezza che la gente in cluster sarebbero tutti bene a lavorare insieme.

Answer 3

Questo problema può essere bruta costretto, da qui il mio approccio sarebbe primo a forza bruta, poi risolvere il problema quando ricevo una migliore idea.

Answer 4

Ci sono un paio di algoritmi che si potrebbero utilizzare. Un grande esempio è il cosiddetto "problema del matrimonio stabile", che ha una soluzione perfetta. Si può leggere di più su di esso qui:

http://en.wikipedia.org/wiki/Stable_marriage_problem

Il problema matrimonio stabile funziona solo con due gruppi di persone (uomini / donne nel caso di matrimonio). Se si vuole formare coppia è possibile utilizzare una variante, il problema compagno di stanza stabile. In questo caso si crea coppie ma tutti proviene da un unico pool.

Ma ti ha chiesto per una squadra (che traduco in> 2 persone per squadra). In questo caso si potrebbe far riempire tutti nella loro migliore al peggiore partita e quindi eseguire il