Mi horario se ve más o menos así:
Los cuadros oscuros indican que tengo clase y los cuadros claros que estoy en mi cubículo, las columnas son los días de la semana y las filas las horas del día laboral. El pequeño problema que se me ocurrió es este: ¿cómo reportarles a mis alumnos los horarios en los que estoy disponible, con la menor cantidad de "bloques" posible? Con bloque quiero decir, por ejemplo, "los lunes y martes estoy disponible de tal a tal hora".
En términos geométricos, lo anterior equivale a cubrir totalmente un polígono rectangular que se forma con los cuadros blancos con la menor cantidad de rectángulos posible, pero sin que se traslapen. Si uno no pone mucho empeño en obtener la mejor solución posible, podrían salirle unos nueve rectángulos (o ya de plano los 25 cuadrados si se tiene demasiada flojera para pensar). Después de repasarlo un rato obtuve una configuración con 6 rectángulos.
Esta solución, de hecho, es óptima (aunque no única). Resulta que existen algoritmos polinomiales para resolver el problema, y el que usé para generar esta solución es de complejidad $O(n^{5/2})$ y fue desarrollado por T. Ohtsuki. En un artículo de Sahni y Wu pueden encontrar más detalles; lo que más me gustó del problema es descubrir que también se relaciona con el diseño de circuitos integrados.
No hay comentarios.:
Publicar un comentario