私のロードトリップへの執着がどこから始まったのかと聞かれたら、それはおそらく、妻と私がバージニア州ブラックスバーグからニューメキシコ州アルバカーキまで I-40 を運転して卒業後すぐに最初の仕事を始めた直後に始まったと言わざるを得ません。学校。 変化する風景を見て、新しい場所を訪れてわくわくする何かがあったのかもしれません。 とはいえ、正直なところ、「ルートを終了」し、I-40 の残りの部分を両端で運転したいという衝動に駆られている可能性が高いです。 私は妥協して、それは両方のビットであったと言います.
当初、私のロードトリップフェチは、主にすべての主要な米国の州間高速道路 (0 または 5 で終わるもの) を旅行することに主に焦点を当てていました。 しかし、私がさまざまな旅行本を熟読していると、ロードトリップのコミュニティは、州間高速道路を商売や万能の「忙しさ」のための道として無視する傾向があり、代わりに、アメリカの他の主要道路である US ハイウェイの静かで少し遅いペースを好むことがわかりました。システム。 これらの高速道路のいくつかを計画することで、新しい場所や風景への興奮が引き起こされました。 私の新しい夢は、米国のすべての主要なハイウェイ、つまり、カリフォルニア州のハイウェイ 101 を除いて、まだ有効な 2 桁の指定があるすべてのハイウェイを旅することでした。
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 Scripting Language の習得の早さに驚きました (確かにまだ JSL を学んでいますが)。 しかし、あることに気づいたら、ドラッグアンドドロップグラフビルダーマップをプロットする能力がありましたか?! まあ、おそらくこれがどこに行くのかを推測できます (タイトルが完全な景品ではなかった場合)。
最初の興奮を克服した後、懐疑的な瞬間がありました。 実際にグラフ ビルダーを使用して遠征を計画できますか? 地域をプロットできることは知っていましたが、線や道路はどうでしょうか? ええと、私が認めるよりもおそらく多くの時間を費やした後、答えはイエスです! Google Maps や AAA Trip Tik ではありませんが、一見の価値があると思います。
パスを敷設する
最初に答えるべき質問は、これはどのようなロードトリップになるのかということでした。 私の夢は、アメリカのすべてのハイウェイを旅することでした。 具体的には、次のような目標になります。
すべてのアクティブな主要な米国高速道路を接続する米国高速道路システムを通るパスを見つけます。
私の内面の完成主義者は、特定の高速道路を構成する舗装を 1 マイルも走らない可能性を恐れていましたが、ある程度の妥協が必要でした。 ただし、最初に、いくつかの基本ルールを示します。
- 目標は、可能な限り米国の高速道路だけを移動することです。 つまり、可能な限り高速道路以外の道路を通らずに、ある高速道路から別の高速道路に直接行きたいと考えています。
- ハイウェイは現在アクティブであり (Route 66ers さん)、ハイウェイ システムのプライマリ メンバー (101 を除く 2 桁の指定) として機能している必要があります。
- 各高速道路は 1 回だけ通行します。
簡単そうに見えますよね？ 最初のステップは、高速道路の交差点のデータベースを作成し、どの高速道路が他のどの高速道路に接続しているか、およびこれらの交差点の位置を示すことでした。 そのような既製のデータベースを探すのにかなりの時間を費やしましたが、そのような運はありませんでした。 そこで、データ テーブルで独自のものを作成することにしました。
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.各交差点の座標を取得するために使用したプロセスの例。 愛の真の労働。
多くの場合、高速道路は互いに複数回交差したり、互いに並行して走ったりすることさえあります。 高速道路を北または東から南または西にたどるときに発生した最初の交差点のみを記録したため、ネットワークに固有の方向性バイアスが吹き込まれました。 実際、これこそまさに私が構築していたものです。交差点の「エッジ」に基づく US ハイウェイの「ノード」のネットワークです。このネットワークが完成したら、次の目標は、(可能であれば) パス内でノードが繰り返されないように、各ノードを接続するネットワークを通るパスを見つけることです。
グラフ理論に詳しい人にとっては、有名な「巡回セールスマン問題」を扱っているように聞こえるかもしれません。そして、あなたはほとんど正しいでしょう。 巡回セールスマンは、実際にはいわゆる特殊なケースです。ハミルトニアン パス、これはすべての単一ノードを繰り返しなしで接続するパスです (と混同しないでくださいオイラー経路、これはネットワーク内のすべてのエッジを繰り返しなしで使用するパスであり、有名なケーニヒスブルク橋問題）。 巡回セールスマンを特別なケースにするのは、エッジに重み (時間や距離など) があるため、パスが総重みを最小化する必要があるという追加の条件があることです。 興味深い事実: ハミルトニアン パスの名前は、12 面体のすべての頂点を結ぶパスの発見に取り組んでいたウィリアム ローワン ハミルトンに由来します。 ある時点で、彼は頂点が有名な都市であるふりをして、「世界ツアー」を探していました。私たちはとてもうまくやっていただろうと感じています。
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)12 面体上のハミルトニアン パスの従来の例 (Wikipedia に公開された Christoph Sommer による画像: https://commons.wikimedia.org/wiki/File:Hamiltonian_path.svg)
このハミルトニアン パスはまさに私が探していたものです。 よく知られた天体だったのですから、それを見つけるための効率的なアルゴリズムがあるはずですよね? まあ、それほど速くはありません。 ご覧のとおり、任意のグラフを通るハミルトニアン パスを見つける問題は、NP 困難な問題と呼ばれるものです。 これは、パスがハミルトニアンであるかどうかを確認するのは非常に簡単ですが、いくつかの例外を除いてそのようなパスを見つけるのは非常に難しいということを言うための派手な用語です。 言い換えれば、すべての状況でハミルトニアン パスを見つける一般的な高速アルゴリズムはありません。 そこで、もう一度、自分の場合のアルゴリズムを開発できるかどうかを調べるために、自分で始めました。
私が最初に始めたのは私のネットワークをJSLの連想配列に変換するそして調べた同僚によって書かれた小さなネットワークでパスを見つけるための単純なアルゴリズム. このアルゴリズムは、深さ優先検索を利用します。これは、ネットワーク内のノードから開始し、接続がなくなるまで、すべてのノードで遭遇する最初の接続をたどります。接続がなくなると、別の非接続ノードに戻り、立ち止まるな。 このアルゴリズムはハミルトニアン パスを保証するものではありませんでしたが、このアルゴリズムを使用して近づけることができることがわかりました。 このアプローチを採用して導き出したアルゴリズムは次のとおりです。
近ハミルトニアン パス ファインダー
- 開始ノードを提供します。
- 接続しているノードごとに、単一パスの深さ優先検索を実行し (つまり、接続を使い果たしたら、接続を逃した場合でも元に戻らないでください)、どのノードが最も長いパスを持つかを確認します。
- その接続ノードをパスに追加します。
- パスに追加できるノードがなくなるまで、手順 2 ～ 3 を繰り返します。
このアルゴリズムの背後にある考え方は、理論的には、潜在的なパスが最長のノードを追加することで、パスが早期に終了するリスクを減らすことで、ネットワーク全体のパス全体に近づけるというものです。
ギャップを埋める
初期パスを取得できるようになったので、次のステップは、初期実行から除外された欠落ノードを「移植」する方法を決定することでした。 私は3つの可能な方法を思いつきました：
- 欠落している最初のノードを選択し、現在のパスで可能な限り早い接続に強制的に接続し、そこから検索を再開します –もちろん、最初の欠落ノードを選択する必要はありません (実際、必ずしも「最初の」欠落ノードがあるとは限りません) が、考え方は同じです。 基本的に、このアプローチは、欠落しているノードをパスに「移植」し、アルゴリズムの実行中 (再起動部分) にノードがこのポイントに到達したように見せかけます。 このアプローチの 1 つのリスクは、終わりのないループに陥る可能性があることです。基本的な検索アルゴリズムの制限により、すべてのノードを組み込んだパスにたどり着けない場合があります。 パス検索により多くのランダムな選択を含めようとすることで、このアプローチを調整できますが、パスがより速く見つかるという保証はまだありません。
- 欠落しているノードが 1 つしかない場合は、それを現在のパスに適合させるすべての可能な組み合わせを調べて、うまく適合したものを返します。本質的に、このアプローチは、現在のパス レイアウトが与えられた場合に欠落しているノードを含むすべての可能なパスを網羅的に検索することになります。 このアプローチの 1 つのリスクは、見つからないノードに多くの接続がある場合です。可能性の数は、マシンの計算限界をすぐに超える可能性があります。 そのため、欠落しているノードの接続が 10 未満の場合にのみ使用しました。 もちろん、複数のノードがあり、それぞれの接続が非常に少ない場合にも、このアプローチを使用できます。
- エルボーグリースを使用して、不足しているノードを手動でパスに入力します –これは警官のように見えるかもしれませんが、アルゴリズムがパスを見つけるのに苦労している場合、必要であり、必ずしもそれほど難しいことではありません. これは、専門家の判断をパスに組み込む良い方法でもあります。おそらく、純粋なコンピューターベースのソリューションよりも、人間からの少しの入力で、より風光明媚なパスが見つかる可能性があります。 共通の目標に向かって調和して働く人間と機械の完璧な例です。
ハミルトニアン パスを検索する際に、実際にこれらの各アプローチを少なくとも 1 回使用することになりました。 の次の投稿、あなたは私の労働の成果を見ることができます。
