algoritmo planificador de calendario

Question

Estoy buscando un algoritmo que, dado un conjunto de elementos que contienen una hora de inicio, hora de finalización, tipo e ID, devolverá un conjunto de todos los conjuntos de elementos que encajan entre sí (sin tiempos superpuestos) y todos los tipos están representados en el conjunto).

S = [("8:00AM", "9:00AM", "Breakfast With Mindy", 234), 
    ("11:40AM", "12:40PM", "Go to Gym", 219), 
    ("12:00PM", "1:00PM", "Lunch With Steve", 079), 
    ("12:40PM", "1:20PM", "Lunch With Steve", 189)] 

Algorithm(S) => [[("8:00AM", "9:00AM", "Breakfast With Mindy", 234), 
        ("11:40AM", "12:40PM", "Go to Gym", 219), 
        ("12:40PM", "1:20PM", "Lunch With Steve", 189)]] 

¡Gracias!

Answer 1

Esto se puede resolver usando graph theory. Me gustaría crear una matriz, que contiene los elementos ordenados por hora de inicio y hora de finalización de las horas de inicio iguales: (añadido algunos más artículos para el ejemplo):

no.: id: [ start - end ] type 
--------------------------------------------------------- 
0: 234: [08:00AM - 09:00AM] Breakfast With Mindy 
1: 400: [09:00AM - 07:00PM] Check out stackoverflow.com 
2: 219: [11:40AM - 12:40PM] Go to Gym 
3: 79: [12:00PM - 01:00PM] Lunch With Steve 
4: 189: [12:40PM - 01:20PM] Lunch With Steve 
5: 270: [01:00PM - 05:00PM] Go to Tennis 
6: 300: [06:40PM - 07:20PM] Dinner With Family 
7: 250: [07:20PM - 08:00PM] Check out stackoverflow.com 

Después de eso me gustaría crear una lista con la matriz sin . del menor elemento que podría ser el siguiente artículo posible. Si no hay un siguiente punto, se añade -1:

0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 
1 | 7 | 4 | 5 | 6 | 6 | 7 | -1 

Con esa lista, es posible generar un directed acyclic graph. Cada vértice tiene una conexión a los vértices a partir del siguiente elemento. Pero para los vértices donde ya hay vértices entre ellos, no se hace ningún borde. Trataré de explicar con el ejemplo. Para el vértice 0, el próximo elemento es 1. Entonces se hace un borde 0 -> 1. El siguiente ítem de 1 es 7, eso significa que el rango para los vértices que están conectados desde el vértice 0 es ahora de 1 to (7-1). Como el vértice 2 está en el rango de 1 a 6, se crea otro borde 0 -> 2 y el rango se actualiza a 1 to (4-1) (porque 4 es el siguiente ítem de 2). Debido a que el vértice 3 está en el rango de 1 a 3, se crea un borde más 0 -> 3. Esa fue la última borde para vertice 0. que tiene que ser continuado con todos los vértices que conducen a un gráfico tal:

Hasta ahora nos encontramos en O (n). Después de eso, todas las rutas se pueden encontrar usando un algoritmo tipo depth first search y luego eliminar los tipos duplicados de cada ruta. Para ese ejemplo, hay 4 soluciones, pero ninguna de ellas tiene todos los tipos porque no es posible en el ejemplo hacer Go to Gym, Lunch With Steve y Go to Tennis.

También esta búsqueda de todas las rutas tiene la peor complejidad de caso de O (2 ⁿ). Por ejemplo, el siguiente gráfico tiene 2 ^n/2 rutas posibles desde un vértice de inicio hasta un vértice final.

example graph2 http://web.archive.org/web/20120103133636/http://img295.imageshack.us/img295/2848/cal.gif

No se podría hacer un poco más de optimización, como la fusión de algunos vértices antes de buscar todos los caminos. Pero eso no siempre es posible. En el primer ejemplo, los vértices 3 y 4 no se pueden fusionar aunque sean del mismo tipo. Pero en el último ejemplo, los vértices 4 y 5 se pueden fusionar si son del mismo tipo. Lo que significa que no importa qué actividad elijas, ambas son válidas. Esto puede acelerar el cálculo de todas las rutas de forma espectacular.

