SICP 勉強会 加速会に行ってきた

4月 16th, 2009 admin

claなんとかさんが開催してくれた
SICP 勉強会 加速会 #01 をやるよ
に4月11日12日と行ってきました。

これは「計算機プログラムの構造と解釈」（愛称：SICP）という本をCSNagoyaで読んでいるのだけど、問題が面倒すぎて毎回3問ずつぐらいしか進まなくて、（幸運にも）このペースで進んだとして終了まであと3年かかるらしいことがわかったので、3年もたったらロンドンオリンピックだし、それに俺30歳だよ！やってらんねえよ！ってわめきたかったけど、他に30歳超えている人が普通にいるので口に出せなくてっていうそういう感じの焦りからとりあえず泊まりでやれば一気に進むんじゃないか？というclaさんらの提案のもの開催された会です。
当日は天気がよくて、窓を開けると本当に昼寝日和といった感じで気持ちのよい勉強会になりました。

場所

旅館かう楽
名古屋市瑞穂区のかう楽という旅館でした。素泊まりで5,500円。地下鉄から徒歩1分、LAN有りなのでなかなかいいですね。

様子

dsc00014
ネットワークはclaなんとかさんが整えてくれたので何の心配も要りませんでした。僕はプロジェクターをもって行きましたが、今回は活躍できませんでした。

dsc00016
まさかのノンアルコール。男7人が同じ部屋に集まり、ろくに外出もせず深夜までカタカタ夜までやっていたので旅館のおばちゃんはさぞ気持ち悪く思ったでしょう。

dsc00017
布団を敷いてもなお勉強するメンバー。

まとめ

・12時間ぐらいやったのに5問ぐらいしか進まないSICP恐ろしい
・アリッサはみんなのために頑張ったのにフルボッコでかわいそう
・なんとかして問題も解きながらお酒を飲みたい
・準備が嫌いなので泊りが嫌いな僕も近ければ気が楽ということに気がついた。またやりたい

Posted in CSNAGOYA, linux, アルゴリズムとデータ構造, 勉強会 | コメントは受け付けていません。

動的計画法（１）　ナップサック問題

1月 22nd, 2009 admin

あと2問で終わりとなった「アルゴリズムとデータ構造シリーズ」です。今回は第11章「動的計画法」のナップサック問題です。

動的計画法

深さ優先探索や幅優先探索などの分割統治法（トップダウン的問題解決法）では指数的に計算量が増えてしまうような問題というのがあります。（本書では例として「４３ペンスのお釣りを出すときに考えられる小銭の組合せ」という問題があげられていました）そのような問題を解決するひとつの方法としてあるのが動的計画法というもので、

全体をいくつかの小問題に分割して、先に一括して小問題の解をすべて得て、最終的にそれらを組み合わせて問題の解決に役立てる。

だそうです。いつもは自分の言葉で説明するのですが、このアルゴリズムは説明しにくい。理解してないということかもしれません・・・

コード

ナップサック問題というのを解く問題です

PLAIN TEXT
RUBY:
  1. class Product
  2.   attr_accessor :size, :value
  3.  
  4.   def initialize(size,value)
  5.     @size = size
  6.     @value = value
  7.   end
  8. end
  9.  
  10. products = [
  11.             Product.new(2,2),
  12.             Product.new(3,4),
  13.             Product.new(5,7),
  14.             Product.new(6,10),
  15.             Product.new(9,14)
  16.            ]
  17.  
  18. NAP_SIZE = 16
  19. NAP_SIZE_RANGE = 1..NAP_SIZE
  20. nap_value = Array.new.fill(0,0..NAP_SIZE)
  21.  
  22. printf("nap size            ");
  23. NAP_SIZE_RANGE.each do |j|
  24.   printf(" %2d",j)
  25. end
  26. puts "\n"
  27.  
  28. 0..products.size.times do |i|
  29.   NAP_SIZE_RANGE.each do |j|
  30.  
  31.     if j - products[i].size>= 0
  32.       new_value = (nap_value[j - products[i].size] || 0) + products[i].value
  33.     else
  34.       new_value = 0
  35.     end
  36.  
  37.     nap_value[j] = new_value if new_value> nap_value[j]
  38.   end
  39.  
  40.   printf("use product until #%d ", i+1);
  41.   NAP_SIZE_RANGE.each do |j|
  42.     printf("%2d ",nap_value[j])
  43.   end
  44.   puts "\n"
  45. end

