Chap7-2

７章最短路問題（続）
杉原厚吉．（２００１）.「データ構造とアルゴリズム」.
東京：共立出版.
2011/07/19
情報知能学科「アルゴリズムとデータ構造」
担当：白井英俊
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 アルゴリズム
• 入力：グラフ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)に
Shortest-Pathにおけるヒープの役割
• 出発点sから「到達可能な」頂点と、出発点ｓからの距離
を記憶
• 簡単な動きの解説
1. 登録：始点から到達可能な頂点と、その始点からの距離の見
積もりをすべて登録
2. 取り出し：始点から最短距離にある頂点が順にとりだされる
取り出された頂点は、始点からの最短距離が確定
3. 距離の更新：「取り出された」頂点を経由する経路による距離
と、見積もりの距離を比較。前者が小さい場合に距離を更新
 辺の長さが負でない限り、この方法は、始点からの距離が小さ
い頂点を順番に「取り出す」ことを保証する
ヒープ（3章から）
• ヒープ(heap)とは、特殊な二進木
定義3.2 高さkの二進木Tがヒープであるための
必要十分条件は次の(i), (ii)を満たすこと
(i) 深さ0 ～ k-1 の可能な頂点はすべて使われ、
深さkの頂点は左から順に使われている
(ii) 頂点uが頂点vの親なら
uの値( f(u) ) ≦
≧ vの値( f(v) ) 最短路探索
親
子
（iii) ｢値」だけではなく頂点も記憶
のための修正
ヒープの操作
• 入力データからヒープを作る
(1) 新たな要素を値とする頂点をヒープに追加
⇒ 条件(i)を満たすところに追加
ヒープを配列で実現する場合、「最後の要素のインデック
ス＋1 」目に要素を追加
(2) 次に、ヒープ条件(ii)を満たすように修正(reform)
付け加えられた要素とその親を比較し交換する、を繰り返す
• ヒープから頂点の要素を取り出してから、ヒープをつ
くり直す
ヒープの最後の要素を『根』に移動し、親と子を比較し、
「小さい」方の子と親を交換する、を繰り返す
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)を更新
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の振る舞いを示せ。
演習問題 7.1 vs =v0, vt = v6のときのアルゴ
リズムShortest-Pathの振る舞い
頂点のリスト（ヒープで表現）
括弧内は始点からの
0
距離(dの値)
v
1 2
v1
1
0
(1) v0(0)
(2) v1(0+1), v10(0+3)
4
2
1 v11 5
6
3
3 v10
(3) v11(1+1), v2(1+2) , v10(3)
(4) v10(3), v2(3), v9(2+3), v12(2+5)
(5) v2(3), v12(7), v9(5),
(6) v9(5),v12(7), v3(8)
(7) v13(5+1), v12(7), v8(5+5) , v3(8)
(8) v12(7), v3(6+1<8), v8(6+3<10)
(9) v3(7), v8(9), v5(7+2)
v2 3
7 5 v3 78
v12 8 1
7
1
2
5
v9
2
6
v13
3
1
3
v4
5
2
9
v5
6
1
9v
2
v7
8
(10) v5(9), v8(9), v4(7+8)
(11) v8(9), v4(9+2<15), v6(9+1),
(12) v6(10), v4(11), v7(9+1)
答え： v6(10)
10
1 v6
課題(教科書 p. 77)
1. 演習問題 7.1
図6.8のグラフで、 vs =v0, vt = v6とおいたときのアル
済み
ゴリズムShortest-Pathの振る舞いを示せ。
2. 演習問題7.2
本日の課題
アルゴリズムShortest-Pathを変更して、頂点vsから
他のすべての頂点までの最短路の長さを求めるア
ルゴリズムを作れ。またshortestPath.rbを改変してこ
れを実現せよ。
別課題：最短路の経路を返すように改変せよ
Shortest-Path プログラム
アルゴリズムからプログラムを実現するた
めに
１．ヒープの実現
２．グラフの表現
を考える必要がある
ヒープの実現
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)
ヒープの実現
heap4Graph.rbファイルから
class Heap
def initialize # ヒープを配列で実現
@size = 0
# ヒープが空かどうかの判定
@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
グラフの表現
• グラフ探索の場合とほぼ同じ考え方
• ただし、辺の長さを記録する必要がある
隣接頂点と辺の長さの対
class Arc
def initialize(x,y)
@node = x
@distance = y
end # def
def value
return @distance
end
end # class
グラフの頂点の表現
グラフ探索とほぼ同じだが、インスタ
ンス変数edgeの値に変更あり
class GraphNode
def initialize(x="")
@label=x
@edges=Hash.new(false)
end # def
attr_accessor :label, :edges
グラフの頂点：辺の長さの記録
参考
class Arc
def initialize(x,y)
@node = x
@distance = y
end # def
class GraphNode
def initialize(x="")
@label=x
@edges=Hash.new(false)
end # def
def addEdge(arc)
if (arc.class == Arc) && (@edges[arc.node] == false)
@edges[arc.node] = arc.distance
end # if
end # def
これにより、v1からv2への辺の長さが
v1.edges[v2] で得られる（辺がなければ falseを返す）
グラフの表現
v = Array.new
vは頂点の配列
for i in 0..13
v[1], v[2], …などによって
v[i]=GraphNode.new("v#{i}")
頂点v1, v2,…を取り出せる
ようにする
end
Edges = [
Edgesの要素一つ一つを取り出し、
[v[0], [Arc.new(v[1],1),
頂点それぞれに辺の情報を記録
Arc.new(v[10],3)]],
Edges.each do |x|
[v[1], [Arc.new(v[0],1),
x[1].each do |z|
Arc.new(v[11],1), Arc.new(v[2],2)]], x[0].addEdge(z)
中途略
end
end
]
Edgesは [ 頂点、辺のリスト]
を要素とする配列
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)に
Shortest-Pathプログラム
def shortestPath(s,t) # sは始点、tは終点
1. d(vs) ← 0
$dist[s]=0
# $dist はすべての頂点に対してsからの距離を記録
2. V-{ vs } に属すすべての頂点 v
h = Heap.new # h はヒープ
に対してd(v) ← ∞
h.insert(s) # まずhに始点を登録 3. A ← { v }
s
loop { # 繰り返し
4. Aの中の頂点のうち d が最小の
v を取り出す
s = h.delete_min
# ヒープの根(最小距離の頂点)を取り出す
5. v = vt ならば d(vt) を出力して
break if (t == s) # それが終点なら終了
終了
s.adjacentNodes.each do |x| # sの隣接頂点それぞれ(x)に対し
6. T(v) に属す各頂点 w に対して
updateDist(s,x,h)
d(w)= ∞ ならAに追加し、d(w)を
end # each
計算。
それ以外ならd(w)を更新
}
4 へ進む
return $dist[t] # 始点から終点までの距離を返す
end # def
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 # if
end # def
演習問題7.2
• アルゴリズムShortest-Pathを変更して、頂点vsから他のすべて
プログラム
の頂点までの最短路の長さを求めるアルゴリズムを作れ。
ここが終了条件。
手続き
1. d(vs) ← 0 vtで止めなければすべての頂点を調べる？
2. V-{ vs } に属すすべての頂点 vに対してd(v) ← ∞
3. A ← { vs }
4. Aの中の頂点のうち d が最小の v を取り出す
5. （５の項目を削除）
v = vt ならば d(vt) を出力して終了
6. T(v) に属す各頂点 w に対して d(w)= ∞ ならAに追
加し、d(w)を計算。
それ以外ならd(w)を更新
7. ４へ進む
Aが空ならdを返して終了。さもなくば4へ進む
ただし、これでは終了条件がなくなるので…
演習問題
• アルゴリズムShortest-Pathを変更して、頂点sから頂点tまでの
最短路の長さと、経路(ｓからｔまでのパスの上の頂点の列）を
求めるアルゴリズムとプログラムを作れ。
手続き r をハッシュ表とする
r(vs ) ← [vs ] # 値はリスト/配列とする
1. d(vs) ← 0
2. V-{ vs } に属すすべての頂点 vに対して
r(v ) ← [ ]
d(v) ← ∞
3. A ← { vs }
4. Aの中の頂点のうち d が最小の v を取り出す
5. v = vt ならば d(vt) と r(vt ) を出力して終了
6. T(v) に属す各頂点 w に対して d(w)= ∞ ならAに追
加し、d(w)を計算。 r(w) ← r(v)+[w] # リスト／配列の接合
それ以外ならd(w)を更新値を更新するなら
7. ４へ進む
r(w) ← r(v)+[w]
質問がなければ
• これらのプログラムの完成を出欠レポートの
課題とします
• できない場合は宿題（締切りは7月18日）

Download Report