algorithm - calendario 2019 con feriados excel
algoritmo del planificador de calendario (5)
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í (no se superponen los tiempos y todos los tipos se representan 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!
Dado que 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 de forma algorítmica es que su estructura de datos de listas de cadenas es bastante terrible.
La implementación depende enormemente del lenguaje, por lo que ni siquiera creo que el pseudocódigo tenga sentido, pero intentaré dar los pasos para el algoritmo básico.
Extraiga los primeros n elementos del mismo tipo y colóquelos en la lista.
Para cada artículo en la lista, agregue ese artículo al conjunto de horarios.
Pop off siguientes n elementos del mismo tipo de lista.
Para cada elemento que comience después de que finalice el primer elemento, ponga en la lista. (Si no hay ninguno, falla)
Continuar hasta terminar.
Lo más difícil es decidir exactamente cómo construir las listas / recursión para que sea más elegante.
Esto se puede resolver utilizando la teoría de grafos . Me gustaría crear una matriz, que contiene los elementos ordenados por hora de inicio y hora de finalización para tiempos de inicio iguales: (se agregaron algunos elementos más al ejemplo):
no.: id: [ start - end ] type
---------------------------------------------------------
0: 234: [08:00AM - 09:00AM] Breakfast With Mindy
1: 400: [09:00AM - 07:00PM] Check out .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 .com
Después de eso crearía una lista con la matriz no. De la menor cantidad de ítems que podría ser el siguiente posible. Si no hay un elemento siguiente, se agrega -1:
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7
1 | 7 | 4 | 5 | 6 | 6 | 7 | -1
Con esa lista es posible generar un gráfico acíclico dirigido . Cada vértice tiene una conexión a los vértices a partir del siguiente elemento. Pero para 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 siguiente elemento es 1. Entonces, un borde se hace 0 -> 1. El siguiente elemento de 1 es 7, lo que significa que el rango para los vértices que están conectados desde el vértice 0 ahora es de 1 to (7-1) . Debido a que 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 elemento de 2). Debido a que el vértice 3 está en el rango de 1 a 3, se crea uno de los bordes 0 -> 3. Ese fue el último borde del vértice 0. Eso debe continuar con todos los vértices que conducen a tal gráfico:
Hasta ahora estamos en O (n 2 ). Después de eso, se pueden encontrar todas las rutas utilizando un algoritmo similar a la primera búsqueda y luego eliminando los tipos duplicados de cada ruta. Para ese ejemplo, hay 4 soluciones, pero ninguna de ellas tiene todos los tipos porque no es posible que el ejemplo Go to Gym , Lunch With Steve y Go to Tennis .
Además, esta búsqueda de todas las rutas tiene una complejidad de O (2 n ). Por ejemplo, el siguiente gráfico tiene 2 n / 2 rutas posibles desde un vértice inicial hasta un vértice final.
Podría hacerse alguna optimización más, como fusionar algunos vértices antes de buscar todas las rutas. Pero eso nunca es posible. En el primer ejemplo, los vértices 3 y 4 no se pueden combinar aunque sean del mismo tipo. Pero en el último ejemplo, los vértices 4 y 5 se pueden combinar 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 todos los caminos dramáticamente.
Tal vez también haya una forma inteligente de considerar los tipos duplicados antes de eliminarlos, pero el peor de los casos es O (2 n ) si desea todas las rutas posibles.
EDIT1:
Es posible determinar si hay conjuntos que contienen todos los tipos y obtener al menos una de estas soluciones en tiempo polinomial. Encontré un algoritmo con un tiempo de peor caso de espacio O (n 4 ) y O (n 2 ). Tomaré un nuevo ejemplo que tiene una solución para 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-matriz, que represente qué nodos pueden alcanzar el nodo real y cuáles pueden ser alcanzados 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 acceder al nodo 4 desde el nodo 2 Esto es posible en O (n 2 ). Para el ejemplo la matriz se vería así:
111111111111
110011111111
101011111111
100101111111
111010111111
111101000001
111110100111
111110010111
111110001011
111110110111
111110111111
111111111111
3.) Ahora tenemos en cada fila, a qué 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 3 ). En el ejemplo, no hay manera de pasar del nodo 1 al nodo 3, pero el nodo 4 tiene el mismo tipo D que el nodo 3 y hay una ruta desde el nodo 1 al nodo 4. Entonces obtenemos 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 ser parte de la solución y podemos eliminarlos del gráfico. Si hubiera al menos un nodo para eliminar, comenzaremos de nuevo 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) como máximo n veces, pero en la mayoría de los casos esto solo ocurrirá algunas veces. Si no quedan 0 en la matriz, podemos continuar con el paso 5.). Esto es posible en O (n 2 ). Para el ejemplo, no es posible construir una ruta con el nodo 1 que también contiene un nodo con el tipo C. Por lo tanto, contiene un 0 y se elimina como el nodo 3 y el nodo 5. En el siguiente bucle con el nodo más pequeño del gráfico 6 y el nodo 8 serán eliminados.
5.) Cuente los diferentes tipos en el conjunto restante de elementos / nodos. Si es más pequeño que el primer conteo, no hay una solución que pueda representar todos los tipos. Así que tenemos que encontrar otra forma de obtener una buena solución. Si es lo mismo que en el primer conteo, ahora tenemos un gráfico más pequeño que aún contiene todas las soluciones posibles. O (nlogn)
6.) Para obtener una solución, seleccionamos 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 a los que no se puede acceder desde el nodo seleccionado. En)
8.) Creamos una matriz como en el paso 2.) y 3.) para esa gráfica y eliminamos los nodos que no pueden alcanzar nodos de ningún tipo como en el paso 4.). O (n 3 )
9.) Elegimos uno de los siguientes nodos del nodo que elegimos antes y continuamos con 7.) hasta que estemos en un nodo final y la gráfica solo tenga un camino a la izquierda.
De esa manera también es posible obtener todos los caminos, pero aún así pueden ser muchos exponenciales. Después de todo, debería ser más rápido que encontrar soluciones en el gráfico original.
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.
Este es un enfoque codicioso. Refinaré un poco su solicitud, dígame si me equivoco. ¿Algorithem debería devolver el subconjunto MAX de tareas no colisionables (en términos de duración total o cantidad de actividades? ¿Supongo que la duración es total?)
Primero ordenaría la lista por los tiempos de finalización (primer tiempo de finalización mínimo, ú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
Análisis del tiempo de ejecución: orden inicial: nlogn cada iteración O (1) * n = O (n)
Total O (nlogn) + O (n) ~ O (nlogn) (bueno, dada la debilidad de la notación O para representar complejidad real en números pequeños ... pero a medida que la escala crece, esto es algo bueno)
Disfrutar.
Actualizar:
Ok, parece que he leído mal la publicación, o puede usar la programación dinámica para reducir el tiempo de ejecución, hay una solución en el enlace de la página 7-19.
necesitas ajustar un poco el algoritmo, primero debes construir la tabla, luego puedes obtener todas las variaciones con bastante facilidad.
Sí, la búsqueda exhaustiva podría ser una opción:
Inicializar programas parciales con las primeras tareas que se superponen (por ejemplo, 9-9.30 y 9.15-9.45)
La programación parcial de Foreach generada hasta ahora genera una lista de nuevas programaciones parciales que se agregan a cada programación parcial la tarea más temprana que no se superpone (genera más de una en caso de empate)
repetir con nuevos horarios parciales
En su caso, la iniciación solo produciría (8-9 breakfast)
Después de la primera iteración: (8-9 brekkie, 11.40-12.40 gym) (sin corbatas)
Después de la segunda iteración: (8-9 brekkie, 11.40-12.40 gym, 12.40-1.20 lunch) (no empates de nuevo)
Esto es una búsqueda de árboles, pero es codicioso. No incluye posibilidades como saltarse el gimnasio e ir a almorzar temprano.
Yo usaría un árbol de intervalo para esto.
Después de crear 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.