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

Presentation on theme: "アルゴリズムからプログラムへ GRAPH-SEARCH"— Presentation transcript:

1 アルゴリズムからプログラムへ GRAPH-SEARCH
情報知能学科 白井　英俊

2 GRAPH-SEARCH (教科書、p.62) 入力： グラフGを表す隣接頂点関数Tと初期頂点v0 出力： Gのすべての頂点のリスト
手続き： 頂点を入れるための入れ物A,B（初期値は空） v0をAとBに入れる Aから一つの頂点vを取り出し「T(v)に属す頂点でBに入っていないものがあれば、AとBに入れる」 Aが空ならBを出力して終了。そうでなければ３へ。 ３の実現方法はいろいろ---p.62の方式を次に示す 2

3 グラフの表現 グラフGは頂点の集合Vと枝の集合Eの組合せ V={v1, v2, v3,v4}
E={ {v1, v2 }, {v2 , v3}, {v1, v3 }, {v3, v4 } } ここでは頂点v0から始めてVを求めることが目的。Gは上記の形で与えられてはおらず、 「グラフGを表す隣接頂点関数Tと初期頂点v0」で与えられている ⇒ 頂点ごとに、それにTという関数によって隣接する頂点の集まりが得られる、と考える

4 ひとつの表現方法 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

5 集合と配列 たとえば T(1)={2, 3} を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)

6 別な方法 今までの講義では、木をClassを用いて表してきた 今示した配列を使う方法とは相容れない…
class GraphNode def initialize(x="") @label=x @edges=Array.new end # def 一つ一つの頂点を表現 頂点のラベル 隣接頂点を要素とする配列

7 Classによるグラフの表現 Classを用いてグラフの頂点を表すとすれば、 頂点v1に対する隣接頂点関数の値 T(v1)は、
v1.edges で与えられる。つまり、 v1.edges ⇒ [v2, v3] v2 v4 v1 注意： edgeとは「辺」のこと。でも上では 隣接頂点を要素とする配列が得られる。 このままだと名前が誤解を与えかねないので、 adjacentNodes (実質はedgesと同じ） によって隣接頂点関数(T)の代わりをさせることとする つまり、上の例では v1.adjacentNodes によってv1の隣接頂点が得られる v3

8 GRAPH-SEARCH (教科書、p.62) 入力： グラフGを表す隣接頂点関数Tと初期頂点v0 出力： Gのすべての頂点のリスト
手続き： 頂点を入れるための入れ物A,B（初期値は空） v0をAとBに入れる Aから一つの頂点vを取り出し「T(v)に属す頂点でBに入っていないものがあれば、AとBに入れる」 Aが空ならBを出力して終了。そうでなければ３へ。 ３の実現方法はいろいろ---p.62の方式を次に示す 8

9 関数graphSearch アルゴリズムの記述から def graphSearch(v0) end という大まかな構造が見える
(1) 入れ物A, Bを用意する (2) 入れ物A, Bにv0を入れる (3) Aから一つの頂点vを取り出し「T(v)に属す頂点 でBに入っていないものがあれば、AとBに入れる」 (4) Aが空ならBを出力して終了。そうでなければ(3)へ

10 (1)入れ物A, Bを用意する プログラムにおいて「入れ物」とは何か？ 答え：データを記憶するための変数、配列、などのこと
ただし、変数で記憶できるのは高々１つ 配列やハッシュ、スタック、キューなど、いろいろな要素を記憶できるものが「入れ物」と呼ぶのにふさわしい

11 (1)入れ物A, Bを用意する（続き) どういう用途の「入れ物」かが選択の鍵 (3)で「Bに入っているかどうか」が重要
なぜ重要かは（３）で説明 どういう用途の「入れ物」かが選択の鍵 (3)で「Bに入っているかどうか」が重要 ⇒Bの中の要素を「すばやく」検索できるデータ構造が向いている⇒それならハッシュ！ でも、どうやって「用意する」？

12 (1)入れ物A, Bを用意する（続き) 配列、ハッシュ、キュー、スタックなどの「データ構造」は、newメソッドでインスタンスを作る 例
配列：　Array.new ハッシュ：　　Hash.new これらはRubyの組み込み （最初からある）のデータ構造 スタック： Stack.new キュー：　Queue.new 木： … これらはRubyの組み込みではない 別途Classの宣言が必要 しかし、newによってインスタンスを 作ることは同じ

13 キューとスタックの準備 キューのクラス queueX.rb スタックのクラス stackX.rb class Queue
attr_accessor :head, :tail def enqueue(item) … end def dequeue … end def empty … end def find(item) … end end class Stack 　　　　　　　　　　 attr_accessor :data, :top def push(item) … end def popup … end def empty … end end

14 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 14

15 関数graphSearch アルゴリズムの記述から def graphSearch(v0) end という大まかな構造が見える
(1) 入れ物A, Bを用意する (2) 入れ物A, Bにv0を入れる (3) Aから一つの頂点vを取り出し「T(v)に属す頂点 でBに入っていないものがあれば、AとBに入れる」 (4) Aが空ならBを出力して終了。そうでなければ(3)へ

16 (2) 入れ物A, Bにvを入れる では、スタックやキューに入れるには？
入れ物とは、配列、ハッシュ、スタック、キュー等のこと これにvを入れるとは？ 配列の場合：インデックスを指定するか、後に付加えるのが普通。 例：arrを配列、iをインデックス用の変数とすれば、 arr[i]=v や arr << v など。 ハッシュの場合：vそのものをインデックスとして、値にnil以外を与える. 例： h をハッシュとすれば、 h[v] = true 参考： ハッシュの場合、「入っていないもの（たとえばw)を参照しようとするとnilが値となる. h[w] -> nil では、スタックやキューに入れるには？

