アルゴリズムからプログラムへ
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を出力して終了。そうでなければ3へ。
3の実現方法はいろいろ---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を出力して終了。そうでなければ3へ。
3の実現方法はいろいろ---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つ
配列やハッシュ、スタック、キューなど、いろいろ
な要素を記憶できるものが「入れ物」と呼ぶの
にふさわしい
(1)入れ物A, Bを用意する(続き)
ここでは、Aにはスタックかキューのどちらかを使う(指定
済み)
Bは指定がないので、配列、ハッシュ、…なんでもよい?
なぜ重要かは(3)で説明
どういう用途の「入れ物」かが選択の鍵
(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をスタックとすれば v=
Aがキューの場合
穴埋め!
キューから要素を取り出すには…
だからqをキューとすれば v=
…「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. 「そうでなければ(3)へ」はどうするか?
これは「繰り返し」を意味する
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
出欠課題(その2)
本日のウェブページから、graphSearch.rb をダウンロー
ドする
そこには queue版のGraph-Searchプログラムが載って
いる
(1) それを動かしてみる。v6を出発点とした時の頂点の
リストが表示されるので、自分の解答と比較する(最
後にエラー表示されるが無視すること)
(2) queue版にならってstack版を作る(graphSearch.rbの
graphSearchS関数を完成させる)
(3) 完成したら、v6を出発点とした時の頂点のリストが
表示されるので自分の解答と比較する
ダウンロード

Chap6-2Pro