７章最短路問題杉原厚吉．（２００１）.「データ構造とアルゴリズム」. 東京：共立出版. 2011/07/12-07/19 情報知能学科「アルゴリズムとデータ構造」担当：白井英俊本章の目的 • グラフにおいて、「目的の一つの頂点を見つけたところで終了する」探索を学ぶ • 7章では「最短路の探索」を例に取り上げる 7.1 最短路の探索 • グラフ（graph) G：頂点(vertex)の集合Vと辺(edge)の集合の対 頂点の集合V={v1, v2, …, vn}：有限集合 辺の集合E： Vの２つの要素からなる集合(つまり、大きさ２のVの部分集合）の集合。・さらに、どの辺 e ∈E も、非負実数 l(e) という長さが与えられているとする e = {u, v} のとき、 l(e) を l(u, v) とも表す「辺の長さ」のあるグラフの例 v2 2 v1 5 v3 4 v12 8 1 8 v4 2 2 1 1 v0 v11 5 1 v6 1 v13 7 3 6 v5 6 3 1 2 3 v10 2 v9 5 注：青字の数は辺の長さを表す（図6.8から） 1 v8 v7 最短路(shortest path)探索問題一般にコスト（距離、費用、時間など） • グラフ G=(V, E) において、 Vの中で指定された始点 vs と終点 vt に対し、辺をたどってvs から vt へ至る経路のうち、その経路に属す辺の長さの最小値を求める、という問題要するに、「vs と vtを結ぶ、最も近道を求める」という問題 v0からv6への最短路は？ v2 2 v1 5 v3 4 v12 8 1 8 v4 2 2 1 1 v0 v11 5 1 v6 1 v13 7 3 6 v5 6 3 1 2 3 v10 2 v9 5 注：青字の数は辺の長さを表す（図6.8から） 1 v8 v7 Shortest-Path (教科書、p.71) • 入力：グラフG=(V, E), 隣接頂点関数T，長さ関数 l, 始点vs，終点 vt • 出力： vsから vt までの経路の最小値手続き 1. d(vs) ← 0 V-{ vs } に属すすべての頂点 vに対してd(v) ← ∞ A ← { vs } Aの中の頂点のうち d が最小の v を取り出す v = vt ならば d(vt) を出力して終了 T(v) に属す各頂点 w に対して d(w)= ∞ ならAに追加し、d(w)を計算。それ以外ならd(w)を更新元のd(w)とd(v)+ l (v,w)の 7. ４へ進む d(w)=d(v)+ l (v,w) 2. 3. 4. 5. 6. 最小値を新たなd(w)に Graph-SearchとShortest-Path 類似点次に探索すべき頂点の集合記録用のA ・始点vsから初めて、新たに見つかった頂点をAに格納し、・ Aから頂点を取り出してその周りの頂点を調べる違い・見つかった頂点をBに入れる代わりに、始点 vsから見つけた頂点vまでの経路の長さd(v)を記憶・ Aから取り出す頂点vはd(v)最小のもの・終了条件： vtへ到達したら終了(すべての頂点を見るとは限らない） Shortest-Path • 頂点を格納するデータ構造として… 「経路の長さ最小」の頂点を取り出されることが重要---評価値優先探索比較：幅優先探索、深さ優先探索それにはヒープが適しているただし以下の修正が必要こうすれば、根はいつも最小の値（１）親の頂点の値＜子の頂点の値 (2) ｢値」だけではなく頂点も記憶ヒープ（3章から） • ヒープ(heap)とは、特殊な二進木定義3.2 高さkの二進木Tがヒープであるための必要十分条件は次の(i), (ii)を満たすこと (i) 深さ0 ～ k-1 の可能な頂点はすべて使われ、深さkの頂点は左から順に使われている (ii) 頂点uが頂点vの親なら uの値( f(u) ) ≦ ≧ vの値( f(v) ) 最短路探索親子（iii) ｢値」だけではなく頂点も記憶のための修正最短路用のヒープを作る例入力データ: 8 5 3 1 7 10 20 { 8 5 7 3 10 9 6 1 20 } 9 6 ヒープ条件(ii)を破っているので、『修正』が必要 Shortest-Path (再掲) • 入力：グラフG=(V, E), 隣接頂点関数T，長さ関数 l, 始点vs，終点 vt • 出力： vsから vt までの経路の最小値手続き dは始点からの最短距離を記憶するための配列 1. d(vs) ← 0 V-{ vs } に属すすべての頂点 vに対してd(v) ← ∞ Aは探索すべき頂点を記憶するためのヒープ A ← { vs } Aの中の頂点のうち d が最小の v を取り出す v = vt ならば d(vt) を出力して終了ヒープの作り直しが必要 T(v) に属す各頂点 w に対して d(w)= ∞ ならAに追加し、d(w)を計算。 d(w)=d(v)+ l (v,w) それ以外ならd(w)を更新元のd(w)とd(v)+ l (v,w)の 7. ４へ進む 2. 3. 4. 5. 6. 最小値を新たなd(w)に v0からv12への最短路の長さは？答： V= {vv00, v1, v2, v9, v10, v11, v12} vv22 A d 1 0 2 ∞ 3 1+ ∞3 4 2+ 5 ∞ 5 ∞ 6 1+2 ∞ 4 2 v0 v1 v2 v9 ≦ 2+ v10 v11 2+ 7 ∞ ≦3+ v12 v11 11 11 v0 v12 v11 5 11 5 3 6 7 33 vv10 10 2 v9 1. 4. d(v Aの中の頂点のうち d が最小の v を取り出す s) ← 0 2. に属すすべての頂点 vに対してd(v) ← ∞ 5. V-{ v = vvts }ならば d(vt) を出力して終了 3. A ←に属す各頂点 { vs } 6. T(v) w に対し d(w)= ∞ ならd(w) =d(v)+ l (v,w)を計算しwをAに追加。それ以外ならd(w)を更新 Shortest-Pathアルゴリズムの正しさ性質7.1(教科書p.72)：アルゴリズムShortest-Pathのステップ4で Aから取り出された頂点v に対して、その時点での値 d(v) は、vsから vまでの最短路の長さをあらわす証明：数学的帰納法による Shortest-Pathアルゴリズムの計算量・グラフG=(V, する。 4. Aの中の頂点のうち v を取り出す 1. d(vds)が最小の ←0 5. v = vt ならば d(v ) を出力して終了 tV-{ 2. vs } に属すすべての 6. T(v) に属す各頂点 w に対し d(w)= ∞mならd(w) E)の頂点数を頂点 n、辺の数をと∞ vに対してd(v) ← =d(v)+ l (v,w)を計算しwをAに追加。それ以外 3. A ← { vs } ならd(w)を更新 1. アルゴリズムのステップ1, 3, 5は定数時間で実行可能（1と3は初期値を与える、5は終了条件） 2. ステップ2の実行は O(n) --- Vの頂点すべてに対してdの初期値を与える 3. ステップ4は最大でn回の繰り返し。各回でヒープAから最小値を取り出す→ O(n log n) 4. ステップ6は、辺の数m個回、ヒープを作り直すから O(m log n) v0からv6への最短路は？ v2 2 v1 5 v3 4 v12 8 1 8 v4 2 2 1 1 v0 v11 5 1 v6 1 v13 7 3 6 v5 6 3 1 2 3 v10 2 v9 5 注：青字の数は辺の長さを表す（図6.8から） 1 v8 v7 課題(教科書 p. 77) 1. 演習問題 7.1 図6.8のグラフで、 vs =v0, vt = v6とおいたときのアルゴリズムShortest-Pathの振る舞いを示せ。 2. 演習問題7.2 アルゴリズムShortest-Pathを変更して、頂点vsから他のすべての頂点までの最短路の長さを求めるアルゴリズムを作れ。またshortestPath.rbを改変してこれを実現せよ。必要ならば shortestPath.rbの簡単な解説 heap4Graph.rb におけるヒープの解説 graphNode, Arcクラスの解説 shortestPathの解説