幅優先探索
11月 12th, 2008 admin Posted in アルゴリズムとデータ構造 | 
昨日に続き「アルゴリズムとデータ構造シリーズ」です。今回は第10章「バックトラック法と幅優先探索」の幅優先探索です。
幅優先探索
前回やったバックトラック法はとてもパワフルなアルゴリズムなのですが、必ずしも最適解が求まるわけではないという問題によっては不都合な特徴もあります。そこで総当たりかつ最適な解をみつけるためのアルゴリズムが幅優先探索法になります。
幅優先探索は、その名のとおり幅を優先させた探索で、まず１回目の試行でできるすべてのパターンをためし、次に２回目の試行でできるすべてのパターンをためし・・・とやっていく方法です。
バックトラック法が木構造を右手法で巡回したのに対し、こちらは1個目のノードをすべて試す、そしたら次に2階層目のノードを試すとやっていく感じです。
コード
セブンパズルというパズルを解くコードを書きました。
RUBY:
-
class Pattern
-
attr_accessor :hash, :pattern_from
-
-
def initialize(hash, pattern_from)
-
@hash = hash
-
@pattern_from = pattern_from
-
end
-
end
-
-
class SevenPuzzle
-
def initialize
-
@history = Array.new
-
@ans = Marshal.dump([1,2,3,4,5,6,7,0])
-
end
-
-
def save_history(pattern, pattern_from)
-
hash = Marshal.dump(pattern)
-
@history.each do |a|
-
return if a.hash == hash
-
end
-
-
@history.push(Pattern.new(hash, pattern_from))
-
end
-
-
def solve
-
pattern = Array.new(8)
-
-
queue_bottom = 0
-
until @history.size == 0 do
-
hash = @history.shift.hash
-
return true if hash == @ans
-
-
pattern = Marshal.load(hash)
-
-
blank_pos = pattern.index(0)
-
-
if blank_pos> 3
-
pattern[blank_pos] = pattern[blank_pos - 4]
-
pattern[blank_pos - 4] = 0
-
save_history(pattern, queue_bottom)
-
pattern = Marshal.load(hash)
-
end
-
-
if blank_pos <4
-
pattern[blank_pos] = pattern[blank_pos + 4]
-
pattern[blank_pos + 4] = 0
-
save_history(pattern, queue_bottom)
-
pattern = Marshal.load(hash)
-
end
-
-
if blank_pos != 0 && blank_pos != 4
-
pattern[blank_pos] = pattern[blank_pos - 1]
-
pattern[blank_pos - 1] = 0
-
save_history(pattern, queue_bottom)
-
pattern = Marshal.load(hash)
-
end
-
-
if blank_pos != 3 && blank_pos != 7
-
pattern[blank_pos] = pattern[blank_pos + 1]
-
pattern[blank_pos + 1] = 0
-
save_history(pattern, queue_bottom)
-
pattern = Marshal.load(hash)
-
end
-
-
queue_bottom += 1
-
end
-
return false
-
end
-
end
-
-
#initial pattern
-
pattern = [2,7,4,3,0,5,1,6]
-
-
p = SevenPuzzle.new
-
p.save_history(pattern, -1)
-
-
if p.solve
-
p 'done'
-
else
-
p 'not found'
-
end
まとめ
今回はキューを使って解きました。バックトラック法がスタックを使っていたのにたいして、こちらがキューを使うというのがなんだか面白いです。データ構造でも対になっているものがあるんですね。
※このシリーズは私がRubyでアルゴリズムとデータ構造を基礎から学ぶ記録です。全体の目次はこちらへ。
Leave a Reply