最短路を ものすごくはやく 答える方法.

Slides:



Advertisements
Similar presentations
組合せ最適化輪講 2.3 連結性 川原 純. 2.3 連結性 内容 – グラフ上の節点をすべてたどるアルゴリズム 計算機上でのグラフの表現 – 強連結成分を求めるアルゴリズム トポロジカル順序を求める方法も – k- 連結、 k- 辺連結について – 2- 連結グラフの耳分解について.
Advertisements

問題案 : 稲葉 解答:秋葉、稲葉.  「 + 」の辺を通ると所持金が 1 円増える  「 - 」の辺を通ると 1 円減る (文無しは通れ ない)  始点を0円で出て終点に0円で着く最短路 は?  |V| ≦ 250 =
1 通信教育学部 コンピュータ演習 Excel の書式設定と関数 授業ページ「コンピュータ演習(通信教育学 部)」を 開いてください。提出課題の一覧が掲載されてい ます。
2 dimensional bit vector approach Mikio Kubo. TIGER/Line graph DC.tmp 9559 nodes and arcs Shortest Paths between all border nodes of 2 regions.
到着時刻と燃料消費量を同時に最適化する船速・航路計画
制約付き最短路問題に対する実験的解析 上智大学 宮本裕一郎 o 1 d (7, 15) (9,4) (12,4)
最短路プロジェクト 共同研究 中間報告 2007年 10月 久保 幹雄.
点対応の外れ値除去の最適化によるカメラの動的校正手法の精度向上
2009/12/4 グラフ (2) 第10講: 平成21年12月4日 (金) 4限 E252教室 コンピュータアルゴリズム.
久保幹雄 東京海洋大 宇野 毅明 国立情報学研究所 藤澤 克樹 中央大学 宮本 裕一郎 上智大学
情報・知能工学系 山本一公 プログラミング演習Ⅱ 第4回 配列(2) 情報・知能工学系 山本一公
A: Attack the Moles 原案:高橋 / 解説:保坂.
最短路問題に対する新しいアルゴリズム 階層メッシュ疎化法 (Level-wise Mesh Sparsification: LMS)
ネットワーク理論 Text. Part 3 pp 最短路問題 pp 最大流問題 pp.85-94
「Self-Organizing Map 自己組織化マップ」 を説明するスライド
データ構造と アルゴリズム 第二回 知能情報学部 新田直也.
日本大学 文理学部 情報システム解析学科 谷研究室 益田真太郎
第7章 データベース管理システム 7.1 データベース管理システムの概要 7.2 データベースの格納方式 7.3 問合せ処理.
第11講: 平成18年12月 8日 (金) 4限 E352教室 グラフ (1).
第4回 カルノー図による組合せ回路の簡単化 瀬戸 目標 ・AND-OR二段回路の実現コスト(面積、遅延)が出せる
第4章 空間解析 2.ネットワーク分析 (3) ネットワーク構造分析
非線形方程式の近似解 (2分法,はさみうち法,Newton-Raphson法)
最短路問題のための LMS(Levelwise Mesh Sparsification)
高山建志 五十嵐健夫 テクスチャ合成の新たな応用と展開 k 情報処理 vol.53 No.6 June 2012 pp
5.5 The Linear Arboricity of Graphs (グラフの線形樹化数)
5. 機能的な組み合わせ回路 五島 正裕.
最短経路.
ネットワーク理論講義補助資料 Text. 組合せ最適化とアルゴリズム 4.3 節 Lagrange緩和 pp
スペクトル・時系列データの前処理方法 ~平滑化 (スムージング) と微分~
応用社会システム計画 (第10回) ここで、学習すること 学籍番号: 氏名: ■これまでの講義内容の整理 ■計画問題の設定と手法
領域分割手法について 2008年2月26日 中島研吾.
k 個のミスマッチを許した点集合マッチング・アルゴリズム
第25章 単一始点最短路 3節 Bellman-Fordのアルゴリズム
決定木とランダムフォレスト 和田 俊和.
ネットワーク理論 Text. Part 3 pp 最短路問題 pp 最大流問題 pp.85-94
定兼邦彦 今井浩 東京大学理学系研究科 情報科学専攻
アルゴリズムとデータ構造 2013年7月16日
グラフアルゴリズムの可視化 数理科学コース 福永研究室 高橋 優子 2018/12/29.
アルゴリズムイントロダクション 第24章 単一始点最短路問題
コードクローン検出ツールを用いた ソースコード分析システムの試作と プログラミング演習への適用
SOA基盤製品 「見る、聞く、体験する SOAノウハウツアー」
多変量解析ゼミ 第10回 第12章クラスター分析 発表者 直江 宗紀.
主成分分析 Principal Component Analysis PCA
25. Randomized Algorithms
アルゴリズムとデータ構造 2012年7月17日
First Course in Combinatorial Optimization
プログラミング 4 整列アルゴリズム.
2009/10/23 整列アルゴリズム (1) 第4講: 平成21年10月23日 (金) 4限 E252教室 コンピュータアルゴリズム.
プログラミング 4 探索と計算量.
7. 機能的な組み合わせ回路 五島 正裕.
実空間における関連本アウェアネス 支援システム
Peer-to-Peerシステムにおける動的な木構造の生成による検索の高速化
情報知能学科「アルゴリズムとデータ構造」
問題作成、解説担当:中島 副担当:坪坂、松本
データ構造とアルゴリズム (第5回) 静岡大学工学部 安藤和敏
短い部分文字列の ミスマッチトレランスを 高速計算するアルゴリズム
大規模ネットワークに対する 実用的クラスタ発見アルゴリズムの開発
アルゴリズムとデータ構造 2011年7月11日
アルゴリズムとプログラミング (Algorithms and Programming)
クローン検出ツールを用いた ソフトウェアシステムの類似度調査
情報ネットワーク 岡村耕二.
2009/11/27 グラフ (1) 第9講: 平成21年11月27日 (金) 4限 E252教室 コンピュータアルゴリズム.
精密工学科プログラミング基礎 第7回資料 (11/27実施)
2008年6月5日 非線形方程式の近似解 2分法,はさみうち法,Newton-Raphson法)
発表者: 稲葉 一浩 複雑ネットワーク・地図グラフ セミナー 2017/1/19
コストのついたグラフの探索 分枝限定法 A*アルゴリズム.
精密工学科プログラミング基礎Ⅱ 第2回資料 今回の授業で習得してほしいこと: 配列の使い方 (今回は1次元,次回は2次元をやります.)
第4章 空間解析 2.ネットワーク分析 (2) 最大流問題
ベイジアンネットワークと クラスタリング手法を用いたWeb障害検知システムの開発
プログラミング論 バイナリーサーチ 1.
Presentation transcript:

