Dividere le persone in squadre per la maggior parte delle soddisfazioni

Question

Solo una domanda di curiosità. Ricorda quando durante la lezione di gruppo il professore dividerebbe le persone in gruppi di un certo numero (n)?

Alcuni dei miei professori vorrebbe un elenco di n gente vuole lavorare con e n la gente non si vuole lavorare con da ogni studente, e poi magicamente si rivelano gruppi di n dove gli studenti sarebbero stati abbinati con le persone che preferiscono ed evitano di lavorare con persone che non preferiscono.

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

EDIT: trovato an ACM article che descrive qualcosa esattamente come la mia domanda. Leggi il secondo paragrafo per deja vu.

Answer 1

A me sembra più una specie di problema clique.

Il mio modo di vedere il problema, che avevo creato la seguente graph:

• vertici sarebbero gli studenti
• Due studenti sarebbero collegati da un bordo se entrambe le seguenti cose sussistono:
  1. Almeno uno dei due studenti desidera 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 sia divisibile per n)

Se ciò non fosse possibile, probabilmente lascerei che il primo vincolo sui bordi scivolasse e avesse margini tra due persone purché nessuno dei due esplicitamente affermasse che non voglio lavorare con l'altro.

Per quanto riguarda un approccio per risolvere questo problema in modo efficiente, non ne ho idea, ma si spera che questo vi possa avvicinare ad alcuni approfondimenti sul problema.

Answer 2

Questo problema può essere bruto-forzato, quindi il mio approccio sarebbe prima di forzarlo, quindi correggerlo quando ho un'idea migliore.

Answer 3

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 definire le distanze:

fare due persone molto vicino se entrambi vogliono lavorare insieme. Chiude se uno di loro vuole lavorare con l'altro. Media distanza se c'è solo apatia. Lontano se uno non vuole lavorare con l'altro.

Quindi potresti trovare solo gruppi, yay. Quindi dividete tutti i gruppi di dimensioni eccessivamente grandi, con la certezza che le persone nei gruppi andrebbero tutti bene insieme.

Answer 4

Ci sono un paio di algoritmi che è possibile 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 vuoi formare una coppia puoi usare una variazione, il problema del compagno di stanza stabile. In questo caso crei coppie ma tutti provengono da un singolo pool.

Ma hai chiesto una squadra (che traduco in> 2 persone per squadra). In questo caso, puoi consentire a tutti di completare il loro meglio fino alla peggiore corrispondenza e quindi eseguire lo