Diviser les gens en équipes pour plus de satisfaction

Question

Juste une question de curiosité. Rappelez-vous quand en classe groupwork le professeur diviserait les gens en groupes d'un certain nombre (n)?

Certains de mes professeurs prendrait une liste de personnes n veut travailler avec et les gens de n on ne veut pas travailler avec de chaque élève, puis tourner comme par magie groupes de n où les élèves seraient jumelés avec des personnes ils préfèrent et éviter de travailler avec des gens qu'ils ne préfèrent.

Pour moi, cet algorithme ressemble beaucoup à un problème Knapsack, mais je pensais que je demanderais autour de ce que votre approche de ce genre de problème serait.

EDIT : Trouvé un article ACM décrivant quelque chose exactement comme ma question. Lisez le deuxième alinéa pour déjà vu.

Answer 1

Pour moi, il ressemble plus à une sorte de problème clique .

La façon dont je vois le problème, je serais mis en place le graphique :

• Vertices serait les étudiants
• Deux étudiants seraient reliés par une arête si ces deux choses suivantes sont:
  1. Au moins un des deux étudiants veut travailler avec l'autre.
  2. Aucun des deux étudiants ne veulent pas travailler avec l'autre.

Il est alors une question de diviser le graphe en cliques de taille n. (En supposant que le nombre d'étudiants est divisible par n)

Si cela n'a pas été possible, je serais probablement laisser la première contrainte sur les bords glisser, et ont des bords entre deux personnes aussi longtemps que aucun d'entre eux dit explicitement qu'ils ne veulent pas travailler avec l'autre.

En ce qui concerne une approche de la résolution de cette efficacité, je ne sais pas, mais cela ne devrait, espérons-vous rapprocher de un aperçu du problème.

Answer 2

Vous pouvez modéliser ce assez facilement comme un problème de mise en cluster et vous même pas vraiment besoin de définir un espace, vous pouvez réellement définir simplement les distances:

Faites deux personnes très proches si les deux veulent travailler ensemble. Fermer si l'un d'eux veut travailler avec l'autre. moyenne distance s'il y a juste l'apathie. Loin si l'on ne veut pas travailler avec l'autre.

Ensuite, vous pouvez tout simplement trouver des grappes, youpi. Ensuite, diviser des grappes de taille trop grande, avec confiance que les gens dans les groupes seraient tous bien travailler ensemble.

Answer 3

Ce problème peut être forcé brute, d'où mon approche serait la première à la force brute, puis la fixer quand je reçois une meilleure idée.

Answer 4

Il y a quelques algorithmes que vous pouvez utiliser. Un bon exemple est le soi-disant « problème du mariage stable », qui a une solution parfaite. Vous pouvez en lire davantage ici:

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

Le problème du mariage stable fonctionne uniquement avec deux groupes de personnes (hommes / femmes dans le cas du mariage). Si vous voulez former paire, vous pouvez utiliser une variante, le problème de camarade de chambre stable. Dans ce cas, vous créez des paires, mais tout le monde vient d'une piscine unique.

Mais vous avez demandé une équipe (que je traduis en> 2 personnes par équipe). Dans ce cas, vous pouvez laisser tout le monde rempli leur meilleur au pire match de puis exécutez le