最短路を ものすごくはやく 答える方法

背景 目的 ★ カーナビゲーションシステム ★ Web上の検索システム ★ DIMACS Challenge 9 (shortest path) 目的 (始点・終点が指定された)最短路を高速に答える 仮定1:ネットワークは滅多に変化しない 仮定2:最短路の問い合わせは頻繁 →最短路高速検索のための理論・データ構造の構築 ★ ネットワークデータに対して何時間も前処理して良い ★ 最短路を答える際の負荷(時間・メモリ)は小さくしたい

google mapの検索例 応答時間は1秒未満

(始点終点が指定された)最短路問題 入力:有向グラフG=(V,E),枝長さ関数d:E→R+始点s,終点t 出力:グラフG上のs-tパス 目的:最短のs-tパスを見つける Dijkstra法 ポテンシャルyの初期設定 S := V while S ≠ φ do yvが最小の点v∈Sを選択 S := S\{v} for all w:vw∈E and w∈S do if yv + cvw < yw then yw := yv + cvw 計算時間O(m log n), メモリ使用量O(n + m)

最短路応答時間と メモリ使用量の trade off 応答時間 前処理なし →Dijkstra法を適用 このあたりを 狙いたい あらかじめ全点間最短路を 計算し記憶 →覚えた最短路を答えるだけ メモリ使用量

基本的な考え方1 オレンジ枠の外側に始点および終点がある最短路をすべて求める(黒線) 赤枠の内側で最短路に使われている道をすべて覚える(黒太線) 直感的解釈:覚えた道は赤枠から遠いところ同士を結ぶ最短路で使われる道

