Dijkstra vs. A* vs. Contraction Hierarchies

ArcadeDBでの経路計画

「AからBへの最も速い方法は？」という古典的な問いに対する答えであるDijkstraとA*は、正確で準備が不要ですが、2点間の距離が離れるほど、ネットワークのより多くの部分を読み取ります。アニメーションは、フロリダ州の実際の道路ネットワーク（107万のジャンクションと270万の道路セグメント）で、タラハシーからコーラルゲイブルズまでの移動時間（8時間18分、I-75とフロリダターンパイクを経由）を対象に、これら3つとカスタマイズ可能な収縮階層（CCH）を実行します。各色の四角は、検索が答えを知るために読み取る必要のある州の一部であり、すべての3つのパネルは同じ速度で再生されます。3つすべてが、秒単位で同じルートを返します。

［画像: アニメーション：フロリダの道路ネットワーク上で、Dijkstraはタラハシーからコーラルゲイブルズへの最短経路を見つけるために1,029,617のジャンクションを解決し、A*は840,138を解決し、CCHは346を解決します。すべてが同じルート、8時間18分を返します。］

Dijkstra: 1,029,617 ジャンクション

開始地点からの移動時間順にジャンクションを解決します。その検索は広がる円です。コーラルゲイブルズに到達する頃には、ペンサコーラ、ジャクソンビル、タンパがコーラルゲイブルズよりもタラハシーに近いので、フロリダのほぼすべてを解決しています。準備不要で、非負の重みを持つ任意のグラフで機能します。

A*: 840,138 ジャンクション

コーラルゲイブルズへの直線距離からの残り時間の推定値を追加し、円を南に傾けます。正確さを保つために、推定値が実際の道路を超えることは決してなく、フロリダの270万セグメントの一部は直線距離よりも速いため、ガイダンスは弱く、検索は依然として州の大部分をカバーします。頂点の座標が必要です。

CCH: 346 ジャンクション

両端から事前に計算された階層を登り、2つの登りが会うまで続きます：タラハシーの上166ジャンクション、コーラルゲイブルズの上163ジャンクション。作業は距離にほとんど依存しないため、ギャップは3桁異なります：約100ミリ秒ではなく0.04ミリ秒。正確であり、ヒューリスティックではありません。

カスタマイズ可能な収縮階層（CCH）の仕組み

Dibbelt、Strasser、Wagnerの研究によるこの技術は、作業をクエリ時間から準備時間に移動させ、準備をどの道路が存在するかのみに依存する部分とそれらのコストが何であるかに依存する部分に分割します。その分割が、階層が交通量を追跡できるようにするものです。

［画像: アニメーション：左側には、ネストされた分割によってフロリダの道路ネットワークが断片化され、最初のカットの17ジャンクション、次にさらに28、43。右側には、タラハシーからコーラルゲイブルズへのクエリが両端から階層を登り、166と163ジャンクション、そして登りがベロビーチの近くで合流し、ショートカットがルートに展開される］

順序付け、契約、カスタマイズ、クエリ

• 順序付け（一度のみ）： ネットワークを2つに分割する少数のジャンクションを見つけます（フロリダでは17ジャンクションが州を半分に分割し、さらに28が4つに分割します）。次に、各半分に再帰します。道路ネットワークは小さな分離器（橋、峠、長距離ルートが通過する少数のジャンクション）でいっぱいです。
• 契約（一度のみ）： ジャンクションを下から上に削除し、削除によってルートが壊れる場合はショートカットを追加します。この時点では重みは必要ありません。
• カスタマイズ（すべての重み変更時に）： 重みから各道路とショートカットに価格を付けます。変更後、変更された道路より上にあるアークのみが再価格設定されます。
• クエリ（すべてのリクエスト時に）： 両端から上に歩き、合流し、ショートカットを実際の道路に展開します。優先度付きキューもフロンティアもありません。数キロバイトのスクラッチ領域です。

ArcadeDBは、グラフ分析ビュー、つまり分析が実行されるグラフのインメモリ列コピーに階層を保持し、すべてのコミットと同期させます。

これを有効にするための1つのステートメント

-- 1つのコストにつき1つの階層：距離と時間
CREATE GRAPH ANALYTICAL VIEW Florida
  EDGE TYPES (ROAD)
  UPDATE MODE SYNCHRONOUS
  CCH (km, minutes)

