の以前の投稿、私はすべての主要な米国の高速道路を横断するロードトリップマップを作成する計画を立てました. ネットワークをセットアップする方法と、パスを見つけるために使用したアルゴリズムについて説明しました。 この投稿では、私が見つけた結果の道筋と、最終的なロードトリップでどのように絞り込んだかを紹介します.
検索アルゴリズムを初めて実行する前に、ネットワークの簡単な概要を作成して、パスを見つけるのに役立つ追加の制約があるかどうかを確認しました。 結局のところ、いくつかありました：
- ハイウェイ 3 は、他の 2 つのハイウェイ (ハイウェイ 2 とハイウェイ 4) とのみ交差します。 これは、シーケンス 2-3-4 または 4-3-2 のいずれかがパスの固定部分になることを意味していました。
- ハイウェイ 48 は、他の 2 つのハイウェイ (ハイウェイ 33 とハイウェイ 11) とのみ交差します。 これは、シーケンス 33-48-11 または 11-48-33 のいずれかがパスの固定部分になることを意味していました。
- ハイウェイ 57 は、技術的にはハイウェイ 83 としか接続していません。 その終点はメキシコ国境にあり、州間高速道路 35 号線はサン アントニオに向かいます。 しかし、それはハイウェイ 90 にかなり近かったので、ハイウェイ 90 に接続することは非常に魅力的でした。 でもルールはルールでしょ？ … 言って、そうじゃない？ジョン・サルそちら側？！ うん、あっち！… そうではありません？... 確信してるの？... 男、私はそれが彼だと断言できた. とにかく、私が言ったように、Hwy 57 は Hwys 83 と 90 のみに接続しているため、83-57-90 または 90-57-83 のシーケンスがパスの固定部分になることを意味します。
- 最後に、ハイウェイ 46 は他の 2 つのハイウェイ (ハイウェイ 1 とハイウェイ 9) にのみ接続します。 ただし、これらの「2 つの」交差点は実際には 1 つの交差点にすぎないため、これは興味深いケースです。 この交差点がある場所 (ニュージャージー州パリセイズ パーク) では、ハイウェイ 1 とハイウェイ 9 が同時に走っています。 したがって、これは、1-46、9-46、46-9、または 46-1 のいずれかがパス上の固定点になることを意味します。 さらに、これは、パスがハイウェイ 46 で開始または終了することも意味していました。
ラウンド1：検索！
これらの制約を慎重にアルゴリズムに組み込んだ後、Hwy 46 からパスを開始し、アルゴリズムを実行することにしました。 取り残された高速道路がいくつかあったので、ギャップを埋める方法の方法 1 を使用してそれらを元に戻しました (「移植と再試行」アプローチ)。 3回リトライしたら…成功!! 図 1 は、この最初の試みの生の出力を示しています。
Figure 1: Raw output of first attemptFigure 1: Raw output of first attemptFigure 1: Raw output of first attemptFigure 1: Raw output of first attempt図 1: 最初の試行の生の出力これは私の好みには少し不格好すぎたので、Google マップの親切な助けを借りて、いくつかの線に余分なポイントを記入して、もう少し曲率を追加し、実際のルートにより近づけました。 また、Marker Type 列をデータに追加しました。これを使用して、経路上の主要な都市やランドマークを特定できます。 あまりにも多くのマーカーでグラフが混雑しないようにするために、緯度の列をコピーし、主要都市やランドマークに関連付けられていないその列の値を削除し、その列を「Y 軸」として使用するポイントを作成しました (これを行うには、適切なグループの下にある [変数] 矢印を選択します。 JMPグラフビルダー)。 ちなみに、ここで使用している背景地図は、アメリカの州が押し付けられた Street Map ビューです (境界線はデフォルトよりも少し暗い灰色に設定されています)。
このように少し整理すると、図 2 に示すパスが得られます。
Figure 2: Cleaned version of first attemptFigure 2: Cleaned version of first attemptFigure 2: Cleaned version of first attemptFigure 2: Cleaned version of first attempt図 2: 最初の試行のクリーン バージョン
この地図に対するあなたの反応は次のようなものだと想像できます。
- ガァァァァァァァァ!! それは何ですか？！ それは恐ろしいです！ 誰かが 2 歳の子供に先の細いマーカーと描画用のアメリカの地図を渡したようです。
- だから私はあなたがどこから始まりどこで終わるかを理解することができますが、一体どうやってそこにたどり着くのですか? ジョージア州アトランタのスパゲッティ交差点は悪いと思いました…。
- ねえ、あなたは私の状態を完全に見逃していました!! (カリフォルニア州、アリゾナ州、ロードアイランド州、メイン州の居住者から)。
- カナダ経由の旅はどうですか？ （これは簡単です。 豆知識: 国道 2 号線は設計上、東側と西側に分かれています。 そのすべてを横断するには、カナダへの迂回が必要です。 ここに苦情はありません！）。
わかりました、わかりました。その最初の試行にはかなりの問題があることを認めます。 私にとって最も注目に値するのは、いくつかの州を完全に見逃していたという事実でした.これは、国を横断するロードトリップには絶対に適していません. では、なぜこれらの州が除外されたのでしょうか。 さて、その質問に答えるために、私は最初にやるべきことをしました: ネットワークをプロットしてください!!
図 3 は、前回の記事で説明したように私がコンパイルしたハイウェイ ネットワークを示しています。
Figure 3: The highway intersection network visualizedFigure 3: The highway intersection network visualizedFigure 3: The highway intersection network visualizedFigure 3: The highway intersection network visualized図 3: 視覚化された高速道路の交差点ネットワーク
この図から、これらの状態が見落とされた理由が明確にわかります。
- カリフォルニアには交差点はなく、終わりか始まりしかありません (どこかに深い声明があります)。
- メイン州には交差点が 1 つしかなく、Houlton の Hwys 1 と 2 の間にあります。 この交差点は、パス検索で簡単に通過できた可能性があります。
- アリゾナには交差点が 2 つしかありません。ハイウェイ 60 と 95 (左) とハイウェイ 60 と 70 (右)。 前のポイントと同じ理由。
- ロードアイランド州の交差点はハイウェイ 6 と 44 の 1 つだけです。
第2弾：待望の続編！
図 3 から収集した情報が手元にあるので、すべての状態を十分に訪問できるように、さらにいくつかの制約を追加します。
- カリフォルニアを確実に訪れてもらうために、ロサンゼルスから始まる州の海岸のほぼ全体に沿って伸びるハイウェイ 101 からパスを開始することにしました。 パスはハイウェイ 46 で終了する必要があります。
- ハイウェイ 101 の次のハイウェイには 4 つの接続オプションがあります。 このオプションでは、ポートランドを抜けてフッド山に行くことができるため、最初は Hwy 26 から始めることにしました。
- 4-3-2 固定点を拡張して、Hwy 1 を含めるようにしました。 これにより、メイン州が強制的にパスの一部になりますが、Hwy 2 (申し訳ありませんが、カナダ) の延長旅行は許可されなくなりました。
- 60-70 と 93-95 の固定点をパスに追加しました。これにより、最終的にチェーン 93-95-60-70 が発生し、アルゴリズムの性質により、パスの一部がその逆になります。 これにより、アリゾナがパスの一部になり、ラスベガスも一部になるという追加のボーナスがあります。 どういたしまして。
- ハイウェイ 52 と 83 はノースダコタ州マイノットで交差するため、ハイウェイ 52 を 83-57-90 チェーンに追加することも決定しました。 これにより、ノースダコタ州をより広くカバーすることができました。 すべての国が愛を分かち合うべきです。
これらの新しい制約を追加して、アルゴリズムを再実行し、ハイウェイを 1 つだけ除外しました。 そこで、ギャップを埋める方法の方法 2 を使用して、それを元に戻しました (「すべてのオプションを試す」方法)。 いくつかのクリーニングの後、図 4 に示すマップが得られました。
Figure 4: The second attempt at a road tripFigure 4: The second attempt at a road tripFigure 4: The second attempt at a road tripFigure 4: The second attempt at a road trip図 4: ロードトリップの 2 回目の試みまあ、少なくともすべての州は現在、ある程度のカバレッジを持っていますが、まだ少し面倒です. この旅行でまだあまり熱心ではなかったのは、ワイオミング州のループです。 Hwys 87 と 85 は、デンバーから I-25 とほぼ同時に走っていることが判明しました。 また、バーモント州と同様に、ワシントン州はほとんど報道されていないようです。 そこで、さらにいくつかの制約 (Hwy 101 – Hwy 12 スタートへの切り替えを含む) を追加し、図 5 に示すパスを得ました。
Figure 5: Yet another attempt at a road tripFigure 5: Yet another attempt at a road tripFigure 5: Yet another attempt at a road tripFigure 5: Yet another attempt at a road trip図 5: ロードトリップでのさらに別の試み見た目が少し良くなりました。 パスのいくつかの部分とまだ多くの重複がありますが、私の意見では、ラウンド 2 バージョンほど悪くはありません。
したがって、これらの最後の 2 つのパスで「欠落状態」の問題に対処できたようです。 ただし、レイアウトにはまだかなりの狂気があります。 この投稿は順調に進んでいるように感じます。次の投稿では、パスをさらにクリーンアップして最終的なパスを表示するために行った調整について説明します。
私はそれをやった方法を持っています...しかし、それが非常に簡単ではなかったことは保証できます. 基本的に、経路の一部を記入していたので、Google マップを使用して運転時間と距離の両方を計算しました。 累積時間と距離を追跡する他の 2 つの列がありました。 ルートが高速道路に沿っていることを確認する必要があったため、かなり骨の折れる作業でしたが、Google が州間高速道路を利用することを主張し続けたため、州間高速道路の隣をたどるとさらに困難になりました。 最終的に、ラウンド 2 マップの合計距離を計算し、ラウンド 3 マップに近づきました。両方とも 36,000 マイル (約 650 時間の運転時間) のオーダーでした。
ストップ間のユークリッド (カラスが飛ぶとき) の距離を取ることで、合計距離を概算できると思います。 明らかに特定の道路の詳細を見逃しているかもしれませんが、実際に使用するのに十分近いと確信しています。 SAS を使用してそれを行う方法はありますが、JMP でそれを行う方法はまだわかりません。
良くやった！ さまざまなルートの総走行距離が気になります。 それを簡単に計算する方法はありますか？
