¿Cómo agrupar a las personas en función de sus elecciones? ¿Qué algoritmos existen?

Question

Por ejemplo, tengo ocho hijos,

A,B,C,D,E,F,G,H

Si les pido que se pongan en grupos de dos, sus opciones son

A->B
B->C
C->B
D->B
E->A
F->A
G->H
H->C

¿Cómo asegurarse de que tienen sus opciones en la medida de lo posible?

O, del mismo modo, para formar grupos de cuatro:

A->B,C,D
B->A,C,G
C->E,A,D
D->B,E,G
E->F,G,H
F->A,B,C
G->E,F,B
H->F,E,C

Estoy seguro de que hay muchas maneras de hacerlo. Pero no sé por dónde empezar a buscar algoritmos. ¿Cuál es el término matemático para estos problemas?

Answer 1

Está buscando algoritmos que coincidan. El algoritmo de camino alterno es bueno para mejorar las coincidencias cuando sólo se trata de crear parejas. No sé si se trata de grupos más grandes, pero deben seguir el mismo patrón.

Answer 2

Al menos para los emparejamientos, una forma de verlo es básicamente el "problema de los compañeros de piso estables", excepto que en lugar de que cada persona clasifique a todos los demás en orden estricto, básicamente tienes una "opción principal" para cada persona y luego todos los demás para esa persona se clasifican igualmente (y más abajo que la opción principal). Puedes ver https://en.wikipedia.org/wiki/Stable_roommates_problem para que un algoritmo eficiente encuentre una solución estable de asignación de cuartos siempre que exista una solución satisfactoria (a veces no existe).

No estoy seguro de lo fácil/estudiado que está el problema para agrupar a la gente en grupos de $k$ personas según sus preferencias, para $k > 2$ . Por un lado, hay muchas formas de definir una "solución óptima". ¿Quiere maximizar el número de pares ordenados $(X,Y)$ donde $X$ preferiría estar en un grupo que tuviera $Y$ ? O maximizar el número de pares en los que ambos $X$ y $Y$ ¿quieren estar en su grupo? O maximizar el número de $X$ tal que $X$ ¿se lleva a todos los que quieren en su grupo? ¿O alguna combinación ponderada de estas medidas? Para ello, se podría modificar de forma similar el $k = 2$ caso de esta manera también y llegar a un objetivo diferente a la formulación de los compañeros estables.