利用者:Fujimoto/最短路問題 - 版の履歴

Fujimoto: 数式修正（すべて画像に置換されるよう）

2009-11-05T07:51:07Z

数式修正（すべて画像に置換されるよう）

差分を表示

Fujimoto: URL誤りを訂正

2009-10-21T11:49:05Z

URL誤りを訂正

Fujimoto: 画像追加、ひとまず完成

2009-10-16T12:05:43Z

画像追加、ひとまず完成

Fujimoto: Cite拡張を使って参考文献を埋め込み（いまいち）。いちおう全文整形。画像はまだ。

2009-10-13T12:03:58Z

Cite拡張を使って参考文献を埋め込み（いまいち）。いちおう全文整形。画像はまだ。

差分を表示

Fujimoto: "利用者:Fujimoto/最短路問題" を保護しました。 [edit=sysop:move=sysop]

2009-09-26T11:08:16Z

"利用者:Fujimoto/最短路問題" を保護しました。 [edit=sysop:move=sysop]

Fujimoto: 新規項目「最短路問題」の途中まで入力。リファレンスを生成する拡張ライブラリが入っていなかったので作業中断。

2009-09-26T11:07:41Z

新規項目「最短路問題」の途中まで入力。リファレンスを生成する拡張ライブラリが入っていなかったので作業中断。

新規ページ

'''【さいたんろもんだい (shortest path problem)】'''

== 概要 ==


最短路問題は経路探索などの多くの応用を持ち, また他の[[最適化問題]]の子問題として用いられることも多く, 適用範囲の広い組合せ最適化問題である. そのため, 最短路問題を高速に解くことは重要な意味を持つ. 最短路問題に対する解法には, 安定的かつ効率的な高速な[[アルゴリズム]]が存在するが, 実問題は大規模(全米の道路ネットワークでは, 2400万点, 5800万枝にも及ぶ)になるため高速化が不可欠である.本解説では最短路問題の定義・種類を述べた後, 著名なアルゴリズムである[[ダイクストラ法]]に対する高速実装と実験結果等について説明を行う.

== 詳説 ==

=== 最短路問題の定義と種類 ===
最短路問題は次のような問題である.



<blockquote>
ある有向グラフ<math>G = (V, E)</math> と各枝 <math>(v,w) \in E</math> に重み <math>l(v,w)</math> が付与されているネットワーク <math>N = (G,l)</math> が与えられているとする. このとき有向グラフ <math>G</math> の任意の 2 点 <math>s, t \in V</math> に対し, 点 <math>s</math> を始点とし, 点 <math>t</math> を終点とする有向パス <math>p</math> の中で, その長さ(パスに含まれる枝の重みの合計)が最小のパスを点 <math>s</math> から点 <math>t</math> への最短路 (shortest path) といい, 最短路を求める問題を最短路問題 (shortest path problem) という.
</blockquote>

最短路問題は次のように 3 種類に分けることができる.

;1対全(single-source)最短路問題: 1点から全点に対する最短路と最短距離(最短路の長さ)を求める問題. 非負の枝の重みを持つグラフ上ではダイクストラ(Dijkstra)法が, 負の重みを持つ枝がある場合にはベルマン・フォード(Bellman-Ford)法が有名である.
;全対全(all-pairs)最短路問題: 全点間の最短路と最短距離を求める問題. ワーシャル・フロイド(Warshall-Folyd)法が有名であるが, 1対全最短路問題アルゴリズムを各点に対して適用することでも求めることができる.
;1対1(point-to-point)最短路問題: 2点間の最短路と最短距離を求める問題.

=== 探索アルゴリズムと実装方法 ===

最短路問題に関する探索アルゴリズムの中でも, 最も頻繁に利用されるダイクストラ法を取り上げ, アルゴリズムの説明から, 高速化のための優先キューの適用方法・実装方法について示していく.

==== ダイクストラ法 ====

1959年, E. W. Dijkstra<ref>E. W. Dijkstra, "A Note on Two Problems in Connexion with Graphs," Numerische Mathematik, 1:269-271, 1959.</ref>によって提案された1 対全最短路問題に対するアルゴリズムである. 探索するグラフ上の全ての枝の重みが非負でなければならないが, ベルマン・フォード法{{ref|bellman}} に比べ効率的かつ高速である.ダイクストラ法は, ベルマン・フォード法と同じように動的計画法の一種とみなすことができるが, 点の探索の順序に特徴をもつ. 探索の途中で得られた始点 <math>s</math> からの距離の最小値をポテンシャルもしくは距離ラベルとよび, その値の小さい順に点の探索を行い,最短路および最短距離を確定していく. つまり, 各点に対し, <math>d(s) = 0, d(v) = +\infty (v \in V)</math> とするポテンシャル <math>d</math> を用意し, 探索点 <math>v</math> に接続する枝 <math>(v,w)</math> に対して, <math>d(v) + l(v,w) < d(w)</math> ならば <math>d(w) := l(v,w) + d(v)</math> とする操作を繰り返し行う. 終点 <math>t</math> が探索点になった時点で終了させることで, 1対1最短路問題も効率的に求解可能である.

