ohp10.dvi

情報科学 2015 久野クラス ＃10 久野 靖∗

はじめに

今回でラス前(次回は出席をとる最終回)ですが、今回は代表的な抽 象データ型の話題を、動的データ構造も交えて取り上げた後、パズル やゲームに関係の深い話題として「探索」について取り上げます。 • スタックとキュー • 表と探索 • 状態空間の探索

演習問題解説

演習

2 —

エディタバッファのメソッド追加

この演習については、メソッドのみだけ掲載します。まず削除:

def delete

if atend then return end

@cur = @prev.next = @cur.next end これは前回授業でもかなり説明しましたが、要は(1)最後のEOFは 消さないようにする、(2)@curは現在行の1つ先にする、(3)@prev の 「次」も同じく現在行の1つ先にする、ということですね。どれかが足 りないとおかしくなるので注意。次に交換です: def exch

if atend || @cur.next == @tail then return end

a = @prev; b = @cur.next; c = @cur; d = @cur.next.next a.next = b; b.next = c; c.next = d; @cur = b

end このように込み入ったつなぎ換えは、作業変数を使った方が間違え ないで済みます。まず現在行か次の行が「おしまい」だったら交換で きないのでそれを除外し、あとは最終的に並ぶ4つのセル(中央の2つ が交換)を変数a、b、c、dに入れて、つなぎ直し、@curを変更します。 次は1つ戻るですが、せっかくある程度メソッドが作ってあるわけで すから、「@prevを覚えておき、先頭に行ってから現在行が覚えておい た行になるまで1行ずつ進む」方法で作ってみました: def backward

if @prev == @head then return end

a = @prev; top; while @cur != a do forward end end

演習

2 —

エディタバッファのメソッド追加

全部反転はちょっと大変そうですね。要は、先頭から順にたどりなが ら、今まで「前→後」の対だったものを「後←前」の順になるように 参照をつなぎ換える(ただし先頭と末尾はそれなりに対処)、という方 針です: def invert

top; if atend then return end

a = @cur; b = @cur.next; a.next = @tail

while b != @tail do c = b.next; b.next = a; a = b; b = c end @head.next = a; top end 先頭と末尾の対処はまず最初に先頭の次を@tailにし、最後にルー プを抜けてきた時のセルを先頭(@headの次)にする、ということです。 なお、バッファ内に1行しかない時はループ周回数が0で、その時も ちゃんと動作することに注意。双方向リストの実現例は長くなります し、やってみたい人のお楽しみなので省略させてください。

演習

4 —

エディタの機能強化

まず、「指定した行へ行く」機能はバッファ側で「何行目」を管理す るのがよいので、エディタバッファ全体を示します。基本的に、イン スタンス変数@linenoを追加して、現在行が変化するメソッドではこ れを更新します。invertみたいにぐちゃぐちゃにいじる場合は最後に topを呼ぶので、ここで1にリセットされるから考える必要はありま せん。そしてこれがあればbackwardはもっと簡単になるので、これも 直しました。行番号を間違いなく維持するのはきわどそうに見えます が、@linenoをアクセスするのもバッファ内容や現在位置を変更する のもBufferの中だけなので、この中できちんと処理すれば大丈夫で す。つまり、オブジェクト指向の持つカプセル化の機能によって、プ ログラムが正しく構成し易くなっているわけです。 class Buffer

Cell = Struct.new(:data, :next) def initialize

@tail = @cur = Cell.new("EOF", nil) @head = @prev = Cell.new("", @cur) @lineno = 1 end def getlineno return @lineno end def goto(n)

top; (n-1).times do forward end end

def atend

return @cur == @tail end

演習

4 —

エディタの機能強化

def top

@prev = @head; @cur = @head.next; @lineno = 1 end

def forward

if atend then return end

@prev = @cur; @cur = @cur.next; @lineno = @lineno + 1 end

def insert(s)

@prev.next = Cell.new(s, @cur)

@prev = @prev.next; @lineno = @lineno + 1 end

def print

puts(" " + @cur.data) end

# delete、exchは上掲のとおり。backwardは以下のように変更

def backward

goto(@lineno - 1) end

def invert

top; if atend then return end

a = @cur; b = @cur.next; a.next = @tail while b != @tail do

c = b.next; b.next = a; a = b; b = c end

@head.next = a; top end

演習

4 —

エディタの機能強化

def subst(str)

if atend then return end a = str.split(’/’)

@cur.data[Regexp.new(a[1])] = a[2] end

def read(file)

open(file, "r") do |f|

f.each do |s| insert(s) end end

end

def save(file) top

open(file, "w") do |f|

while not atend do f.puts(@cur.data); forward end end

end end

演習

4 —

エディタの機能強化

エディタドライバ側も一応示します(「位置変更しない指定行数プリ ント」も、最初に行番号を覚えて、印刷し終わったらそこに戻ればよ いので簡単です): def edit e = Buffer.new while true do printf(">")

line = gets; c = line[0..0]; s = line[1..-2] if c == "q" then return

elsif c == "t" then e.top; e.print elsif c == "p" then

e.print; l = e.getlineno;

s.to_i.times do e.forward; e.print end; e.goto(l) elsif c == "i" then e.insert(s)

elsif c == "r" then e.read(s) elsif c == "w" then e.save(s)

elsif c == "s" then e.subst(s); e.print elsif c == "d" then e.delete

elsif c == "x" then e.exch

elsif c == "b" then e.backward elsif c == "v" then e.invert

elsif c == "a" then e.forward; e.insert(s); e.backward elsif c == "c" then e.delete; e.insert(s); e.backward elsif c == "g" then e.goto(s.to_i)

