Un problema de horario es un problema de satisfacción o optimización de restricciones en torno a la programación de recursos.
Por ejemplo, una escuela tiene un número fijo de aulas y profesores. Un horario no puede hacer una doble reserva para un profesor o un aula. Entonces, el problema del horario podría ser: dado un conjunto de clases (profesor, tamaño de inscripción, duración) y aulas (tamaño, horas disponibles), ¿hay un horario que acomode todas las clases?
Otras elaboraciones son posibles. Por ejemplo, los estudiantes pueden necesitar tomar un conjunto particular de materias para graduarse, y el horario debe garantizar que esto sea factible. O también podemos tener algunas restricciones suaves en las que nos gustaría satisfacer la mayor cantidad posible, como dejar las horas de almuerzo abiertas, distribuir las clases de manera uniforme o las preferencias de horas de trabajo del profesor. Algunas clases pueden necesitar ser programadas una al lado de la otra, o * no * una al lado de la otra.
- ¿Apache Hadoop es realmente bueno para algoritmos recursivos?
- ¿Qué es un árbol binario desequilibrado y cuáles son sus usos?
- ¿Puede un programa escribir un programa (es decir, el programa x puede identificar un algoritmo para escribir el programa y, a pesar del algoritmo z)?
- ¿Cuál es la intuición de que la factorización no es NP completa?
- ¿Dónde es útil el conocimiento de las estructuras de datos en Swift?
Para ver que tal problema está en NP, podemos observar que la verificación de las restricciones (¡siempre que no sean problemas de decisión complicados!) Se puede realizar en tiempo polinómico. En el nivel más básico, dada una solución, solo necesitamos verificar para cada aula y profesor que no haya doble reserva, y que cada clase fue asignada, para reconocer que la solución es válida. Debido a que la solución se puede verificar en P, el problema de decisión “¿existe una solución” está en NP.
Para demostrar la dureza de NP, una reducción del problema de 3 particiones es suficiente: cree 3 aulas del mismo tamaño y cree una clase por número en el conjunto múltiple, con un profesor por clase.