@@ 4行目: / 4行目: @@
 <!-- 原稿では概要、詳説という分け方になっていないのですが、どうしましょうかね。 -->
-最短路問題は経路探索などの多くの応用を持ち, また他の[[最適化問題]]の子問題として用いられることも多く, 適用範囲の広い組合せ最適化問題である. そのため, 最短路問題を高速に解くことは重要な意味を持つ. 最短路問題に対する解法には, 安定的かつ効率的な高速な[[アルゴリズム]]が存在するが, 実問題は大規模(全米の道路ネットワークでは, 2400万点, 5800万枝にも及ぶ)になるため高速化が不可欠である.本解説では最短路問題の定義・種類を述べた後, 著名なアルゴリズムである[[ダイクストラ法]]に対する高速実装と実験結果等について説明を行う.
+最短路問題は経路探索などの多くの応用を持ち, また他の[[最適化問題]]の子問題として用いられることも多く, 適用範囲の広い組合せ最適化問題である. そのため, 最短路問題を高速に解くことは重要な意味を持つ. 最短路問題に対する解法には, 安定的かつ効率的な高速な[[アルゴリズム]]が存在するが, 実問題は大規模(全米の道路ネットワークでは, 2400万点, 5800万枝にも及ぶ)になるため高速化が不可欠である.本解説では最短路問題の定義・種類を述べた後, 著名なアルゴリズムである[[ダイクストラ法]]に対する高速実装と実験結果<ref>安井雄一郎, 藤澤克樹, 笹島啓史, 後藤和茂, 宮本裕一郎, "大規模最短路問題に対するダイクストラ法の高速化," 2008 年度日本 OR 学会秋季研究発表会. 314-315, 2008.</ref>等について説明を行う.
 == 詳説 ==
@@ 111行目: / 111行目: @@
 ====優先キューの性能====
--heap, Buckets, MLB それぞれの全米道路ネットワークに対しての計算機実験を行い, 実行時間とメモリ要求量をまとめると,表2, 表3のようになる. 用いたグラフデータは, 約 2400 万点, 約 5800 万枝にも及ぶ道路ネットワークを変換させた大規模な実データである(TIGER/Line<ref>http://www.census.gov/geo/www/tiger/tigerua/ua\_tgr2k.html</ref>で公開されている). 実行時間は, ランダムに選択した1対1最短路問題を 256 回解いた際の平均である.
+-heap, Buckets, MLB それぞれの全米道路ネットワークに対しての計算機実験を行い, 実行時間とメモリ要求量をまとめると,表2, 表3のようになる. 用いたグラフデータは, 約 2400 万点, 約 5800 万枝にも及ぶ道路ネットワークを変換させた大規模な実データである(TIGER/Line<ref>http://www.census.gov/geo/www/tiger/tigerua/ua_tgr2k.html</ref>で公開されている). 実行時間は, ランダムに選択した1対1最短路問題を 256 回解いた際の平均である.
 最短路問題では計算量に対してデータ量が大規模であるため, データ型によるメモリ使用量や実行時間に対する影響が大きい. 各変数が 32ビット整数型と 64ビット変数型の 2 種類の計算機実験の結果を記載する. グラフデータは大規模であるが, 32ビット整数型の範囲で収まるため, どちらの場合でもアルゴリズムは正しく終了するが, 距離ラベルはいずれも 64ビット整数である.
@@ 154行目: / 154行目: @@
 == 参考文献 ==
 <references />

@@ 59行目: / 59行目: @@
 ===== 2-heap(バイナリ・ヒープ) =====
 -heap<ref name="heap">J. Williams, "Heapsort," Communications of the ACM, 7:347-348, 1964.</ref>は, 図1のように, 親は高々2つの子を持つ木構造で構成される. 常に親の優先度は子より高い. 点数 ''n'', 枝数 ''m'' に対して, 1対全最短路問題の計算量は <math>O((m+n)\log{n})</math> である.
 -heapは以下の特徴をもつ.
@@ 70行目: / 81行目: @@
 #実行時間・メモリ要求量が, 最大枝長に依存する(重み小:高速, 重み大:低速).
 #道路ネットワークグラフと相性が良い.
 ===== MLB(マルチレベル・バケット) =====
@@ 94行目: / 107行目: @@
 | <math>O(1)</math> || <math>O(1)</math> || <math>O(\log{U})</math> || <math>O(m+n\log{U})</math>
 |}
 ====優先キューの性能====

← 古い版	2009年9月26日 (土) 11:08時点における版
(相違点なし)