Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
Hub Labeling による高速経路探索
Search
NearMeの技術発表資料です
PRO
June 06, 2025
0
91
Hub Labeling による高速経路探索
NearMeの技術発表資料です
PRO
June 06, 2025
Tweet
Share
More Decks by NearMeの技術発表資料です
See All by NearMeの技術発表資料です
強化学習アルゴリズムPPOの改善案を考えてみた
nearme_tech
PRO
0
3
Apple Containerについて調べて触ってみた
nearme_tech
PRO
0
49
Rust 並列強化学習
nearme_tech
PRO
0
21
並列で⽣成AIにコーディングをやらせる
nearme_tech
PRO
1
130
希望休勤務を考慮したシフト作成
nearme_tech
PRO
0
34
Build an AI agent with Mastra
nearme_tech
PRO
0
77
Rustで強化学習アルゴリズムを実装する vol3
nearme_tech
PRO
0
43
Webアプリケーションにおけるクラスの設計再入門
nearme_tech
PRO
1
110
AIエージェント for 予約フォーム
nearme_tech
PRO
2
170
Featured
See All Featured
Build The Right Thing And Hit Your Dates
maggiecrowley
37
2.8k
How STYLIGHT went responsive
nonsquared
100
5.7k
A Modern Web Designer's Workflow
chriscoyier
695
190k
Documentation Writing (for coders)
carmenintech
73
5k
Rails Girls Zürich Keynote
gr2m
95
14k
Faster Mobile Websites
deanohume
309
31k
Creating an realtime collaboration tool: Agile Flush - .NET Oxford
marcduiker
31
2.2k
A better future with KSS
kneath
239
17k
Chrome DevTools: State of the Union 2024 - Debugging React & Beyond
addyosmani
7
820
Refactoring Trust on Your Teams (GOTO; Chicago 2020)
rmw
34
3.1k
The MySQL Ecosystem @ GitHub 2015
samlambert
251
13k
Building Flexible Design Systems
yeseniaperezcruz
328
39k
Transcript
Hub Labeling による⾼速経路探索 2025-06-06 第123回NearMe技術勉強会 Shunma Serizawa
⽬次 1. 最短経路問題とは? 2. Hub Labeling の概要と利点 3. Hub Labeling
の仕組み 4. 実装と⽐較
1. 最短経路問題とは? • 最短経路問題とは? →ある場所から、他のある場所へ⾏くとき、最も移動距離 (時間) の 短いものを⾒つける • 有名なアルゴリズム
- ベルマンフォード法 - ダイクストラ法
2. Hub Labeling の概要と利点 • Hub Labeling とは? →最短経路クエリを⾼速に処理するための事前計算ベースの アルゴリズム
- 各頂点に対して、「ラベル」という情報を保持 - ラベルには、ある共通の「中継点(hub)」とその距離を記録 - クエリ時は、出発点と到着点のラベルを⽐較し、共通の hub を通 る経路の中で最短のものを選ぶ
2. Hub Labeling の概要と利点 • Hub Labeling の利点 - クエリ時間が⾮常に短い
- ハブ情報に経路中継情報を持たせると、経路を復元できる - 道路ネットワークのような疎なグラフが得意 • Hub Labeling の⽋点 - 前処理が重い - 動的グラフへの適⽤が困難
3. Hub Labeling の仕組み A B C D E F
G 1 2 2 3 2 2 1 3 2
3. Hub Labeling の仕組み A B C D E F
G 1 2 2 3 2 2 1 3 2 ラベリング A: (B, 1), (C, 2), (E, 3) B: (A, 1), (E, 2), (F, 3) C: (A, 2), (D, 2), (E, 2) D: (C, 3), (F, 2) E: (B, 2), (C, 2), (F, 1) F: (E, 1), (G, 2) G: (E, 3), (F, 2)
3. Hub Labeling の仕組み A B C D E F
G 1 2 2 3 2 2 1 3 2 ラベリング A: (B, 1), (C, 2), (E, 3) B: (A, 1), (E, 2), (F, 3) C: (A, 2), (D, 2), (E, 2) D: (C, 3), (F, 2) E: (B, 2), (C, 2), (F, 1) F: (E, 1), (G, 2) G: (E, 3), (F, 2)
3. Hub Labeling の仕組み A B C D E F
G 1 2 2 3 2 2 1 3 2 ラベリング A: (B, 1), (C, 2), (E, 3) B: (A, 1), (E, 2), (F, 3) C: (A, 2), (D, 2), (E, 2) D: (C, 3), (F, 2) E: (B, 2), (C, 2), (F, 1) F: (E, 1), (G, 2) G: (E, 3), (F, 2)
3. Hub Labeling の仕組み • Hub 数は性能に直結! - 各ノードのラベルに含まれるハブ数が少ないほど、クエリは⾼速 -
上⼿く設計すれば、数千万ノードでもノードあたりの平均ハブ数 は数⼗程度に • 上⼿く設計するには? - Contraction Hierarchies - Pruned Highway Labeling
4. 実装と⽐較 • データ - 東京駅を中⼼とした、⼀辺が 10 km の正⽅形内の道路情報 -
道路を無向辺、交差点を頂点 - 頂点数が 27247 、辺の数が 73624 • ⽐較⽅法 - ランダムな頂点対 1000 組の最短距離を取得 これくらい→
4. 実装と⽐較 前計算 クエリ Dijkstra - 50 ms Hub Labeling
3 時間くらい 0.5 ms
参考⽂献 • Route Planning in Transportation Networks ◦ https://arxiv.org/pdf/1504.05140 •
A Hub-Based Labeling Algorithm for Shortest Paths on Road Networks ◦ https://www.microsoft.com/en-us/research/wp-content/ uploads/2010/12/HL-TR.pdf
Thank you