5

私は最近、London Ungerground データセットのデータを使用して、特定の駅から n 分離れたルートを見つけるプロジェクトを開始しました。

これまでのところ、データセットからのデータを解析し、各ステーション間の可能なルートを作成することができました。次のプロパティを持つルート オブジェクトのリストができました。

Parent - the first station
Child - the next linked station
Line - whichever line the station is on
Time - the time between the two stations

VICTORIA を出発駅として使用している現在のデータは次のとおりです。

読みやすくするために出力をフォーマットしましたが、各行はルート オブジェクトを表しています。つまり、始発駅、時間、次の駅、路線があります。

VICTORIA => 1 <= PIMLICO : Victoria
VICTORIA => 2 <= GREEN PARK : Victoria
VICTORIA => 2 <= ST JAMES PARK : Circle
VICTORIA => 2 <= SLOANE SQUARE : Circle
PIMLICO => 2 <= VAUXHALL : Victoria
GREEN PARK => 2 <= OXFORD CIRCUS : Victoria
GREEN PARK => 1 <= WESTMINSTER : Jubilee
GREEN PARK => 2 <= BOND STREET : Jubilee
GREEN PARK => 1 <= PICCADILLY CIRCUS : Piccadilly
GREEN PARK => 1 <= HYDE PARK CORNER : Piccadilly
ST JAMES PARK => 1 <= WESTMINSTER : Circle
SLOANE SQUARE => 1 <= SOUTH KENSINGTON : Circle
VAUXHALL => 2 <= STOCKWELL : Victoria
VAUXHALL => 2 <= PIMLICO : Victoria
OXFORD CIRCUS => 1 <= PICCADILLY CIRCUS : Bakerloo
OXFORD CIRCUS => 2 <= REGENTS PARK : Bakerloo
OXFORD CIRCUS => 2 <= TOTTENHAM COURT ROAD : Central
OXFORD CIRCUS => 1 <= BOND STREET : Central
OXFORD CIRCUS => 2 <= GREEN PARK : Victoria
OXFORD CIRCUS => 1 <= WARREN STREET : Victoria

VICTORIA から、すべての可能なルートを収集するための最良の方法は何でしょうか?

例えば：

VICTORIA > GREEN PARK > WESTMINSTER
VICTORIA > GREEN PARK > BOND STREET
VICTORIA > PIMLICO > VAUXHALL
4

1 に答える 1

12

グラフ理論の問題のように聞こえます。お気に入り！

「すべての可能なルート」を見つける際の問題は、指定したデータ (またはこの状況では現実的なデータセット) を使用すると、ループが発生することです。したがって、特定のルートについて、各駅が 1 回だけ訪れるようにする必要があります。

出発点は 1 つなので、Djikstra のアルゴリズムをお勧めします。これにより、 VICTORIAから他のすべてのステーションへのパス (実際には最短パス) が見つかります。少なくとも、到達可能な他のすべての駅。これはよく知られている、高速で実装が比較的簡単なアルゴリズムです。通常は O(n^2) 時間で実行されますが、いくつかのデータ構造ジミーを使用して O(m + nlogn) に変換できます。

うまくいけば、少なくとも正しい軌道に乗ることができます!

于 2013-07-02T12:10:48.330 に答える