Se dovessi chiedermi dove è iniziata la mia ossessione per i viaggi su strada, direi che probabilmente è iniziata poco dopo che io e mia moglie abbiamo guidato la I-40 da Blacksburg, VA, ad Albuquerque, NM, per iniziare il mio primo lavoro dopo la laurea scuola. Forse c'era qualcosa nel vedere il paesaggio che cambiava e visitare nuovi posti che trovavo eccitante. Anche se, ad essere onesti, probabilmente è più probabile a causa della compulsione a "finire il percorso" e guidare il resto della I-40 su entrambe le estremità. Scendo a compromessi e dico che è stato un po' di entrambi.
Inizialmente, il mio feticismo del viaggio su strada si concentrava principalmente sul viaggio in tutte le principali autostrade statunitensi (quelle che terminavano con uno 0 o un 5), visto che ne avevo già quasi finito uno. Tuttavia, mentre esaminavo vari libri di viaggio, ho scoperto che la comunità dei viaggi su strada tendeva a liquidare le autostrade come vie per il commercio e la "frenesia" a tutto tondo, preferendo invece il ritmo più tranquillo e leggermente più lento delle altre strade principali d'America: la US Highway sistema. La mappatura di molte di queste autostrade ha innescato l'eccitazione di nuovi luoghi e paesaggi. Il mio nuovo sogno era quello di percorrere tutte le maggiori Highway degli Stati Uniti, cioè tutte quelle con designazione a due cifre ancora attive, con l'unica eccezione della Hwy 101 in California.
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)La materia di cui sono fatti i sogni... (immagine da Wikipedia: https://commons.wikimedia.org/wiki/File:Map_of_current_US_Routes.svg)
Da quando ho iniziato la mia posizione di recente come tester statistico di ricerca presso JMP , ho imparato di più sul software di quanto avrei mai creduto possibile. Sono rimasto sorpreso dalla rapidità con cui ho imparato JMP Scripting Language (anche se sicuramente sto ancora imparando JSL), che mi ha aperto ancora più possibilità. Ma, una volta scoperto che il file trascinare e rilasciare Costruttore di grafici aveva la capacità di tracciare mappe?! Bene, probabilmente puoi indovinare dove sta andando (se il titolo non fosse un omaggio morto).
Dopo aver superato il mio entusiasmo iniziale, c'è stato un momento di scetticismo. Potresti davvero pianificare un viaggio su strada con Graph Builder? Sapevo che potevi tracciare regioni, ma per quanto riguarda linee e strade? Bene, sono felice di poter dire che, dopo aver trascorso forse più tempo di quanto non voglia ammettere, la risposta è SÌ! Non è Google Maps o AAA Trip Tik, ma penso che valga sicuramente la pena dare un'occhiata.
Tracciare un sentiero
Quindi la prima domanda a cui rispondere era che tipo di viaggio sarebbe stato? Beh, il mio sogno era percorrere tutte le autostrade degli Stati Uniti, quindi perché non fare un viaggio che facesse proprio questo! Nello specifico, l'obiettivo sarebbe il seguente:
Trova un percorso attraverso il sistema autostradale degli Stati Uniti che collega tutte le principali autostrade statunitensi attive.
Mentre il mio completista interiore si opponeva alla possibilità di non percorrere ogni singolo miglio di marciapiede che componeva una particolare autostrada, era necessario fare qualche compromesso, e questa sarebbe comunque stata una grande sfida. Ma prima, alcune regole di base:
- L'obiettivo è viaggiare il più possibile solo sulle autostrade statunitensi. Cioè, vorrei passare direttamente da un'autostrada all'altra senza dover prendere una strada non autostradale nel mezzo, ove possibile.
- L'autostrada deve essere attualmente attiva (scusate, Route 66ers) e fungere da membro principale del sistema autostradale (designazione a due cifre, eccetto 101)
- Ogni autostrada sarebbe percorsa solo una volta.
Sembra abbastanza semplice, vero? Il primo passo è stato compilare un database di incroci autostradali, mostrando quali autostrade erano collegate a quali altre autostrade e l'ubicazione di questi incroci. Ho passato molto tempo a cercare di trovare un database di questo tipo già pronto, ma senza tanta fortuna. Quindi ho deciso di crearne uno mio in una tabella di dati.
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.Esempio del processo che ho usato per ottenere le coordinate per ogni intersezione. Un vero lavoro d'amore.
Vale la pena ricordare che spesso le autostrade si intersecano più volte o addirittura corrono in concomitanza l'una con l'altra. Ho registrato solo il primo incrocio che si è verificato seguendo un'autostrada da nord o da est a sud o ovest, conferendo alla mia rete un orientamento direzionale intrinseco. In effetti, è esattamente quello che stavo costruendo: una rete di "nodi" della US Highway basata sui loro "bordi" di intersezione. Una volta completata questa rete, l'obiettivo sarebbe quindi trovare un percorso attraverso la rete che collega ogni nodo senza che nessun nodo venga ripetuto nel percorso (se possibile).
Per chi ha familiarità con la teoria dei grafi, potrebbe sembrare che sto lavorando con il famoso "problema del venditore ambulante". E avresti quasi ragione. Il venditore ambulante è in realtà un caso speciale di ciò che è noto come a Cammino hamiltoniano , che è un percorso che collega ogni singolo nodo senza ripetizioni (da non confondere con an percorso euleriano , che è un percorso che utilizza ogni singolo bordo della rete senza ripetizioni ed è associato al famoso Problema del ponte di Koenigsburg ). Ciò che rende il commesso viaggiatore un caso speciale è il fatto che i bordi hanno pesi (diciamo, tempo o distanza), e quindi c'è la condizione aggiuntiva che il percorso deve minimizzare il peso totale. Curiosità: il percorso hamiltoniano prende il nome da William Rowan Hamilton, che stava lavorando alla ricerca di un percorso che collegasse tutti i vertici di un dodecaedro. Ad un certo punto, ha fatto finta che i vertici fossero città famose e stava cercando un "giro del mondo". Ho la sensazione che saremmo andati abbastanza d'accordo.
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)Esempio tradizionale di cammino hamiltoniano su un dodecaedro (immagine di Christoph Sommer pubblicata su Wikipedia: https://commons.wikimedia.org/wiki/File:Hamiltonian_path.svg)
Questo percorso hamiltoniano è esattamente quello che stavo cercando! Dato che era un oggetto ben noto, dovrebbe esserci un algoritmo efficiente per trovarlo, giusto? Beh, non così in fretta. Vedi, il problema di trovare un cammino hamiltoniano attraverso un grafo arbitrario è quello che viene chiamato un problema NP-difficile. Questo è solo un termine di fantasia per dire che è molto facile verificare se un percorso è hamiltoniano, ma piuttosto difficile trovare un tale percorso tranne poche eccezioni. In altre parole, non esiste un algoritmo rapido generale per trovare un percorso hamiltoniano per ogni situazione. Quindi, ancora una volta, mi sono messo da solo per vedere se potevo sviluppare un algoritmo per il mio caso.
Ho iniziato da convertire la mia rete in un array associativo in JSL e poi ha esaminato un semplice algoritmo per trovare un percorso in una piccola rete scritto da un collega . Questo algoritmo utilizza una ricerca in profondità, che implica l'avvio da un nodo nella rete e il seguire la prima connessione che incontri per ogni nodo successivo fino a quando non esaurisci le connessioni, a quel punto torni a un altro nodo non connesso e continuare. Sebbene questo algoritmo non garantisse un percorso hamiltoniano, ho scoperto che potevo ancora usarlo per provare ad avvicinarmi. L'algoritmo che ho derivato adattando questo approccio è il seguente:
Path Finder quasi hamiltoniano
- Fornire un nodo iniziale.
- Per ogni nodo di connessione, esegui una ricerca Depth-First a passaggio singolo (ovvero, non tornare indietro una volta esaurite le connessioni, anche se ne hai perse alcune) e vedi quale nodo ha il percorso più lungo.
- Aggiungi quel nodo di connessione al percorso.
- Ripeti i passaggi 2-3 finché non ci sono più nodi disponibili da aggiungere al percorso.
L'idea alla base di questo algoritmo è che l'aggiunta di nodi con il percorso potenziale più lungo dovrebbe, in teoria, avvicinarsi molto di più a un percorso complessivo attraverso la rete riducendo il rischio che un percorso termini in anticipo.
Colmare le Lacune
Ora che posso ottenere un percorso iniziale, il passaggio successivo è stato determinare come "innestare" eventuali nodi mancanti che sono stati esclusi dall'esecuzione iniziale. Ho pensato a tre possibili metodi:
- Scegli il primo nodo mancante, forzalo a connettersi alla prima connessione possibile nel percorso corrente e riavvia la ricerca da lì: Ovviamente, non devi scegliere il primo nodo mancante (in effetti, potrebbe non esserci necessariamente un "primo" nodo mancante), ma l'idea sarebbe la stessa. Essenzialmente, questo approccio "innesta" un nodo mancante nel percorso e quindi finge che abbia raggiunto questo punto durante l'esecuzione dell'algoritmo (la parte di riavvio). L'unico rischio di questo approccio è che potresti trovarti intrappolato in un ciclo infinito; a causa delle limitazioni dell'algoritmo di ricerca di base, potresti non raggiungere mai un percorso che incorpori ogni singolo nodo. Potresti modificare questo approccio cercando di includere più selezioni casuali nella ricerca del percorso, ma non c'è ancora alcuna garanzia di trovare un percorso più velocemente.
- Se c'è un solo nodo mancante, esplora ogni possibile combinazione per adattarlo al percorso corrente e restituisci quello che lo fa con successo - In sostanza, questo approccio equivale semplicemente a una ricerca esaustiva su tutti i possibili percorsi che includono il nodo mancante dato l'attuale layout del percorso. L'unico rischio di questo approccio è se il nodo mancante ha molte connessioni; il numero di possibilità può superare rapidamente i limiti computazionali della tua macchina. Ecco perché l'ho usato solo se il nodo mancante aveva meno di 10 connessioni. Ovviamente, puoi anche utilizzare questo approccio se ci sono più nodi, ma ognuno ha pochissime connessioni.
- Usa un po' di olio di gomito e inserisci manualmente i nodi mancanti nel percorso: Potrebbe sembrare una scappatoia, ma potrebbe essere necessario e non necessariamente così difficile se l'algoritmo ha difficoltà a trovare un percorso. È anche un buon modo per incorporare il giudizio di esperti nel percorso; forse si potrebbe trovare un percorso più panoramico con un piccolo input da parte dell'umano rispetto a una soluzione puramente basata su computer. L'esempio perfetto di uomo e macchina che lavorano in armonia verso un obiettivo comune.
Nella ricerca del mio percorso hamiltoniano, in realtà ho finito per utilizzare ciascuno di questi approcci almeno una volta. In il prossimo post , puoi vedere i frutti del mio lavoro.
