À chaque instant, de grands télescopes sont tournés vers le ciel nocturne, car il fait toujours nuit quelque part sur la planète. Ils scrutent Bételgeuse qui, dit-on, serait sur le point d’exploser, ils cherchent des exoplanètes, photographient des nébuleuses, et même des trous noirs. Et leur temps est précieux ! Chaque observation ne peut se faire que dans une fenêtre de temps propice et il faut dès lors choisir quelles observations effectuer chaque nuit et à quel moment précis. Un catalogue de onze observations figure ci-dessous, schéma de gauche. Chacune est représentée par une durée (rectangle noir) et un intervalle temporel possible. Au-dessous est précisé le planning d’observation du télescope mis au point par les astrophysiciens et incluant neuf d’entre elles sur deux nuits. Il n’y a presque pas de temps mort pour le télescope, qui va passer de l’une à l’autre.
Problèmes d’affectation -----------------------
Mais peut-on faire mieux et observer une étoile de plus en deux nuits ? L’enjeu est de taille pour l’équipe d’astrophysique, car un télescope se loue à la nuit ! Est-ce le meilleur planning, la meilleure combinaison parmi tous les possibles ? Comment savoir, quand le catalogue d’étoiles à l’Institut de planétologie et d’astrophysique de Grenoble (Isère) comporte des centaines de milliers de cibles ? L’analyse combinatoire étudie les collections (souvent finies) d’objets qui respectent certaines propriétés. Dénombrer toutes ces collections ou exhiber la « meilleure » sont des questions combinatoires.
Un problème combinatoire célèbre a été posé par Leonhard Euler en 1779 : en considérant six régiments de six officiers de rangs distincts, est-il possible de placer les trente-six officiers dans un carré de 6 par 6 de telle sorte qu’il n’y ait pas deux officiers de même rang ou de même régiment dans chaque ligne et colonne ? Le problème est simple à exprimer et sa difficulté vient souvent du trop grand nombre de combinaisons à évaluer pour pouvoir déterminer la bonne. Il s’agit de limiter autant que possible cette explosion combinatoire, mais même les problèmes les plus simples sont au-delà des capacités humaines. L’ordinateur est donc un outil indispensable de la résolution, au moins depuis 1953 si on en croit Harold William Kuhn (1925 − 2014), l’inventeur de la méthode hongroise pour le problème d’affectation. L’ordinateur lui-même ne peut explorer l’arbre de toutes les combinaisons possibles sans une bonne dose d’anticipation (look-ahead ) et une bonne analyse de l’exploration déjà effectuée (look-back) !