短縮階層

コンピュータサイエンスにおいて、縮約階層法はグラフ内の最短経路を見つけるための高速化手法である。最も直感的なアプリケーションはカーナビゲーションシステムであり、ユーザーは可能な限り最短のルートを使用してからまで運転したいとします。ここで最適化されるメトリックは移動時間です。交差点は頂点で表され、それらを接続する道路セクションはエッジで表されます。エッジの重みは、道路のこのセグメントに沿って運転するのにかかる時間を表します。からへのパスはエッジ（道路セクション）のシーケンスであり、最短パスはすべての可能なパスの中でエッジの重みの合計が最小のパスです。グラフの最短パスはダイクストラのアルゴリズムを使用して計算できますが、道路ネットワークは数千万の頂点で構成されているため、これは非現実的です。^[1]縮約階層は、道路ネットワークを表すグラフの特性を利用するように最適化された高速化手法です。^[2]高速化は、前処理段階でショートカットを作成し、最短経路クエリ中に「重要でない」頂点をスキップすることで実現されます。^[2]これは、道路ネットワークが高度に階層化されているという観察に基づいています。高速道路のジャンクションなどの一部の交差点は、行き止まりにつながるジャンクションなどよりも「重要」で、階層の上位にあります。ショートカットを使用すると、2つの重要なジャンクション間の事前計算された距離を保存できるため、アルゴリズムはクエリ時にこれらのジャンクション間の完全なパスを考慮する必要がありません。収縮階層は、人間がどの道路を「重要」と見なしているか（高速道路など）を認識しませんが、グラフを入力として提供され、ヒューリスティックを使用して頂点に重要性を割り当てることができます。 ${\displaystyle A}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B}$

縮約階層は、カーナビゲーションシステムの高速化アルゴリズムだけでなく、ウェブベースのルートプランナー、交通シミュレーション、物流最適化にも応用されています。^{[3] [1] [4]このアルゴリズムの実装は}オープンソースソフトウェアとして公開されています。^{[5] [6] [7] [8] [9]}

収縮階層 (CH) アルゴリズムは、最短経路問題に対する 2 段階のアプローチで、前処理段階とクエリ段階から構成されます。道路ネットワークはめったに変化しないため、クエリに回答する前に、より多くの時間 (数秒から数時間) を使っていくつかの計算を事前に実行することができます。この事前計算されたデータを使用することで、多くのクエリにそれぞれ非常に短い時間 (マイクロ秒) で回答できます。^{[1] [3]} CH はこの高速化を実現するためにショートカットを利用しています。ショートカットは、元のグラフでは隣接していない 2 つの頂点を接続します。そのエッジの重みは、最短経路上のエッジの重みの合計です。 ${\displaystyle u}$${\displaystyle v}$${\displaystyle u}$${\displaystyle v}$

高速道路で結ばれた 2 つの大都市について考えてみましょう。この 2 つの都市の間には、小さな村や郊外につながるジャンクションが多数あります。ほとんどのドライバーは、1 つの都市から別の都市へ (おそらくは大きなルートの一部として) 移動したいと考えており、途中の出口は利用しません。この道路レイアウトを表すグラフでは、各交差点がノードで表され、隣接する交差点の間にエッジが作成されます。この 2 つの都市間の距離を計算するには、アルゴリズムは途中のすべてのエッジをトラバースして、その長さを合計する必要があります。この距離を 1 回事前に計算し、2 つの大都市の間に作成された追加のエッジに格納しておくと、クエリでこの高速道路を評価するたびに計算を節約できます。この追加のエッジは「ショートカット」と呼ばれ、現実世界には対応するものはありません。縮約階層アルゴリズムは道路の種類についての知識はありませんが、グラフのみを入力として使用して、どのショートカットを作成する必要があるかを判断できます。

