5月12日、同僚と私は午前中に開業してモスクワの地下鉄に入り、起きずに、地下鉄が閉まる前に現在利用可能な199の駅すべてを訪れました。 なぜこれをすべて行ったのかは完全には不明ですが、どのように起こったのかをお話しします。
ずいぶん前に、一年前、妻がどうにかしてモスクワのすべての地下鉄駅の写真を撮りたいと言ってきたようです。 それから私はそのようなことの下で、あなたがすべてのステーションを訪問することができる最適なルートを計算することができると冗談を言いました。 彼は冗談を言って忘れていましたが、冬にそれを思い出し、それを試してみることにしました。
私が問題を研究していたとき、私はそのアイデア自体はそれほど新しいものではないことを発見しました-ニューヨークの地下鉄では、1966年から同様の競技会が開催されています。 モスクワの地下鉄については、LJユーザーのestrella-de-sur が 6か月前に「すべての駅への一歩」ルールに従って12時間36分（推定時間11時間50分） 運転しました 。 しかし、私たちには別のタスクがありました。各ステーションに出て、可能であれば美しい写真を撮りたかったのです。 これは、ほとんどの場合、次の列車を待つ必要があることを意味しました。 これに基づいて、計算を作成しました。
警告：200ノードで巡回セールスマン問題を解決する方法を知っている場合（遺伝的アルゴリズムの有無にかかわらず）、別の場所で期待される可能性が高いでしょう。 単に投稿をスクロールして、写真を見ることができます。
データを取得する場所
このタスクの最初のステップは、メトログラフ（ノード-駅、エッジ-交差点および遷移）をデジタル化し、その要素にさまざまな有用な情報を追加することでした：駅-地理座標、開始時刻、時刻の異なる列車間隔; rib骨の場合-運搬またはステーション間の移行の時間。
モスクワには多くの駅があります（サラリエボはまだオープンしていませんでしたが、まだ十分でした）。私はこれをすべて自分の手でやりたくありませんでした。 次に、 Yandex.Metroサイトに目を向けました。 開始にはちょうどよかったのですが、このサービスは時間の平均推定値を使用しており、深刻な計算のためには、より正確な情報が必要でした。 それから私はカップルをかなり思い出しました 古代人 人気のある時間測定機能を備えたプログラム-pMetroおよびmMetro-これらは、 誰も知らない場合、デスクトップメトロルート計算機です。 最初のものは2011年に公式に更新されるのをほぼやめ、2番目のものはさらに早くなりましたが、すべては何よりも優れています。
pMetroフォルダー内のファイルの中に、Moscow.pmzが見つかりました。これは、実際には、古風な.ini形式のファイルの束を持つ通常のzipアーカイブであることが判明しました。 ほぼすべての必要な情報がそこに見つかりました（図にはいくつかの最新のステーションがありませんでした）。 このすべての1回限りのパーサーをtsvに積み上げ、行方不明のステーションとステージを手でドブし、 Yandex.Metroでそれらのタイミングを「電話」しました。 ウィキペディアの記事から取った新しいステーションの座標。
最終的にこのスキームは次のようになりました（当然、投影法はメルカトル図法ではありませんが、本質を伝えます）。
（ここではモノレール線も描きましたが、将来的には放棄することになりました）
今、私はこれらすべてを始めようとしなければなりませんでした。
セールスマンのゲノム
そのため、200頂点を超える不完全なグラフのステートメントで古典的な巡回セールスマンの問題を解決する必要がありました。 私たちの先祖の経験は、このタスクがNP完全であり、おそらくトランス計算であることを教えてくれます。 ロシア語に翻訳すると、最初は、おおよそ、すべての可能な答えを整理する以外に、最良の解決策を見つける方法を知らないことを意味し、2番目は、かなり長い時間（数十億年以上）を整理する必要があることを意味します。 しかし実際には、徹底的な検索を慎重に整理して、次第に適切なソリューションを見つけて、「準備ができたら」停止することができます。
続行する前に、健康な人にとって最初の通常の動機は、自分で最適なルートを手動で設定するか、少なくとも大きなストロークでスケッチしてから自動的に終了することです。 しかし、以来 私たちの場合、rib骨の価格はルート内の位置（つまり、時刻）に依存し、51の駅はグラフのかなり密集したセクション（リング内および転送を含む）に位置し、その通過は実質的に入口と出口に依存します常識を使用することはそれほど簡単ではありません。 また、各駅で降りて次の電車を待つかどうかによって、最適なルートが完全に異なる場合があることも興味深いです（異なる路線の電車の間隔は異なるため）。
しかし、続けましょう。 既に述べたように、次第に優れたソリューションを徐々に見つけるように検索を整理することができ、見つかったソリューションが最良であることを保証する必要がなければ、現在の最良の結果が「十分」であると考えるときにいつでも停止できます良い」。 この状況での古代の古典的なアプローチの1つは、 遺伝的アルゴリズムの使用です 。
これは進化論の以前の人気の時代のかなり単純な考えです：各ソリューションを特定のベクトル（「ゲノム」）で記述し、特定のゲノムの品質関数（この場合、ルート全体を完了するのにかかる時間）を定式化し、進化を開始します：ランダムな変異を追加するか、さらには「個人」は自然に交尾します。 ある種の優生学の数千世代-そして私たちは良い準備ができています スーパーマン ルート
しかし、いつものように、悪魔は詳細にあります。 まず、ゲノム内の情報の表示方法を適切に選択する必要があります。 たとえば、ゲノムを、ルートをたどる順番ですべてのステーションの番号を持つベクターにすることができます。 なぜこれが悪いのですか？ 異なる経路のゲノムは異なる長さになります-それらが交差するのは不便です。 そして、ゲノムのランダムな値の中には、多くの無効なルートがあります-すべてのステーションを訪れることを許可しないルートです。 言い換えれば、ゲノム値の空間では、本当に可能性のある候補の集中度は低くなります。つまり、各候補の有効性を個別にチェックし、これに余分な時間を費やす必要があります。
長さ200の順列をゲノムとして宣言する方がはるかに便利です。つまり、 各ステーションが1回だけ発生する、長さ200のこのようなベクトル。 ただし、このアプローチでは、ルートに沿ったステーションが隣接する場合があり、その間に直接接続はありません。 問題ではありません-頂点の各ペア間のグラフに沿った最短ルートを計算することで完全なグラフに移動できます（これは額のO（| V | ^ 3）操作で簡単に実行できますが、この場合はそれほど多くありません）。 この最短ルートは、スケジュールのダイナミクスを考慮して、1日の異なる時間でも異なる場合があることに注意することが重要です。 したがって、間隔スケジュールの各スライスに対してこのようなテーブルを計算することは理にかなっています。
第二に、さまざまな種類の突然変異や交配で遊ぶ必要があります。 ここには科学があまりなく、確固とした経験主義があり、主に一方では急速な収束を確保し、他方では脱出する能力を確保することを目的としています。 進化の行き止まり ローカル最適。 最終的に、私は次の一連の変換を決定しました。
•ランダムゲノムインターバルのランダムシャッフリングは迅速な突然変異ですが、それほどきれいではありません。進化の最終段階では、非常に優れたソリューションを非常によく改善できます。
•ランダムなゲノム間隔の鏡面反射-強い変化（ローカル最適から抜け出す）に役立ち、タスクのコンテキスト内でルートの順序（高品質）を維持する可能性があります
•ゲノム内のランダムな値のX個のペアの順列-良い変異ですが、遅い変異であるため、行き止まりから抜け出すことはできません。
•2つのゲノムの「クロスオーバー」-最初にゲノム上の交点を選択し、そこからゲノムのテールを切り取り、それらを交換します。 その後、間違ったルートを取得できます。したがって、結果を統合し、失われたノードをすべて、たとえばゲノムのランダムな場所に追加します。
合計で、各反復で、最高の個人の特定のサブセットをさまざまな突然変異にさらし、その子孫から新しい世代を形成し、近親交配の犠牲者にならないようにいくつかの完全にランダムなルートを追加します。 デスクトップでpythonスクリプトを使用して、このような50,000世代の進化を計算するには、自宅のデスクトップで平均20分かかります。 そして、待つのがそれほど退屈しないように、あなたはダイナミクスで彼をスパイし、それぞれの最高の個人、例えば100代目を描くことができます。 サイクルの最初の数千世代のお気に入りを示す小さなGIFは次のとおりです。
ルートの一連のステップは、灰色のグラデーションに対応しています。 最初の段階でルートがかなりランダムに変化し、その後すぐに最適なローカルに到達し、微調整が開始されることがわかります。 そして、十分に長く待っていれば（すでにこのgifの外で）、運が良ければ、進化が新しい、より深い最適化にジャンプし、そこで最適化を続ける様子を見ることができます。
重要な点は、独立した最適化の実行により、品質は似ているものの、大幅に異なる答えが得られることがわかった場合、グローバル最適を見つける可能性が低いことを意味します。 しかし、「マルチスタート」で取得しようとするかなり良い近似に満足しています-アルゴリズムを何度も実行し（たとえば、異なる固定ブランチに等しいルートの開始と終了を設定するなど）、観察された結果の最良を選択します。
サスペンスを少し延長するために、私の計算によると、2番目になったルートを示します（明から暗へ）。
そして、最適なルートの期間の最終評価は19時間51分でした。 モスクワの地下鉄の間隔は約20時間であり、列車の間隔に関するすべてのソースデータをアマチュアの測定から取得したことを思い出させてください。 10時間または40時間でルートを取得した場合、すべてが明確になります。 しかし、ここでのマージンはわずか9分であり、未知の（ただし明らかに小さい）エラーがあります。
現実の世界に戻る
この瞬間に、実際にこのルートをテストするという考えが強くなりました。 その時までに、私の友人の何人かはすでに私の奇妙な研究を知っていました。 そのうちの2、3人は十分にクレイジーであることが判明しました。そして今、チームを編成して戦いをテストしました。 しかし、割り当てられた時間に入らないリスクが非常に高かったので、私は最初にいくつかの代替オプションをチェックアウトすることにしました。
オプション「モノレールを返す」。 奇妙な事実：ティミリヤゼフスカヤからメトロでVDNHに移動するには、リングを乗り換えてモノレールに乗り換えて戻るよりも時間がかかりません（pMetroによると、各駅を離れる必要はありません）。 オプションが拒否されました。
オプション「地上輸送を追加」。 アイデアは、地上の公共交通機関で異なる線の端の間を移動しようとすることができるということです。 陸上輸送への移動に関するデータについては、YandexからDima Kryukovに行きました。 地下鉄と地上交通機関間の移動に関する正確な情報はないことが判明しましたが、すべての地上停車地とバス/トロリーバス/路面電車のルートに関する詳細な情報があります。
何もすることはありません。名前で駅と停留所のマッチをする必要がありました。 かなり多くの水中の熊手がありましたが、これはあまりおもしろい話ではありません。 モスクワには、特定の地下鉄駅の「名誉ある」という名前の、正確に999の地上停留所があるとしか言えません（いくつかの「メトロブリッジ」、「メトロデポ」、「メトロタウン」などは含まれません）。 それでも、一部の停留所は、すでに名前が変更された地下鉄駅にちなんで命名されています。 しかし、これらは些細なことです。
ちなみに、見つかったグラウンド「コード」の図です。
しかし、何らかの方法で、出口時間+地上交通+旅行+地下鉄への戻りの推定値を追加すると、これらの「コード」は実際には役に立たないことがわかりました-地下鉄旅行の概念は元の純度を失い、推定利得は15-20分。 オプションが拒否されました。
オプション「タクシーを追加」。 実際、これは以前のバージョンの修正ですが、公共交通機関の代わりに、タクシーの使用が想定されています。 これを行うために、手で各放射状ブランチの各最終ストランスに対して、隣接するブランチで地理的に最も近いステーションを選択し、Yandex.Navigatorを使用した推定時間でそのようなペアの「コード」を追加しました。
最適化後、これは4つの「コード」を持つ非常に興味深いルートであることがわかりました。
そのような計算ルートは、私の最適なルートよりも約30分短いことがわかりました。 「スポーティーではない」として拒否されたオプション。
まとめ
激しい議論の末、私たちはコードなしで各ステーションにアクセスできる最適なルートに進むことにしました。 最終的に、名目上すべてのステーションを回るだけであれば、車をまったく出せずに、約12時間の時間が取れたはずです。 しかし、モスクワの地下鉄は当然、世界で最も美しい地下鉄の1つと見なされているため、何も見ずにすべてを訪れるよりも駅の一部を楽しむ方が良いでしょう。
気分は深刻だったので、この段階でモスクワメトロに目を向け、彼らの助けを借りてルートをテストしました。 私たちは、乗客の移動センターから特別な護衛を割り当てられ、写真やビデオを撮影することを許可され、時には各駅にあるサービストイレを使用することさえ許可されました。
それで、5月12日、同僚と私は早朝にモスクワの地下鉄に入り、起きずに、地下鉄が閉じるまで199の現在アクセス可能なすべての駅を訪れました。 これをすべて行った理由は完全に不明ですが、それはポイントではなく、主なことは成功したことです。
メトロ全体を「時間通りに」運転するというタスクはありませんでしたが、1日ですべての駅を見たいと思っていました。 私たちは各駅に出かけ、写真を撮って（数百枚の写真をさまざまな ソーシャルメディア フィードで見つけることができます ）、運転しました-時々同じ列車で、時にはいくつかの列車を連続して飛ばしました。もっと時間があります。
合計時間は16時間22分でした。 ルートを公開して 、誰でもこの時間を改善できるようにしたいと思っています。
このクレイジーな取り組みで何らかの形で私たちを助けてくれたみんな、そしてマラソンランナーのチーム、オンラインサポートチーム、そして準備に私たちを助けてくれた多くの人々に感謝することは大きな喜びです。
詳細な感謝は、FBの最後の投稿にあります。