17 (2) 入れ物A, Bにvを入れる（続) スタックやキューに入れるには? そう、もう学んだこと… スタック： stをスタックとすれば、st.push(v) キュー： qをキューとすれば、 q.enqueue(v) 質問：　スタックやキューの中のものを取り出すには？ 答：　スタック： stをスタックとすれば、st.popup キュー: qをキューとすれば、 q.dequeue

18 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 18

19 関数graphSearch アルゴリズムの記述から def graphSearch(v0) end という大まかな構造が見える
(1) 入れ物A, Bを用意する (2) 入れ物A, Bにv0を入れる (3) Aから一つの頂点vを取り出し「T(v)に属す頂点 でBに入っていないものがあれば、AとBに入れる」 (4) Aが空ならBを出力して終了。そうでなければ(3)へ

20 (3) Aから一つの頂点vを取り出し... Aにはスタックかキューを使う（指定済み） Aから要素を取り出してそれをvとする、ということ Aがスタックの場合（もうわかっていますね？） スタックから要素を取り出すには… だからstをスタックとすれば ｖ= Aがキューの場合 キューから要素を取り出すには… だからqをキューとすれば ｖ= 穴埋め！

21 …「T(v)に属す頂点でBに入っていないものがあれば、AとBに入れる」
(3)の前半でAから取り出された頂点をv‘とし、T(v’)の一つの要素をvとしておく vがBに入っているかいないかは、どうやってわかる？ Bはハッシュを使うことにした(スライド11枚目） 　…それは、検索が速いから。でもどうやって？ 答え：hをハッシュとすれば h[v]の値でわかる 説明：　hに要素(例えばw)を入れる時に、h[w]=true として値を設定。だから「true以外」の値が返されれば、「入っていない」ことがわかる

22 ここで、条件式について一言 条件式は、 if 条件式 … elsif 条件式 … end や、 while 条件式… end などで用いられる Rubyの場合、条件式がtrueを返すと、その条件式が「成り立った」ことになり、たとえばifではその次のプログラムが、whileではendまでのプログラムが実行される たとえば、 x==3はxが3ならtrue、そうでなければfalseを返す 条件式の値がfalse(やnil)の場合、その条件式は「成り立たなかった」ということになる

23 vがBに入っているかいないか なぜこれが重要なのだろうか？ このチェックをしないプログラムを書いた人からのコメント：「キューにものが入りすぎてQueue overflowが表示されてしまう」 グラフは(木と異なり)頂点から枝をたどっていくと、その頂点に戻る可能性がある。つまり迷路でいえば同じところをぐるぐる回ってしまう可能性がある。これを何とかしたい！ →　頂点をAにいれるための条件として「すでに訪れたことがない」 （Bに入っていない）とすればよい

24 (3)をまとめて書くと。。。 おっと！v.adjacentNodesは配列だ！ A(キューqとする）から一つの頂点v1を取り出し
確認： 「T(v)に属す頂点でBに入っていないものがあれば、AとBに入れる」は大丈夫ですね？（「AとBに入れる」方法はもうわかっている？） 以下ではAをキューとします（スタックの場合は自分で書いてみてください） v.adjacentNodesでT(v)の代わりをする A(キューqとする）から一つの頂点v1を取り出し v1 = q.dequeue 「T(v1)に属す頂点vでB(hとする)に入っていないものがあれば、AとBに入れる if (h[v1.adjacentNodes] != true) q.enqueue(v.adjacentNodes); h[v.adjacentNodes]=true end おっと！v.adjacentNodesは配列だ！

25 (3)をまとめて書くと。。。 ちょっと焦りすぎました 頂点vに隣接する頂点集合が v.adjcentNodes (T(v)と同じ）で得られるのですが、これは頂点を要素とする配列を返す これをそのままAやBに入れてはいけません（AやBに入れるのは「頂点」と決めているので） ここは「繰り返し」(forやwhile)を使って、 v.adjcentNodesの要素を一つ一つBにないことを確認して次々AやBに入れる必要があります

26 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 26

27 関数graphSearch まだ完成ではありません。(4)を忘れています。 def graphSearch(v0) end
という大まかな構造が見える (1) 入れ物A, Bを用意する (2) 入れ物A, Bにv0を入れる (3) Aから一つの頂点vを取り出し「T(v)に属す頂点 でBに入っていないものがあれば、AとBに入れる」 (4) Aが空ならBを出力して終了。そうでなければ(3)へ

28 (4) Aが空ならBを出力して終了。そうでなければ(3)へ
1に対しては、hをハッシュとすれば、h.keysによって、記憶された頂点を配列にして返してくれます（？！） 2に対しては、A(スタックかキュー)が空かどうかを判定するメソッドを使います（そのためにemptyというメソッドをあらかじめ定義しておいた）

29 (4) Aが空ならBを出力して終了 「何を返すか」は本当は大事な問題 B（ハッシュhとする）に入っている頂点の集合を返すだけなら、h.keys でよいが。。。 ここでは、どの頂点がどういう順番で入ってきたかも示したい（と思いません？） だから、resultという配列を別に用意して、それを返すようにした 最終形は次のスライド…

30 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 30

31 出欠課題（その２） 本日のウェブページから、graphSearch.rb をダウンロードする そこには queue版のGraph-Searchプログラムが載っている (1) それを動かしてみる。ｖ6を出発点とした時の頂点のリストが表示されるので、自分の解答と比較する(最後にエラー表示されるが無視すること） (2) queue版にならってstack版を作る（graphSearch.rbのgraphSearchS関数を完成させる） (3) 完成したら、v6を出発点とした時の頂点のリストが表示されるので自分の解答と比較する