バックグラウンドでビルドされ、フロリダの270万の道路に対して約7秒かかります。クエリが待機することはありません。

CypherとSQLでの同じルート

// Cypher: ルートと総移動時間
MATCH (a:Junction {name: 'Tallahassee'}),
      (b:Junction {name: 'Coral Gables'})
CALL algo.cch.shortestPath(a, b,
     'ROAD', 'minutes', 'OUT')
YIELD path, weight
RETURN weight AS minutes, size(path.nodes) AS junctions

-- SQL: ルートのジャンクション、順序通り
SELECT lat, lon FROM (
  SELECT expand(cchShortestPath($from, $to, 'minutes',
    { direction: 'OUT', edgeTypeNames: ['ROAD'] }))
LET $from = (SELECT FROM Junction WHERE name = 'Tallahassee'),
    $to   = (SELECT FROM Junction WHERE name = 'Coral Gables')
)

dijkstra()とastar()は同じ引数を取るため、アルゴリズムの切り替えは1単語です。

常に正確、決して古くない

cchShortestPath()とalgo.cch.shortestPathは常に正確な最短経路を返し、それを計算する最も速い方法を選択します。階層は、ビューが提供するデータに正確に準備されたときに回答します。それ以外の場合は、同じ呼び出しが双方向Dijkstraで回答します。階層が構築中であるか、コミットのキャッチアップ中であるか、異なる重みであるか、または未コミットの変更を保持するトランザクションである場合、それはルートの一部として見なされます。

速度のみが変化し、回答は変化しません。これは、データベースのルーティング機能と、その隣にあるルーティングキャッシュとの違いです。クエリが1秒前に閉鎖された道路のルートを返すウィンドウはありません。

すべての階層は、SELECT FROM schema:graphAnalyticalViewsを通じて、そのステータス、サイズとメモリ、回答したクエリ、Dijkstraに渡したクエリ、およびコミットから準備完了までの最後の更新にかかった時間を示します。Cypherでは、PROFILEはクエリが階層によって回答された時期を示します。

ライブトラフィック：1回のUPDATE、1ミリ秒後の新しいルート

重みは通常の辺のプロパティです。トラフィックフィード、閉鎖、メンテナンスウィンドウは、データセットの隣にあるトランザクション内の単純なUPDATEまたはCypher SETステートメントです。階層は変更された道路より上のアークのみを再価格設定します。

［画像: アニメーション：タラハシーからコーラルゲイブルズへの最短ルートは、8時間18分でI-75とフロリダターンパイクを下ります。オーランドの南にあるターンパイクに4時間の渋滞が追加されたCypher SETの後、階層は0.9ミリ秒で追いつき、次のクエリは8時間20分で大西洋沿岸を下るI-10とI-95に沿ったルートを返します］

重みは毎秒変化し、階層は追いつく

フロリダの道路ネットワークで測定された、コミットから階層が新しいデータに対して回答するまでの時間（3回の実行の中央値）：

道路は負の重みを与えることで閉鎖され、パスファインダーはそれを歩きません。復旧はそれを元に戻すことによって行われます。新しい道路は既存の順序を維持し、再契約のみを行います。

トラフィックは単なるプロパティ更新

-- ターンパイクでの4時間の渋滞
MATCH (:Junction {id: 702459})
      -[r:ROAD]->(:Junction {id: 702911})
SET r.minutes = 240

-- 同じ道路を閉鎖、SQLで：
-- 負の重みは決して歩かれない
UPDATE ROAD SET minutes = -1
WHERE @rid = :road

タラハシーからコーラルゲイブルズへは、I-75とターンパイク（8時間18分）を離れ、I-10とI-95を大西洋沿岸（8時間20分）を下ります。階層は0.9ミリ秒で追いつきました。

タラハシーからコーラルゲイブルズへ

同じクエリ、同じビュー、異なる重みプロパティ：46 km長く、3時間速い。

1つのネットワーク上の複数のコスト

最短経路が重要であるとは限りません。距離、移動時間、通行料、燃料、排出量、リスク：それぞれが同じエッジ上のプロパティであり、ビューは1つの階層をコストごとに保持します。すべて同じトポロジーから構築され、すべて同じコミットによって最新の状態に保たれます。

