Plus court chemin : comment éviter l’explosion des choix ?

Intervenant 10:00

Bienvenue dans le podcast du magazine Tangente. Bon, commençons avec un truc un peu fou. Si l'objectif, c'est de voyager vers l'ouest le plus rapidement possible, la meilleure stratégie absolue, c'est parfois de grimper dans un train à grande vitesse qui part d'abord droit vers l'est.

Intervenant 20:15

Ah oui, c'est un paradoxe formidable ça !

Intervenant 10:17

Complètement absurde dit comme ça, non ? Mais en fait, notre perception du temps de trajet est systématiquement faussée par notre perception de la géométrie.

Intervenant 20:26

Mais c'est tellement vrai. Sur une carte, on a tous ce réflexe. On trace une ligne droite imaginaire. La distance physique, elle nous saute aux yeux.

Intervenant 10:34

Oui, le chemin le plus court.

Intervenant 20:36

Exactement. Sauf que le temps, lui, s'écoule selon des règles bien plus subtiles. C'est dicté par la topologie, les modes de transport et les fameuses connexions.

Intervenant 10:45

Et c'est exactement le cœur de notre exploration d'aujourd'hui. On se retrouve tous, un jour ou l'autre, face au plan tentaculaire d'un réseau de métro ou devant une immense carte routière à chercher le meilleur chemin.

Intervenant 20:56

La fameuse question de tous les jours.

Intervenant 10:58

La question paraît toute bête. Comment aller d'un point A à un point B le plus vite possible ? Faut-il prendre cette fameuse autoroute tracée en bleu qui fait un énorme détour ? Ou privilégier la petite route départementale toute droite dessinée en rouge ?

Intervenant 21:12

Et le truc, c'est que chaque tronçon a ses propres règles. Une petite ligne droite, sur la carte, ça peut très bien représenter un chemin de montagne super rockeyeux où l'on avance à 2 km par heure.

Intervenant 11:23

L'enfer quoi !

Intervenant 21:24

Carrément ! Tandis qu'une immense courbe géométrique peut être une voie express totalement dégagée. En fait, la vraie géographie, c'est celle du temps, pas celle de l'espace.

Intervenant 11:33

Ce qui nous amène à la mission de notre décryptage du jour. Quand on ouvre une application de navigation sur un téléphone, on rentre une destination et paf ! En une fraction de seconde, l'écran affiche le trajet parfait.

Intervenant 21:46

C'est presque magique.

Intervenant 11:47

Mais grave, comment nos machines, nos ordinateurs, font-ils pour s'y retrouver et extraire ce trajet idéal sans se perdre instantanément dans une infinité de détours possibles ?

Intervenant 21:58

Eh bien, derrière cette magie apparente qui tient dans la poche, il y a un cadre mathématique fascinant. Cette simple question de notre quotidien cache en réalité l'un des défis les plus vertigineux de la science informatique.

Intervenant 12:11

Ah oui, le fameux monstre théorique.

Intervenant 22:13

C'est ça. Contourner ce que l'on appelle l'explosion combinatoire. C'est un mur que les mathématiciens ont dû apprendre à contourner, sous peine de voir nos ordinateurs calculer dans le vide jusqu'à la fin des temps.

Intervenant 12:23

Simplement lister absolument toutes les routes possibles entre le départ et l'arrivée, calculer le temps pour chacune d'entre elles et juste garder la plus courte.

Intervenant 22:32

C'est ce qu'on appelle l'approche de la force brute. C'est le tout premier réflexe quand on cherche à résoudre un problème d'algorithmique. Ça paraît logique ? Oui. Imaginons un labyrinthe géant. La force brute s'est décidé de tester chaque couloir, de dérouler un fil d'Ariane, d'aller jusqu'au bout, de revenir et d'essayer le suivant. Un par un, sans réfléchir ? Exactement. Mais regardons les chiffres pour comprendre pourquoi ça casse. Plaçons-nous au point de départ, l'origine de notre carte. À ce premier carrefour, il y a généralement, disons, au moins trois routes possibles.

