地下鉄路線図のための高速経路探索アルゴリズム

1. 概要

過去2日間、Blog Parkで地下鉄マップの実装について話していました。その前に、私もクラスメイトのNeoRAGEx2002と一緒にAndroidの地下鉄マップアプリケーションを作成しました。そのため、地下鉄マップの経路検索アルゴリズムについては、ブログを書いて、私たちのソリューションを皆さんの参考として提供する必要があると思います。この論文で説明されているアルゴリズムの時間計算量は O(|E|log|E|) です。ここで、|E| はエッジの数です。

2. コンセプト

1) 点と辺

基本的な要素は、ポイント (地下鉄の駅) とエッジ (隣接する 2 つの駅間の有向線路) です。

たとえば、新荘駅を通過する 1 号線と 5 号線があり、新荘駅を含むエッジは 4 つあります。また、世紀大道駅を通過する路線は 4 つあり、世紀大道駅を含むエッジは 8 つあります。

2) 運用段階

エッジに基づいて、連続したエッジのセットである操作セグメントの概念もあります。

例えば、1号線は、新荘〜富錦路（出発間隔8分）、新荘〜上海駅（出発間隔6分）、上海南駅〜富錦路（出発間隔8分）、上海南駅〜上海駅（出発間隔6分）、富錦路〜新荘（出発間隔8分）、上海駅〜新荘（出発間隔6分）などの運行区間があります。

3) コスト

経路探索アルゴリズムの基礎は、時間、転送回数、通過したエッジ数などの非負のコストになります。ここでは、モデリング時間に焦点を当てます。

各エッジには移動時間コストがあり、これは地下鉄に乗ってエッジを通過するのに必要な時間を表します。

各運行区間には待機時間コストがあり、これは運行区間を通過する側バスに必要な待機時間です。これは通常、出発間隔（最大待機時間）または出発間隔の半分（待機時間の数学的期待値）と想定できます。

各ポイントには転送時間コストマトリックスがあり、これは任意の 2 つのエッジ間の転送に必要な時間を表します。両者の関係には、直接接続、転送、接続なしの 3 つのタイプがあります。接続された転送の時間コストは 0、転送の時間コストは転送歩行時間 + 待機時間、切断された転送の時間コストは +∞ です。この行列は疎行列で表すことができ、切断された辺は表示されません。地下鉄は、ある路線に沿って引き返すルートを考える必要がないように設計されているため、乗り換えではなく片側と反対側を切断したものと見なすことができ、グラフの複雑さを軽減できます。

3. アルゴリズム

1) アイデア

従来の最短経路アルゴリズムには、次のようなものが数多くあります。

Dijkstra アルゴリズムですが、このアルゴリズムでは転送時間コストの問題を解決できません。

幅優先アルゴリズムでは、重み付きグラフの場合、最適なソリューションを取得できません。

制限付き深さ優先アルゴリズムでは結果を得ることができますが、パスが長い場合はアルゴリズムに時間がかかりすぎます。

山頂の雪が溶けて谷間を流れていく自然現象を思い浮かべることができます。各駅は谷間の地点であり、乗換駅は谷が複数の支線に分かれる交差点です。

出発点を山頂とすると、水は各エッジに沿って拡散します。1 つのエッジを通過するのにかかる時間は、エッジに乗る時間コストと同じです。1 つのエッジから隣接するエッジに移動するには、乗り換えを待つ時間コストが必要です。開始点まで水を注ぎ続けると、水は流れ続けます。水が終了点に到達したとき、水が通った経路は、必要な最短経路です。

このモデルの問題は、水が同時に複数の流れを流れる可能性があるが、アルゴリズムには順序がある必要があることです。すべての水の流れの前面の位置を表す水の流れの接線があると想定できます。任意のエッジ e について、その開始点が水の流れで覆われているが、終了点が水の流れで覆われていない場合、コストでソートされた接線エッジリスト C (赤黒木またはバランス木によって実装される) に e を追加し、e -> 水の流れが通過した前のエッジを記録します。水の流れを続けると、まず C の最初の辺 e の終点が水の流れに覆われ、e は C から削除されます。パス検索の終了点に到達すると、最後のエッジから前のエッジ、さらに前のエッジの前のエッジへと遡って、パス検索の開始点に到達するまで、必要なパスを取得できます。

このアルゴリズムは、終点ではなく、パフォーマンスに顕著な影響を与えることなく、水の流れがマップ上のすべてのポイントをカバーするまで終了することもできます。

2) 例

図1に示すように:

図1 (a) 時間コスト図1 (b) 検索順序

問題を単純化するために、ライン 2 (緑) とライン 9 (水色) は存在しないものとし、ライン 4 (濃い青) とライン 6 (紫) のみを考慮します。

図1(a)は、ライン4とライン6のエッジの時間コストを示しています。白は待ち時間、黄色は乗車時間を表しています。

各乗り換え駅での乗り換えにかかる徒歩時間は4分と想定しています。

図1(b)は探索順序を示しています。同じコストの場合、探索順序は不確定であり、接線エッジリストCの実装によって決定されます。

この例では、出発点は Century Avenue、到着点は上海小児医療センターです。

接線エッジリストCは次のように変化する。

 {1、2、3、5}
 {2、3、4、5}
 {3、4、5、6}
 {4、5、6、9}
 {5、6、7、9}
 {6、7、8、9}
 {7、8、9、10、..、..}
 {8、9、10、..、..、..}
 {9、10、..、..、..、..}
 {10、..、..、..、..、..}

