Divida a los equipos para mayor satisfacción

Question

Sólo una pregunta curiosidad. Recuerde que cuando el trabajo en grupo en clase el profesor podría dividir a la gente en grupos de un número determinado (n)?

Algunos de mis profesores tomaría una lista de personas n 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 y prefieren evitar trabajar con personas que no prefieren.

Para mí este algoritmo se parece mucho a un problema de la mochila, pero yo pensaba que iba a preguntar acerca de lo que sería su acercamiento a este tipo de problema.

editar : Encontrado un artículo ACM describir algo exactamente igual a mi pregunta. Lea el segundo párrafo de deja vu.

Answer 1

A mí me suena más como una especie de camarilla problema.

La forma en que veo el problema, me estableció el siguiente gráfico :

• Los 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 quieren 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 era posible, probablemente me dejo la primera restricción en los bordes deslizarse, y tienen bordes entre dos personas, siempre y cuando ninguno de los dos dice explícitamente que no quieren trabajar con el otro.

En cuanto a un enfoque para resolver esto de manera eficiente, no tengo ni idea, pero esto es de esperar que debe acercarse a una cierta penetración en el problema.

Answer 2

Se puede modelar esta 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. media distancia si sólo hay apatía. A lo lejos, si uno no quiere trabajar con el otro.

A continuación, usted podría encontrar racimos, yay. A continuación, dividir los grupos de excesivamente grandes dimensiones, con la seguridad de las personas en los grupos estarían todos muy bien trabajando juntos.

Answer 3

Este problema puede ser bruta forzada, por lo tanto, mi enfoque sería la primera a la fuerza bruta, y luego solucionarlo cuando consigo una mejor idea.

Answer 4

Hay un par de algoritmos que puede utilizar. Un gran ejemplo es el llamado "problema de la unión 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 desea formar par se puede utilizar una variación, el problema compañero de piso estable. En este caso se crea pares pero todo el mundo proviene de un solo grupo.

Pero se pidió un equipo (que traduzco en> 2 personas por equipo). En este caso se podría dejar de llenado todo el mundo en su mejor a peor partido y ejecute el