CHアルゴリズムは、前処理段階で作成されたショートカットを利用して検索空間（クエリ時にCHが調べる頂点の数）を減らします。これを実現するために、反復的な頂点の縮約が実行されます。頂点を縮約すると、その頂点は一時的にグラフから削除され、からへの最短経路に が含まれる場合は、隣接する頂点の各ペアの間にショートカットが作成されます。^[2]との間の最短経路に が含まれるかどうかを判断するプロセスは、証人検索と呼ばれます。これは、たとえば、まだ縮約されていないノードのみを使用して順方向検索を使用してからへのパスを計算することによって実行できます。^[3]${\displaystyle v}$${\displaystyle G}$${\displaystyle \{u,w\}}$${\textstyle u}$${\textstyle w}$${\displaystyle v}$${\textstyle u}$${\textstyle w}$${\displaystyle v}$${\displaystyle u}$${\displaystyle w}$

入力グラフの頂点は、縮小によってグラフに追加される辺の数を最小化する方法で縮小されなければならない。最適なノード順序付けはNP完全であるため、^[10] ヒューリスティックスが使用される。^[2]

ボトムアップ型とトップダウン型のヒューリスティックが存在します。一方では、計算コストの低いボトムアップ型ヒューリスティックが貪欲な方法で頂点を縮小する順序を決定します。つまり、順序は事前にはわかりませんが、前の縮小が完了した後に次のノードが縮小用に選択されます。一方、トップダウン型ヒューリスティックは、最初のノードが縮小される前にノード全体の順序を事前に計算します。これにより、より良い結果が得られますが、より多くの前処理時間が必要になります。^[2]

ボトムアップヒューリスティックでは、複数の要因を組み合わせて、次の頂点を縮小する選択を行います。ショートカットの数は、前処理とクエリの実行時間を決定する主な要因であるため、できるだけ小さく抑える必要があります。したがって、次のノードを縮小する選択に最も重要な項は、ノードを縮小するときに追加されるエッジの正味数です。これは次のように定義されます。ここで、は縮小された場合に作成されるショートカットの数、は に付随するエッジの数です。この基準のみを使用すると、線形パスは線形階層 (多くのレベル) になり、ショートカットは作成されません。すでに縮小されている近くの頂点の数を考慮すると、均一な縮小とフラットな階層 (レベルが少ない) が実現されます。これは、たとえば、隣接する頂点が縮小されるたびに増加する各ノードのカウンターを維持することで実現できます。カウンターが低いノードは、カウンターが高いノードよりも優先されます。^[11]${\displaystyle x}$${\displaystyle A(x)-|\{(u,x)\colon (u,x)\in E\}|}$${\displaystyle A(x)}$${\displaystyle x}$${\displaystyle |\{(u,x)\colon (u,x)\in E\}|}$${\displaystyle x}$

一方、トップダウンヒューリスティックは、より良い結果をもたらしますが、より多くの前処理時間を必要とします。このヒューリスティックでは、多数の最短経路の一部である頂点を、少数の最短経路にのみ必要な頂点よりも重要と分類します。これは、ネストされた分割を使用して近似できます。^[2]ネストされた分割を計算するには、グラフを再帰的に 2 つの部分に分割し、それらの部分自体もさらに 2 つの部分に分割し、これを繰り返します。つまり、グラフから削除すると、となるほぼ等しいサイズの2 つの分離部分に分割されるノードのサブセットを見つけます。すべてのノードをノード順序の最後に配置してから、およびについてネストされた分割を再帰的に計算します。^[12]直感的には、グラフの半分からグラフのもう半分へのすべてのクエリは小さなセパレータを通過する必要があるため、このセパレータ内のノードは重要度が高いと考えられます。ネストされた分割は、セパレータが小さいため、道路ネットワーク上で効率的に計算できます。^[13]${\displaystyle S\subseteq V}$${\displaystyle G}$${\displaystyle G}$${\displaystyle G_{1},G_{2}}$${\displaystyle S\cup G_{1}\cup G_{2}=G}$${\displaystyle v\in S}$ ${\displaystyle G_{1}}$${\displaystyle G_{2}}$

