Wenn Sie mich fragen würden, wo meine Besessenheit von Autoreisen begann, müsste ich sagen, dass sie wahrscheinlich kurz nachdem meine Frau und ich die I-40 von Blacksburg, VA, nach Albuquerque, NM, gefahren waren, begann, um meinen ersten Job nach dem Abschluss anzutreten Schule. Vielleicht war es etwas, die sich verändernde Landschaft zu sehen und neue Orte zu besuchen, die ich spannend fand. Um ehrlich zu sein, liegt es wahrscheinlich eher an dem Zwang, „die Route zu Ende zu führen“ und den Rest der I-40 an beiden Enden zu fahren. Ich gehe Kompromisse ein und sage, es war ein bisschen von beidem.
Anfangs konzentrierte sich mein Roadtrip-Fetisch hauptsächlich darauf, alle wichtigen US-Interstates zu bereisen (diejenigen, die mit einer 0 oder einer 5 endeten), da ich bereits eine fast beendet hatte. Als ich jedoch verschiedene Reisebücher las, stellte ich fest, dass die Roadtrip-Community dazu neigte, die Interstates als Alleen für den Handel und allumfassende „Geschäfte“ abzutun und stattdessen das ruhigere, etwas langsamere Tempo der anderen großen Straßen Amerikas vorzog: den US Highway System. Die Kartierung mehrerer dieser Autobahnen löste die Begeisterung für neue Orte und Landschaften aus. Mein neuer Traum war es, alle großen US-Highways zu befahren, also alle mit zweistelligen Bezeichnungen, die noch aktiv waren, mit Ausnahme des Hwy 101 in Kalifornien.
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)Der Stoff, aus dem Träume sind... (Bild aus Wikipedia: https://commons.wikimedia.org/wiki/File:Map_of_current_US_Routes.svg)
Seit ich vor kurzem meine Stelle als Research Statistician Tester bei angetreten habe JMP , ich habe mehr über die Software gelernt, als ich je für möglich gehalten hätte. Ich war überrascht, wie schnell ich die JMP-Skriptsprache gelernt habe (obwohl ich sicherlich noch JSL lerne), was mir noch mehr Möglichkeiten eröffnete. Aber sobald ich entdeckte, dass die Drag-and-Drop Graph-Generator hatte die Fähigkeit, Karten zu zeichnen?! Nun, Sie können wahrscheinlich erraten, wohin das führt (wenn der Titel kein sicheres Zeichen wäre).
Nachdem ich meine anfängliche Aufregung überwunden hatte, gab es einen Moment der Skepsis. Könnten Sie mit Graph Builder tatsächlich einen Roadtrip planen? Ich wusste, dass man Regionen darstellen kann, aber was ist mit Linien und Straßen? Nun, ich freue mich sagen zu können, dass die Antwort, nachdem ich vielleicht mehr Zeit damit verbracht habe, als ich zugeben möchte, JA lautet! Es ist kein Google Maps oder AAA Trip Tik, aber ich denke, es ist definitiv einen Blick wert.
Legen Sie einen Pfad fest
Die erste zu beantwortende Frage war also, was für eine Art Roadtrip soll das werden? Nun, mein Traum war es, jeden US Highway zu befahren, also warum nicht eine Reise machen, die genau das tut! Konkret wäre das Ziel wie folgt:
Finden Sie einen Pfad durch das US-Highway-System, das alle aktiven primären US-Highways verbindet.
Während mein innerer Vervollständiger vor der Möglichkeit zurückschreckte, nicht jeden einzelnen Kilometer des Bürgersteigs zu fahren, der eine bestimmte Autobahn ausmachte, musste ein Kompromiss eingegangen werden, und dies würde in jedem Fall eine große Herausforderung darstellen. Aber zuerst einige Grundregeln:
- Ziel ist es, so viel wie möglich nur auf US Highways zu fahren. Das heißt, ich möchte direkt von einer Autobahn zur anderen fahren, ohne nach Möglichkeit eine Straße nehmen zu müssen, die keine Autobahn ist.
- Die Autobahn muss derzeit aktiv sein (sorry, Route 66ers) und als primäres Mitglied des Autobahnsystems dienen (zweistellige Bezeichnung, außer 101)
- Jede Autobahn würde nur einmal befahren werden.
Scheint einfach genug, oder? Der erste Schritt bestand darin, eine Datenbank mit Autobahnkreuzungen zusammenzustellen, aus der hervorgeht, welche Autobahnen mit welchen anderen Autobahnen verbunden sind und wo sich diese Kreuzungen befinden. Ich habe viel Zeit damit verbracht, eine solche fertige Datenbank zu finden, aber kein Glück. Also beschloss ich, meine eigene in einer Datentabelle zu machen.
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.Beispiel für den Prozess, den ich verwendet habe, um die Koordinaten für jede Kreuzung zu erhalten. Eine wahre Liebesarbeit.
Es ist erwähnenswert, dass Autobahnen sich oft mehrmals kreuzen oder sogar gleichzeitig verlaufen. Ich habe nur die erste Kreuzung aufgezeichnet, die auftrat, wenn ich einer Autobahn von Norden oder Osten nach Süden oder Westen folgte, wodurch mein Netzwerk mit einer inhärenten Richtungsverzerrung versehen wurde. Tatsächlich habe ich genau das gebaut: ein Netzwerk von US-Highway-„Knoten“, basierend auf ihren Kreuzungs-„Kanten“. Sobald dieses Netzwerk vollständig ist, besteht das Ziel darin, einen Pfad durch das Netzwerk zu finden, der jeden Knoten verbindet, ohne dass sich ein Knoten im Pfad wiederholt (wenn möglich).
Für diejenigen, die mit der Graphentheorie vertraut sind, mag dies so klingen, als würde ich mit dem berühmten „Problem des Handlungsreisenden“ arbeiten. Und fast hättest du Recht. Der Handlungsreisende ist eigentlich ein Sonderfall dessen, was man als einen bezeichnet Hamiltonscher Weg , was ein Pfad ist, der jeden einzelnen Knoten ohne Wiederholungen verbindet (nicht zu verwechseln mit einer Eulerscher Weg , das ist ein Pfad, der jede einzelne Kante im Netzwerk ohne Wiederholung nutzt und mit dem Berühmten verbunden ist Brückenproblem Königssburg ). Was den Handelsreisenden zu einem Sonderfall macht, ist die Tatsache, dass die Kanten Gewichte haben (z. B. Zeit oder Entfernung) und daher die zusätzliche Bedingung besteht, dass der Pfad das Gesamtgewicht minimieren muss. Wissenswertes: Der Hamilton-Pfad hat seinen Namen von William Rowan Hamilton, der daran arbeitete, einen Pfad zu finden, der alle Ecken eines Dodekaeders verbindet. Einmal gab er vor, die Scheitelpunkte seien berühmte Städte, und er suchte nach einer „Welttournee“. Ich habe das Gefühl, wir hätten uns ganz gut verstanden.
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)Traditionelles Beispiel eines Hamilton-Pfads auf einem Dodekaeder (Bild von Christoph Sommer veröffentlicht auf Wikipedia: https://commons.wikimedia.org/wiki/File:Hamiltonian_path.svg)
Dieser Hamilton-Pfad ist genau das, wonach ich gesucht habe! Da es sich um ein bekanntes Objekt handelt, sollte es einen effizienten Algorithmus geben, um es zu finden, richtig? Nun, nicht so schnell. Sehen Sie, das Problem, einen Hamilton-Pfad durch einen beliebigen Graphen zu finden, wird als NP-schweres Problem bezeichnet. Dies ist nur ein schicker Begriff, um zu sagen, dass es sehr einfach ist, zu überprüfen, ob ein Pfad hamiltonsch ist, aber ziemlich schwierig, einen solchen Pfad für alle bis auf wenige Ausnahmen zu finden. Mit anderen Worten, es gibt keinen allgemeinen schnellen Algorithmus, um für jede Situation einen Hamilton-Pfad zu finden. Also machte ich mich wieder einmal auf den Weg, um zu sehen, ob ich einen Algorithmus für meinen Fall entwickeln könnte.
Ich fing zuerst an Konvertieren meines Netzwerks in ein assoziatives Array in JSL und dann reingeschaut ein einfacher Algorithmus zum Finden eines Pfades in einem kleinen Netzwerk, der von einem Kollegen geschrieben wurde . Dieser Algorithmus verwendet eine Tiefensuche, bei der Sie an einem Knoten im Netzwerk beginnen und danach für jeden Knoten der ersten Verbindung folgen, auf die Sie stoßen, bis Ihnen die Verbindungen ausgehen. An diesem Punkt kehren Sie zu einem anderen nicht verbindenden Knoten zurück und weitermachen. Obwohl dieser Algorithmus keinen Hamilton-Pfad garantierte, stellte ich fest, dass ich ihn dennoch verwenden konnte, um zu versuchen, ihm nahe zu kommen. Der Algorithmus, den ich abgeleitet habe, um diesen Ansatz anzupassen, lautet wie folgt:
Near-Hamiltonian Path Finder
- Geben Sie einen Startknoten an.
- Führen Sie für jeden Verbindungsknoten eine Single-Pass-Tiefensuche durch (dh gehen Sie nicht zurück, wenn Ihnen die Verbindungen ausgehen, auch wenn Sie einige verpasst haben) und sehen Sie, welcher Knoten den längsten Pfad hat.
- Fügen Sie diesen Verbindungsknoten dem Pfad hinzu.
- Wiederholen Sie die Schritte 2-3, bis keine weiteren verfügbaren Knoten vorhanden sind, die dem Pfad hinzugefügt werden können.
Die Idee hinter diesem Algorithmus ist, dass das Hinzufügen von Knoten mit dem längsten potenziellen Pfad Sie theoretisch einem Gesamtpfad im gesamten Netzwerk viel näher bringen sollte, indem das Risiko einer vorzeitigen Beendigung eines Pfads verringert wird.
Lücken füllen
Jetzt, da ich einen anfänglichen Pfad erhalten kann, bestand der nächste Schritt darin, zu bestimmen, wie alle fehlenden Knoten, die aus dem anfänglichen Lauf ausgelassen wurden, „eingepfropft“ werden können. Mir sind drei mögliche Methoden eingefallen:
- Wählen Sie den ersten fehlenden Knoten aus, zwingen Sie ihn, sich mit seiner frühestmöglichen Verbindung im aktuellen Pfad zu verbinden, und starten Sie die Suche von dort aus neu – Natürlich müssen Sie nicht den ersten fehlenden Knoten auswählen (tatsächlich muss es nicht unbedingt einen „ersten“ fehlenden Knoten geben), aber die Idee wäre die gleiche. Im Wesentlichen „pfropft“ dieser Ansatz einen fehlenden Knoten in den Pfad und gibt dann vor, dass er diesen Punkt während der Ausführung des Algorithmus erreicht hat (der Neustart-Teil). Das einzige Risiko bei diesem Ansatz besteht darin, dass Sie sich in einer Endlosschleife wiederfinden. Aufgrund der Einschränkungen des grundlegenden Suchalgorithmus erreichen Sie möglicherweise nie einen Pfad, der jeden einzelnen Knoten enthält. Sie könnten diesen Ansatz anpassen, indem Sie versuchen, mehr zufällige Auswahlen in die Pfadsuche aufzunehmen, aber es gibt immer noch keine Garantie dafür, dass Sie einen Pfad schneller finden.
- Wenn nur ein Knoten fehlt, untersuchen Sie jede mögliche Kombination, um ihn in den aktuellen Pfad einzufügen, und geben Sie denjenigen zurück, der dies erfolgreich tut – Im Wesentlichen läuft dieser Ansatz einfach auf eine erschöpfende Suche über alle möglichen Pfade hinaus, die den fehlenden Knoten enthalten, wenn das aktuelle Pfadlayout gegeben ist. Das einzige Risiko dieses Ansatzes besteht darin, dass der fehlende Knoten viele Verbindungen hat; Die Anzahl der Möglichkeiten kann schnell die Rechengrenzen Ihrer Maschine überschreiten. Deshalb habe ich es nur verwendet, wenn der fehlende Knoten weniger als 10 Verbindungen hatte. Natürlich könnten Sie diesen Ansatz auch verwenden, wenn es mehr als einen Knoten gibt, aber jeder nur sehr wenige Verbindungen hat.
- Verwenden Sie etwas Ellenbogenfett und geben Sie die fehlenden Knoten manuell in den Pfad ein – Dies mag wie ein Ausweg erscheinen, aber es könnte notwendig und nicht unbedingt allzu schwierig sein, wenn der Algorithmus Schwierigkeiten hat, einen Weg zu finden. Es ist auch eine gute Möglichkeit, Expertenurteile in den Pfad einzubeziehen; vielleicht ließe sich mit etwas menschlichem Input ein landschaftlich reizvollerer Weg finden als eine rein computerbasierte Lösung. Das perfekte Beispiel dafür, wie Mensch und Maschine harmonisch auf ein gemeinsames Ziel hinarbeiten.
Bei der Suche nach meinem Hamilton-Pfad habe ich tatsächlich jeden dieser Ansätze mindestens einmal verwendet. In der nächste Beitrag , Sie können die Früchte meiner Arbeit sehen.
