En todo momento hay grandes telescopios apuntando al cielo nocturno, pues siempre es de noche en algún lugar del planeta. Escrutan Betelgeuse, que, según se dice, estaría a punto de explotar; buscan exoplanetas, fotografían nebulosas e incluso agujeros negros. ¡Y su tiempo es valioso! Cada observación solo puede realizarse en una ventana temporal propicia, por lo que hay que elegir qué observaciones efectuar cada noche y en qué momento exacto. A continuación, en el esquema de la izquierda, aparece un catálogo de once observaciones. Cada una está representada por una duración (rectángulo negro) y un intervalo temporal posible. Debajo se indica la planificación de observaciones del telescopio elaborada por los astrofísicos, que incluye nueve de ellas repartidas en dos noches. El telescopio apenas tendrá tiempo muerto al pasar de una a otra.
Problemas de asignación -----------------------
Pero ¿se puede mejorar y observar una estrella más en dos noches? Para el equipo de astrofísica, hay mucho en juego, ¡pues un telescopio se alquila por noche! ¿Es esta la mejor planificación, la mejor combinación entre todas las posibles? ¿Cómo saberlo, cuando el catálogo de estrellas del Instituto de Planetología y Astrofísica de Grenoble (Isère) contiene cientos de miles de objetivos? El análisis combinatorio estudia colecciones, a menudo finitas, de objetos que cumplen determinadas propiedades. Enumerar todas esas colecciones o exhibir la «mejor» son cuestiones combinatorias.
Leonhard Euler planteó en 1779 un célebre problema combinatorio: considerando seis regimientos de seis oficiales de rangos distintos, ¿es posible colocar a los treinta y seis oficiales en un cuadrado de 6 por 6 de modo que no haya dos oficiales del mismo rango ni del mismo regimiento en cada fila y columna? El problema es sencillo de expresar, y su dificultad suele deberse al excesivo número de combinaciones que hay que evaluar para determinar la correcta. Se trata de limitar en lo posible esta explosión combinatoria, pero incluso los problemas más sencillos superan las capacidades humanas. Por tanto, el ordenador es una herramienta indispensable para la resolución, al menos desde 1953, si creemos a Harold William Kuhn (1925 − 2014), inventor del método húngaro para el problema de asignación. ¡El propio ordenador no puede explorar el árbol de todas las combinaciones posibles sin una buena dosis de anticipación (look-ahead ) y un buen análisis de la exploración ya realizada (look-back)!