クエリフェーズでは、前処理フェーズで作成されたショートカットによって拡張された元のグラフの開始ノードとターゲットノードから始まる双方向の検索が実行されます。 ^[2]と間の最短パス上の最も重要な頂点は、 または 自身であるか、と の両方よりも重要です。したがって、頂点を最小化するのは、元のグラフの最短パス上にあり、が成立します。^[2]これは、ショートカットの作成方法と相まって、前方検索と後方検索の両方で、階層内のより重要なノード（上方）につながるエッジを緩和するだけでよく、検索スペースが小さくなることを意味します。^[3]すべての上（下上）下パスでは、ショートカットが前処理段階で作成されているため、内側の（下上）はスキップできます。 ${\displaystyle s}$${\displaystyle t}$${\displaystyle s}$${\displaystyle t}$${\displaystyle s}$${\displaystyle t}$${\displaystyle s}$${\displaystyle t}$${\displaystyle u}$${\displaystyle \mathrm {dist} (s,u)+\mathrm {dist} (u,t)}$${\displaystyle s-t}$${\displaystyle \mathrm {dist} (s,u)+\mathrm {dist} (u,t)=\mathrm {dist} (s,t)}$

上で説明したように、CHクエリはからへの時間または距離を返しますが、実際の経路は返しません。最短経路上のエッジ（道路）のリストを取得するには、経由したショートカットを展開する必要があります。各ショートカットは、2つのエッジの連結です。元のグラフの2つのエッジ、2つのショートカット、または元のエッジ1つとショートカット1つです。縮小中に各ショートカットの中央の頂点を保存することで、最短経路の線形時間再帰展開が可能になります。^{[2] [3]}${\displaystyle s}$${\displaystyle t}$

エッジの重みがネットワーク トポロジよりも頻繁に変更される場合、前処理フェーズとクエリ フェーズの間にカスタマイズ フェーズを含めることで、CH を 3 フェーズ アプローチに拡張できます。これは、たとえば、最短距離と最短時間を切り替えたり、現在の交通情報や、特定の種類の道路 (フェリー、高速道路など) を避けるなどのユーザー設定を含めたりするために使用できます。前処理フェーズでは、実行時間の大部分が、ノードが縮小される順序の計算に費やされます。^[3]前処理フェーズでのこの一連の縮小操作は、後でカスタマイズ フェーズで必要になったときのために保存できます。メトリックがカスタマイズされるたびに、カスタム メトリックを使用して、保存された順序で縮小を効率的に適用できます。^[2]さらに、新しいエッジの重みによっては、いくつかのショートカットを再計算する必要がある場合があります。^[3]これが機能するには、メトリックに依存しないネストされた分割を使用して縮小順序を計算する必要があります。^[1]

上で説明したように、CH は 1 つの開始ノードから 1 つの目標ノードまでの最短経路を検索します。これは1 対 1 の最短経路と呼ばれ、たとえばカーナビゲーション システムで使用されます。その他の用途としては、 GPSトレースを道路セグメントに一致させたり、ネットワーク内のすべてのドライバーが取る可能性のあるルートを考慮しなければならない交通シミュレータを高速化したりすることが挙げられます。ルート予測では、車両の現在位置と過去の位置が、開始点から可能性のある目標までの最短経路とどの程度一致するかを計算して、車両がどこに向かっている可能性があるかを推定します。これは、CH を使用して効率的に行うことができます。^[2]

1対多のシナリオでは、開始ノードとターゲットノードのセットが指定され、すべての距離を計算する必要があります。1対多クエリの最も顕著なアプリケーションは、興味のあるポイントの検索です。典型的な例としては、地理的な距離ではなく実際の移動時間を基準として、最も近いガソリンスタンド、レストラン、郵便局を見つけることが挙げられます。^[2]${\displaystyle s}$${\displaystyle T}$${\displaystyle \mathrm {dist} (s,t)}$${\displaystyle t\in T}$

