Algoritmo para una herramienta de planificación

Question

Estoy escribiendo una pequeña aplicación de software que necesita para servir como una simple herramienta de planificación para una escuela local. El 'problema' que tiene que resolver es bastante básico. A saber, los maestros necesitan hablar con los padres de todos los niños. Sin embargo, algunos niños tienen, por supuesto, hermanos y hermanas en diferentes grupos, por lo que estas conversaciones necesario programar junto al otro, para evitar las situaciones eran los padres tener una charla a las 6 pm y otra a las 10 pm. Así, en pocas palabras, dada una colección de n los niños, donde algunos niños tienen 1 o más hermanos o hermanas, generar un horario donde se planifican todas las conversaciones de estos niños al lado del otro.

Ahora, puede que el problema puede ser resuelto muy fácil, pero por otro tengo la sensación de que esto puede ser un problema bastante complicado, que necesita y puede ser resuelto con algún tipo de algoritmo. Esmeradamente. Pero estoy en lo cierto? ¿Esta ahí? He mirado en la húngaro alorithm pero no acaba de aplicar a este problema en particular.

Editar:. Me olvidé de mencionar, que todas las conversaciones toman la misma cantidad de tiempo

Gracias!

Answer 1

Creo que es bastante fácil.

En primer grupo de los niños que pertenecen juntos porque comparten los padres. Programar los niños dentro de un grupo de forma consecutiva, programar el resto como al azar.

Otra manera de abstraerse de ella y hacer el problema más fácil es mirar desde la perspectiva de los padres, hermanos y hermanas ver como "niño" y darles más tiempo. A continuación, sólo puede programar los padres al azar, pero algunos necesitan más tiempo (porque tienen múltiples childeren).

Answer 2

Uno de los enfoques woul DBE para definir el problema en un lenguaje de restricción declarativa y luego dejar que se resuelve el problema para usted. La última vez que hice esto, utiliza Eclipse , que es un poco el lenguaje ingenioso donde se define el espacio del problema por las restricciones , y luego dejar que se encuentran valores permitidos que satisfagan esas limitaciones.

Por ejemplo, creo que usted tiene dos clases de restricciones:

1. Un maestro sólo puede tener una conferencia a la vez
2. Todos los estudiantes de la misma familia debe tienen ranuras consecutivas

Una vez que defina estos en Eclipse, calculará los valores para cada estudiante que satisfacen los requisitos. Si usted va esta manera, también se puede agregar fácilmente las limitaciones como sea necesario. Por ejemplo, es fácil decir que un enseñan no está disponible para la ranura Y, o los maestros deben tomar turnos haciendo trabajo administrativo, etc.

Answer 3

Este tipo se siente como un tipo de "algoritmo de mochila" del problema. Es necesario agrupar a los miembros de la familia juntos y luego llenar los espacios de manera apropiada.

Si google "algoritmo de la mochila", verá suficientes escribir-ups para hacer girar su cabeza y también algunas soluciones buenas codificada.

Answer 4

Creo que si cada charla se podría reducir a "actividades" que cada actividad tiene un tiempo de inicio y una hora de finalización se puede utilizar el algoritmo de selección de actividad estudiado en la informática. Se basa en un enfoque codiciosos y podría resolverse en O (n) (donde n es el número de actividades). Usted puede encontrar más información aquí . Estoy seguro de que tendrá que tener que hacer un pre-procesamiento aquí para ser capaz de reducir la emisión hermano / hermana como las actividades del mismo tipo.