Algoritmo de programación de tiempo del estudiante

Question

Necesito encontrar un algoritmo para encontrar el mejor momento para reunirse, digamos un grupo de estudio. El sistema tiene información sobre un grupo de estudiantes y sus horarios de clase. El sistema debe dar un tiempo para la reunión, donde no hay conflicto con los horarios de clase de nadie. cuál sería la mejor forma de atacar este problema. Estaba buscando cualquier algoritmo de programación, pero no encontré a nadie que se ajuste.

gracias de antemano

Answer 1

que yo recuerde las mejores soluciones para este problema son las soluciones generadas por algoritmos genéticos

ver este enlace http://www.codeproject.com/KB/recipes/GaClassSchedule.aspx

Answer 2

pregunta interesante.

Esto es lo que haría:

1. En primer lugar, se alinean todos timescheduals, para todos los estudiantes (por ejemplo, a partir del lunes, todos los días dividido por 24 horas). Puede usar un booleano o un número entero para cada período y almacenarlos en una matriz.
2. A continuación, realice una operación de suma en todas las hojas de servicio juntas.

Que a su vez se ve así, por ejemplo:

Student A: 11100000111111100000 
Student B: 00000011111000010001 
Student C: 00000000111111110001 
_______________________________+ 
      11100022333222220002 
       ^^^   ^^^ 

Entonces será necesario encontrar todos los huecos en la matriz (áreas con ceros) mediante el uso de un bucle simple que realiza un seguimiento de la corriente cero longitud. Recuerde el índice de inicio y finalización y vuélvalo a traducir (al revés del paso 1) a una región de tiempo.

Answer 3

Este es un problema a juego y se puede resolver por maximum flow algorithm

cada grupo de estudiantes y el estudio es un nodo en un gráfico direccional y de entrada para cada estudiante tiene una unidad de flujo como entrada y está conectado a todos los grupos de estudio nodo. cada grupo de nodos estudio tiene una capacidad de producción ilimitada, cuando el flujo en la red es máxima que tenga su combinación correcta

ver también Introduction to Algorithms (capítulo redes de flujo)

Answer 4

Hay 24*60 = 1440 minutos por día. Entonces podría fácilmente forzarlo brutalmente, ya que no necesita obtener más que una precisión de un minuto. Sin embargo, voy a describir un simple DP.

Puede crear una matriz booleana que almacena si ese minuto tiene una clase en él por uno de los alumnos del grupo. También tienes una segunda matriz. Esta matriz almacena el número de espacios abiertos en este bloque y a la izquierda. Entonces, lo que puede hacer es atravesar la matriz booleana de derecha a izquierda y si el bloque tiene una clase, debe hacer el número 0; de lo contrario, lo hace 1 más el número del minuto anterior.

Sin embargo, siento que mi explicación que carece, por lo que aquí es pseudo código:

blocked = <boolean array>; 
numtoleft = <array containing the counts>; 
if blocked[0]: 
    numtoleft[0] = 0; 
else: 
    numtoleft[0] = 1; 

for i = 1 to 1440-1: 
    if blocked[i]: 
     numtoleft[i] = 0; 
    else: 
     numtoleft[i] = numtoleft[i-1]; 

entonces usted puede encontrar fácilmente la mayor ranura abierta al encontrar el número máximo de la matriz 'numtoleft' y se puede añadir restricciones a los tiempos que estás mirando.

EDIT:

Aquí es el algoritmo en Python:

def largestslot(blocked, startminute, endminute): 
    numtoleft = [0]*1440 
    numtoleft[startminute] = 0 if blocked[startminute] else 1 
    for i in xrange(startminute+1, endminute+1): 
     numtoleft[i] = 0 if blocked[i] else 1 
    ansmax = max(numtoleft[startminute:endminute+1) 
    ansi = numtoleft.index(ansmax) 
    return (ansi-ansmax, ansi) 

Answer 5

Me gustaría empezar con un enfoque muy simple para esto:

• tipo todos programada bloques de tiempo de todos los miembros de la agrupe en una lista, ordenada por la hora de inicio de un bloque
• vaya a la lista y combine elementos adyacentes, si se superponen (endTime of n es más que el tiempo de inicio de n + 1)

Ahora su lista contiene bloques de tiempo donde todos los miembros del grupo tienen otras actividades. Por lo tanto, debe verificar la lista de franjas horarias gratuitas y verificar si la ranura es lo suficientemente grande para la reunión deseada.

Answer 6

Cada estudiante tiene un rango de horas disponibles. Y todos deben reunirse (lo que significa que hay al menos una hora en la que todos son libres). Simplemente comienza con el primer alumno e intersecta su rango de horas disponibles con el próximo alumno y lo hace (sigue reduciendo el rango original) para cada alumno y debería quedar con un rango que se adapte a cada alumno.

Answer 7

Establecí la duración de la reunión y un intervalo de tiempo válido cuando la reunión puede tener lugar, es decir, una duración de 45 minutos a partir de las 8:00 AM pero no después de las 9:30 PM. Entonces debería ser una simple cuestión de intersectar el tiempo libre del miembro del grupo y encontrar un bloque que encaje. Deberá incluir tolerancias para la superposición, es decir, si el 75% del grupo puede reunirse, entonces es viable.

Es posible que también desee incluir almacenamientos intermedios para las horas de inicio/finalización para permitir el viaje, etc. e incluir esos almacenamientos intermedios en sus criterios de búsqueda. Lo que más odio de la mayoría de las reuniones es que no tienen en cuenta el tiempo de viaje/configuración y, en su lugar, reservan una reunión justo encima de otra.