情報知能学科「アルゴリズムとデータ構造」

Presentation on theme: "情報知能学科「アルゴリズムとデータ構造」"— Presentation transcript:

1 情報知能学科「アルゴリズムとデータ構造」
７章　最短路問題（続） 杉原厚吉．（２００１）.「データ構造とアルゴリズム」. 東京：共立出版. 2011/07/19 情報知能学科「アルゴリズムとデータ構造」 担当：白井英俊

2 v0からv6への最短路は？ v0 v1 v2 v10 v11 v12 v5 v3 v6 v4 v9 v8 v13 v7 1 2 4 5 3
注：青字の数は辺の長さを表す （図6.8から）

3 Shortest-Path アルゴリズム 手続き 入力： グラフG=(V, E), 隣接頂点関数T，長さ関数 l, 始点vs，終点 vt
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は始点からの最短距離を記憶するための配列 Aは探索すべき頂点を記憶するためのヒープ ヒープの作り直しが必要 d(w)=d(v)+ l (v,w) 元のd(w)とd(v)+ l (v,w)の最小値を新たなd(w)に

4 Shortest-Pathにおけるヒープの役割
簡単な動きの解説 登録：始点から到達可能な頂点と、その始点からの距離の見積もりをすべて登録 取り出し：始点から最短距離にある頂点が順にとりだされる 　 取り出された頂点は、始点からの最短距離が確定 距離の更新：　「取り出された」頂点を経由する経路による距離と、見積もりの距離を比較。前者が小さい場合に距離を更新 辺の長さが負でない限り、この方法は、始点からの距離が小さい頂点を順番に「取り出す」ことを保証する

5 ヒープ（3章から） 最短路探索 ≦ のための修正 ヒープ(heap)とは、特殊な二進木
定義3.2　高さkの二進木Tがヒープであるための必要十分条件は次の(i), (ii)を満たすこと 　(i) 深さ0 ～ k-1 の可能な頂点はすべて使われ、 深さkの頂点は左から順に使われている 　(ii) 頂点uが頂点vの親なら 　　 uの値( f(u) ) ≧ vの値( f(v) ) 最短路探索 のための修正 ≦ 親 子 （iii) ｢値」だけではなく頂点も記憶

6 ヒープの操作 入力データからヒープを作る ヒープから頂点の要素を取り出してから、ヒープをつくり直す
(1) 新たな要素を値とする頂点をヒープに追加 　　⇒　条件(i)を満たすところに追加 (2) 次に、ヒープ条件(ii)を満たすように修正(reform) ヒープから頂点の要素を取り出してから、ヒープをつくり直す ヒープを配列で実現する場合、「最後の要素のインデックス＋1 」目に要素を追加 付け加えられた要素とその親を比較し交換する、を繰り返す ヒープの最後の要素を『根』に移動し、親と子を比較し、「小さい」方の子と親を交換する、を繰り返す

7 v0からv12への最短路の長さは？ 答： V= {v0, v1, v2, v9, v10, v11, v12} v0 v0 v1 v2
4 3 6 5 7 v2 d 4 A 2 v12 1 v0 v1 v1 1 2 ∞ 1 v11 5 3 v2 3 1+ ∞ 5 v9 7 4 2+ ∞ 3 6 5 ∞ ≦ 2+ v10 3 2 6 1+ ∞ v11 2+ 7 2 ∞ ≦3+ v12 v10 v9 d(vs) ← 0 V-{ vs } に属すすべての頂点 vに対してd(v) ← ∞ A ← { vs } 4. Aの中の頂点のうち d が最小の v を取り出す 5. v = vt　ならば d(vt) を出力して終了 6. T(v) に属す各頂点 w に対し d(w)= ∞ ならd(w) =d(v)+ l (v,w)を計算しwをAに追加。それ以外ならd(w)を更新

8 v0からv6への最短路は？ v0 v1 v2 v10 v11 v12 v5 v3 v6 v4 v9 v8 v13 v7 1 2 4 5 3
注：青字の数は辺の長さを表す （図6.8から）