else e.forward; e.print

end end end

演習

8 —

抽象構文木の機能追加

代入などの基本的な拡張は前回既に説明してありますので、そこに無 かったぶんだけ説明します。動作の種別を増やすのはNodeのサブクラ スを増やすだけなので難しくありません。比較演算の例としてLe(<=) と、あと目新しいものとしてif、while、read、printのみ示します。

readやprintは数値を読み込んだり画面に出力したりします。

class Le < Node

def initialize(l, r) super; @op = ’<=’ end

def exec() return (if @left.exec<=@right.exec then 1 else 0 end) end

# Lt(<), Gt(>), Ge(>=), Eq(==), Ne(!=)も同様 class If < Node

def initialize(l, r) super; @op = ’I’ end

def exec() if @left.exec != 0 then @right.exec end end end

class While < Node

def initialize(l, r) super; @op = ’W’ end

def exec() while @left.exec != 0 do @right.exec end end end

class Read < Node

def initialize() super; @op = ’R’ end

def exec() print ’> ’; return gets.to_i end end

class Print < Node

def initialize(l) super; @op = ’P’ end def exec() puts(@left.exec) end

演習

8 —

抽象構文木の機能追加

これらが動作する例として、「素数列挙」のプログラムを組み立てて 実行してみましょう。 def test2 e = Seq.new( Assign.new(Var.new(’n’), Read.new), Seq.new( Assign.new(Var.new(’i’), Lit.new(2)), While.new( Le.new(Var.new(’i’), Var.new(’n’)), Seq.new( Assign.new(Var.new(’k’), Lit.new(2)), Seq.new( Assign.new(Var.new(’sosu’), Lit.new(1)), Seq.new( While.new( Lt.new(Var.new(’k’), Var.new(’i’)), Seq.new(

If.new(Eq.new(Mod.new(Var.new(’i’), Var.new(’k’)), Lit.new(0)), Assign.new(’sosu’, Lit.new(0))),

Assign.new(Var.new(’k’), Add.new(Var.new(’k’), Lit.new(1))))), Seq.new(

If.new(Ne.new(Var.new(’sosu’), Lit.new(0)), Print.new(Var.new(’i’))), Assign.new(Var.new(’i’), Add.new(Var.new(’i’), Lit.new(1)))))))))) puts(e)

return e.exec end

演習

8 —

抽象構文木の機能追加

