Download presentation
Presentation is loading. Please wait.
1
アルゴリズムとデータ構造 2011年7月8日課題の復習
情報知能学科 白井英俊
2
グラフ探索の演習 図6.8(下図）に示すグラフに対するGraph-Searchの振る舞いをv6を始点として、(1)Aとしてキューを使った場合と、(2)スタックを使った場合のそれぞれに対して示せ。（複数の頂点をいれる場合は、番号の若い方を先にいれるものとする） v3 v0 v1 v2 v10 v11 v12 v5 v6 v4 v9 v8 v13 v7
3
グラフ探索（キューによるもの） Graph Search with QUEUE: v6 v5 v7 v4 v8 v12 v3 v9 v13 v2 v11 v10 v1 v0 v3 v0 v1 v2 v10 v11 v12 v5 v6 v4 v9 v8 v13 v7
4
グラフ探索（スタックによるもの） Graph Search with STACK: v6 v5 v7 v8 v9 v13 v3 v12 v2 v11 v1 v10 v0 v4 v3 v0 v1 v2 v10 v11 v12 v5 v6 v4 v9 v8 v13 v7
5
GRAPH-SEARCH (教科書、p.62) 入力： グラフGを表す隣接頂点関数Tと初期頂点v0 出力： Gのすべての頂点のリスト
手続き： 頂点を入れるための入れ物A,B（初期値は空） v0をAとBに入れる Aから一つの頂点vを取り出し「T(v)に属す頂点でBに入っていないものがあれば、AとBに入れる」 Aが空ならBを出力して終了。そうでなければ３へ。 ３の実現方法はいろいろ---p.62の方式を次に示す 5
6
(1)入れ物A, Bを用意する（続き) 配列、ハッシュ、キュー、スタックなどの「データ構造」は、newメソッドでインスタンスを作る 例
配列： Array.new ハッシュ： Hash.new これらはRubyの組み込み （最初からある）のデータ構造 スタック： Stack.new キュー： Queue.new 木： … これらはRubyの組み込みではない 別途Classの宣言が必要 しかし、newによってインスタンスを 作ることは同じ
7
キューとスタックの準備 キューのクラス 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
8
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 8
9
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 9
10
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 10
11
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 11
12
課題 queue版にならってstack版を作る（graphSearch.rbのgraphSearchS関数を完成させる） Stack.new
インスタンスを作る Queue.new データを追加（記憶） enqueue 記憶したデータの取り出し dequeue 空っぽかどうかの判定 empty Stack.new push popup empty
13
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 13
Similar presentations