多対多の最短経路シナリオでは、開始ノードのセットとターゲットノードのセットが与えられ、すべてのノードの距離を計算する必要があります。これは、たとえばロジスティックアプリケーションで使用されます。^[2] CH は、次の方法で多対多のクエリに拡張できます。まず、各 から後方上向き検索を実行します。この検索中にスキャンされた各頂点について、バケット に格納します。次に、各 から前方上向き検索を実行し、空でないバケットごとに、対応する頂点を経由するルートによって最適な距離が改善されるかどうかを確認します。つまり、任意の について が である場合です。^{[2] [3]}${\displaystyle S}$${\displaystyle T}$${\displaystyle \mathrm {dist} (s_{i},t_{i})}$${\displaystyle (s_{i},t_{j})\in S\times T}$${\displaystyle t_{j}\in T}$${\displaystyle u}$${\displaystyle \mathrm {dist} (t_{j},u)}$${\displaystyle \beta (u)}$${\displaystyle s_{i}\in S}$${\displaystyle \mathrm {dist} (s_{i},u)+\mathrm {dist} (u,t_{j})<\mathrm {dist} (s_{i},t_{j})}$${\displaystyle (s_{i},t_{j})\in S\times T}$

アプリケーションによっては、1 対全の計算、つまりソース頂点からグラフ内の他のすべての頂点までの距離を求める計算も必要になる。ダイクストラのアルゴリズムは各エッジを 1 回だけ訪問するため線形時間で実行されるため、理論的には最適である。しかし、ダイクストラのアルゴリズムは並列化が難しく、局所性が悪いためキャッシュに最適ではない。CH を使用すると、よりキャッシュに最適な実装ができる。そのためには、ショートカットが豊富なグラフ内のすべてのノードに対して、上向きの順方向検索と下向きのスキャンを実行する。後者の操作では、ノードが重要度の降順で処理されるため、メモリを線形にスキャンし、それに応じてメモリに配置することができる。^[14]これが可能なのは、第 2 フェーズでノードが処理される順序がソース ノードに依存しないからである。^[2]${\displaystyle s}$${\displaystyle s}$${\displaystyle s}$

実用化に向けて、カーナビゲーションシステムは予測交通情報を使用して最速の移動ルートを計算し、代替ルートを表示できる必要があります。どちらもCHを使用して実行できます。^[2]前者は時間依存ネットワークによるルーティングと呼ばれ、特定のエッジの移動時間は一定ではなく、エッジに入る時刻の関数になります。代替ルートは滑らかに見え、最短経路とは大幅に異なりますが、大幅に長くはありません。^[2]

CHは複数の指標を同時に最適化するように拡張することができ、これをマルチ基準ルート計画と呼びます。たとえば、移動コストと時間の両方を最小限に抑えることができます。別の例としては、バッテリーが空にならない可能性があるため、利用可能なバッテリー充電量によって有効なルートが制限される電気自動車があります。 ^[2]

収縮階層の前処理とクエリのパフォーマンスについては、いくつかの境界が確立されています。以下では、グラフの頂点の数を 、エッジの数を 、ハイウェイの次元を、グラフの直径を 、ツリーの深さを、ツリーの幅をとします。 ${\displaystyle n}$${\displaystyle m}$${\displaystyle h}$${\displaystyle D}$${\displaystyle td}$${\displaystyle tw}$

収縮階層の性能に関する最初の分析は、ハイウェイ次元と呼ばれる量に部分的に依存しています。この量の定義は技術的ですが、直感的には、任意の に対して、長さが より大きいすべての最短経路に の頂点が含まれるような疎な頂点集合がある場合、グラフは小さなハイウェイ次元を持ちます。ハイウェイ次元の正確な値を計算することはNP 困難^{[15] [16]}であり、おそらくW[1] 困難ですが^[17]、グリッドの場合、ハイウェイ次元は であることがわかっています。^[18]${\displaystyle r>0}$${\displaystyle S_{r}}$${\displaystyle r}$${\displaystyle S_{r}}$${\displaystyle h\in \Theta ({\sqrt {n}})}$

代替分析は、カスタマイズ可能な縮約階層の研究で発表されました。クエリの実行時間は で制限できます。ツリーの深さはツリーの幅で制限できるため、も有効な上限です。主な出典は^[19]ですが、最悪の場合の実行時間の結果は^{[20]でより詳しく説明されています。}${\displaystyle O(td^{2})}$${\displaystyle O((tw\log n)^{2})}$

• https://www.graphhopper.com/
• https://github.com/ifsttar/Tempus
• https://github.com/RoutingKit/RoutingKit
• http://project-osrm.org/
• http://www.opentripplanner.org/