Pour faire suite à l’article de la semaine dernière qui vous permettait de connaître le prix moyen de la pinte de bière par pays, voici l’itinéraire le plus court pour visiter tous les pubs du Royaume-Uni !
Entre le Bells But & Ben (à John o ‘Groats) et le Witchball (à Land’s End), soit les pubs le plus au nord et le plus au sud du royaume, il y a une petite trotte. Cette carte vous montre comment les rallier mais en passant par les quelques 24 725 autres pubs existants sur la route ! Ce serait tout de même dommage de passer à coté sans s’arrêter boire un coup.
Mis à part l’intérêt gustatif il y a un intérêt scientifique derrière cette performance : la réponse par les mathématiques computationnelles à une énigme cartographique appelée le problème du voyageur de commerce (TSP en anglais). Supposons en effet que vous soyez représentant et que votre tournée de pas de portes contienne de nombreux points de passage. Quel serait le chemin le plus court en partant de chez vous et en y retournant le soir ? Pour un petit nombre de lieux la solution est généralement assez évidente, mais lorsque la quantité augmente le problème peut vite devenir très complexe. Et puisque les solutions empiriques sont vite dépassées, les scientifiques, toujours en mal de défis, se sont attaqués au problème. Le mathématicien irlandais du 19 e siècle, WR Hamilton a ainsi développé le jeu de l’icosa qui vise à trouver un cycle hamiltonien dans un dodécaèdre: un circuit qui commence et se termine au même point et visite tous les autres points une seule fois.
Le jeu de l’icosa qui vise à trouver un cycle hamiltonien dans un dodécaèdre.
Comme le souligne le mathématicien viennois Karl Menger en 1930, la solution la plus simple consiste à essayer toutes les options. Mais même pour un nombre relativement faible de localités, la quantité de variables est énorme, il existe par exemple plus de 180 000 combinaisons pour seulement 10 villes… La problématique a pourtant de nombreuses applications utiles puisqu’elle permet par exemple au Père Noël d’optimiser sa tournée qui est déjà plutôt longue. Plus prosaïquement elle permet aussi de rechercher les routes les plus efficaces pour les facteurs et livreurs de tous poils. Trouver la route la plus courte entre tous les pubs du Royaume-Uni ne figurait peut-être pas parmi les priorités mais cette question a tout de même été résolue par la faculté de mathématiques de l’Université de Waterloo au Canada.
La carte complète de l’itinéraire, qui comprend quelques traversées en ferry pour relier les îles Hébrides, Orcades et Shetland, l’île de Man et l’Irlande du Nord :
Quelques chiffres à son propos :
- Trouver la réponse manuellement aurait impliqué la vérification d’un nombre de possibilités exprimées par un « 1 » suivi de 100 000 « 0 ». Ce qui fait beaucoup de possibilités.
- Ce travail a été achevé en deux ans. Il s’agit du plus grand TSP routier à avoir été résolu à ce jour, couvrant 100 fois plus d’arrêts que n’importe quel autre exemple similaire.
- Cette petite randonnée optimale qui s’arrête dans chacun des 24 727 pubs et vous ramène chez vous (légèrement éméché et un peu fatigué) fait 45 495,2 km de long.
Vous pouvez consulter la version interactive ici (attention il faut être patient pendant le chargement).
Essayer l’itinéraire complet n’est peut-être pas recommandé, mais vous pouvez zoomer sur certaines zones du pays ou cliquer directement sur les villes répertoriées dans le menu de droite, et planifier votre prochain barathon !
La carte entière représentée avec des marqueurs Google map pour chaque pub donne l’impression que la réflexion inverse (traverser le pays du nord au sud sans croiser un pub) est encore plus difficile…
Source : https://bigthink.com, https://wall.alphacoders.com, Google map.
Guillaume Sciaux – Cartographe indépendant
Leave a Comment