1. Inicio
  2. Pregunta y respuesta
  3. Algoritmo/problema de programación

Algoritmo/problema de programación

2009-10-20 13 views
6

Estoy aburrido, y este problema simplemente me persiguió de nuevo. De vuelta en la universidad, siempre me preguntaba cómo programaban los exámenes. La capacidad de programar 10k estudiantes para hacer exámenes en 2 semanas y garantizar que ningún estudiante tendrá un examen en dos períodos consecutivos. Supongo que se aplicará alguna forma de heurística.Algoritmo/problema de programación

Esta noche estoy aburrido, y si me dan las herramientas adecuadas, voy a trabajar en esta noche y hasta el fin de semana

aplausos, dassouki

EDIT 1: I supongo que el supuesto sería que todo lo que sabemos es la siguiente:

  1. número de alumnos y los cursos que están matriculados en cada
  2. Número de puntos del período del examen

Fuente

2009-10-20 dassouki

+0

Si realmente hacen eso, las cosas han cambiado desde que fui a la universidad, definitivamente tuve algunos exámenes durante períodos consecutivos. –

+1

Me temo que todavía se hace a mano en la gran mayoría de los casos. No es que los diez mil estudiantes tengan un conjunto de exámenes completamente diferente, ¿verdad? Probablemente haya unas pocas decenas de "grupos de exámenes", cada uno con hasta cientos de estudiantes. No debería ser un gran problema programarlos a mano si tiene suficiente espacio. – Joren

+0

Fui a la universidad hace unos años. A pesar de que todos nuestros sistemas de programación eran electrónicos, la responsabilidad recaía en el estudiante en conflicto para resolver los horarios conflictivos programados y encontrar un administrador para reprogramarlos. El sistema no tenía inteligencia de programación propia. – ephemient

Respuesta

1

Es caro, pero he visto CPLEX usado para problemas similares.

Fuente

2009-10-20 22:01:45

5

Este es un ejemplo de un problema de satisfacción de restricciones, que es una clase difícil de problemas. Algunos de ellos están en la clase NP. Existen grandes paquetes de software comercial para tratar de resolver problemas como estos (por ejemplo, CPLEX) y, en general, usan algunas matemáticas y mucha heurística.

Fuente

2009-10-20 22:02:30 Peter

+0

Un buen comentario, pero no es exactamente lo que llamo una "respuesta". ¿Tiene alguna sugerencia sobre cómo resolver este problema o recursos sobre el tema? –

1

El problema en realidad puede ser un poco más general que eso. Por ejemplo, en mi escuela, los exámenes están programados para cuando la clase está programada, es decir, todas las clases que se reúnen al mismo tiempo normalmente durante el semestre, tienen un examen programado en un determinado bloque de la semana del examen (no necesariamente el mismo tiempo que la reunión de clase regular, sin embargo). Por lo tanto, los conflictos generalmente no existen, ya que los estudiantes no asistirían a dos clases en el mismo horario de reunión por razones obvias, y por lo tanto no tendrían dos exámenes al mismo tiempo.

Sin embargo, esto significa que entonces todavía necesita programar clases para que no entren en conflicto. :)

Fuente

2009-10-20 22:03:09 Amber

1

Usé el tabu search durante mi maestro. La idea no es demasiado complicado:

  1. inicio de una posible solución (cualquiera) y Pounder del mismo (por ejemplo dar -1000 puntos si un estudiante tiene dos exámenes al mismo tiempo)
  2. cambio de esa solución con sólo cambiando algunas asignaciones y volver a calcular la ponderación
  3. si es mejor que 2. 1. y 2. de repetición comenzando por la raíz como la solución

si está bloqueado, puede "visitar" otras soluciones al hacer cambios importantes a la solución inicial.

Fuente

2009-10-20 22:03:15 Vladimir

7

Sé que esto está fuera de tema para SO, pero mi universidad simplemente programó los exámenes en bloques que coincidían con los tiempos de clase. Entonces, todos los que tenían un MWF de clase a la 1:20 p.m. estaban en un examen el día 15 a la 1:00 p.m. Como no puede tomar dos clases al mismo tiempo, era imposible tener conflictos en los exámenes.

Fuente

2009-10-20 22:04:18

+1

+1 - bien, sin embargo, – Jacob

+0

¡Una buena manera de hacerlo, pero todavía tenían que generar los horarios de clase! –

+2

¡No tendrían que preocuparse por la programación para generar horarios de clases! Si dos clases son al mismo tiempo, no podrá tomarlas ambas. ¡A menos por supuesto que tengas un cambio de tiempo como Hermione! – Hari

1

Cuando estaba en el último año de la universidad, hicimos un proyecto final en nuestra clase de IA similar a este. Escribimos un sistema (apenas) operativo para programar clases en edificios en los momentos apropiados. Ciertas reglas no pueden ser violadas: si el prof. necesitaba un aula multimedia, él consiguió uno. Si era una clase de CS, entonces no debería programarse en el edificio de Arte. Los profesores no deberían tener más de 2 horas entre una clase, etc.

Utilizamos un algoritmo genético.

Fuente

2009-10-22 12:14:23

1

Algunas cosas para simplificar el problema. Probablemente disminuyas el número de "unidades para programar" de decenas de miles a unos cientos, al observar a las personas que realizan los mismos exámenes. Si tiene 300 personas que están sentadas en "Introducción a la informática" y "Matemáticas para estudiantes de CS", puede programar las 300 como una sola unidad, porque todas tendrán las mismas restricciones y usted (probablemente) no deseará las mismas. exámenes que se darán en múltiples máquinas tragamonedas.

Fuente

2009-10-22 12:31:55 Vatine

+1

¿Por qué no solo programar según cada clase? Olvídese de los estudiantes, piense en el nivel de clase. No puede estar en dos lugares a la vez, independientemente de si se trata de un examen o una conferencia. –

+0

La razón principal es que cuando estaba en la universidad, no había nada (excepto tiempo) para evitar que los estudiantes tomaran clases adicionales. Agregue la complicación de volver a tomar un examen fallido más adelante y se encuentra en un mundo de dolor. – Vatine

1

Esta es una aplicación del graph coloring problem. Este problema se puede representar como un gráfico donde cada vértice es un curso y un límite entre dos vértices significa que hay un estudiante común inscripto en ambos cursos. Así que este es un problema de coloración de gráficos donde el número mínimo de intervalos de tiempo es igual al número mínimo de color requerido para colorear los vértices del gráfico de tal manera que no haya dos vértices adyacentes que compartan el mismo color.

Fuente

2014-10-03 23:24:57

Cuestiones relacionadas

 Cuestiones relacionadas