大規模最短路問題に対するダイクストラ法の高速化

スポンサーリンク

概要

• 論文の詳細を見る

• 最短路問題はネットワーク上の経路探索などの多くの応用を持ち,また他の最適化問題の子問題として用いられることも多く,適用範囲の広い組合せ最適化問題である.そのため最短路問題を高速に解くことの重要性は非常に大きくなってきている.最短路問題に対する解法としてはダイクストラ法などの安定的かつ効率的な高速アルゴリズムが存在するが,実問題は非常に大規模になるためさらなる高速化が不可欠である.そこで本論文では大規模最短路問題に対し,計算機のメモリ階層構造を考慮しつつ汎用的かつ効率的に高速化を行うための実装方法を示す.さらに論文中では計算機のメモリ階層構造における律速箇所の特定を行うための汎用的な解析方法を示し,高速化の有用性を検証していく.本手法により実装されたバイナリ・ヒープを適用したダイクストラ法は,実行性能,安定性,メモリ要求量などを他の実装と比較すると総合的に最も優れているといえる.また本実装を用いた大規模最短路問題に対するオンライン・ソルバーについても説明を行う.

著者

• 藤澤 克樹

  中央大学

• 藤澤 克樹

  中央大学理工学部経営システム工学科

• 安井 雄一郎

  中央大学

• 笹島 啓史

  中央大学

• 安井 雄一郎

  中央大学理工学研究科経営システム工学専攻

• 藤澤 克樹

  東京電機大学:産業技術総合研究所

• 後藤 和茂

  マイクロソフト株式会社

• 後藤 和茂

  マイクロソフト

関連論文

• 大規模最短路問題に対する高速処理システム : メモリ階層構造の考慮とクラスタ&クラウド技術による高速化 (21世紀の数理計画 : アルゴリズムとモデリング)
• 最適化ソルバー開発への最新の情報技術の適用について(半正定値計画に対するソルバーと応用例)
• 特集にあたって(半正定値計画に対するソルバーと応用例)
• 半正定値計画問題に対するソフトウェア開発で用いられる新技術について (21世紀の数理計画 : アルゴリズムとモデリング)
• 2-G-2 重み付き対数行列式を持つ半正定値計画問題を解くSDPA(連続最適化(1))
• 2-F-14 大規模最短路問題に対するダイクストラ法の高速化(グラフ(2))
• 最短路検索(OR事典Wiki)
• 2-B-8 決定係数最大化ポートフォリオ選択に対する凸最適化アプローチ(連続最適化)
• 1-A-5 大規模最短路問題に対する高速処理システム : メモリ階層構造の考慮とクラスタ&クラウド技術による高速化(つくばOR学生発表(5))
• 最短路問題(OR事典Wiki)
• グリッドチャレンジテストベッドの構築と運用 : グリチャレテストベッドの作り方(HPC-3 : 大規模運用システム(1))
• "Bare Metal" Cloud: 実マシンを提供するクラウドサービス
• 2-D-14 最適化問題用オンライン・ソルバーの構築と自動選択機能の開発(非線形計画(3))
• 庁舎建築の企画・設計におけるコストプランニングシステムに関する研究(建築経済・住宅問題)
• 大規模最短路問題に対するダイクストラ法の高速化 (最適化モデルとアルゴリズムの新展開)
• SDPA project and new features of SDPA 7.1.0 (計算科学の基盤技術としての高速アルゴリズムとその周辺--RIMS研究集会)
• 2-D-6 半正定値計画による分子の電子構造計算(数理計画(1))
• 最適化ソフトウェアSDPA
• 半正定値計画に対する行列補完型主双対内点法の並列化(錘計画問題と相補正問題)
• 半正定値計画問題を解くソフトウェアのPCクラスタ上における並列実装(最適化(2))
• 大規模最短路問題に対するダイクストラ法の高速化 (最適化モデルとアルゴリズムの新展開--RIMS研究集会報告集)
• 最適化問題に対する並列計算技術の適用(パラレルコンピューティングの応用)
• グリッド技術を用いたサプライ・チェイン最適化システム(OR研究の最前線)
• 広域分散コンピューティング環境における数理計画ソフトウェアSDPA
• SOLVING LARGE SCALE OPTIMIZATION PROBLEMS VIA GRID AND CLUSTER COMPUTING(Network Design, Control and Optimization)
• ウェーブレット解析手法を用いた建築内部空間画像と知覚イメージの相関関係の分析
• High Performance Grid Computing for Optimization Problem (Mathematics and Algorithms of Optimization)
• 11022 ウェーブレット解析手法を用いた建築内部空間画像と知覚イメージの相関分析
• 繰り返し型建築工事におけるTOCを用いた工程計画に関する研究
• 建築プロジェクトにおける工事編成最適化 : 工事編成支援システムの提案
• 多面体ホモトピー法から生じる条件付き線形不等式系の全解列挙法
• ENUMERATION OF ALL SOLUTIONS OF A COMBINATORIAL LINEAR INEQUALITY SYSTEM ARISING FROM THE POLYHEDRAL HOMOTOPY CONTINUATION METHOD
• 建築工事編成最適化システムの構築
• 建築生産情報の確定過程に関する研究
• 建築画像の消失点検出手法の開発とそれに基づく3次元建築モデルの再構成手法
• 2-A-15 アルゴリズムサイエンス分野における最適化ソフトウエアの実装方式(計算と最適化(3))
• 1-A-7 計算と最適化の新展開に向けて(計算と最適化(1))
• 最適化分野におけるクラウド技術の利用 (特集 クラウドとアナリティクス)
• 最適化分野におけるクラウド技術の利用(クラウドとアナリティクス)
• 計算機のメモリ階層構造を考慮した高性能ネットワーク解析ライブラリNETAL
• 計算機のメモリ階層構造を考慮した高性能ネットワーク解析ライブラリNETAL
• 計算機のメモリ階層構造を考慮した高性能ネットワーク解析ライブラリNETAL
• 計算機のメモリ階層構造を考慮した高性能ネットワーク解析ライブラリNETAL
• 大規模最短路問題に対するダイクストラ法の高速化
• 2-A-6 最適化と計算に関する最新の傾向について(計算と最適化の新展開)
• 不揮発性メモリを用いたHybrid-BFSアルゴリズムの最適化と性能解析
• 不揮発性メモリを用いたHybrid BFSアルゴリズム
• 不揮発性メモリを用いたHybrid-BFSアルゴリズムの最適化と性能解析
• 最適化と計算の今後 : 大規模問題をどこまで解決できるのか?(研究の楽しさ)
• 2-F-10 最速フローを用いた避難所の評価(最適化(2))
• 1-E-4 大規模グラフに対する幅優先探索の高速化(探索理論)
• 2-E-1 緊急避難計画に対する普遍的最速流の実験的解析(防災・減災)

もっと見る 閉じる

スポンサーリンク