まとめ

これを使うべきときに思い出せるかどうか不安。

※このシリーズは私がRubyでアルゴリズムとデータ構造を基礎から学ぶ記録です。全体の目次はこちらへ。

Posted in Ruby, アルゴリズムとデータ構造 | コメントは受け付けていません。

幅優先探索

11月 12th, 2008 admin

昨日に続き「アルゴリズムとデータ構造シリーズ」です。今回は第10章「バックトラック法と幅優先探索」の幅優先探索です。

幅優先探索

前回やったバックトラック法はとてもパワフルなアルゴリズムなのですが、必ずしも最適解が求まるわけではないという問題によっては不都合な特徴もあります。そこで総当たりかつ最適な解をみつけるためのアルゴリズムが幅優先探索法になります。
幅優先探索は、その名のとおり幅を優先させた探索で、まず１回目の試行でできるすべてのパターンをためし、次に２回目の試行でできるすべてのパターンをためし・・・とやっていく方法です。
バックトラック法が木構造を右手法で巡回したのに対し、こちらは1個目のノードをすべて試す、そしたら次に2階層目のノードを試すとやっていく感じです。

コード

セブンパズルというパズルを解くコードを書きました。

PLAIN TEXT
RUBY:
  1. class Pattern
  2.   attr_accessor :hash, :pattern_from
  3.  
  4.   def initialize(hash, pattern_from)
  5.     @hash = hash
  6.     @pattern_from = pattern_from
  7.   end 
  8. end
  9.  
  10. class SevenPuzzle
  11.   def initialize
  12.     @history = Array.new
  13.     @ans = Marshal.dump([1,2,3,4,5,6,7,0])
  14.   end
  15.  
  16.   def save_history(pattern, pattern_from)
  17.     hash = Marshal.dump(pattern)
  18.     @history.each do |a|
  19.       return if a.hash == hash
  20.     end
  21.    
  22.     @history.push(Pattern.new(hash, pattern_from))
  23.   end
  24.  
  25.   def solve
  26.     pattern = Array.new(8)
  27.  
  28.     queue_bottom = 0
  29.     until @history.size == 0 do
  30.       hash = @history.shift.hash
  31.       return true if hash == @ans
  32.  
  33.       pattern = Marshal.load(hash)
  34.      
  35.       blank_pos = pattern.index(0)
  36.  
  37.       if blank_pos> 3
  38.         pattern[blank_pos] = pattern[blank_pos - 4]
  39.         pattern[blank_pos - 4] = 0
  40.         save_history(pattern, queue_bottom)
  41.         pattern = Marshal.load(hash)
  42.       end
  43.  
  44.       if blank_pos <4
  45.         pattern[blank_pos] = pattern[blank_pos + 4]
  46.         pattern[blank_pos + 4] = 0
  47.         save_history(pattern, queue_bottom)
  48.         pattern = Marshal.load(hash)
  49.       end
  50.  
  51.       if blank_pos != 0 && blank_pos != 4
  52.         pattern[blank_pos] = pattern[blank_pos - 1]
  53.         pattern[blank_pos - 1] = 0
  54.         save_history(pattern, queue_bottom)
  55.         pattern = Marshal.load(hash)
  56.       end
  57.  
  58.       if blank_pos != 3 && blank_pos != 7
  59.         pattern[blank_pos] = pattern[blank_pos + 1]
  60.         pattern[blank_pos + 1] = 0
  61.         save_history(pattern, queue_bottom)
  62.         pattern = Marshal.load(hash)
  63.       end
  64.      
  65.       queue_bottom += 1
  66.     end
  67.     return false
  68.   end
  69. end
  70.  
  71. #initial pattern
  72. pattern = [2,7,4,3,0,5,1,6]
  73.  
  74. p = SevenPuzzle.new
  75. p.save_history(pattern, -1)
  76.  
  77. if p.solve
  78.     p 'done'
  79. else
  80.     p 'not found'
  81. end

まとめ

今回はキューを使って解きました。バックトラック法がスタックを使っていたのにたいして、こちらがキューを使うというのがなんだか面白いです。データ構造でも対になっているものがあるんですね。

※このシリーズは私がRubyでアルゴリズムとデータ構造を基礎から学ぶ記録です。全体の目次はこちらへ。

Posted in アルゴリズムとデータ構造 | コメントは受け付けていません。

バックトラック法

