如果你要問我對公路旅行的痴迷是從哪裡開始的，我不得不說這可能是在我和妻子駕駛 I-40 從弗吉尼亞州布萊克斯堡到新墨西哥州阿爾伯克基開始我畢業後的第一份工作後不久開始的學校。 也許看到不斷變化的風景和參觀新的地方讓我感到興奮。 不過，老實說，這更有可能是因為“完成路線”並在兩端駕駛 I-40 的其餘部分。 我會妥協並說兩者兼而有之。
最初，我對公路旅行的迷戀主要集中在穿越美國所有主要州際公路（那些以 0 或 5 結尾的州際公路），因為我幾乎已經完成了一個。 然而，當我仔細閱讀各種旅遊書籍時，我發現公路旅行社區傾向於將州際公路視為商業和全方位“繁忙”的途徑，而不是更喜歡美國其他主要公路更安靜、更慢的步伐：美國高速公路系統。 繪製出其中幾條高速公路引發了新地方和新景觀的興奮。 我的新夢想是在美國的每條主要高速公路上行駛，也就是說，所有那些仍然有效的兩位數名稱的高速公路，唯一的例外是加利福尼亞州的 101 號高速公路。
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)夢想是由...組成的 （圖片來自維基百科：https://commons.wikimedia.org/wiki/File:Map_of_current_US_Routes.svg）
自從最近擔任研究統計學家測試員以來，我在JMP , 我對軟件的了解比我想像的要多。 我對自己學習 JMP 腳本語言的速度如此之快感到驚訝（儘管我肯定還在學習 JSL），這為我打開了更多的可能性。 但是，一旦我發現拖放圖形生成器有能力繪製地圖？！ 好吧，你可能會猜到這是怎麼回事（如果標題不是一個死贈品）。
在克服了最初的興奮之後，出現了片刻的懷疑。 您真的可以使用 Graph Builder 規劃公路旅行嗎？ 我知道您可以繪製區域，但是線條和道路呢？ 好吧，我很高興地說，在花費了比我願意承認的更多的時間之後，答案是肯定的！ 它不是谷歌地圖或 AAA Trip Tik，但我認為它絕對值得一看。
鋪設道路
所以第一個要回答的問題是這將是怎樣的公路旅行？ 好吧，我的夢想是走遍美國的每條高速公路，所以為什麼不來一次這樣的旅行呢！ 具體來說，目標如下：
找到一條通過美國高速公路系統的路徑，連接每條活躍的美國主要高速公路。
雖然我內心的完美主義者會猶豫不走構成特定高速公路的每一英里人行道的可能性，但必須做出一些妥協，無論如何這仍然是一個巨大的挑戰。 但首先，一些基本規則：
- 目標是盡可能多地在美國高速公路上行駛。 也就是說，我想直接從一條高速公路到另一條高速公路，而不必在可能的情況下在兩者之間走非高速公路。
- 高速公路必須當前處於活動狀態（抱歉，66 人公路）並作為高速公路系統的主要成員（兩位數名稱，101 除外）
- 每條高速公路只能行駛一次。
看起來很簡單，對吧？ 第一步是編制高速公路交叉口數據庫，顯示哪些高速公路與哪些其他高速公路相連，以及這些交叉口的位置。 我花了很多時間試圖找到這樣一個現成的數據庫，但沒有這樣的運氣。 所以我決定自己製作一個數據表。
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.我用來獲取每個交叉點坐標的過程示例。 真正的愛的勞動。
值得一提的是，高速公路經常會多次相交，甚至並發。 我只記錄了從北或東向南或西沿高速公路行駛時發生的第一個交叉路口，從而使我的網絡具有固有的方向偏差。 事實上，這正是我正在構建的：基於交叉點“邊緣”的美國高速公路“節點”網絡。一旦這個網絡完成，目標就是找到一條通過網絡的路徑，連接每個節點，路徑中沒有重複的節點（如果可能）。
對於那些熟悉圖論的人來說，這聽起來像是我在處理著名的“旅行商問題”。你幾乎是對的。 旅行推銷員實際上是所謂的一個特例哈密頓路徑，這是一條連接每個節點的路徑，沒有重複（不要與歐拉路徑，這是一條不重複地使用網絡中每條邊的路徑，並且與著名的相關聯柯尼斯堡橋問題). 使旅行推銷員成為特例的是邊緣具有權重（例如，時間或距離），因此存在路徑必須最小化總權重的附加條件。 有趣的事實：哈密頓路徑得名於 William Rowan Hamilton，他正在努力尋找連接十二面體所有頂點的路徑。 有一次，他假裝頂點是著名的城市，他正在尋找“世界之旅”。我有一種感覺，我們會相處得很好。
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)十二面體上哈密頓路徑的傳統示例（Christoph Sommer 的圖片發佈到維基百科：https://commons.wikimedia.org/wiki/File:Hamiltonian_path.svg）
這條哈密頓路徑正是我一直在尋找的！ 既然是眾所周知的對象，應該有一個高效的算法來找到它吧？ 好吧，沒那麼快。 你看，通過任意圖找到哈密頓路徑的問題就是所謂的 NP-hard 問題。 這只是一個奇特的術語，它表示很容易驗證一條路徑是否為哈密頓量，但除了少數例外情況外，要找到這樣一條路徑非常困難。 換句話說，沒有通用的快速算法可以為每種情況找到哈密頓路徑。 因此，我再次獨自出發，看看是否可以為我的案例開發一個算法。
我首先開始將我的網絡轉換為 JSL 中的關聯數組然後調查同事寫的一個在小型網絡中尋找路徑的簡單算法. 該算法使用深度優先搜索，它涉及從網絡中的一個節點開始，然後跟隨您遇到的每個節點的第一個連接，直到您用完所有連接，此時您返回到另一個非連接節點並繼續前進。 雖然這個算法不能保證哈密頓路徑，但我發現我仍然可以用它來嘗試接近。 我採用這種方法得出的算法如下：
近哈密頓路徑查找器
- 提供起始節點。
- 對於每個連接節點，運行單通道深度優先搜索（即，一旦用完連接就不要返回，即使您錯過了一些連接）並查看哪個節點具有最長路徑。
- 將該連接節點添加到路徑中。
- 重複步驟 2-3，直到沒有更多可用節點添加到路徑中。
該算法背後的想法是，從理論上講，添加具有最長潛在路徑的節點應該可以通過降低路徑提前終止的風險，使您更接近整個網絡的整體路徑。
填補空白
現在我可以獲得初始路徑，下一步是確定如何“移植”初始運行中遺漏的任何缺失節點。 我想出了三種可能的方法：
- 選擇第一個丟失的節點，強制它連接到當前路徑中最早可能的連接，然後從那裡重新開始搜索——當然，您不必選擇第一個缺失節點（事實上，可能不一定有“第一個”缺失節點），但思路是一樣的。 本質上，這種方法將缺失的節點“嫁接”到路徑中，然後假裝它在算法運行期間到達了這一點（重啟部分）。 這種方法的一個風險是您可能會發現自己陷入了一個永無止境的循環；由於基本搜索算法的局限性，您可能永遠無法到達包含每個節點的路徑。 您可以通過嘗試在路徑搜索中包含更多隨機選擇來調整此方法，但仍然不能保證更快地找到路徑。
- 如果只有一個缺失節點，探索將其擬合到當前路徑的每一種可能組合，並返回成功這樣做的那個 -從本質上講，這種方法簡單地相當於對所有可能的路徑進行詳盡搜索，其中包括給定當前路徑佈局的缺失節點。 這種方法的一個風險是如果丟失的節點有很多連接；可能性的數量可能會很快超過您機器的計算限制。 這就是為什麼我只在丟失的節點少於 10 個連接時才使用它。 當然，如果有多個節點，但每個節點的連接很少，你也可以使用這種方法。
- 使用一些肘部潤滑脂並手動將缺失的節點輸入到路徑中 –這似乎是一種逃避，但如果算法很難找到路徑，這可能是必要的，而且不一定那麼困難。 這也是將專家判斷納入路徑的好方法；與純基於計算機的解決方案相比，通過人工的少量輸入，也許可以找到一條風景更優美的路徑。 人與機器為實現共同目標而和諧工作的完美典範。
在尋找我的哈密頓路徑時，我實際上最終至少使用了這些方法中的每一種。 在下一篇，你可以看到我的勞動成果。