9 課題(教科書 p. 77) 1. 演習問題 7.1 図6.8のグラフで、 vs =v0, vt = v6とおいたときのアルゴリズムShortest-Pathの振る舞いを示せ。

10 演習問題 7.1 vs =v0, vt = v6のときのアルゴリズムShortest-Pathの振る舞い
3 v2 v3 7 7 5 8 v4 1 2 8 v12 9 4 1 頂点のリスト（ヒープで表現） 括弧内は始点からの 距離(dの値) v1 2 2 10 2 v5 1 6 1 v0 v11 v6 5 1 1 v13 7 6 6 1 3 2 (1) v0(0) 3 3 (2) v1(0+1), v10(0+3) 1 v7 3 v10 2 5 9 v8 (3) v11(1+1), v2(1+2) , v10(3) v9 5 (4) v10(3), v2(3), v9(2+3), v12(2+5) (5) v2(3), v12(7), v9(5), (10) v5(9), v8(9), v4(7+8) (6) v9(5),v12(7), v3(8) (11) v8(9), v4(9+2<15), v6(9+1), (7) v13(5+1), v12(7), v8(5+5) , v3(8) (12) v6(10), v4(11), v7(9+1) (8) v12(7), v3(6+1<8), v8(6+3<10) 答え：　v6(10) (9) v3(7), v8(9), v5(7+2)

11 課題(教科書 p. 77) 済み 本日の課題 1. 演習問題 7.1 2. 演習問題7.2
図6.8のグラフで、 vs =v0, vt = v6とおいたときのアルゴリズムShortest-Pathの振る舞いを示せ。 2. 演習問題7.2 　　アルゴリズムShortest-Pathを変更して、頂点vsから他のすべての頂点までの最短路の長さを求めるアルゴリズムを作れ。またshortestPath.rbを改変してこれを実現せよ。 済み 本日の課題 別課題：最短路の経路を返すように改変せよ

12 Shortest-Path プログラム アルゴリズムからプログラムを実現するために １．ヒープの実現 ２．グラフの表現 を考える必要がある

13 ヒープの実現 heap4Graph.rbファイル参照 ヒープを作る： 例 h = Heap.new
ヒープhに要素sを追加: 　例　h.insert(s) ヒープhの根を削除し、ヒープの修正を行う。削除されたヒープの根の要素を返す　例　 s = h.delete_min 　　 ヒープhから要素xを見つけ、インデックスを返す 　　例 y=h.find(x) ヒープhのインデックスy（その要素の値の変更）に注目してヒープを作り直す　　例 h.up_heap(y)

14 ヒープの実現 heap4Graph.rbファイルから class Heap
　　def initialize # ヒープを配列で実現 @size = @data = [nil] # ヒープが空かどうかの判定 def empty　 end # 最小値を返す def delete_min ... end # fromからtoまでの番号でヒープをつくり直す def down_heap(from,to) end # ヒープに値xを付け加える def insert(x) end # ヒープから値xをもつ要素を探しその番号を返す def find(x)　... end

15 グラフの表現 グラフ探索の場合とほぼ同じ考え方 ただし、辺の長さを記録する必要がある 隣接頂点と辺の長さの対 class Arc
def initialize(x,y) @node = x @distance = y end # def def 　value end end # class グラフの頂点の表現 グラフ探索とほぼ同じだが、インスタンス変数edgeの値に変更あり class GraphNode def initialize(x="") @label=x @edges=Hash.new(false) end # def attr_accessor :label, :edges

16 グラフの頂点：辺の長さの記録 参考 class Arc
def initialize(x,y) @node = x @distance = y end # def class GraphNode end # def def addEdge(arc) if (arc.class == Arc) && == = arc.distance end # if これにより、v1からv2への辺の長さが v1.edges[v2] で得られる（辺がなければ falseを返す）

