書誌事項
- タイトル別名
-
- FAST IMPLEMENTATION OF DIJKSTRA'S ALGORITHM FOR THE LARGE-SCALE SHORTEST PATH PROBLEM
- ダイキボ サイタンロ モンダイ ニ タイスル ダイクストラホウ ノ コウソクカ
この論文をさがす
説明
最短路問題はネットワーク上の経路探索などの多くの応用を持ち,また他の最適化問題の子問題として用いられることも多く,適用範囲の広い組合せ最適化問題である.そのため最短路問題を高速に解くことの重要性は非常に大きくなってきている.最短路問題に対する解法としてはダイクストラ法などの安定的かつ効率的な高速アルゴリズムが存在するが,実問題は非常に大規模になるためさらなる高速化が不可欠である.そこで本論文では大規模最短路問題に対し,計算機のメモリ階層構造を考慮しつつ汎用的かつ効率的に高速化を行うための実装方法を示す.さらに論文中では計算機のメモリ階層構造における律速箇所の特定を行うための汎用的な解析方法を示し,高速化の有用性を検証していく.本手法により実装されたバイナリ・ヒープを適用したダイクストラ法は,実行性能,安定性,メモリ要求量などを他の実装と比較すると総合的に最も優れているといえる.また本実装を用いた大規模最短路問題に対するオンライン・ソルバーについても説明を行う.
収録刊行物
-
- 日本オペレーションズ・リサーチ学会和文論文誌
-
日本オペレーションズ・リサーチ学会和文論文誌 54 (0), 58-83, 2011
公益社団法人 日本オペレーションズ・リサーチ学会
- Tweet
詳細情報 詳細情報について
-
- CRID
- 1390001205756104192
-
- NII論文ID
- 110008913792
-
- NII書誌ID
- AA11998080
-
- ISSN
- 21888280
- 13498940
-
- NDL書誌ID
- 023468863
-
- 本文言語コード
- ja
-
- 資料種別
- journal article
-
- データソース種別
-
- JaLC
- NDLサーチ
- Crossref
- CiNii Articles
- KAKEN
- OpenAIRE
-
- 抄録ライセンスフラグ
- 使用不可
