Quel est le trajet le plus court en métro?
Vous êtes en vacances dans une métropole, et vous vous trouvez devant un plan de métro. Votre problème est le suivant: quel est l'itinéraire le plus court pour aller de la station de métro où vous vous trouvez à celle où vous souhaitez aller? Sans le savoir, vous vous trouvez face à un problème qui peut être facilement résolu par un…
Lire un résumé →Lorsqu'on cherche le chemin le plus court entre deux stations de métro, une approche naïve testant toutes les combinaisons possibles devient rapidement impraticable : avec 30 stations, un supercalculateur mettrait plus de 2 982 siècles. Heureusement, un algorithme bien plus efficace existe : explorer les stations voisines par « couches » de distance croissante. Cette méthode résout le problème en moins d'une milliseconde même pour un réseau d'un million de stations.
Cependant, la situation change radicalement lorsqu'on souhaite visiter plusieurs lieux à différentes stations : il faut alors trouver l'itinéraire le plus court passant par tous ces points. Ce problème, connu sous le nom de problème du voyageur de commerce, n'admet pas d'algorithme efficace garanti. Cette différence entre problèmes « faciles » (classe P) et « difficiles » (classe NP) soulève l'une des grandes questions de l'informatique et des mathématiques : P est-il égal à NP ? Les chercheurs en doutent et travaillent à développer des approches heuristiques pour obtenir de bonnes solutions aux problèmes difficiles.
Actu