Algoritmo para unir socios preferidos en grupos de tres
https://stackoverflow.com/questions/294660
-
08-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
¿Qué es un buen algoritmo para resolver este problema?
Tengo tres grupos de personas: grupo A, grupo B y grupo C. Hay la misma cantidad de personas en cada grupo. Cada uno tiene una lista de personas en los otros grupos con los 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 en su grupo.
¿Cómo puedo encontrar estos grupos de manera rápida? Si no hay manera 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 pudiera dar una gran O del tiempo de ejecución de su algoritmo, ¡sería genial!
Solución
Esto es como el problema del matrimonio estable, pero con 3 partes en lugar de dos.
Eche un vistazo a soluciones eficientes para problemas anteriores (coincidencia de gráficos bi-partita) y adáptelos 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 tienen que ser emparejados con un trabajador del grupo C cada uno. Deje que las parejas solo prefieran trabajadores en 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-partitas 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 de k-partitas:
Estoy seguro de que puedes encontrar a otros en Google tú mismo ahora que conoces los términos para buscar. No sé si existe un algoritmo eficiente que ofrezca la solución óptima para k = 3.
Otros consejos
Esto es diferente de una extensión del problema del matrimonio estable, ya que según entiendo la pregunta del OP, las personas en cada grupo no tienen una lista ordenada de con quién quieren trabajar de mayor a menor; es una relación binaria (querer / no querer).
Esto puede formularse como un problema de programación de enteros que puede resolverse con bastante rapidez. 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 un (miembro dado 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 un (miembro dado 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 defina 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, byc trabajen juntos.
Ahora, defina nuestra función objetivo:
// Maximiza el número de grupos
maximizar Sum[(all a, all b, all c) X(a,b,c)]
sujeto a las siguientes restricciones:
// Para garantizar que nadie se coloque 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 por individuos compatibles
Para todos a, b, c: X(a,b,c) <= M1(a,b)/3 + M2(a,c)/3 + M3(b,c)/3
Solo una nota rápida a este problema. Primero, no es un ejemplo del problema del matrimonio estable, ni de hecho es una extensión del mismo (es decir, el problema del emparejamiento estable 3D). Independientemente, sin embargo, es un problema de coincidencia 3D que se sabe que es NP-hard (ver Garey y Johnson). Para resolver este problema de una manera razonable, es probable que necesite usar alguna forma de restricción, entero o programación lineal (existen otros métodos). Algo que podría ser útil es la nueva Microsoft Solver Foundation, así que échale un vistazo.
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 comience una búsqueda de fuerza bruta, profundidad primero, siempre escogiendo de menos popular a más popular.
Alternativamente, equivalente a la eliminación anterior, forme una lista de todos los tríos posibles y trabaje a partir de eso.
Me encontré con un problema similar y acabo de escribir un script que lo fuerza por fuerza bruta ... 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? Haga N intercambios aleatorios M veces. Califique cada nuevo arreglo por alguna función de 'felicidad'. Tome los mejores, críe, repita.
Para grupos pequeños, terminé obteniendo mejores resultados al recorrer algunos grupos, encontrar el 'mejor' intercambio (el que produjo la mayor ganancia general de 'felicidad'), hacer eso y luego repetirlo.