11月 11th, 2008 admin

久しぶりに「アルゴリズムとデータ構造シリーズ」です。今回は第10章「バックトラック法と幅優先探索」のバックトラック法です。

バックトラック法

ある解を求めるときに、考えられるパターンをすべて試しながら解く方法のひとつです。迷路の右手法をイメージするといいんじゃないでしょうか。パワープレイすぎてスマートさはありませんが、結局この方法が早かったり、この方法でないと解けなかったりします。以前ナンプレに挑戦したときも結局このバックトラック法を使いました。

コード

今回はエイトクイーン問題をバックトラック法で解くようにしました。

PLAIN TEXT
RUBY:
  1. class Qween
  2.   def initialize(n)
  3.     @size = n
  4.     @board = Array.new
  5.     @size.times do |i|
  6.       @board[i] = Array.new
  7.       @size.times do |j|
  8.         @board[i].push(nil)
  9.       end
  10.     end
  11.   end
  12.  
  13.   def check(y,x)
  14.  
  15.     (0...x).each do |i|
  16.       return nil unless @board[y][i].nil?
  17.     end
  18.  
  19.     (x+1).times do |i|
  20.       if (y-i)>= 0 && (x-i)>= 0
  21.         return nil unless @board[y-i][x-i].nil?
  22.       end
  23.  
  24.       if (y+i) <@size && (x-i)>= 0
  25.         return nil unless @board[y+i][x-i].nil?
  26.       end
  27.     end
  28.     true
  29.   end
  30.  
  31.   def solve(x)
  32.     return true if x == @size
  33.  
  34.     (0...@size).each do |i|
  35.       if check(i,x)
  36.         @board[i][x] = true
  37.  
  38.  
  39.         if solve(x+1)
  40.           return true
  41.         else
  42.           @board[i][x] = nil
  43.         end
  44.       end
  45.     end
  46.     return nil
  47.   end
  48.  
  49.   def show
  50.     @board.each do |row|
  51.       row.each do |c|
  52.         print c ? 'Q' : '-'
  53.         print ' '
  54.       end
  55.       print "\n"
  56.     end
  57.   end
  58. end
  59.  
  60. q = Qween.new(ARGV[0].to_i
  61. )
  62. q.solve(0)
  63. q.show

結果

PLAIN TEXT
CODE:
  1. Q - - - - - - -
  2. - - - - - - Q -
  3. - - - - Q - - -
  4. - - - - - - - Q
  5. - Q - - - - - -
  6. - - - Q - - - -
  7. - - - - - Q - -
  8. - - Q - - - - -

たしかにQが縦にも横にも斜めにも重ならないように配置されています。

まとめ

ちなみにNクイーン問題は４x4以上ならすべて解があるそうです。個人的には４x4の解が一番かっこよく見えるかな。クイーン同士が仲良さそうで

PLAIN TEXT
CODE:
  1. - - Q -
  2. Q - - -
  3. - - - Q
  4. - Q - -

※このシリーズは私がRubyでアルゴリズムとデータ構造を基礎から学ぶ記録です。全体の目次はこちらへ。

Posted in アルゴリズムとデータ構造 | 2 Comments »

文字列探索(1)

10月 25th, 2008 admin

久しぶりに「アルゴリズムとデータ構造シリーズ」です。今回は第9章「浮動小数点数と数値計算」です。

文字列探索

このアルゴリズムについては説明は必要ないでしょうね。文字列の探索はコンピュータがビジネスに欠かせなくなってしまった今日では非常に重要になっています。
第2章のあたりでサーチについては学びましたが、効率の良いバイナリサーチは文字列探索の場合はつかえません。なぜならバイナリサーチはあらかじめサーチ対象をソートしておく必要があったからです。
では、どのような方法があるのでしょうか。この章は３つぐらいコードが必要で正直面倒ですが順番にやっていきたいと思います。

まず今回はもっとも単純ですが、単純がゆえにバグもおこりにくいということから最も使われているアルゴリズムからです。ようするに最初から順番に調べていくという方法です。
[ruby]
def simple_search(text,pattern)
text.length.times do |n|
print " text:" + text + "\npattern:"
print " " * n
print pattern

flag = true
pattern.length.times do |i|
flag = false if (pattern[i] != text[n + i]) Read the rest of this entry »

Posted in Ruby, アルゴリズムとデータ構造 | 2 Comments »

« Previous Entries