アルゴリズムからプログラムへ GRAPH

アルゴリズムからプログラムへ
GRAPH-SEARCH
情報知能学科
白井英俊
GRAPH-SEARCH (教科書、p.62)
入力：
グラフGを表す隣接頂点関数Tと初期頂点v0
出力： Gのすべての頂点のリスト
手続き：
1. 頂点を入れるための入れ物A,B（初期値は空）
2. v0をAとBに入れる
3. Aから一つの頂点vを取り出し「T(v)に属す頂点でB
に入っていないものがあれば、AとBに入れる」
4. Aが空ならBを出力して終了。そうでなければ３へ。
３の実現方法はいろいろ---p.62の方式を次に示す
グラフの表現
グラフGは頂点の集合Vと枝の集合Eの組合せ
V={v1, v2, v3,v4}
E={ {v1, v2 }, {v2 , v3}, {v1, v3 }, {v3, v4 } }
ここでは頂点v0から始めてVを求めることが目的。Gは
上記の形で与えられてはおらず、
「グラフGを表す隣接頂点関数Tと初期頂点v0」で与え
られている
⇒ 頂点ごとに、それにTという関数によって隣接する頂
点の集まりが得られる、と考える
ひとつの表現方法
V={v1, v2, v3,v4}
E={ {v1, v2 }, {v2 , v3}, {v1, v3 }, {v3, v4 } }
に対しては、
T(1)={2, 3}
T(2)={1, 3}
T(3) ={1,2,4}
T(4)={3}
という関数Tを作る
v2
v4
v1
v3
集合と配列
たとえば
T(1)={2, 3}
をRubyで表現（実現）することを考えよう。
Rubyでは「集合」を表現することはできない（そうういう
データ構造を持っていない）
しかし、「データの集まり」を表すには「配列」でもよさそ
う。。。
とすると、E={ {v1, v2 }, {v2 , v3}, {v1, v3 }, {v3, v4 } }は
T=[nil, [2,3], [1,3], [1,2,4], [3] ] で表現できそう
T(1)
T(2)
T(3)
T(4)
別な方法
今までの講義では、木をClassを用いて表してきた
今示した配列を使う方法とは相容れない…
そこで、グラフもClassを用いて表すことを考えよう
class GraphNode
一つ一つの頂点を表現
def initialize(x="")
@label=x
頂点のラベル
@edges=Array.new
隣接頂点を要素とする配列
end # def
Classによるグラフの表現
Classを用いてグラフの頂点を表すとすれば、
頂点v1に対する隣接頂点関数の値 T(v1)は、
v1.edges
v
で与えられる。つまり、
v1.edges ⇒ [v2, v3]
2
v1
注意： edgeとは「辺」のこと。でも上では
隣接頂点を要素とする配列が得られる。
このままだと名前が誤解を与えかねないので、
adjacentNodes (実質はedgesと同じ）
v3
によって隣接頂点関数(T)の代わりをさせることとする
つまり、上の例では v1.adjacentNodes によってv1の隣接頂点が得られる
v4
GRAPH-SEARCH (教科書、p.62)
• 入力：グラフGを表す隣接頂点関数Tと初期
頂点v0
• 出力： Gのすべての頂点のリスト
手続き：
1. 頂点を入れるための入れ物A,B（初期値は空）
2. v0をAとBに入れる
3. Aから一つの頂点vを取り出し「T(v)に属す頂点でB
に入っていないものがあれば、AとBに入れる」
4. Aが空ならBを出力して終了。そうでなければ３へ。
３の実現方法はいろいろ---p.62の方式を次に示す
関数graphSearch
アルゴリズムの記述から
def graphSearch(v0)
(1) 入れ物A, Bを用意する
(2) 入れ物A, Bにv0を入れる
(3) Aから一つの頂点vを取り出し「T(v)に属す頂点
でBに入っていないものがあれば、AとBに入れる」
(4) Aが空ならBを出力して終了。そうでなければ(3)へ
end
という大まかな構造が見える
(1)入れ物A, Bを用意する
プログラムにおいて「入れ物」とは何か？
答え：データを記憶するための変数、配列、など
のこと
ただし、変数で記憶できるのは高々１つ
配列やハッシュ、スタック、キューなど、いろいろ
な要素を記憶できるものが「入れ物」と呼ぶの
にふさわしい
(1)入れ物A, Bを用意する（続き)
ここでは、Aにはスタックかキューのどちらかを使う（指定
済み）
Bは指定がないので、配列、ハッシュ、…なんでもよい？
なぜ重要かは（３）で説明
どういう用途の「入れ物」かが選択の鍵
(3)で「Bに入っているかどうか」が重要
⇒Bの中の要素を「すばやく」検索できるデー
タ構造が向いている⇒それならハッシュ！
でも、どうやって「用意する」？
(1)入れ物A, Bを用意する（続き)
• 配列、ハッシュ、キュー、スタックなどの「デー
タ構造」は、newメソッドでインスタンスを作る
• 例
配列： Array.new
ハッシュ： Hash.new
スタック： Stack.new
キュー： Queue.new
木： …
これらはRubyの組み込み
（最初からある）のデータ構造
これらはRubyの組み込みではない
別途Classの宣言が必要
しかし、newによってインスタンスを
作ることは同じ
キューとスタックの準備
• キューのクラス
queueX.rb
class Queue
attr_accessor :head, :tail
def enqueue(item) … end
def dequeue … end
def empty
… end
def find(item) … end
end
• スタックのクラス
stackX.rb
class Stack
attr_accessor :data, :top
def push(item) … end
def popup
…
end
def empty
…
end
end
GRAPH-SEARCHプログラム(queue版)
def graphSearchQ(v)
# キューを用いたグラフ探索
check = Hash.new(false)
# 頂点が記録済みかどうかのチェック用(B)
agenda = Queue.new
# 調査すべき頂点の記憶用(A)
agenda.enqueue(v)
# 始点vをAに入れる(enqueue)
result = [v]
# 始点vを訪問リストに入れる
check[v] = true
#始点vを記録済みとしてチェック
while (! agenda.empty)
# 調査すべき頂点がある限り繰り返し
v = agenda.dequeue
# 次に調査すべき頂点(v)を取出す
for w in v.adjacentNodes
# vに隣接する頂点それぞれ(w)に対し
if (! check[w])
# wが記録済みでなければ
agenda.enqueue(w)
# wを調査すべき頂点に登録(A)
check[w]=true
# wを記録済みとして登録(B)
result << w
# wを訪問リストの末尾に入れる
end # if
end # for
end # while
return result
# (すべての頂点を調査したので) 訪問リストを返す
end # def
関数graphSearch
アルゴリズムの記述から
def graphSearch(v0)
(1) 入れ物A, Bを用意する
(2) 入れ物A, Bにv0を入れる
(3) Aから一つの頂点vを取り出し「T(v)に属す頂点
でBに入っていないものがあれば、AとBに入れる」
(4) Aが空ならBを出力して終了。そうでなければ(3)へ
end
という大まかな構造が見える
(2) 入れ物A, Bにvを入れる
入れ物とは、配列、ハッシュ、スタック、キュー等のこと
これにvを入れるとは？
配列の場合：インデックスを指定するか、後に付加えるのが普通。
例：arrを配列、iをインデックス用の変数とすれば、
arr[i]=v や arr << v など。
ハッシュの場合：vそのものをインデックスとして、値にnil以外を
与える.
例： h をハッシュとすれば、 h[v] = true
参考：ハッシュの場合、「入っていないもの（たとえばw)を参照
しようとするとnilが値となる. h[w] -> nil
では、スタックやキューに入れるには？
(2) 入れ物A, Bにvを入れる（続)
スタックやキューに入れるには?
そう、もう学んだこと…
スタック： stをスタックとすれば、st.push(v)
キュー： qをキューとすれば、 q.enqueue(v)
質問：スタックやキューの中のものを取り出すには？
答：スタック： stをスタックとすれば、st.popup
キュー: qをキューとすれば、 q.dequeue
GRAPH-SEARCHプログラム(queue版)
def graphSearchQ(v)
# キューを用いたグラフ探索
check = Hash.new(false)
# 頂点が記録済みかどうかのチェック用(B)
agenda = Queue.new
# 調査すべき頂点の記憶用(A)
agenda.enqueue(v)
# 始点vをAに入れる(enqueue)
result = [v]
# 始点vを訪問リストに入れる
check[v] = true
#始点vを記録済みとしてチェック
while (! agenda.empty)
# 調査すべき頂点がある限り繰り返し
v = agenda.dequeue
# 次に調査すべき頂点(v)を取出す
for w in v.adjacentNodes
# vに隣接する頂点それぞれ(w)に対し
if (! check[w])
# wが記録済みでなければ
agenda.enqueue(w)
# wを調査すべき頂点に登録(A)
check[w]=true
# wを記録済みとして登録(B)
result << w
# wを訪問リストの末尾に入れる
end # if
end # for
end # while
return result
# (すべての頂点を調査したので) 訪問リストを返す
end # def
関数graphSearch
アルゴリズムの記述から
def graphSearch(v0)
(1) 入れ物A, Bを用意する
(2) 入れ物A, Bにv0を入れる
(3) Aから一つの頂点vを取り出し「T(v)に属す頂点
でBに入っていないものがあれば、AとBに入れる」
(4) Aが空ならBを出力して終了。そうでなければ(3)へ
end
という大まかな構造が見える
(3) Aから一つの頂点vを取り出し...
Aにはスタックかキューを使う（指定済み）
Aから要素を取り出してそれをvとする、ということ
Aがスタックの場合（もうわかっていますね？）
スタックから要素を取り出すには…
だからstをスタックとすればｖ=
Aがキューの場合
穴埋め！
キューから要素を取り出すには…
だからqをキューとすればｖ=
…「T(v)に属す頂点でBに入っていないも
のがあれば、AとBに入れる」
(3)の前半でAから取り出された頂点をv‘とし、T(v’)の一つの要素
をvとしておく
vがBに入っているかいないかは、どうやってわかる？
Bはハッシュを使うことにした(スライド11枚目）
…それは、検索が速いから。でもどうやって？
答え：hをハッシュとすれば h[v]の値でわかる
説明： hに要素(例えばw)を入れる時に、
h[w]=true として値を設定。だから「true以外」の
値が返されれば、「入っていない」ことがわかる
ここで、条件式について一言
条件式は、 if 条件式 … elsif 条件式 … end
や、 while 条件式… end などで用いられる
Rubyの場合、条件式がtrueを返すと、その条件式が
「成り立った」ことになり、たとえばifではその次のプロ
グラムが、whileではendまでのプログラムが実行され
る
たとえば、 x==3はxが3ならtrue、そうでなければfalseを
返す
条件式の値がfalse(やnil)の場合、その条件式は「成り
立たなかった」ということになる
vがBに入っているかいないか
なぜこれが重要なのだろうか？
このチェックをしないプログラムを書いた人から
のコメント：「キューにものが入りすぎてQueue
overflowが表示されてしまう」
グラフは(木と異なり)頂点から枝をたどっていくと
、その頂点に戻る可能性がある。つまり迷路
でいえば同じところをぐるぐる回ってしまう可能
性がある。これを何とかしたい！
→ 頂点をAにいれるための条件として「すでに訪れたことがない」
（Bに入っていない）とすればよい
(3)をまとめて書くと。。。
確認：「T(v)に属す頂点でBに入っていないものがあれば、
AとBに入れる」は大丈夫ですね？（「AとBに入れる」方
法はもうわかっている？） v.adjacentNodesでT(v)の代わりをする
以下ではAをキューとします（スタックの場合は自分で書い
てみてください）
A(キューqとする）から一つの頂点v1を取り出し
v1 = q.dequeue
「T(v1)に属す頂点vでB(hとする)に入っていないものがあれ
ば、AとBに入れる if (h[v1.adjacentNodes] != true)
q.enqueue(v.adjacentNodes);
おっと！v.adjacentNodesは配列だ！
h[v.adjacentNodes]=true
end
(3)をまとめて書くと。。。
ちょっと焦りすぎました
頂点vに隣接する頂点集合が v.adjcentNodes
(T(v)と同じ）で得られるのですが、これは頂点を
要素とする配列を返す
これをそのままAやBに入れてはいけません（A
やBに入れるのは「頂点」と決めているので）
ここは「繰り返し」(forやwhile)を使って、
v.adjcentNodesの要素を一つ一つBにないこと
を確認して次々AやBに入れる必要があります
GRAPH-SEARCHプログラム(queue版)
def graphSearchQ(v)
# キューを用いたグラフ探索
check = Hash.new(false)
# 頂点が記録済みかどうかのチェック用(B)
agenda = Queue.new
# 調査すべき頂点の記憶用(A)
agenda.enqueue(v)
# 始点vをAに入れる(enqueue)
result = [v]
# 始点vを訪問リストに入れる
check[v] = true
#始点vを記録済みとしてチェック
while (! agenda.empty)
# 調査すべき頂点がある限り繰り返し
v = agenda.dequeue
# 次に調査すべき頂点(v)を取出す
for w in v.adjacentNodes
# vに隣接する頂点それぞれ(w)に対し
if (! check[w])
# wが記録済みでなければ
agenda.enqueue(w)
# wを調査すべき頂点に登録(A)
check[w]=true
# wを記録済みとして登録(B)
result << w
# wを訪問リストの末尾に入れる
end # if
end # for
end # while
return result
# (すべての頂点を調査したので) 訪問リストを返す
end # def
関数graphSearch
まだ完成ではありません。(4)を忘れています。
def graphSearch(v0)
(1) 入れ物A, Bを用意する
(2) 入れ物A, Bにv0を入れる
(3) Aから一つの頂点vを取り出し「T(v)に属す頂点
でBに入っていないものがあれば、AとBに入れる」
(4) Aが空ならBを出力して終了。そうでなければ(3)へ
end
という大まかな構造が見える
(4) Aが空ならBを出力して終了。そうでな
ければ(3)へ
(4)を忘れていました。ここでは二つ大事なことがあります
1. どういう値を返すか … このアルゴリズムではB（ハッ
シュを使っている）を返すことになっている
2. 「そうでなければ（３）へ」はどうするか？
これは「繰り返し」を意味する
1に対しては、hをハッシュとすれば、h.keysによって、
記憶された頂点を配列にして返してくれます（？！）
2に対しては、A(スタックかキュー)が空かどうかを判定
するメソッドを使います（そのためにemptyというメソッド
をあらかじめ定義しておいた）
(4) Aが空ならBを出力して終了
「何を返すか」は本当は大事な問題
B（ハッシュhとする）に入っている頂点の集合を
返すだけなら、h.keys でよいが。。。
ここでは、どの頂点がどういう順番で入ってきた
かも示したい（と思いません？）
だから、resultという配列を別に用意して、それを
返すようにした
最終形は次のスライド…
GRAPH-SEARCHプログラム(queue版)
def graphSearchQ(v)
# キューを用いたグラフ探索
check = Hash.new(false)
# 頂点が記録済みかどうかのチェック用(B)
agenda = Queue.new
# 調査すべき頂点の記憶用(A)
agenda.enqueue(v)
# 始点vをAに入れる(enqueue)
result = [v]
# 始点vを訪問リストに入れる
check[v] = true
#始点vを記録済みとしてチェック
while (! agenda.empty)
# 調査すべき頂点がある限り繰り返し
v = agenda.dequeue
# 次に調査すべき頂点(v)を取出す
for w in v.adjacentNodes
# vに隣接する頂点それぞれ(w)に対し
if (! check[w])
# wが記録済みでなければ
agenda.enqueue(w)
# wを調査すべき頂点に登録(A)
check[w]=true
# wを記録済みとして登録(B)
result << w
# wを訪問リストの末尾に入れる
end # if
end # for
end # while
return result
# (すべての頂点を調査したので) 訪問リストを返す
end # def
出欠課題（その２）
本日のウェブページから、graphSearch.rb をダウンロー
ドする
そこには queue版のGraph-Searchプログラムが載って
いる
(1) それを動かしてみる。ｖ6を出発点とした時の頂点の
リストが表示されるので、自分の解答と比較する(最
後にエラー表示されるが無視すること）
(2) queue版にならってstack版を作る（graphSearch.rbの
graphSearchS関数を完成させる）
(3) 完成したら、v6を出発点とした時の頂点のリストが
表示されるので自分の解答と比較する

Download Report