ネットワークがマルチモデルデータベース内に存在するため、コストはどこからでも取得できます：時系列センサーデータから集計された移動時間、ドキュメントとして保存された通行料、資産レコードから結合された制限事項。ルートはデータが既に存在する場所で計算されます。

ベンチマーク：100万ジャンクションでのCCH vs Dijkstra vs A*

DIMACSフロリダ道路グラフ（USA-road-d.FLA）は、1,070,376のジャンクションと2,712,798の道路セグメントを持ちます。ルートはタラハシーから始まり、最短経路ツリーの最も近いものから最も遠いものまでの12の宛先、さらに州を横断するコーラルゲイブルズに向かいます。［画像: チャート：フロリダの道路ネットワーク上で、タラハシーからのDijkstraのクエリ時間は宛先が離れるにつれて7.8ミリ秒から104ミリ秒に増加し、Aは3.1ミリ秒から132ミリ秒に増加します。カスタマイズ可能な収縮階層は0.010〜0.041ミリ秒の間を維持します。タラハシーからコーラルゲイブルズへ：CCHで0.039ミリ秒、Dijkstraで99ミリ秒、Aで121ミリ秒］

Dijkstraはすべてのキロメートルに対して支払い、CCHは支払いません：その線は平坦です。クエリあたりでも、数メガバイトではなくキロバイトを割り当てます。これにより、1つのサーバーが多くのルーティングリクエストを並列で処理し、ガベージコレクタに供給することなく実行できます。

Aはその推定値と同じくらい良いです。正確さを保つために、宛先への直線距離は実際の道路コストを超えることはできません。このデータでは、270万セグメントのうち112セグメントがその端間の直線距離よりも短い場合があります。これにより、推定値は真の距離の67％に制限されます。Aは、近くの宛先ではDijkstraの2.5倍高速ですが、州を横断する際には、推定値が弱いため追加の作業に見合うだけの価値がなくなります。より大胆な推定値はより速く、より長いルートを返す可能性があります。CCHには調整する推定値がありません。

CCHは一度、前払いで支払います：フロリダの階層を構築するために7秒、それを保持するためのメモリ。多くのクエリを提供するネットワークでは、その取引は容易です。すべての数値は、オープンソースエンジンでCCHRoadNetworkBenchmarkを実行した3回の実行の中央値です。詳細な結果はベンチマークページにあります。

フロリダ、Apple M5 Pro

どのパスファインダーをいつ使うか

収縮階層を使用しない場合

CCHは、地理的なネットワーク（道路、鉄道、パイプ、電力線、フロアプラン、ゲームマップ）で多数の点対点クエリに応答するためのツールです。以下のような場合は、別のものを選択してください：

• グラフに小さな分離器がない場合。 ソーシャルネットワーク、引用グラフ、スーパーノードを持つものはすべて、グラフの何倍も大きい階層が必要になります。ArcadeDBはこれを検出し、階層をUNSUITABLEとマークし、Dijkstraで回答を続けます。
• クエリがまれな場合。 1日に数回のルートの場合、DijkstraまたはA*は準備もメモリも不要です。
• 重みが負になる可能性がある場合。 Bellman-Fordを使用してください。
• 1つのソースからすべての宛先が必要な場合（例：配達エリアマップ）。単一ソースDijkstraを使用してください。
• 公共地図でのターンバイターンナビゲーションが必要な場合。 OpenStreetMap上に構築された専用エンジン（ターンコストと道路プロファイル付き）が適切なツールです。ArcadeDBは、あなたのネットワークとあなたのデータ上のルーティング用です。

ルート計画アプリケーション

物流と配送

デポ、ハブ、顧客サイトを1つのネットワーク上に。距離、時間、またはコストで、派遣計画のすべての候補レッグをマイクロ秒単位で価格設定し、道路が閉鎖されたらすぐに再計画します。出荷が既に存在するサプライチェーングラフと自然にペアになります。

フリートとフィールドサービス

数分前のテレマティクスが報告した移動時間、および同じデータベースに隣接して保存されているスキルとスペアパーツを使用して、障害のある資産に最初に到達できる技術者を見つけます。

公共事業と通信ネットワーク

