Asientos de invitados basados ​​en parámetros priorizados

El siguiente modelo de datos representa tablas con asientos e invitados, en una aplicación que le permite al usuario crear tablas y asientos, utilizando visualmente HTML5.

// The data model var data = { guests: [], // id, name, tags tables: [], // id, seats seats: [], // id, guest tags: [] // id, name }; 

Los invitados tienen tags (tipo de categorías) adjuntas a ellos. Estas tags se pueden priorizar y configurar para que funcionen como parámetros de “agrupación” o “desagrupación”. El usuario luego hace clic en “Asiento”, y los invitados están sentados (aparentemente al azar), mientras se respetan los parámetros priorizados.

Ejemplo completo: http://jsfiddle.net/kBp49/2/ (busque “LA SOLUCIÓN VA AQUÍ” en el panel JS)

La pregunta es: ¿Cómo implemento una función que haga que los invitados se sienten en las mesas, teniendo en cuenta que algunos deben estar sentados uno al lado del otro y otros deben sentarse uno junto al otro para crear uno de los mejores asientos? configuraciones? El número de invitados puede exceder 1000 pero no 2000.

Ejemplo de la vida real, para aclarar el problema.

Digamos que tenemos 3 tablas. Tienen 4 asientos cada uno. Digamos también que tenemos 9 invitados para llenar estas tablas. Son los siguientes:

  1. Invitado 1, judío, de Estados Unidos.
  2. Invitado 2, judío, de Reino Unido
  3. Invitado 3, Christian, de los Estados Unidos.
  4. Invitado 4, Christian, de Reino Unido
  5. Invitado 5, Christian, de Suecia
  6. Invitado 6, ateo, de Reino Unido
  7. Invitado 7, ateo, de Suecia
  8. Invitado 8, musulmán, de Arabia Saudita
  9. Invitada 9, musulmana, del Reino Unido.

Ahora, el usuario prioriza los parámetros como este. Lo primero es lo más importante.

  1. Quiero que los que tienen la misma religión se sienten separados uno del otro
  2. Quiero que aquellos con la misma ubicación geográfica se sientan uno al lado del otro

Esto esta bien:

  1. Tabla 1: Invitados: 1, 3, 7, 8
  2. Tabla 2: Invitados: 2, 4, 6, 9
  3. Tabla 3: Invitados: 5

Una solución de actualización podría ser el algoritmo Minimax. Calcularía una puntuación para cada posibilidad y presentaría la mejor solución encontrada (encontrada después, digamos 10 segundos de cálculo). El algoritmo es para lo que necesito ayuda, la implementación en sí, por supuesto, requerirá decisiones que solo yo puedo tomar.

No hay una mejor respuesta a esta pregunta, porque no hay una mejor disposición de asientos; de hecho, diría que el acuerdo que usted dice que está bien es probablemente bastante malo, si se ve obligado a usar tres mesas y puede sentarse al máximo 4 por mesa, probablemente deberías sentar a tres en cada mesa para que nadie termine sentado solo. Eso es, sin embargo, la selección de liendres, y evita la base de la pregunta.

Hay algunos algoritmos que puedo imaginar.

Primero, puede tratar cada “etiqueta” como una dimensión en un espacio N-dimensional (esto suena más complicado de lo que es). Por ejemplo, en la dimensión de región, puede asignar a cada país un valor entero, y la dimensión de su espacio regional tendrá cada uno de estos enteros como valores potenciales. Luego, coloque a cada invitado como un punto en este espacio N-dimensional, y seleccione para cada mesa los invitados que estén más cerca en ese espacio. Puede respaldar las prioridades al ignorar algunas características al crear el espacio, es decir, si no desea agruparse por religión, no incluya la religión mientras construye el espacio, o si desea activamente la separación entre personas con religión “me gusta”, puede modificar su cálculo de distancia para tener una relación inversa en esa dimensión. Este algoritmo podría tener un buen rendimiento dependiendo de la cantidad de funciones (es decir, las dimensiones) y la cantidad de puntos; esta es esencialmente la forma en que crean los motores de recomendación.

Si quisiera algo simple pero lento, podría usar un algoritmo de fuerza bruta: es decir, para cada invitado, mire cada tabla que tiene miembros, si estos miembros no son deseables dadas sus prioridades, siéntese en una mesa nueva. Si no existen tablas nuevas, seleccione la tabla con los miembros menos indeseables. ¡Esto es probablemente tan simple como puedes ir!

Finalmente, puede preprocesar a sus invitados y contar: cuántos son de la región x, cuántos son de la religión y, … luego, una vez que tenga estas estadísticas, puede crear las tablas (según la prioridad). ) como: la mesa de Canadá, la mesa del Reino Unido, …, y luego coloque a los invitados en cualquier mesa que coincida con su descripción. El tiempo en que esto es factible depende del conjunto de entrada.

Espero que esto ayude, y te dé algunas ideas sobre cómo resolver este problema 🙂