Intervenant 13:03

D'accord, on a nos trois routes de départ, on en choisit une et on avance jusqu'au croisement suivant.

Intervenant 23:08

C'est ça. Et à ce nouveau croisement, pour continuer à avancer sans faire demi-tour, on se retrouve avec, au minimum, deux nouvelles options.

Intervenant 13:16

Et ça se démultiplie du

Intervenant 23:17

coup. À chaque fois qu'on touche une intersection, le nombre de chemins possibles se multiplie. C'est le principe classique de la croissance exponentielle. Au premier carrefour, on multiplie par trois, puis par deux, puis par deux.

Intervenant 13:28

Donc, si je te suis, les mathématiques nous disent que pour un trajet traversant un certain nombre de points, le nombre de chemins possibles grimpe à une vitesse affolante.

Intervenant 23:37

Exactement.

Intervenant 13:38

Mais attends, sur une application GPS, le trajet le plus rapide n'a pas forcément besoin de traverser beaucoup d'intersections si on cherche justement à faire au plus vite.

Intervenant 23:49

Et c'est là que notre intuition géométrique nous trahit encore. On pourrait se dire, limitons l'ordinateur aux chemins qui font très peu d'étapes.

Intervenant 13:57

Bah oui, ça paraît être un bon

Intervenant 23:59

filtre. Mais rappelle-toi notre fameux train qui part vers l'est pour aller à l'ouest. Le chemin le plus rapide implique parfois un immense détour sur des voies très rapides. Donc, le chemin idéal pourrait théoriquement traverser un très très grand nombre de carrefours.

Intervenant 14:12

Ah ouais, l'ordinateur ne sait pas à l'avance combien d'étapes compte le trajet gagnant.

Intervenant 24:16

C'est tout à fait ça. Il doit donc chercher les chemins à deux étapes, puis ceux à trois étapes, à quatre étapes, jusqu'à presque tous les points de la carte.

Intervenant 14:24

Si ma carte contient 100 intersections, l'ordinateur doit tester les chemins qui font jusqu'à 98 ou 99 étapes. Mais ça fait combien de combinaisons au total ça ?

Intervenant 24:35

C'est là qu'on heurte le mur de plein fouet. La formule mathématique pour additionner tous ces chemins possibles dépend des puissances de 2. Le nombre de chemins passant par k points est d'au moins 2 puissance k.

Intervenant 14:46

Ah d'accord, il faut tout additionner !

Intervenant 24:48

Exactement. On additionne 2 à la puissance 1, plus 2 à la puissance 2, plus 2 puissance 3, et ainsi de suite, jusqu'à 2 puissance n-2. Et ça, le total mathématique de cette série, c'est 2 à la puissance n-1, le tout, moins 1.

Intervenant 15:02

Concrètement, ça veut dire quoi dans le monde physique ? Si on prend cette carte de 100 intersections, enfin 100 carrefours, c'est rien du tout. C'est un minuscule village de campagne.

Intervenant 25:11

Eh bien, pour un si petit village de 100 points, si l'on demandait à l'ordinateur le plus puissant du monde actuel d'énumérer et de comparer chaque chemin possible un par un, il n'aurait pas encore terminé aujourd'hui s'il avait commencé ses calculs au moment du Big Bang.

Intervenant 15:29

Pardon ! L'âge de l'univers pour traverser un village de 100 rues.

Intervenant 25:34

C'est ça, l'explosion combinatoire. L'énumération exhaustive par la force brute est une impasse totale, une impossibilité stricte dans notre réalité physique.

Intervenant 15:44

Ah ouais, c'est un truc de fou ! D'accord, donc la méthode naïve nous amène directement à l'apocalypse mathématique. Comment on survit à ça ? Puisque mon téléphone me donne le trajet en un dixième de seconde, c'est bien qu'on a trouvé une astuce pour ne pas calculer jusqu'à la fin des temps.

Intervenant 25:56

Pour survivre, il faut ruser.