Divida a las personas en equipos para mayor satisfacción

Question

Sólo una pregunta de curiosidad. ¿Recuerda cuando en el trabajo de grupo de la clase el profesor dividiría a las personas en grupos de un cierto número (n)?

Algunos de mis profesores tomaría una lista de n la gente que uno quiere trabajar con la gente y n uno no quiere trabajar con el uno del estudiante, y luego mágicamente a salir grupos de n donde los estudiantes se emparejan con las personas que prefieren y evitan trabajar con personas que no prefieren.

Para mí, este algoritmo se parece mucho a un problema de mochila, pero pensé que podría preguntar acerca de cuál sería su enfoque para este tipo de problema.

EDIT: Encontrado an ACM article describiendo algo exactamente como mi pregunta. Lee el segundo párrafo para deja vu.

Answer 1

Para mí, suena más como un tipo de problema clique.

La forma en que veo el problema, que había definido la siguiente graph:

• vértices serían los estudiantes
• Dos estudiantes estarían conectados por un borde si ambas cosas siguientes sostienen:
  1. Al menos uno de los dos estudiantes quiere trabajar con el otro.
  2. Ninguno de los dos estudiantes no quiere trabajar con el otro.

Es entonces una cuestión de dividir el gráfico en grupos de tamaño n. (Suponiendo que el número de estudiantes es divisible por n)

Si esto no fuera posible, probablemente dejaría que la primera restricción en los bordes se deslice, y tenga bordes entre dos personas siempre y cuando ninguno de ellos diga explícitamente que no quiero trabajar con el otro

En cuanto a un enfoque para resolver esto de manera eficiente, no tengo ni idea, pero esto con suerte te acercará a una idea del problema.

Answer 2

Este problema puede ser forzado por la fuerza bruta, por lo tanto, mi enfoque sería primero forzarlo a fuerza bruta, luego arreglarlo cuando tenga una mejor idea.

Answer 3

Se podría modelar esto con bastante facilidad como un problema de agrupamiento y que ni siquiera realmente necesita para definir un espacio, en realidad se podría simplemente definir las distancias:

Hacer dos personas muy cerca si ambos quieren trabajar juntos. Cerrar si uno de ellos quiere trabajar con el otro. Distancia media si solo hay apatía. Lejos si ninguno de los dos quiere trabajar con el otro.

Entonces usted podría encontrar agrupaciones, yay. Luego, divida los grupos de tamaño demasiado grande, con la confianza de que las personas de los grupos estarán bien trabajando juntas.

Answer 4

Hay un par de algoritmos que puede usar. Un gran ejemplo es el llamado "problema de matrimonio estable", que tiene una solución perfecta.Puede leer más sobre esto aquí:

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

El problema de la unión estable sólo trabaja con dos grupos de personas (hombres/mujeres en el caso del matrimonio). Si quieres formar un par puedes usar una variación, el problema del compañero de cuarto estable. En este caso, usted crea pares, pero todos provienen de un solo grupo.

Pero usted pidió un equipo (que traduzco en> 2 personas por equipo). En este caso, puede dejar que todos rellenen su mejor y peor coincidencia y luego ejecutar