実行のようすは次のようになります。 irb> test2 ((n=(R));((i=2);((i<=n)W((k=2);((sosu=1);(((k<i)W((((i%k)==0)I(s (k=(k+1))));(((sosu!=0)I(iP));(i=(i+1))))))))) > 20 2 3 5 7 11 13 17 19 => nil irb> 確かに素数列挙ができています。

演習

8 —

抽象構文木の機能追加

しかし、この方法でプログラムを組み立てるのは大変すぎますね? 実 際にはRubyインタプリタ等の言語処理系は、普段私たちが書いてい るような「普通の」ソースコードを読み込み、字句解析(名前や演算 子などのかたまりに分ける)、構文解析(木構造を組み立てる)、意味解 析(意味的におかしくないか検査)などを経て、上のような抽象構文木 を組み立てます(図1)。そしてそれを実行する部分は、たとえばここ に示したような形でできるわけです。1 字句 解析 構文解析 意味解析 ＋ ＊ ｘ ３ １ 実行 def p(x) x*3+1 ... ソースコード 抽象構文木 図 1: インタプリタの構成の例 1 実際には抽象構文木を作らない方式や構文木からさらに実行形式に変換して高速に実行するなど、処理系の作り方も色々あります。

スタックとキュー

スタック

今回は、複数の抽象データ型について、その内部の実現がさまざま であり得ることも含めて扱って行きます。抽象データ型(abstract data type — ADT)というのは内部構造は隠したまま汎用的な機能を提供す るような単位(Rubyの場合はクラス)のことでした。これだけではよ く分からないでしょうけれど、今回の題材を見ていくと納得して頂け るかと思います。 スタック(stack)とはコンピュータのアルゴリズムで多く使われる汎 用の抽象データ型であり、「LIFO(last-in, first-out)の記憶領域」とも 呼ばれます。つまり、スタックには多数のデータが入れられますが、 取り出す時には(残っているものの中で)一番最近に入れたものが取り 出されてくるのです。これはちょうど、ものを上に積んでいって取り 降ろす時の動作を同じなので、スタック(積む) と呼ばれるわけです。 スタックの入れる/取る動作は伝統的にpush/popと呼ばれます(図2 左)。 A B C push pop array top top: A B C A B C 図 2: スタック スタックの実現方法の1つは、配列を用意して、そこに順番にpushさ れた要素を詰めていくことです(図2右上)。先頭の位置は変数topに 覚えておき、pushしたらtop を進め、popしたら1つ戻します。

スタック

この方法は簡潔ですが、多くのプログラミング言語では配列のサイズ が作成時に指定した値から変えられないため、最大いくつの要素を格 納するか予め決める必要があります。Rubyでは…実は配列にpush/pop というメソッドが用意されていてスタックの機能が実現済みです。し かし練習なので、ここでは固定サイズの配列でスタックを実現してみ ます。 スタックのもう1つの実現方法は、連結リストを用いて要素を覚えて おく方法です(図2右下)。この場合、最大要素数を指定する必要はあ りません。 配列を使ったスタックの実現を示します: class Stack1

def initialize() @arr = Array.new(100); @ptr = -1 end def isempty() return @ptr < 0 end

def push(x) @ptr += 1; @arr[@ptr] = x end

def pop() x = @arr[@ptr]; @ptr -= 1; return x end end

スタック

動かす様子を見てみましょう: irb> s = Stack1.new ... irb> s.push(1) => 1 irb> s.push(2) => 2 irb> s.push(3) => 3 irb> s.isempty => false irb> s.pop => 3 irb> s.pop => 2 irb> s.push(4) => 4 irb> s.push(5) => 5 irb> s.pop => 5 irb> s.pop => 4 irb> s.pop => 1 irb> s.isempty => true

キュー

キュー(queue)もスタックと類似した機能を提供しますが、(残ってい

るものの中で)一番先に入ったものが取り出される点が違います。この ためキューのことを「FIFO(fist-in, first-out)のデータ構造」とも呼び ます。そもそもキューとはおなじみ「行列」を意味する英語です(もち ろん最初に並んだ人が最初にサービスしてもらえなかったら怒ります よね…)。 キューの入れる/取り出す操作は伝統的にenq/deqと呼ばれます(3 左)。実はフルスペルはenqueueとdequeueですが、長いし発音が同じ なので短く書くのが普通なわけです。 C D E enq deq array optr top: D E C E D C iptr J I H iptr optr K last top: D E F last 図 3: キュー キューの実現も配列版と連結リスト版が考えられます。配列版では、 iptrとoptrという2つの変数で「入れる場所」と「取り出す場所」を 覚えておきます(図3右上)。出し入れを繰り返すと、入っている場所が 配列の端まで来るので、ぐるっと回って先頭に戻るようにします。最 初と最後がくっついて輪になっているため、このようなデータ構造を 環状バッファ(circular buffer)、リングバッファ(ring buffer)と呼ぶこと もあります。

キュー

満杯になった/空っぽになったことを知るために、現在いくつ入って いるかを別の変数で覚えておきます。別の方法として、iptがoptに 追い付きそうになったら満杯だと判断する方法もありますが、その場 合は常に1箇所は空けておかないと空っぽと満杯の区別がつかなくな ります。2 連結リスト版は、リストの先端をlastで指しておいて、そこに新しい 要素を追加するようにします(図3右下)。リストが空っぽ(topがnull の場合はlastは意味を持たない(セルが1個もないのだから)ので、入 れる時に特別扱いになります。 以下には配列版のキューのプログラムを示します: class Queue1

def initialize() @arr = Array.new(100); @iptr = @optr = @cnt def isempty() return @cnt <= 0 end

def enq(x) @arr[@iptr] = x; @iptr = (@iptr+1)%100; @cnt += 1 def deq() x = @arr[@optr]; @optr = (@optr+1)%100; @cnt -= 1; end

キュー

動かす様子を見てみましょう: irb> q = Queue1.new ... irb> q.enq(1) => 1 irb> q.enq(2) => 2 irb> q.isempty => false irb> q.deq => 1 irb> q.enq(3) => 2 irb> q.enq(4) => 3 irb> q.deq => 2 irb> q.deq => 3 irb> q.deq => 4 irb> q.isempty => true 演習1 スタックとキューのうち好きな方を打ち込んで動かせ。動いた ら、連結リストを使ったスタックないしキューの実現を作り、上の 例で同じに動作することを確認せよ。

表と探索

表

表(table)とは、鍵(key)となる値を指定してデータを格納でき、後で 同じ鍵を指定して登録したデータを取り出せるような抽象データ型で す。実は配列も、「鍵として0∼Nの範囲の整数を許す」ような表だと 言えます。 a[99] = ’abc’ # 鍵99でデータを格納 ... ... a[99] ... # 鍵99でデータを取り出し 「鍵が0∼Nの整数」というのはかなり強い制約であり、現実のコー ドでは「氏名を指定して年齢を登録する」のように、より柔軟な表が 作りたい場合が多くあります。ここではそのような表について考えま しょう。 ’kuno’ ’saito’ ... 20 30 鍵を指定して 値を格納 key val 鍵を指定して 格納してあった 値を取り出し 図 4: 抽象データ型としての「表」 上に述べたように、表は「格納」「取り出し」という2つのメソッド を持つ抽象データ型です。普通はこれらにはput、getのようなメソッ ド名をつけるのですが、ここでは使っている言語がRubyなので、そ れぞれ次のようなメソッドとして定義します(そうすることで、配列 と同じ形で読み書きできるので)。 def []=(k,v) ...鍵kで値vを登録... end def [](k) ...鍵kに対応する値を返す... end

線形探索

最も簡単な方法として、表の各項目(entry)を鍵と値を保持するレコー ドで表し、その配列が表、という方法を使ってみます(図5)。登録時 も取り出し時も、指定された鍵をループで探し、見つかったらそこを アクセスします(登録時に見つからなかったら末尾に新項目を追加)。 コードを見てみましょう。 ’kuno’ ’saito’ ’hata’ ’okano’ 20 30 28 44 図 5: 素直な表のデータ構造

TableEntry1 = Struct.new(:key, :val) class Table1

def initialize() @tbl = [] end def [](k)

@tbl.each do |e|

if e.key == k then return e.val end end

return nil end

def []= (k,v)

@tbl.each do |e|

if e.key == k then e.val = v; return end end

@tbl.push(TableEntry1.new(k, v)) end

線形探索

動かしてみましょう。 irb> t1 = Table1.new => #<Table1:0x81e668c @tbl=[]> irb> t1[’kuno’] = 20 => 20 irb> t1[’okano’] = 44 => 44 irb> t1[’kuno’] => 20 irb> require ’pp’ # ppを使えるようにする => true irb> pp t1 #<Table1:0x81e668c @tbl=

[#<struct TableEntry1 key="kuno", val=20>, #<struct TableEntry1 key="okano", val=44>]> => nil 確かに、指定した鍵で格納した値が、同じ鍵を指定することで取り 出せます。 表の中でどの位置に求める(指定した鍵を持つ)項目があるかを探す ことを探索(search)と呼びます。上のコードではごく素直に表を「順 番に調べていく」わけですが、この方法を線形探索(linear search) と呼 びます。整列の時の単純選択法などと同様、線形探索はあまり速い方 法ではありません。具体的には、登録されている鍵を探す場合、平均 して登録されているデータ数nの半分くらい探す必要があるので、探 索の時間計算量がO(n)となるからです。

2

分探索木

別の方法として、動的データ構造、具体的には前回の抽象構文木な どで使った木構造を利用した表について説明します。この方法は線形 探索の表よりも高速ですが、ただし鍵となる値には「大小関係」がな ければいけません。3 整数や実数にはもちろん大小がありますが、文 字列も「辞書順」で大小が定められているので、鍵に使うことができ ます。ここでは見やすさのため、整数の鍵を例に説明します。 木を用いて大小関係のある鍵を前提とした表の代表例は、2分探索木 (binary search tree)です。この手法では、各ノード鍵・値に加えて2つ 以下の子を持ち(2分木)、あるノードの左側の子には「そのノードの 鍵よりも小さい鍵だけが格納されており」右側の子には「そのノード の鍵よりも大きい鍵だけが格納されている」という条件が常に成り立 つようになっています(図6)。 38 16 50 44 68 99 60 41 12 30 13 図 6: 2 分探索木の例 この方法では、鍵を指定されたとき、根から始めて各ノードの値が その鍵よりも大きければ左、小さければ右の子へだとっていくことを 繰り返すことで、その鍵のノードが見つけられる(か、またはその鍵 はまだ格納されていないと分かる)ことになります。そのたどっていく 回数は木の高さ(段数)ぶんなので、「木がだいたいバランスした形で あれば」探索の計算量はO(logn)となります。ではコードを見てみま しょう。 3 正確に数学の言葉で言えば全順序 total order が必要です。

2

分探索木

TableEntry2 = Struct.new(:key, :val, :left, :right) class Table2

def initialize() @tree = nil end def [](k)

if @tree == nil then return nil

elsif @tree.key == k then return @tree.val

elsif @tree.key > k then return @tree.left[k]

else return @tree.right[k]

end end def []=(k,v) if @tree == nil @tree = TableEntry2.new(k,v) elsif @tree.key == k @tree.val = v elsif @tree.key > k

if @tree.left == nil then @tree.left = Table2.new end @tree.left[k] = v

else

if @tree.right == nil then @tree.right = Table2.new end @tree.right[k] = v end end end 説明ですが、取り出しの場合はまず木が空っぽだったら「無い」ので nilを返します。次に、鍵が現在のノードの鍵と同じなら、対応する値 を返します。それ以外は鍵とノードの鍵の大小に応じて、左または右

2

分探索木

格納の場合は木が空っぽならレコードを割り当てて鍵と値を格納し ます。鍵が現在のノードの鍵と同じなら、対応する値を書き換えます。 それ以外は左または右の子に行くわけですが、その前にまだその枝が nilであれば、空っぽの表を作って格納し、いずれにせよそこに対して 再帰的に格納を行えばよいわけです。 演習2 線形探索または2分探索木の表のプログラムを打ち込んで動か せ。動いたら、「0∼N − 1の範囲の乱数をN 回格納する」ときの 計算量を見積もり、さまざまなN に対してbenchで次のように計測 してチェックしてみよ。また、添字0∼N − 1の範囲の配列の場合 と時間を比べてみよ。

t = Table1.new #ないしTable2.new、Array.new(10000)等

bench(10000) do x = rand(10000); t[x] = x end #1万の場合

演習3 2分探索木は鍵を格納する順番がきっちり鍵の大小順通りだと

遅くなるという(クイックソートの場合と似た)弱点がある。この

ことを計測等により確認しなさい。またできれば、この弱点を改 善する方法を検討してみなさい。

ハッシュ表

ここまで引っ張って今更ですが、実はRubyには言語組み込みの表機 能のクラスHashが備わっています。そしてそれは、配列と似たような 見た目を持っていることから、連想配列(associative array)とも呼ばれ ます。

Perl、JavaScript、Pythonなど多くの言語に連想配列の機能が備わっ ています。ハッシュというのはRubyやPerlでの呼び名ですが、それは この機能の実現にハッシュ表(hash table)のアルゴリズムが使われてい ることによります。Rubyの場合については、ハッシュの作り方は次の とおりです(使い方はここまでにやってきた表と同じです)。 • Hash.new(値)で作る。「値」は表を検索して見つからない場合に 返される値(省略した場合はnil)。 • いくつかの値を予め登録した形で「{ 鍵=>値, 鍵=>値, ... }」 という形で作る(たとえば次のように)。

h = {1 => "abc", 8 => "xyz", 3 => "a"} h = {"abc" => 3, "def" => "u"}

h = { } # Hash.new(nil)と同じこと

さて、このハッシュ表とはどのようなアルゴリズムなのでしょうか。 先の演習で配列の時間も計った方は、配列が極めて高速であることが お分かりと思います。配列はコンピュータのメモリ領域の特定位置を 読み書きするだけなので、時間計算量O(1)なのです。

ハッシュ表

ただし、配列では鍵が「整数であり」かつ「0∼N − 1の範囲で連続」 という制約があります。非常に大きな数とか、実数とか、文字列など を鍵にすることはできないわけです。そこで、これらの鍵の値を次の ような形で整数に変換します。 i = hash(鍵の値) 関数hashは「同じ鍵を渡したら同じ整数が得られること」(関数だっ たらそれは当然ですね)、および「0∼N − 1の範囲にできるだけばら ばらに散らばった整数を返す」ことが求められます。4 これを使って、 たとえば0∼9999の範囲の整数が得られたら、そこにこれまで通り鍵 と値を格納すればよいのです(図7)。検索のときも、同じhashを使え ば同じ番号が得られますから、その場所を見ればそこにその鍵が格納 されているはずです。この方法は、hashの計算に一定時間掛かるとす れば(大抵そうです)、配列アクセスはO(1)ですから、全体としてO(1) で検索ができます。 ’saito’ ’kuno’ 20 30 ’kuno’ ’saito’ hash hash 図 7: ハッシュ表 4 たとえば整数なら「表のサイズで割った余り」などがあり得ます。文字列なら、その各文字の文字コード値を全部書けてから大きな整数として扱 うなどがあります。

ハッシュ表

ただし1つだけ問題があります。hashが十分散らばった値を計算して くれるようになっていれば、「だいたいは」バラバラの(互いに異なる) 場所に項目を入れられるからいいのですが、「運悪く」2つの別の鍵の hash値が同じになってしまうこともあります。これを衝突(collision) と言います。実は衝突が起きていないかチェックするために、各項目 には値だけでなく鍵も入れておくようにしているわけです。 衝突が起きた時の対応方法は次の2つがあります。 • 配列の各項目をさらに配列や単連結リストなどにして、複数の鍵 と値の組を保持させる。 • 衝突が起きたら、後から格納する値はその「次」の場所に入れる。 5 いずれにせよ、ハッシュ表は「ほとんどの場合衝突なしに済む」こ とが前提なので、表のサイズに比べて登録項目数が多くなってしまう と(たとえば50%)衝突だらけで性能が悪くなります。そのような場合 は、改めて大きな表を作ってそこに全部登録し直すなどの処理が必要 です。 演習4 上の説明に基づいて、ハッシュ表を作ってみよ(簡単のため、鍵 は整数でよいことにする)。性能も計測し、Rubyのハッシュと比較 してみなさい。

状態空間の探索

スタック・キュー・再帰による構造のたどり

スタックやキューはどういう役に立つのでしょうか? それは、何か を入れて(覚えて)おいて、後で取り出して使うためです。当り前だと 思うかもしれませんが、こういうことは結構あります。単独の変数に 覚えておくのだと、1つしか覚えておけません(2つ目を入れると前に 入っていたものは上書きされて失われます)。配列だと、「どこに」入 れてあるかを覚えておかないと役に立ちません。ところが、スタック やキューでは「とにかく入れて」「とにかく取り出す」ことができるの で使うのが楽であり、そして入れたものは必ずいつか出てくることが 保証されます。 東京 秋葉原 お茶の水 新宿 立川 八王子 品川 田端 池袋 赤羽 大崎 川崎 横浜 図 8: とある鉄道路線図 たとえば、グラフ(頂点と辺から成る構造)をたどる例として、図8の ような路線図を考えてみます。ここで問題は「横浜から池袋まで何ス テップで行けるか」調べることです。6 6 交差がある方が面白いので、横須賀線武蔵小杉はまだ開業していないものとしています。

スタック・キュー・再帰による構造のたどり

まず、このグラフをRubyで扱えるようなデータ構造にしてみます。 def prepare $graph = Hash.new() cn("赤羽", "池袋"); cn("赤羽", "田端"); cn("池袋", "田端") cn("八王子", "立川"); cn("立川", "新宿"); cn("池袋", "新宿") cn("新宿", "お茶の水"); cn("お茶の水", "秋葉原"); cn("田端", "秋葉原"); cn("お茶の水", "東京") cn("秋葉原", "東京"); cn("東京", "品川"); cn("新宿", "大崎"); cn("大崎", "品川"); cn("品川", "川崎"); cn("立川", "川崎"); cn("大崎", "横浜"); cn("川崎", "横浜"); cn("八王子", "横浜") end

Node1 = Struct.new(:name, :arr, :path) def cn(name1, name2)

if $graph[name1] == nil then $graph[name1] = Node1.new(name1, if $graph[name2] == nil then $graph[name2] = Node1.new(name2, $graph[name1].arr.push($graph[name2]) $graph[name2].arr.push($graph[name1]) end メソッドprepareを呼ぶと、グローバル変数$graphにハッシュが入 り、続いてcnを呼ぶことですべての配線を行います。cnの中では、ま だ駅のノードが生成されていなければ指定した名前を持つノードを生 成し、その後で両方の駅のarr(隣接する駅を保持する配列)に他方の 駅のノードを追加します。pathというフィールドは経路を見つけると きに経路を表すデータを入れるためのもので、最初は何も値を指定し ていないのでnilが入っています。

スタック・キュー・再帰による構造のたどり

では、この路線図の上でA駅からB駅まで行く経路の長さ(経由する 辺の数)をとりあえず1つ見つけるメソッドを見ていただきます。

def traverse1(start, goal)

s = Stack1.new; n = $graph[start]; n.path = [start]; s.push(n) puts("START: #{start}")

while !s.isempty do n = s.pop

n.arr.each do |m| if m.path == nil

m.path = n.path.dup; m.path.push(m.name) puts("#{m.name}: #{m.path.join(’,’)}")

if m.name == goal then return else s.push(m) end end end end end まず開始駅のノードを取り出し、経路長を0にし、スタックに積みま す。続いて、スタックが空でない間、スタックからノードを1つ取り 出し、そのノードに隣接する全ての駅について、始めて訪問した場合 は(pathがnilのときは)、経路を今処理している駅までのの経路長に新 たな駅を追加したものに設定し、名前と経路を表示し、ゴールなら終 わりですがそうでなければまだ先をチェックするためスタックに積み ます。7 7 dupというのは配列の複製を作るメソッド、join というのは配列の各要素の間に指定文字列をはさんで連結するメソッドです。

スタック・キュー・再帰による構造のたどり

実行例を見てみましょう。

def test1 prepare; traverse1(’横浜’, ’池袋’) end

irb> test1 START: 横浜 大崎: 横浜,大崎 川崎: 横浜,川崎 八王子: 横浜,八王子 立川: 横浜,八王子,立川 新宿: 横浜,八王子,立川,新宿 池袋: 横浜,八王子,立川,新宿,池袋 => nil ちょっと遠回りぽいですが、確かに池袋まで4ステップで行けます。 ところで、上の例はスタックを使っていましたが、代わりにキューを 使ったらどうなるでしょう(当然、push/popをenq/deqにします)。 irb> test2 START: 横浜 大崎: 横浜,大崎 川崎: 横浜,川崎 八王子: 横浜,八王子 新宿: 横浜,大崎,新宿 品川: 横浜,大崎,品川 立川: 横浜,川崎,立川 池袋: 横浜,大崎,新宿,池袋 => nil

スタック・キュー・再帰による構造のたどり

スタックとキューの順序の違いは何から来ているのでしょう? スタッ クはLIFOなので、一番最後に新たに見つかったノードから先にその 先をたどります。つまり図9で言うと「どんどん深い方へ行って、息詰 まったら戻って来て次の枝をまた深い方へ行く」ようになります。こ れを深さ優先探索(depth first search)と呼びます。これに対してキュー はFIFOなので、あるノードから出ている枝を全部処理し終わってか ら、まだ処理していない古いものから順に取り出して処理して行きま す。つまり図9で言うと「まずレベル1を全部調べ、それが尽きたらレ ベル2を全部調べ、…」となります。これを幅優先探索(と)言います。 幅優先探索 深さ優先探索 図 9: 深さ優先と幅優先 一般に深さ優先探索の方が早く(短い時間で)目的ノードを見つけま すが、幅優先探索は遅いかわりに「最もステップ数が短い」目的ノー ドを見つけることが保証される、という利点があります。 演習5 上の例題を打ち込んで動かしてみよ。動いたら、路線図を別の グラフに変えてみて、経路が探せることを確認せよ。幅優先と深 さ優先の両方についてやるとなおよい。 演習6 再帰手続きが「別の1人の自分を呼び出す」ことを利用して、ス タックやキューの代わりに再帰手続きで上の路線図の経路をたどっ てみよ。

スタック・キュー・再帰による構造のたどり

演習7 探索とは関係ないが、エディタバッファのデータ構造として、 次のようなものも考えられる。 • 2つのスタックA、Bに「現在位置より上の行」「現在位置以降 の行」を入れるものとする。 • スタックBの一番上が現在行と考える。 • 1つ下に行くには、スタック Bから1つpopしてスタック Aに push。 • 1つ上に行くには、スタック Aから1つpopしてスタックBに push。 • 現在行を消すには、スタックBから1つpop。 • 新しい行を挿入するには、スタックAに1つpush。 この方針によるエディタを作ってみよ。コマンドや機能の設計は各 自に任せます。

状態と状態遷移

我々の日常生活において、ある同じ行動をしても結果が異なること はよくあります。たとえば大学の食堂で友人と談笑するのは構いませ んが、授業中の講義室ではまずいですね。つまり談笑という同じ行動 を取っても、文脈(context)が違うと結果が違うわけです。ここで、同 等と見なせる文脈の集合を状態(state)と呼びます。つまり講義中とい う状態、映画館で映画を見ている状態、普段の状態、などの状態があ り、「どの状態である」かに応じて「行動の結果」が変化すると考える わけです。 コンピュータ上では日常生活よりもいっそう「状態」の違いを意識 する必要があります。同じコンピュータの前に座っていて同じように キーボードを打ち込んでも、動いているプログラムがワープロソフト なのかコマンドの窓なのかによって全く結果が違います。そして、プ ログラムの中もまた同様です。たとえばx + 1という式の値は、変数 xに入っている値が4であれば5 になるし、10であれば11 になります。 ですから、変数の値を書き換えつつ計算が進行していく手続き型計算 モデルの場合、状態とは「すべての変数の値の集合」ということにな るわけです。 状態について考える時は、ある状態から別の状態への移行、つまり 状態遷移(state transition)も一緒に考える必要があります。これは、ど のような場合にどの状態からどの状態へ移る、という定式化がなけれ ば、現在いる状態はどれなのかも分からないからです。たとえば、先 の路線図の問題の場合、「現在どの駅にいるか」が状態であり、「ある 駅から(電車に乗って)別の駅へ移動する」ことが状態遷移ということ になります。

ゲーム・パズルと状態空間

カードや駒などを使う多くのゲーム(game)やパズル(puzzle) は、個々 の場面を1つの状態と考え、プレーヤが選択する「手」を状態遷移と 考えることで定式化できます。たとえばソリティア(トランプの一人遊 び)では場のカードの内容(どれが表/裏かも含む)と山のカードの内容 全部を合わせたものが1つの状態であり、プレーヤが場のカードを移 動したり次のカードをめくってどこかに置いたりするのが状態遷移と なります。 この時、先のグラフと違うのは、グラフでは比較的少数の状態(ノー ド) が予め分かっていてそれを予め全部用意していたのに対し、ゲー ムやパズルでは可能な状態の数が非常に多く、それを全部生成してお くことは非現実的だという点です。 そこで、「手」を打つごとに次の状態をその場で生成して行き、目指す 状態(自分が勝利したり、パズルが解けた状況のことです)が見つかっ たらそこでおしまい、という処理が必要です。これを状態空間の探索 (state space search)と言います。

ゲーム・パズルと状態空間

図 10: マルバツの状態空間 (一部) 簡単なゲームの例として、図10にマルバツの状態空間の始めの方を 描いてみました(×が先手であるものとします)。マス目が9個あり、そ れぞれに(1) ○が入る、(2)×が入る、(3)まだどちらも入っていない、 の3つがあるので、最大で39 = 19683通りの状態があることになりま す。ただし、途中でどちらかが勝ったらおしまいですし、上下/左右/ 点対称のものは分けなくてもよいわけなので、実際に扱う状態はだい ぶ少なくて済みます。 2万程度の状態数であれば、今日のコンピュータではすべてを列挙す ることが可能です。状態を全部列挙できてしまえば、その中で「勝ち 筋」をたどっていくだけでゲームに勝てることになります。または勝 ち筋がなければ引き分けをめざしますが、途中で相手が失策をしたら 勝ち筋に乗れるかもしれません。 一方、囲碁とか将棋とかだと、状態の数が本当にすごく多くなるの で、これをコンピュータで扱うのはまだまだ大変です。

ゲーム・パズルと状態空間

スタックを用いた深さ優先探索の場合、状態空間探索の基本的なア ルゴリズムは次の形になります(スタックをキューに取り換えると幅 優先探索になります): s = 初期状態; s.mark; stack.push(s) while !stack.isempty do s = stack.pop (sに隣接ずる状態を生成) do |s1| if s1.isgoal then ☆☆☆ゴールに到達した!☆☆☆

elsif !s.ismarked then s1.mark; stack.push(s1) end end end ☆☆☆全状態を生成したがゴールに到達できなかった!☆☆☆ マルバツのように駒を置く一方のゲームはある状態から遷移していっ て再度同じ状態に来ることは(駒は増える一方なので)あり得ませんが、 将棋のようなゲームでは同じ状態に戻って来ることがあります。この 時に、また同じ処理をしていたら終わらなくなりますから、状態ごと に「この状態は処理し終わった」という印をつけて再度同じ状態に来た ら「もう処理ずみ」として飛ばす必要があります。これを上ではmark、 ismarkedで表しています。

例題

:

箱入り娘

「箱入り娘」というパズルをご存じでしょうか。これは図11のよう な枠と駒から成るパズルで、初期状態から駒をスライドさせていって、 最終的には「箱入り娘」が出口から出られる状態にする、というもの です。 小 小 小 小 番頭 娘 父_親 母 親 下 男 下女 小 小 小 小 番頭 娘 父 親 母 親 下 男 下女 図 11: 箱入り娘の初期状態と最終状態 (の 1 つ) では、これを解くプログラムを説明しましょう。まず、縦横のマス目 の数、「目標」となる娘の位置、駒(0∼9で表す)の縦と横のサイズ、お よび駒の名前を表す1文字(表示文字列生成用)をグローバル変数に入 れておきます:

$hmax = 3; $vmax = 4; $goalx = 1; $goaly = 3 $hsize = [2, 1, 1, 1, 1, 2, 1, 1, 1, 1]

$vsize = [2, 2, 2, 2, 2, 1, 1, 1, 1, 1] $names = ’Mvvvvwssss.’

例題

:

箱入り娘

次に、9個の駒の位置(X座標、Y座標をそれぞれ要素数9の配列に入 れてあるものとします)を受け取り、盤面を表現した2次元配列を作る メソッドmakeboardを示します:

def makeboard(x, y)

b = Array.new($vmax+1) do Array.new($hmax+1, -1) end $hsize.length.times do |i|

$hsize[i].times do |j|

$vsize[i].times do |k| b[y[i]+k][x[i]+j] = i end end end return b end 最初に全要素が-1(何も置いてない)の2次元配列を作ります。そして 各駒について、その駒の置かれている全範囲に駒の番号を入れます。

例題

:

箱入り娘

さて次に、盤面bを受け取り、駒iが現在x,yにあるものとして、こ

れをdx,dyだけ動かすことが可能かどうか調べるメソッドmovableを

見てみましょう:

def movable(b, i, x, y, dx, dy)

if x+dx < 0 || x+$hsize[i]-1+dx > $hmax ||

y+dy < 0 || y+$vsize[i]-1+dy > $vmax then return false end $hsize[i].times do |j|

$vsize[i].times do |k| p = b[y+dy+k][x+dx+j];

if p != -1 && p != i then return false end end end return true end まず、動かした後が盤面からはみ出るならNOを返します。そうでな いなら、動かした後の自分の置かれる範囲のマスすべてについて、そ こが-1(何も置いてない)でもこれまで自分が置いてあったマスでもな いなら直ちにNOを返します。最後までNOでなければOKを返します。 盤面の1つの状態を表すのにオブジェクトを使うことにしたので、State というクラスを作成しました。インスタンス変数としては、9個の駒 のXY座標の配列、および「1つ前の状態」を保持します。なお、配列 はinitailzeで渡されてきたものをそのまま持っていると書き換えら れてしまうので、メソッドdupでコピーを作ってそれを保持します。

例題

:

箱入り娘

getx、getyは各駒の座標値の配列をそのまま返します。isgoalは駒 0が目標位置にあるか否かを返します。moveは自分の状態から駒iを dx,dyだけ動かした新しい状態を作って返します。この時一時的に配 列中の駒の位置を動かして新しい状態を作り(selfというのは「この オブジェクト」を渡すという意味)、終わったら戻します (このため、 dupによるコピーが必要なのでした): class State

def initialize(x, y, p=nil) @x=x.dup; @y=y.dup; @prev = p end def getx() return @x end

def gety() return @y end

def isgoal() return @x[0] == $goalx && @y[0] == $goaly end def move(i, dx, dy)

@x[i] = @x[i] + dx; @y[i] = @y[i] + dy; s = State.new(@x, @y, self)

@x[i] = @x[i] - dx; @y[i] = @y[i] - dy; return s end

def to_s() s = ’’

makeboard(@x, @y).each do |a|

a.each do |i| s = s + $names[i..i] end; s = s + "\n" end

return s end

def output(f)

if @prev != nil then @prev.output(f) end f.puts(to_s); f.puts(’---’)

例題

:

箱入り娘

to sはmakeboardで盤面の配列を作ったあと、それを1つの文字列に していますが、その時駒の番号ではなく各駒を表す文字1文字にして いるのに注意してください。これは、縦長の駒や小僧の駒はどれでも 同じことなので、これらを同じ名前にすることで状態数を少なくでき るためです。outputは最終状態に到達できた時使うメソッドで、ファ イルfを渡されて最初に近い状態から順にファイルに状態を書き出し ます。@prevは逆向きのリストなので、先頭から表示するため再帰を 使っています。 では最後にmainを示します。今回は速度が問題なので自前のスタッ クではなくRubyの配列をスタックに使うことにしました。xとyは各 駒の初期配置で、これらを指定して最初の状態を作り、スタックに積 みます。また、ハッシュvisitedは状態の文字列表現を入れることで その状態を既に処理ずみであることを表すのに使うので、まずは最初 の状態を「訪問ずみ」としました。その後が処理本体で、まずスタック が空ならもう調べる状態がないので失敗です。そうでなければスタッ クから1つ取り出し(進捗を見るためここで画面に表示してみるのも参 考になります)、取り出したのが目的状態ならループを抜け出します。 そうでない場合は、処理する状態の各駒の座標を取り出し、全ての駒 について上下左右に移動できるか調べ、できるのならその新しい状態 を生成し、それが既に処理ずみ(な状態と同等)でないなら、スタック に積んで処理ずみとして登録します:

例題

:

箱入り娘

def main

x = [1,0,3,0,3,1,0,1,2,3]; y = [0,0,0,2,2,2,4,3,3,4]

stack = [State.new(x,y)]; visited = {stack[0].to_s => true} while true do

if stack.length == 0 then puts("impossible."); return false

s = stack.pop # or s = stack.shift

puts(s.to_s); puts(’----’) if s.isgoal then break end

x = s.getx; y = s.gety; b = makeboard(x, y) $hsize.length.times do |i|

[[1,0],[-1,0],[0,1],[0,-1]].each do |a| if movable(b, i, x[i], y[i], a[0], a[1])

s1 = s.move(i, a[0], a[1]); k1 = s1.to_s

if visited[k1] == nil then stack.push(s1); visited[k1] end

end end end

File.open(’out.data’, ’w’) do |f| s.output(f) end return true

end

成功してループを抜けた時にはファイルout.dataに初期状態から目 的状態までの各状態を出力しておしまいです。長かったですね、おつ かれ様でした。では動かしてみましょう:

例題

:

箱入り娘

irb> main vMMv vMMv vwwv vssv s..s ----vMMv vMMv vwwv vssv s.s. ----vMMv vMMv vwwv vssv ss.. ----(途中略) vvvv vvvv ssww MM.s MM.s ----vvvv vvvv ssww

.MMs .MMs ----=> true 解けたようですね。そして、実行時の表示には「行き詰まった」枝 も全部含まれますが、ファイルには見た目はこれと同様でも、正しく 解ける経路だけが記録されています。 ちなみに、スタックを使うと探索が深さ優先なので、解けるまでの 時間は短いですが、得られた解が最短とは限りません。幅優先探索に すると状態数が多くなりがちですが、得られた解は最短手数のものと なります。そうするにはstack.popの代わりに配列の先頭から取り除 くメソッドstack.shiftを使えばよいでしょう(もはやスタックでな いのにstackという名前なのはまずいですけど)。 演習8 上のプログラムを打ち込み、動作を確認せよ。成功したら、駒 の大きさや配置を変更して正しく動作するか確認せよ。できれば、 幅優先と深さ優先の比較もやってみてほしい。 演習9 自分の好きなゲームないしパズルを扱う状態空間探索プログラ ムを作れ。 演習10 その他、ここまでにこの授業で学んだ内容を活かした面白い プログラムを作れ。何が面白いかの定義は各自に任されます。

本日の課題

10A

任意の演習問題について、動かしたプログラムを含む小レポートを 今日中に久野までメールで送ってください。

1. Subject: は「Report 10A」とする。

2. 学籍番号、氏名、投稿日時を書く。 3. プログラムどれか1つのソース。 4. 以下のアンケートの回答。 Q1. スタック、キュー、表などの抽象データ型を理解しましたか。 Q2. 「グラフの探索」「状態空間の探索」はどうでしたか。 Q3. 本日の全体的な感想と今後の要望をお書きください。

次回までの課題

10B

次回までの課題はありませんが、よろしければ気に入った演習問題 の解答+考察をこれまで通り「Report 10B」のようなタイトルで提出 してください。サイトに掲載し、講評を記載します。ただし加点はあ りません。