Si vous deviez me demander où mon obsession pour les voyages en voiture a commencé, je dois dire qu'elle a probablement commencé peu de temps après que ma femme et moi avons conduit l'I-40 de Blacksburg, VA, à Albuquerque, NM, pour commencer mon premier emploi. école. Peut-être y avait-il quelque chose à voir le paysage changeant et à visiter de nouveaux endroits que j'ai trouvé passionnant. Bien que, pour être honnête, cela soit probablement dû à une contrainte de "terminer l'itinéraire" et de conduire le reste de la I-40 aux deux extrémités. Je vais faire un compromis et dire que c'était un peu des deux.
Au départ, mon fétichisme du road trip se concentrait principalement sur le voyage sur toutes les principales autoroutes américaines (celles qui se terminaient par un 0 ou un 5), vu que j'en avais déjà presque terminé une. Cependant, en parcourant divers livres de voyage, j'ai découvert que la communauté des road trip avait tendance à rejeter les autoroutes comme des avenues de commerce et d'"activité" générale, préférant plutôt le rythme plus calme et légèrement plus lent des autres grandes routes américaines : l'autoroute américaine. système. La cartographie de plusieurs de ces autoroutes a déclenché l'excitation de nouveaux lieux et paysages. Mon nouveau rêve était de voyager sur toutes les autoroutes américaines majeures, c'est-à-dire toutes celles avec des désignations à deux chiffres qui étaient encore actives, la seule exception étant l'autoroute 101 en Californie.
The stuff dreams are made of... (image from Wikipedia: https://commons.wikimedia.org/wiki/File:Map_of_current_US_Routes.svg)The stuff dreams are made of... (image from Wikipedia: https://commons.wikimedia.org/wiki/File:Map_of_current_US_Routes.svg)The stuff dreams are made of... (image from Wikipedia: https://commons.wikimedia.org/wiki/File:Map_of_current_US_Routes.svg)The stuff dreams are made of... (image from Wikipedia: https://commons.wikimedia.org/wiki/File:Map_of_current_US_Routes.svg)L'étoffe dont sont faits les rêves... (image de Wikipédia : https://commons.wikimedia.org/wiki/File:Map_of_current_US_Routes.svg)
Depuis que j'ai commencé mon poste récemment en tant que testeur de statisticien de recherche chez JMP , j'en ai appris plus sur le logiciel que je n'aurais jamais cru possible. J'ai été surpris de la rapidité avec laquelle j'ai appris le langage de script JMP (bien que j'apprenne certainement encore JSL), ce qui m'a ouvert encore plus de possibilités. Mais, une fois que j'ai découvert que le glisser déposer Générateur de graphiques avait la capacité de tracer des cartes ? ! Eh bien, vous pouvez probablement deviner où cela se passe (si le titre n'était pas un cadeau mort).
Après avoir surmonté mon excitation initiale, il y a eu un moment de scepticisme. Pourriez-vous réellement tracer un road trip avec Graph Builder ? Je savais que vous pouviez tracer des régions, mais qu'en est-il des lignes et des routes ? Eh bien, je suis heureux de dire qu'après avoir passé peut-être plus de temps que je ne veux l'admettre, la réponse est OUI ! Ce n'est pas Google Maps ou AAA Trip Tik, mais je pense que ça vaut vraiment le coup d'œil.
Tracer un chemin
Donc, la première question à laquelle il fallait répondre était quel genre de road trip cela allait-il être ? Eh bien, mon rêve était de voyager sur toutes les autoroutes américaines, alors pourquoi ne pas faire un voyage qui a fait exactement cela ! Concrètement, l'objectif serait le suivant :
Trouvez un chemin à travers le système d'autoroutes américaines qui relie toutes les principales autoroutes américaines actives.
Alors que mon perfectionniste intérieur rechignerait à la possibilité de ne pas parcourir chaque kilomètre de chaussée qui constituait une autoroute particulière, un compromis devait être fait, et cela constituerait toujours un grand défi dans tous les cas. Mais avant, quelques règles de base :
- L'objectif est de voyager uniquement sur les autoroutes américaines autant que possible. C'est-à-dire que j'aimerais passer directement d'une autoroute à une autre sans avoir à emprunter une route non routière entre les deux, dans la mesure du possible.
- L'autoroute doit être actuellement active (désolé, Route 66ers) et servir de membre principal du système d'autoroute (désignation à deux chiffres, à l'exception de 101)
- Chaque autoroute ne serait empruntée qu'une seule fois.
Cela semble assez simple, non? La première étape consistait à compiler une base de données des intersections d'autoroutes, montrant quelles autoroutes étaient reliées à quelles autres autoroutes et les emplacements de ces intersections. J'ai passé beaucoup de temps à essayer de trouver une telle base de données prête à l'emploi, mais pas de chance. J'ai donc décidé de créer le mien dans un tableau de données.
Example of the process I used to get the coordinates for each intersection. A true labor of love.Example of the process I used to get the coordinates for each intersection. A true labor of love.Example of the process I used to get the coordinates for each intersection. A true labor of love.Example of the process I used to get the coordinates for each intersection. A true labor of love.Exemple du processus que j'ai utilisé pour obtenir les coordonnées de chaque intersection. Un vrai travail d'amour.
Il convient de mentionner que souvent, les autoroutes se croisent plusieurs fois ou même se déroulent simultanément. J'ai seulement enregistré la première intersection qui s'est produite en suivant une autoroute du nord ou de l'est au sud ou à l'ouest, imprégnant mon réseau d'un biais directionnel inhérent. En fait, c'est exactement ce que je construisais : un réseau de "nœuds" de l'autoroute américaine basé sur leurs "bords" d'intersection. Une fois ce réseau terminé, l'objectif serait alors de trouver un chemin à travers le réseau qui connecte chaque nœud sans qu'aucun nœud ne se répète dans le chemin (si possible).
Pour ceux qui connaissent la théorie des graphes, cela peut donner l'impression que je travaille avec le fameux "problème du voyageur de commerce". Et vous auriez presque raison. Le voyageur de commerce est en fait un cas particulier de ce qu'on appelle un Chemin hamiltonien , qui est un chemin qui relie chaque nœud sans répétitions (à ne pas confondre avec un Chemin eulérien , qui est un chemin qui utilise chaque arête du réseau sans répétition et est associé au célèbre Problème du pont de Koenigsburg ). Ce qui fait du voyageur de commerce un cas particulier, c'est le fait que les arêtes ont des poids (par exemple, le temps ou la distance), et il y a donc la condition supplémentaire que le chemin doit minimiser le poids total. Fait amusant : Le chemin hamiltonien tire son nom de William Rowan Hamilton, qui travaillait à trouver un chemin reliant tous les sommets d'un dodécaèdre. À un moment donné, il a prétendu que les sommets étaient des villes célèbres et il cherchait un "tour du monde". J'ai l'impression que nous nous serions bien entendus.
Traditional example of a Hamiltonian path on a dodecahedron (image by Christoph Sommer published to Wikipedia: https://commons.wikimedia.org/wiki/File:Hamiltonian_path.svg)Traditional example of a Hamiltonian path on a dodecahedron (image by Christoph Sommer published to Wikipedia: https://commons.wikimedia.org/wiki/File:Hamiltonian_path.svg)Traditional example of a Hamiltonian path on a dodecahedron (image by Christoph Sommer published to Wikipedia: https://commons.wikimedia.org/wiki/File:Hamiltonian_path.svg)Traditional example of a Hamiltonian path on a dodecahedron (image by Christoph Sommer published to Wikipedia: https://commons.wikimedia.org/wiki/File:Hamiltonian_path.svg)Exemple traditionnel d'un chemin hamiltonien sur un dodécaèdre (image de Christoph Sommer publiée sur Wikipedia : https://commons.wikimedia.org/wiki/File:Hamiltonian_path.svg)
Ce chemin hamiltonien est exactement ce que je cherchais ! Puisqu'il s'agissait d'un objet bien connu, il devrait y avoir un algorithme efficace pour le trouver, n'est-ce pas ? Eh bien, pas si vite. Vous voyez, le problème de trouver un chemin hamiltonien à travers un graphe arbitraire est ce qu'on appelle un problème NP-difficile. C'est juste un terme fantaisiste pour dire qu'il est très facile de vérifier si un chemin est hamiltonien, mais assez difficile de trouver un tel chemin pour tous sauf quelques exceptions. En d'autres termes, il n'y a pas d'algorithme rapide général pour trouver un chemin hamiltonien pour chaque situation. Donc, encore une fois, je me suis lancé seul pour voir si je pouvais développer un algorithme pour mon cas.
J'ai d'abord commencé par convertir mon réseau en tableau associatif en JSL puis s'est penché sur un algorithme simple pour trouver un chemin dans un petit réseau écrit par un collègue . Cet algorithme utilise une recherche en profondeur d'abord, qui consiste à commencer à un nœud du réseau et à suivre la première connexion que vous rencontrez pour chaque nœud par la suite jusqu'à ce que vous manquiez de connexions, auquel cas vous revenez à un autre nœud non connecté et continuer. Bien que cet algorithme ne garantisse pas un chemin hamiltonien, j'ai découvert que je pouvais toujours l'utiliser pour essayer de m'en approcher. L'algorithme que j'ai dérivé en adaptant cette approche est le suivant :
Localisateur de chemin proche de l'hamiltonien
- Fournissez un nœud de départ.
- Pour chaque nœud de connexion, exécutez une recherche en profondeur en un seul passage (c'est-à-dire, ne remontez pas une fois que vous manquez de connexions, même si vous en avez manqué) et voyez quel nœud a le chemin le plus long.
- Ajoutez ce nœud de connexion au chemin.
- Répétez les étapes 2 et 3 jusqu'à ce qu'il n'y ait plus de nœuds disponibles à ajouter au chemin.
L'idée derrière cet algorithme est que l'ajout de nœuds avec le chemin potentiel le plus long devrait, en théorie, vous rapprocher beaucoup plus d'un chemin global à travers le réseau en réduisant le risque qu'un chemin se termine tôt.
Combler les lacunes
Maintenant que je peux obtenir un chemin initial, l'étape suivante consistait à déterminer comment "greffer" tous les nœuds manquants qui ont été laissés de côté lors de l'exécution initiale. Je suis venu avec trois méthodes possibles:
- Choisissez le premier nœud manquant, forcez-le à se connecter à sa première connexion possible dans le chemin actuel et redémarrez la recherche à partir de là - Bien sûr, vous n'êtes pas obligé de choisir le premier nœud manquant (en fait, il n'y a peut-être pas nécessairement de « premier » nœud manquant), mais l'idée serait la même. Essentiellement, cette approche "greffe" un nœud manquant dans le chemin, puis prétend qu'il a atteint ce point pendant l'exécution de l'algorithme (la partie de redémarrage). Le seul risque de cette approche est que vous puissiez vous retrouver pris dans une boucle sans fin ; en raison des limites de l'algorithme de recherche de base, vous n'atteindrez peut-être jamais un chemin qui intègre chaque nœud. Vous pouvez ajuster cette approche en essayant d'inclure plus de sélections aléatoires dans la recherche de chemin, mais il n'y a toujours aucune garantie de trouver un chemin plus rapidement.
- S'il n'y a qu'un seul nœud manquant, explorez toutes les combinaisons possibles pour l'adapter au chemin actuel et renvoyez celui qui le fait avec succès - Essentiellement, cette approche revient simplement à une recherche exhaustive sur tous les chemins possibles qui incluent le nœud manquant compte tenu de la disposition actuelle du chemin. Le seul risque de cette approche est si le nœud manquant a beaucoup de connexions ; le nombre de possibilités peut rapidement dépasser les limites de calcul de votre machine. C'est pourquoi je ne l'ai utilisé que si le nœud manquant avait moins de 10 connexions. Bien sûr, vous pouvez également utiliser cette approche s'il y a plus d'un nœud, mais chacun a très peu de connexions.
- Utilisez un peu d'huile de coude et entrez manuellement les nœuds manquants dans le chemin - Cela peut sembler une échappatoire, mais cela peut être nécessaire et pas nécessairement si difficile si l'algorithme a du mal à trouver un chemin. C'est aussi un bon moyen d'intégrer le jugement d'un expert dans le parcours ; peut-être qu'un chemin plus pittoresque pourrait être trouvé avec une petite contribution de l'humain qu'une solution purement informatique. L'exemple parfait de l'homme et de la machine travaillant en harmonie vers un objectif commun.
En cherchant mon chemin hamiltonien, j'ai fini par utiliser chacune de ces approches au moins une fois. Dans le prochain poste , vous pouvez voir les fruits de mon travail.