tal vez hay también una forma inteligente para considerar tipos duplicados anteriores para eliminarlos, pero peor de los casos sigue siendo O (2 ⁿ) si desea que todos los caminos posibles.

EDIT1:

Es posible determinar si hay conjuntos que contienen todos los tipos y conseguir un t menos una de estas soluciones en tiempo polinómico. Encontré un algoritmo con el peor tiempo posible de O (n) y O (n) espacio. Tomaré un nuevo ejemplo que tiene una solución con todos los tipos, pero es más complejo.

no.: id: [ start - end ] type 
--------------------------------------------------------- 
0: 234: [08:00AM - 09:00AM] A 
1: 400: [10:00AM - 11:00AM] B 
2: 219: [10:20AM - 11:20AM] C 
3: 79: [10:40AM - 11:40AM] D 
4: 189: [11:30AM - 12:30PM] D 
5: 270: [12:00PM - 06:00PM] B 
6: 300: [02:00PM - 03:00PM] E 
7: 250: [02:20PM - 03:20PM] B 
8: 325: [02:40PM - 03:40PM] F 
9: 150: [03:30PM - 04:30PM] F 
10: 175: [05:40PM - 06:40PM] E 
11: 275: [07:00PM - 08:00PM] G 

1.) Contar los diferentes tipos en el conjunto de elementos.Esto es posible en O (nlogn). Es 7 para ese ejemplo.

2.) Cree una n * n-matrix, que representa qué nodos pueden alcanzar el nodo real y cuáles se pueden alcanzar desde el nodo real. Por ejemplo, si la posición (2,4) se establece en 1, significa que hay una ruta desde el nodo 2 al nodo 4 en el gráfico y (4,2) también se establece en 1, porque se puede llegar al nodo 4 desde el nodo 2 Esto es posible en O (n). Para el ejemplo de la matriz que se vería así:

111111111111 
110011111111 
101011111111 
100101111111 
111010111111 
111101000001 
111110100111 
111110010111 
111110001011 
111110110111 
111110111111 
111111111111 

3.) Ahora que tenemos en cada fila, que los nodos se puede llegar. También podemos marcar cada nodo en una fila que aún no está marcada, si es del mismo tipo que un nodo al que se puede llegar. Establecemos las posiciones de la matriz de 0 a 2. Esto es posible en O (n). En el ejemplo no hay manera desde el nodo 1 al nodo 3, pero el nodo 4 tiene el mismo tipo D como el nodo 3 y hay un camino desde el nodo 1 al nodo 4. lo que obtener esta matriz:

111111111111 
110211111111 
121211111111 
120121111111 
111212111111 
111121020001 
111112122111 
111112212111 
111112221211 
111112112111 
111112111111 
111111111111 

4.) Los nodos que aún contienen 0 (en las filas correspondientes) no pueden formar parte de la solución y podemos eliminarlos del gráfico. Si hubo al menos un nodo para eliminar, comenzamos nuevamente en el paso 2.) con el gráfico más pequeño. Debido a que eliminamos al menos un nodo, tenemos que volver al paso 2.) a lo sumo n veces, pero lo más frecuente es que esto ocurra pocas veces. Si no quedan 0 en la matriz, podemos continuar con el paso 5.). Esto es posible en O (n). Por ejemplo, no es posible construir una ruta con el nodo 1 que también contenga un nodo con tipo C. Por lo tanto, contiene un 0 y se elimina como el nodo 3 y el nodo 5. En el siguiente ciclo con el nodo 6 más pequeño y el nodo 8 será eliminado.

5.) Cuente los diferentes tipos en el conjunto restante de elementos/nodos. Si es más pequeño que el primer recuento, no hay solución que pueda representar todos los tipos. Así que tenemos que encontrar otra manera de obtener una buena solución . Si es lo mismo que el primer recuento, ahora tenemos un gráfico más pequeño que todavía contiene todas las soluciones posibles. O (nlogn)

6.) Para obtener una solución elegimos un nodo de inicio (no importa cuál, porque todos los nodos que quedan en el gráfico son parte de una solución). O (1)