6 が削除されると、10 (藍村路、塘橋) の 3 つのエッジと 9 の逆エッジが追加されることに注意してください。9 が削除されると、6 の逆エッジが追加されます。

9が消えたら、再び10を探します。この時の時間コストは13+4+8=25ですが、10はすでに上辺を記録しているので、Cは追加されません。

#p#

3) 実装

疑似コードは次のとおりです。

頂点を記録する//point  
    InEdges:List<Edge> //エントリエッジ 
    OutEdges:List<Edge> // アウトバウンドエッジ 
    Connection:Map<Tuple<Edge, Edge>, EdgeConnection> //接続されていない場合は、転送歩行時間コストを含むエッジ接続マトリックスは存在しません。  
 
レコードエッジ//edge  
    Start:Vertex //開始点 
    End:Vertex //終点 
    コスト: Int //乗車時間コスト 
    Ranges:List<Range> //操作セグメント 
 
レコード範囲//操作セグメント 
    エッジ:List<Edge> //エッジ 
    コスト: Int // 待機時間 
 
タグ付きユニオン EdgeConnection
    接続:ユニット//直接接続 
    Transferable:Int //転送、歩行時間コスト 
 
 CalculateRoute(開始:頂点、終了:頂点):List<Edge> 
    開始 == 終了の場合
        戻る  new List<Edge>() //開始点と終了点が一致する 
 
    let Previous <- new Map<Edge, Edge>() // エッジから前のエッジへのマッピング 
    let cmp <- (Comparer<Edge>)(...) // パスコスト比較関数。以下に示す 
    let CutEdges <- new RedBlackTree<Edge>(cmp) //水流接線エッジリスト 
 
    Start.OutEdges の o を foreach する
        カットエッジ <- カットエッジ + o
        前 <- 前 + (o, null) 
 
    let e <- (Edge)(null) // エッジの終了 
 
     CutEdges.Count > 0 の場合
        i <- CutEdges.First とします
        カットエッジ <- カットエッジ - i 
 
        s <- i.End とします
         s == 終了の場合
            え <- 私
            壊す 
 
        s.OutEdges 内の o を foreach する
             !s.Connection.ContainsKey((i, o))の場合
                続く 
 
             Previous.ContainsKey(o)の場合
                続く 
 
            前 <- 前 + (o, i)
            カットエッジ <- カットエッジ + o 
 
     e == nullの場合
         nullを返す// パスなし 
 
    l <-新しいリスト<Edge>() を記述します。 
     e != null の場合
        l <- l + e
        e <- 前へ(e) 
 
     l.Reverse()を返す

以下は、経路探索の基準が時間である場合の比較関数です。

 Time <-新しいMap<Edge, Int>() を作成します。
 Range <-新しいMap<Edge, Range>()を作成します。
 GetBestRange <- l:List<Range> => l.OrderBy(r => r.Cost).First を実行します。
 GetTime <- を取得します。
    e => 
         e == nullの場合
             0を返す
         Time.ContainsKey(e)の場合
             Time(e)を返す
        p <- 前へ(e)
        v <- GetTime(p) とします。 
         p != null の場合
            c <- e.Start.Connection((p, e)) とします。 
            もしc
            | 接続済み ->
                rgOld <- Range(p) とします。
                rg <- GetBestRange(p.Ranges.Intersect(e.Ranges)) とします。
                範囲 <- 範囲 + (e, rg) 
                 rgOld != rgの場合
                    v <- v - rgOld.Cost + rg.Cost
            | 譲渡可能 t ->
                rg <- GetBestRange(e.Ranges) を実行します。
                範囲 <- 範囲 + (e, rg)
                v <- v + rg.Cost + t 
        それ以外 
            rg <- GetBestRange(e.Ranges) を実行します。
            範囲 <- 範囲 + (e, rg)
            v <- v + rg.コスト
        v <- v + e.コスト
        時間 <- 時間 + (e, v) 
        リターンv
 cmp <- をします
    (l:エッジ、r:エッジ) => 
         GetTime(l) - GetTime(r)を返す

以下は、経路探索基準が乗り換え回数である場合の比較関数である。

 TransferCount <-新しいMap<Edge, Int>()を作成します。
 GetTransferCount を実行します <-
    e => 
         e == nullの場合
             0を返す
         TransferCount.ContainsKey(e)の場合
             TransferCount(e)を返す
        p <- 前へ(e)
        v <- GetTransferCount(p) を実行します。 
         p != null の場合
            c <- e.Start.Connection((p, e)) とします。 
            もしc
            | 接続済み ->
                （）
            | 譲渡可能 _ ->
                1 + = 1
        転送回数 <- 転送回数 + (e, v) 
        リターンv
 cmp <- をします
    (l:エッジ、r:エッジ) => 
         GetTransferCount(l) - GetTransferCount(r)を返す

以下は、パス検索の基準が通過したエッジの数である場合の比較関数です。

 StopCount <-新しいMap<Edge, Int>()を追加します。
 GetStopCount を実行します <-
    e => 
         e == nullの場合
             0を返す
         StopCount.ContainsKey(e)の場合
             StopCount(e)を返す
        p <- 前へ(e)
        v <- GetStopCount(p) + 1 とします
        ストップカウント <- ストップカウント + (e, v) 
        リターンv
 cmp <- をします
    (l:エッジ、r:エッジ) => 
         GetStopCount(l) - GetStopCount(r)を返す