平面グラフと交通ネットワークのアルゴリズム
本日，PFI セミナーにて「平面グラフと交通ネットワークのアルゴリズム」というタイトルで話をさせてもらいました．スライドは以下になります．
- 「平面グラフでは色々な問題が効率的に解けると聞くけど一体何故？」
- 「道路ネットワークを処理するにはそういうアルゴリズムが使われているの？」
というような自分が昔持っていた疑問に答える，そんなつもりで準備をしました．そんな疑問を持っている方は，是非ご覧ください．
内容は以下のような感じです．
- 平面グラフのアルゴリズム（理論コミュニティ）
- 平面グラフとは何か
- 平面グラフのアルゴリズムテクニックとその応用例
- 双対グラフ
- 小さいセパレータの存在 (r-division)
- グラフ分割 (Deletion Decomposition)
- 交通ネットワークのアルゴリズム（応用コミュニティ）
- どのような課題が取り組まれているか
- 道路ネットワークは平面グラフなのか？
- 経路計画の手法 4 つ（CH, CRP, HL, PHL）
平面グラフのアルゴリズムの話は，日本語の資料は世の中にほとんど無いと思うので，わりかし珍しい話だとは思います．しかし，時間の制約もあってあまり踏み込んではないので，基礎的なグラフアルゴリズムさえわかっていればそこそこ理解できるような簡単な話になっています．そして，結構それでも（純粋な意味で）面白いと思います．
交通ネットワークの話は，応用寄りの方にも興味を持ってもらえるよう，2 系統の手法の話を 2 つずつしました．前者 2 つは，Bing Maps や OSRM 等で実際に採用されている，拡張性等の面で使いやすい手法です．そして，後者 2 つは，純粋に性能を追い求める手法になっています．
Ustream の録画もあります．