電力網、水道管、ガスパイプライン、光ファイバー：障害を迂回し、最低損失または最低遅延パスを見つけ、セグメントをオフにする影響を確認してから実行します。

倉庫と屋内ナビゲーション

倉庫、病院、空港、キャンパスの通路、フロア、エレベーター、ゲート。障害のある通路や混雑した廊下がリアルタイムで発生するのに追従するピッキングパスと案内。

モビリティと輸送

鉄道、フェリー、道路リンクに、移動時間、通行料、排出量を同じエッジ上の別々のコストとして設定します。1つのネットワークから「最速」、「最安」、「最もグリーン」に回答します。

ゲームとシミュレーション

多数のエージェントが同時にルーティングし、地形が変化する広大な世界マップ。マイクロ秒単位のクエリと数キロバイトのスクラッチ領域、ゲームサーバーのJVMに埋め込まれます。

なぜArcadeDBでルート計画をするのか

収縮階層はよく研究されています。それらをデータベース機能のように動作させることが難しい部分です：

• データベース内： エクスポートなし、前処理ジョブなし、同期を維持するルーティングサービスなし。ネットワーク、その重み、および階層は、1つのエンジンと1つのトランザクションログを共有します。
• 変更下でも正確： クエリは、準備されたデータに対してのみ階層によって回答され、それ以外の場合は双方向Dijkstraによって回答されます。トランザクションは独自の未コミットの変更を認識します。
• 増分： 重みの変更、閉鎖、削除は、それらの上のアークのみを再カスタマイズします。新しい道路は既存の順序を維持します。
• 複数のコスト： CCH (km, minutes, toll)、すべて一緒に構築され、最新の状態に保たれます。
• 永続化： 高価な部分（順序）は、クリーンなクローズ時に保存され、再起動時に再利用されます。
• 間違ったグラフでも安全： 小さな分離器のないグラフは検出され、ヒープを使い果たす代わりに拒否されます。
• 軽量： 全体にプリミティブ配列、階層の高さ（フロリダでは6.6 KB）にサイズ設定されたクエリあたりのスクラッチ、純粋なJava、ネイティブライブラリなし。
• クエリするすべての場所： SQLとCypher、Java（埋め込みまたはクライアント/サーバー）、HTTP API、およびドライバーから。

Apache 2.0、永久に

カスタマイズ可能な収縮階層は、ArcadeDB 26.10.2以降のオープンソースエンジンの一部です。エンタープライズエディション、ルーティングアドオン、コアあたりのライセンスはありません。ArcadeDBはApache 2.0 foreverです。製品に組み込み、どこにでもデプロイし、必要ならフォークしてください。

試してみる：ラップトップでタラハシーからコーラルゲイブルズへ

このページ上のすべては、9th DIMACS Implementation Challengeのフロリダ道路ネットワークで実行されます：座標を持つ1,070,376のジャンクションと、長さ（km）と移動時間（分）を持つ2,712,798の道路セグメント。 route-planning use caseはそれをダウンロードし、GraphBatchエンドポイントへの1回の要求でロードします。約11秒かかります。Dockerを使用する場合：

git clone https://github.com/ArcadeData/arcadedb-usecases.git
cd arcadedb-usecases/route-planning
docker compose up -d     # ArcadeDBをポート2480で起動
./setup.sh               # フロリダをダウンロードし、ロードし、CCH（km、分）でビューを作成
./queries/queries.sh     # このページのすべてのクエリをcurl経由で実行

javaフォルダは、Javaクライアントから同じクエリを実行し、embedded/FloridaRoutes.javaはサーバーもビルドステップもなしで埋め込みデータベースで実行します。GraphBatch Java APIでネットワークをロードし、同じルートでdijkstra()、astar()、cchShortestPath()を比較し、2つのコストを表示し、トラフィックジャムを適用します。

java -Xmx4g -cp "$ARCADEDB_HOME/lib/*" embedded/FloridaRoutes.java

HTTP API経由では、タラハシーからコーラルゲイブルズへの移動は、dijkstra()で約3秒、astar()で6秒、cchShortestPath()で2ミリ秒かかります。SQL関数は格納されたレコードを歩き、階層はインメモリビューを読み取ります。上記のベンチマークは、その同じビューで3つすべてを比較します。Shortest Path guideは、重みなしのshortestPath()からA*ヒューリスティックまで、すべてのオプションと、どのエンジンがクエリを回答したかを確認する方法をカバーしています。

