Les fêtes approchant, voici l’occasion de faire un petit billet de Noël.  Est-ce que vous savez comment le Père-Noël arrive à visiter toutes les maisons en une seule nuit ? Il a un secret, bien caché : il a embauché une équipe de lutins Data Scientists.

Pas le temps de lire ? Retrouvez cet article en podcast

Le problème du voyageur de commerce

Le Père-Noël est tous les ans confronté au même problème : comment visiter toutes les maisons en un minimum de temps ? Considérant que le Père-Noël vole à vitesse constante sur son traîneau, et qu’il vole en ligne droite, cela revient pour lui à chercher le trajet le plus court possible qui lui permet de relier toutes les maisons. Et ce problème, c’est un cas d’école : le problème du voyageur de commerce.

Le problème du voyageur de commerce est un problème classique, posé en 1832, qui consiste à trouver le plus court chemin qui passe par un ensemble de points. La résolution de ce problème a des applications concrètes, par exemple pour la planification des tournées de bus, ou la création des pistes sur les cartes électroniques. On l’utilise même en astronomie, pour observer le plus d’étoiles possible tout en limitant les mouvements nécessaires du télescope !

Solutions au problème

Alors que l’énoncé du problème est simple, sa résolution est très complexe, et plusieurs approches sont possibles. Si l’on veut obtenir la solution exacte au problème, l’approche la plus directe consiste à tester toutes les combinaisons de chemins, et de choisir au final le chemin le plus court. Sauf que le nombre de chemins possibles pour un nombre N de villes est N! . N!, c’est ce qu’on appelle factoriel de N. Par exemple, 5! = 1x2x3x4x5, et 10! = 1x2x3x..x10. On arrive vite sur des très grands nombres. Grands comment ? Très grands. 20! est du même ordre de grandeur que le nombre de grains de sables sur Terre. 42!, c’est environ le nombre d’atomes qui composent la Terre.

Il existe d’autres algorithmes pour trouver une solution exacte au problème, mais cela prend du temps. En 2006, un algorithme a permis de trouver le plus court chemin entre 85900 points. La puissance de calcul nécessaire était telle qu’il aurait fallu à un ordinateur de bureau 136 ans pour trouver la solution.

Comme il est très difficile de trouver une solution exacte au problème, on se contente souvent de calculer des solutions approximatives, qui sont très satisfaisantes. Une solution approximative permet de trouver un des plus courts chemins. Pas forcément le plus court, mais un des plus courts.

Une des procédures que je préfère est une vraie recette de Noël. Mais avant le repas, offrons nous une petite balade champêtre.

Activité de Noël, l’escalade de colline.

L’escale de colline (hill climbing) est une technique de résolution de problème.

Cette technique s’appelle l’escalade de colline parce que quand on cherche à maximiser un résultat, le graphique de tous les résultats possibles forme une petite bosse, une colline, et on cherche à atteindre le sommet de cette colline.

Comment ça se passe :

  1. Vous êtes à un endroit.
  2. Vous avancez d’un pas dans une direction aléatoire.
  3. Si vous êtes à une altitude supérieure à celle où vous étiez avant, vous restez là.
  4. Sinon vous reculez d’un pas pour revenir à la position d’avant.
  5. Vous recommencez jusqu’à ce que vous n’arriviez plus à augmenter l’altitude. Vous êtes au sommet de la colline.

Quand le Père-Noël choisit son trajet, il utilise le même principe :

  1. On commence par choisir un trajet au hasard entre toutes les villes.
  2. Ensuite, on modifie un petit peu le trajet, au hasard. (on dit qu’on crée un chemin voisin)
  3. Si le nouveau trajet est meilleur (plus court) que le précédent, alors on garde le nouveau trajet.
  4. Si le nouveau trajet est moins bon (plus long) que le précédent, on garde l’ancien
  5. On continue comme ça jusqu’à ce que l’on arrive plus à améliorer le résultat.

Cette technique a un inconvénient. Imaginez que vous vous trouviez dans une zone où il y a plusieurs collines, de tailles différentes, et votre but est d’atteindre le sommet de la plus grande colline, ce qu’on appelle le maximum global. Que se passe-t-il quand vous arrivez en haut de la plus petite colline ? Vous êtes coincé. Peu importe où vous regardez, vous n’arriverez pas à grimper plus haut en avançant d’un pas. Vous avez atteint ce qu’on appelle un maximum local.

 

Le maximum local, c’est bien mais ce n’est pas assez. L’atteinte du maximum global demande un peu de cuisine : le recuit simulé.

Recette de Noël : le recuit simulé

Pourquoi on appelle ça le recuit ? L’histoire est intéressante. Cela vient de la métallurgie. Quand on veut refroidir une pièce qui vient d’être usinée, il arrive parfois que le refroidissement ne permette pas au matériau d’acquérir la meilleure structure. Donc à la place de ça, on refroidit le matériau, et de temps en temps on le réchauffe un peu (on le recuit) ce qui permet au matériau d’acquérir une structure optimale.

Le détail de la recette du recuit est vraiment compliqué, réservé aux chefs étoilés. Mais le principe est très accessible. Imaginons que nous sommes dans la même configuration que toute à l’heure, avec 3 collines de tailles différentes.

  1. Vous êtes à un endroit.
  2. Vous avancez d’un pas dans une direction aléatoire.
  3. Si vous êtes à une altitude supérieure à celle où vous étiez avant, vous restez là.
  4. Sinon vous reculez d’un pas pour revenir à la position d’avant. Mais de temps en temps, vous décidez de quand même rester où vous êtes pour voir ce que ça donne à partir de là. C’est ça le recuit. Pause casse-croûte.
  5. Vous recommencez jusqu’à ce que vous n’arriviez plus à augmenter l’altitude. Vous êtes au sommet de la plus haute colline, et vous avez atteint le maximum global.

Le recuit, c’est la procédure qui permet de choisir à quel moment on décide de rester où l’on est, même si on est un petit peu descendu le long de la colline.

Quand le Père-Noël choisit son trajet, il fait des pauses recuisson :

  1. On commence par choisir un trajet au hasard entre toutes les villes.
  2. Ensuite, on modifie un petit peu le trajet, au hasard.
  3. Si le nouveau trajet est meilleur (plus court) que le précédent, alors on garde le nouveau trajet.
  4. Si le nouveau trajet est moins bon (plus long) que le précédent, on garde l’ancien. Mais de temps en temps on garde quand même le nouveau mauvais trajet, pour voir où ça va nous mener.
  5. On continue comme ça jusqu’à ce que l’on arrive plus à améliorer le résultat.

Magie de Noël : les lutins ont des super pouvoirs.

Le super pouvoir des lutins du Père-Noël chargés d’organiser la tournée, c’est l’algorithmique. Leur truc à eux, c’est de prendre un problème super complexe à résoudre, et d’établir une procédure (un algorithme) composée d’étapes simples. Ils tirent ce pouvoir de décennies de recherche en algorithmique, en algèbre, en théorie des graphs, en thermodynamique, etc. C’est de la Science. Ce n’est que de la Science.

Mais quand la Science permet au Père Noël de réussir sa tournée, je ne sais pas vous, mais moi je trouve ça un peu magique 😉

Retrouvez une démonstration dans la vidéo ci-dessous :