Algoritmo para asientos de grupos de personas?

Estoy interesado en escribir una aplicación que puede determinar cómo sentar grupos de 2-10 personas en mesas que pueden albergar a 10 personas. Probablemente habrá alrededor de 15 tablas y 140 personas en total. No quiero separar a ninguno de los grupos de personas.Algoritmo para asientos de grupos de personas?

parece que podría ser un problema común y me preguntaba si alguien tenía alguna sugerencia sobre donde debería empezar a buscar una solución a esto. Cualquier enlace o sugerencia apreciada.

Fuente

2010-07-07 Abe Miessler

Define best por favor. – IVlad

Mejor: la operación toma O (0) para resolver. ¡Ningún cálculo realizado! – mcandre

No hay grupos divididos. Todos los grupos están sentados. –

Este es el bin packing problem.

Fuente

2010-07-07 14:29:50 Svante

@Abe Miessler, consulte este enlace y lea sobre el algoritmo _Primer-ajuste_. El problema general es difícil, pero los límites de tamaño facilitan el enfoque ingenuo y codicioso. – grossvogel

El límite de tamaño lo hace fácil si está poco especificado, lo que significa que hay muchas soluciones. Sin embargo, en el otro caso extremo donde es imposible sentar a todos los grupos en diez mesas (pero apenas), debe agotar todas las posibilidades para determinar que es imposible. –

AFAIK, el enfoque de primer ajuste es lo que la mayoría de los sistemas de archivos y administradores de memoria usan cuando se asigna espacio, y funciona bastante bien. – rmeador

Vamos a los grupos decidir dónde sentarse. ¿Está bien si los grupos deciden por sí mismos separarse, fusionarse con otros grupos o mover mesas juntos?

Fuente

2010-07-07 14:26:00 mcandre

No si se trata de una boda, donde la novia y el novio están pagando por cada mesa, y la gente ha pedido con anticipación qué comida quieren. –

No, es demasiado grande para eso, si les dejo decidir que los grupos generalmente se rompen. –

Distribuya los grupos más grandes primero, luego agregue grupos más pequeños siempre que pueda. – mcandre

Ésta es sólo una variación en el estándar "Knapsack problem"

Fuente

2010-07-07 14:26:18

¡No, no lo es! Knapsack tiene soluciones pseudopolinomiales, mientras que el bin-packing no. –

Cuando tuvimos este problema en la escuela hemos resuelto como un problema TSP.

Fuente

2010-07-07 14:28:54

Eso significa que el problema es NP-hard. Entonces, es probable que Abe no encuentre un algoritmo óptimo ... – YuppieNetworking

@Yuppie: No, eso significa que es NP, lo cual realmente no nos dice nada * (aunque el hecho de que usted modeló el problema como TSP en clase en lugar de usar un polinomio -time algoritmo insinúa que el instructor sabía que el problema es NP-completo:) * –

Este es el bin packing problem, que es NP-Hard (no es fácil encontrar la mejor respuesta, y no es fácil verificar si la respuesta es la mejor).

Los grupos de personas son un objetos individuales, con el volumen = el número de personas de personas en el grupo. Las mesas son los contenedores de tamaño 10.

Hay unos algoritmos de aproximación por ahí, que debería ser fácil de encontrar sabiendo que usted debe de google para el embalaje bin.

Sin embargo, el problema está relajado (en cierto modo) porque tiene 10 mesas - es decir, que no está tratando de adaptarse a la gente sobre el número mínimo de mesas. Si 10 tablas es la solución ÓPTIMA, tendrá problemas para encontrar la solución (si es que existe), pero si la óptima es realmente 7 u 8, encontrar la solución será fácil. Todo depende de las distribuciones grupales.

Fuente

2010-07-07 14:33:49

Lo óptimo no puede ser 7 u 8, ya que hay ~ 140 personas y el tamaño de la tabla es 10. –

Algoritmo para asientos de grupos de personas?

Respuesta

Cuestiones relacionadas