7.) Eliminamos todos los nodos que no pueden ser alcanzados desde el nodo elegido. O (n)

8.) Creamos una matriz como en el paso 2.) y 3.) para ese gráfico y eliminamos los nodos que no pueden alcanzar nodos de ningún tipo como en el paso 4.). O (n)

9.) Elegimos uno de los siguientes nodos del nodo que elegimos antes y continuamos con 7.) hasta que estamos en un nodo final y el gráfico solo tiene una ruta.

De esta manera también es posible obtener todas las rutas, pero eso aún puede ser exponencial. Después de todo, debería ser más rápido que encontrar soluciones en el gráfico original.

Answer 2

Como usted está buscando todos los horarios posibles, creo que la mejor solución que encontrará será una simple búsqueda exhaustiva.

Lo único que puedo decir algorítmicamente es que su estructura de datos de listas de cadenas es bastante terrible.

La implementación depende en gran medida del idioma, por lo que ni siquiera creo que el pseudocódigo tenga sentido, pero intentaré dar los pasos para el algoritmo básico.

1. sobresalen de los primeros n elementos de un mismo tipo y las puso en la lista.

2. Para cada elemento de la lista, agréguelo a la programación.

3. Apague los próximos n elementos del mismo tipo de la lista.

4. Para cada artículo que comienza después de que termina el primer artículo, ponga en la lista. (Si ninguno, falla)

5. Continúe hasta que finalice.

parte más difícil es decidir exactamente cómo construir las listas/recursividad por lo que es más elegante.

Answer 3

Yo usaría un Interval Tree para esto.

Después de compilar la estructura de datos, puede iterar cada evento y realizar una consulta de intersección. Si no se encuentran intersecciones, se agrega a su horario.

Answer 4

búsqueda exhaustiva Sí podría ser una opción:

inicializar horarios parciales con las tareas más tempranas que se superponen (por ejemplo 9-9,30 y 9,15-9,45)

foreach horario parcial generado hasta ahora generar una lista de nuevas planificaciones parciales que se agregan a cada plan parcial la tarea más antigua que no se solapa (genera más de una en caso de vínculos)

recurre con nuevas planificaciones parciales

En su caso initlialisation produciría solamente (8-9 breakfast)

Después de la primera iteración: (8-9 brekkie, 11.40-12.40 gym) (sin ataduras)

Después de la segunda iteración: (8-9 brekkie, 11.40-12.40 gym, 12.40-1.20 lunch) (sin lazos de nuevo)

Se trata de un árbol de búsqueda , pero es codicioso. Deja fuera posibilidades como saltarse el gimnasio e ir a un almuerzo temprano.

Answer 5

Hmmm, esto me recuerda una tarea en la universidad, describiré lo que puedo recordar El tiempo de ejecución es O (n * logn) que es bastante bueno.

Ésta es una approuch codiciosos .. voy a afinar su solicitud ABIT, dime si me equivoco .. algorithem debe devolver el subconjunto de tareas MAX no chocan (en términos de longitud total? O cantidad de actividades ?supongo longitud total)

Me gustaría primero ordenar la lista por los tiempos de acabado (tiempo de primer mínimo de acabado, de último máximo) = O (nlogn)

Find_set(A): 
    G<-Empty set; 
    S<-A 
    f<-0 
    while S!='Empty set' do 
    i<-index of activity with earliest finish time(**O(1)**) 
    if S(i).finish_time>=f 
     G.insert(S(i)) \\add this to result set 
     f=S(i).finish_time 
    S.removeAt(i) \\remove the activity from the original set 
    od 
    return G 

Run análisis de tiempo: inicial orden: nlogn cada iteración O (1) * n = O (n)

Total O (nlogn) + O (n) ~ O (nlogn) (bueno, dada la debilidad de notación O para representar la complejidad real en pequeño números ... pero a medida que crece la escala, este es un buen algo)

Disfrútalo.

Actualización:

Ok, parece que he leído mal el mensaje, puede utilizar alternativamente programación dinámica para reducir el tiempo de funcionamiento, hay una solución en link text página 7-19.

necesita ajustar el algoritmo un poco, primero debe construir la tabla, entonces puede obtener todas las variaciones de ella bastante fácil.