17 グラフの表現 v = Array.new for i in v[i]=GraphNode.new("v#{i}") end Edges = [ [v[0], [Arc.new(v[1],1), Arc.new(v[10],3)]], [v[1], [Arc.new(v[0],1), Arc.new(v[11],1), Arc.new(v[2],2)]], 中途略 ] vは頂点の配列 v[1], v[2], …などによって 頂点v1, v2,…を取り出せる ようにする Edgesの要素一つ一つを取り出し、 頂点それぞれに辺の情報を記録 Edges.each do |x| x[1].each do |z| x[0].addEdge(z) end Edgesは　　[ 頂点、 辺のリスト] を要素とする配列

18 Shortest-Path アルゴリズム 手続き 入力： グラフG=(V, E), 隣接頂点関数T，長さ関数 l, 始点vs，終点 vt
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は始点からの最短距離を記憶するための配列 Aは探索すべき頂点を記憶するためのヒープ ヒープの作り直しが必要 d(w)=d(v)+ l (v,w) 元のd(w)とd(v)+ l (v,w)の最小値を新たなd(w)に

19 Shortest-Pathプログラム d(vs) ← 0 V-{ vs } に属すすべての頂点 vに対してd(v) ← ∞
def shortestPath(s,t) # sは始点、tは終点 $dist[s]=0 # $dist はすべての頂点に対してsからの距離を記録 h = Heap.new # h はヒープ h.insert(s) # まずhに始点を登録 loop { # 繰り返し s = h.delete_min # ヒープの根(最小距離の頂点)を取り出す break if (t == s) # それが終点なら終了 s.adjacentNodes.each do |x| # sの隣接頂点それぞれ(x)に対し updateDist(s,x,h) end # each } return $dist[t] # 始点から終点までの距離を返す end # def d(vs) ← 0 V-{ vs } に属すすべての頂点 vに対してd(v) ← ∞ A ← { vs } 4. Aの中の頂点のうち d が最小の v を取り出す 5. v = vt　ならば d(vt) を出力して終了 6. T(v) に属す各頂点 w に対して　 d(w)= ∞ ならAに追加し、d(w)を計算。　　　　　　　　　　　　　　　　　　　　　　　　それ以外ならd(w)を更新 4 へ進む

20 def updateDist(s,x,h) # 距離の更新 if ($dist[x] == Max) # 始点からxまでの距離がMaxなら # 「(s,x)の長さ+始点からsまでの距離」をxの距離として登録 $dist[x] = arclength(s,x)+$dist[s] h.insert(x) # xをヒープに登録 else # 上記以外というのは、xが登録済の場合 # 「(s,x)の長さ+始点からsまでの距離」をzとする z = arclength(s,x)+$dist[s] if (z < $dist[x]) # zと登録されたxの距離を比較 $dist[x] = z #zの方が小さければzの値を登録 h.up_heap(h.find(x)) # ヒープの作りなおし end # if end # def

21 演習問題7.2 アルゴリズムShortest-Pathを変更して、頂点vsから他のすべての頂点までの最短路の長さを求めるアルゴリズムを作れ。
プログラム ここが終了条件。 vtで止めなければすべての頂点を調べる？ 手続き 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)を更新 ４へ進む （５の項目を削除）　　　　　　 Aが空ならdを返して終了。さもなくば4へ進む　　　　　　 ただし、これでは終了条件がなくなるので…

22 演習問題 アルゴリズムShortest-Pathを変更して、頂点sから頂点tまでの最短路の長さと、経路(ｓからｔまでのパスの上の頂点の列）を求めるアルゴリズムとプログラムを作れ。 手続き 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)を更新 ４へ進む r をハッシュ表とする r(vs ) ← [vs ] # 値はリスト/配列とする r(v ) ← [　] と　r(vt ) r(w) ← r(v)+[w] # リスト／配列の接合 値を更新するなら 　　r(w) ← r(v)+[w]

23 質問がなければ これらのプログラムの完成を出欠レポートの課題とします できない場合は宿題（締切りは7月18日）