アルゴリズムとデータ構造 2011年7月8日課題の復習 情報知能学科 白井英俊 グラフ探索の演習 • 図6.8(下図）に示すグラフに対するGraph-Searchの 振る舞いをv6を始点として、(1)Aとしてキューを使っ た場合と、(2)スタックを使った場合のそれぞれに対 して示せ。（複数の頂点をいれる場合は、番号の若 い方を先にいれるものとする） v3 v2 v12 v1 v5 v11 v0 v10 v4 v13 v9 v8 v7 v6 グラフ探索（キューによるもの） Graph Search with QUEUE: v6 v5 v7 v4 v8 v12 v3 v9 v13 v2 v11 v10 v1 v0 v3 v2 v12 v1 v5 v11 v0 v10 v4 v13 v9 v8 v7 v6 グラフ探索（スタックによるもの） Graph Search with STACK: v6 v5 v7 v8 v9 v13 v3 v12 v2 v11 v1 v10 v0 v4 v3 v2 v12 v1 v5 v11 v0 v10 v4 v13 v9 v8 v7 v6 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の方式を次に示す (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 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 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 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 課題 queue版にならってstack版を作る（graphSearch.rbの graphSearchS関数を完成させる） 考え方： Queueが関係する操作を、対応するStackの操作で置き 換える インスタンスを作る Queue.new Stack.new データを追加（記憶） enqueue push 記憶したデータの取り出し dequeue popup empty 空っぽかどうかの判定 empty GRAPH-SEARCHプログラム(stack版) def graphSearchQ(v) # キューを用いたグラフ探索 check = Hash.new(false) # 頂点が記録済みかどうかのチェック用(B) agenda = Stack.new # 調査すべき頂点の記憶用(A) agenda.push(v) # 始点vをAに入れる(enqueue) result = [v] # 始点vを訪問リストに入れる check[v] = true #始点vを記録済みとしてチェック while (! agenda.empty) # 調査すべき頂点がある限り繰り返し v = agenda.popup # 次に調査すべき頂点(v)を取出す for w in v.adjacentNodes # vに隣接する頂点それぞれ(w)に対し if (! check[w]) # wが記録済みでなければ agenda.push(w) # wを調査すべき頂点に登録(A) check[w]=true # wを記録済みとして登録(B) result << w # wを訪問リストの末尾に入れる end # if end # for end # while return result # (すべての頂点を調査したので) 訪問リストを返す end # def
© Copyright 2024 ExpyDoc