基本的な考え方1 オレンジ枠の外側に始点および終点がある最短路を求める場合には 赤枠の内側では覚えた線(黒太線)のみを使っても最短路を求めることができる →最短路計算で使われるデータが少なくなる

基本的な考え方2 位置をずらした枠で同様に,遠いところ同士の最短路に使われる道を覚えておけば 最短路計算で使われるデータがさらに少なくなる

基本的な考え方2 たくさんの枠で同様に,遠いところ同士の最短路に使われる道を覚えておけば 最短路計算で使われるデータがさらに少なくなる

基本的な考え方3 枠の大きさは大きくても小さくてもよい 大きい枠→覚える道は少ない : 始点や終点の近くでは使えない 大きい枠→覚える道は少ない : 始点や終点の近くでは使えない 小さい枠→覚える道は多い : 始点や終点の近くでも使える

基本的な考え方(まとめ) いろいろな大きさの枠で,遠いところ同士の最短路で使われる道を覚え, 始点と終点が指定されたら,なるべく道数の少ないネットワークを構成し (大きい枠を優先的に使う),最短路を計算する

基本的な考え方(まとめ) いろいろな大きさの枠で,遠いところ同士の最短路で使われる道を覚え, 始点と終点が指定されたら,なるべく道数の少ないネットワークを構成し (大きい枠を優先的に使う),最短路を計算する

最短路応答時間 応答時間 テキサス州 平均約36ms 元のデータの大きさ 州ごとに1000対の始点・終点をランダムに選出 応答時間の平均値をプロット 一番大きいテキサス州で平均約36msの応答時間 (Dijkstra法に比べ約100倍の高速化)

抽出された道路データの大きさ 付加データの大きさ テキサス州 元データ:約512万 付加データ:約507万 元のデータの大きさ データの大きさ=道路の数 抽出されたデータの大きさは,元の大きさとほぼ同じ

前処理(道路の抽出)時間 前処理時間 テキサス州 元データ:約512万 前処理時間:約8時間 元のデータの大きさ 最も大きいテキサス州で約8時間

結論 今後の課題 最短路検索を高速に行うためのグラフ疎化法を開発 利点:他の探索法との組み合わせが容易,単純 欠点:これ単独ではたいした高速化ではない(高々1000倍程度) 今後の課題 ★ さらなる高速化,目標は1,000,000倍 ★ 他の探索手法との組み合わせ ★ 単純な最短路から拡張 →多目的最短路 →条件付き最短路

応答時間:通常のダイクストラ法の500倍(4ms) 関連研究【ビットベクトル法】 An Experimental Evaluation of Point-To-Point Shortest Path Calculation on Roadnetworks with Precalculated Edge-Flags Ulrich Lauther (シーメンズ) (1次元)ビットベクトルを用いた高速化 前処理の工夫 再最適化の利用 ビットがすべて0の枝は除く 同じビットベクトルをもつ枝の情報の統合 問題例:600万点,1千600万枝 前処理:約100分,メモリ:1枝あたり6バイト 応答時間:通常のダイクストラ法の500倍(4ms)

関連研究【 Highway Hierarchies 】 Highway Hierarchies Star Daniel Delling, Peter Sanders, Dominik Schultes, and Dorothea Wagner (カールスルーエ大) 階層ネットワークによる方法+ランドマークを用いたA*探索 階層の最上位では距離行列を保管 問題例:ヨーロッパ(1千800万点,4千200万枝)とUSA(2千400万点,5千800万枝) 前処理:ヨーロッパ(21分,1714MB),USA(25分,2013MB) 応答時間:ヨーロッパ(0.66ms;20-30倍),USA(0.71ms;15-20倍)

関連研究【A. +ランドマーク】 Better Landmarks within Reach Andrew V 関連研究【A*+ランドマーク】 Better Landmarks within Reach Andrew V. Goldberg, Haim Kaplan, and Renato F. Werneck (マイクロソフト研究所) 到達限界(reach)とA*探索とランドマークを合わせた解法(REAL:Reach+A*+Landmark) 問題例:ヨーロッパ(1千800万点,4千200万枝)とUSA(2千400万点,5千800万枝) 前処理:ヨーロッパ(143分,703MB),USA(142分,1019MB) 応答時間:ヨーロッパ(1.8ms),USA(1.5ms):階層ネットワーク法より若干遅い