よくある質問

カスタマイズ可能な収縮階層（CCH）とは何ですか？

CCHは、点対点最短経路のための事前に計算された構造です。ネットワークを分割する少数の頂点のセットが最上位に来るように頂点をランク付けし、ショートカットエッジを追加し、両端から最上位まで登ることでクエリに応答します。クエリのコストは、2つの頂点の距離ではなく、階層の高さに依存します。ランキングとショートカットはトポロジーのみに依存するため、カスタマイズ可能です。重みが変更されると、変更されたエッジより上のコストのみが再計算されます。

CCHはDijkstraよりもどれくらい速いですか？

DIMACSフロリダ道路ネットワーク（107万ジャンクション、270万道路セグメント）では、CCHはタラハシーからの12のクエリを距離が増加するにつれて0.010〜0.041ミリ秒で回答し、Dijkstraは7.8〜104ミリ秒、Aは3.1〜132ミリ秒でした。DijkstraまたはAよりも300〜3,200倍高速です。タラハシーからコーラルゲイブルズへは、CCHで0.039ミリ秒、Dijkstraで99ミリ秒、Aで121ミリ秒かかりました。Dijkstraの時間​​はルートの長さに比例して増加しますが、CCHはそうではありません。各CCHクエリは6〜43 KBのメモリを使用し、Dijkstraは11〜44 MB、Aは9〜52 MBでした。

ルートはライブトラフィックや道路閉鎖に従うことができますか？

はい。重みは通常の辺のプロパティです。UPDATEで変更すると、階層はそれより上のアークのみを再価格設定します。フロリダネットワークでは、単一の重み変更はコミットから階層が回答するまで約0.8ミリ秒、100の変更は約41ミリ秒、閉鎖された道路は約1ミリ秒かかりました。クエリは待機しません。階層が追いつくまで、双方向Dijkstraによって正確に回答されます。

データベースの隣に別のルーティングエンジンが必要ですか？

独自のネットワーク上のルーティングには不要です。ArcadeDBは、ネットワーク、その重み、および階層を1つのトランザクションエンジン内に保持するため、エクスポート、前処理ジョブ、データベースとルーティングサービス間の同期はありません。OpenStreetMap上に構築された専用エンジンは、公共道路地図でのターンバイターンナビゲーションに適しています。

DijkstraまたはA*をCCHの代わりにいつ使用すべきですか？

時折のクエリ、常に形状が変わるネットワーク、およびソーシャルネットワークやスーパーノードを持つグラフのような小さな分離器のないグラフの場合。これらのグラフでは、階層がグラフの何倍も大きくなります。ArcadeDBはこれらのグラフを検出し、階層をUNSUITABLEとマークし、Dijkstraで回答を続けます。重みが負になる可能性がある場合はBellman-Fordを使用してください。

1つのネットワークで距離や移動時間など、複数のコストを持つことはできますか？

はい。Graph Analytical Viewは、コストごとに1つの階層（例：CCH（km、minutes））を保持し、すべてを一緒に最新の状態に保ちます。各クエリは、最小化するコストを指定します。

ArcadeDBで最短経路を計算できるクエリ言語は何ですか？

SQL（dijkstra()、astar()、cchShortestPath()、bellmanFord()、shortestPath()を使用）とCypher（algo.dijkstra、algo.astar、algo.cch.shortestPath、algo.kShortestPaths、shortestPath()パターンを使用）の両方です。どちらもJava、HTTP API、およびドライバーから利用できます。

ArcadeDBでのルート計画は無料で使用できますか？

はい。ArcadeDBはApache 2.0ライセンスで、本番環境でも無料です。これには、ArcadeDB 26.10.2以降のエンジンの一部であるカスタマイズ可能な収縮階層が含まれます。Javaで記述されており、ネイティブ依存関係はありません。

あなた自身のネットワークでルーティングする準備はできましたか？

あなたのネットワークをロードし、1つのビューを追加して、コミットするすべての変更に従うマイクロ秒単位の正確な最短経路を取得します。デプロイするルーティングサービスなし、維持するパイプラインなし。