algorithm - Algoritmo para unir a los socios preferidos en grupos de tres
language-agnostic grouping (5)
¿Cuál es un buen algoritmo para resolver este problema?
Tengo tres grupos de personas: grupo A, grupo B y grupo C. Hay el mismo número de personas en cada grupo. Cada uno tiene una lista de personas en los otros grupos con las que están dispuestos a trabajar. Quiero agrupar a todas estas personas en grupos de 3 (uno de A, uno de B y uno de C) para que todos en un grupo quieran trabajar con las otras personas de su grupo.
¿Cómo puedo encontrar estos grupos de manera rápida? Si no hay forma de hacer felices a todos, entonces el algoritmo primero debe hacer que tantos grupos tengan tres personas que quieran trabajar entre ellos, y luego hacer felices a tantas personas en los otros grupos.
Un último punto: las personas acuerdan con quién quieren trabajar (si la persona x quiere trabajar con la persona y, entonces y también quiere trabajar con x). Si también pudieras dar una gran O del tiempo de ejecución de tu algoritmo, ¡sería genial!
Esto es como el problema estable del matrimonio, pero con 3 partes en lugar de dos.
Eche un vistazo a las soluciones eficientes para el problema anterior (concordancia gráfica bipartita) y adáptelas a sus necesidades.
http://en.wikipedia.org/wiki/Stable_marriage_problem
Una adaptación podría ser construir primero pares de trabajo de los grupos A y B solamente. Luego, estos pares deben emparejarse con un trabajador del grupo C cada uno. Deje que las parejas solo prefieran a los trabajadores con los que ambos miembros están de acuerdo (dadas sus listas). Tenga en cuenta que esto solo dará un óptimo local.
Una solución óptima para la coincidencia de k-partite es NP-difícil de encontrar:
http://www.math.tau.ac.il/~safra/PapersAndTalks/k-DM.ps
Consulte este documento para obtener una solución no óptima para el problema de coincidencia k-partite:
Estoy seguro de que puede encontrar otros en Google usted mismo ahora que conoce los términos que debe buscar. No sé si hay un algoritmo eficiente que proporcione la solución óptima para k = 3.
Para empezar, puede eliminar cualquier hecho en el que las dos partes tengan listas disjuntas de con quién trabajarán en el tercer grupo. Luego, inicie una fuerza bruta, realice una primera búsqueda en profundidad, seleccionando siempre de menos popular a más popular.
Alternativamente, equivalente a la eliminación anterior, forma una lista de todos los tríos posibles y trabaja desde ese lugar.
Solo una nota rápida para este problema. En primer lugar, no es un ejemplo del problema del matrimonio estable, ni de hecho una extensión del mismo (es decir, el problema de compatibilidad estable en 3D). Sin embargo, es un problema de compatibilidad 3D que se sabe que es NP-hard (ver Garey y Johnson). Para resolver dicho problema de una manera razonable, es probable que necesite usar algún tipo de restricción, entero o programación lineal (existen otros métodos). Algo que podría ser de utilidad es la nueva Microsoft Solver Foundation, así que échale un vistazo.
Esto es diferente de una extensión del problema del matrimonio estable, ya que, según entiendo la pregunta del OP, las personas de cada grupo no tienen una lista ordenada de quienes quieren trabajar de mayor a menor; es una relación binaria (dispuesta / no dispuesta).
Esto se puede formular como un problema de programación entero que se puede resolver bastante rápido. Doy la formulación matemática del problema a continuación; puede usar un paquete como glpk o AMPL / CPLEX para procesar los datos.
Defina las siguientes matrices:
M1 = |A| x |B| matriz, donde
M1(a,b) = 1 si a (dado miembro de A) está dispuesto a trabajar con b (miembro dado de B), y 0 de lo contrario
M2 = |A| x |C| matriz, donde M2(a,c) = 1 si a (dado miembro de A) está dispuesto a trabajar con c (miembro dado de C), y 0 de lo contrario
M2 = |B| x |C| matriz, donde
M3(b,c) = 1 si b (miembro dado de B) está dispuesto a trabajar con c (miembro dado de C), y 0 de lo contrario
Ahora define una nueva matriz que usaremos para nuestra maximización:
X = |A| x |B| x |C| matriz, donde
X(a,b,c) = 1 si hacemos que a, b, y c trabajen juntos.
Ahora, define nuestra función objetivo:
// Maximiza la cantidad de grupos
maximizar la Sum[(all a, all b, all c) X(a,b,c)]
sujeto a las siguientes restricciones:
// Para asegurar que nadie sea colocado en dos grupos
Para todos los valores de a: Sum[(all j, k) X(a, j, k)] <= 1
Para todos los valores de b: Sum[(all i, k) X(i, b, k)] <= 1
Para todos los valores de c: Sum[(all i, j) X(i, j, c)] <= 1
// Para garantizar que todos los grupos estén compuestos de individuos compatibles
Para todo a, b, c: X(a,b,c) <= M1(a,b)/3 + M2(a,c)/3 + M3(b,c)/3
Me encontré con un problema similar y simplemente escribí un script que lo fuerza brutalmente ... http://grouper.owoga.com/
Mis pensamientos iniciales fueron: ¿para un grupo más grande que era demasiado grande para la fuerza bruta, algún tipo de algoritmo genético? Realice N intercambios aleatorios M veces. Califique cada nueva disposición mediante alguna función de "felicidad". Tome los mejores, críe, repita.
Para grupos pequeños terminé obteniendo mejores resultados al pasar por algunos grupos, encontrar el "mejor" intercambio (el que produjo la mayor ganancia total de "felicidad"), hacer eso y luego repetir.