2010-01-15
Ruby勉強 -- 追記：統計的なアプローチ（のつもり）
最適解？何それ美味しいの？なコード
解を見つけたり見つけなかったりします。
探索を繰り返して良さそうな経路の評価を高くし、悪そうな経路の評価を低くしていきます。
探索は前回までの評価を元に行いますが、乱数によるフラつきをいれています。
評価、乱数パラメータのバランスで挙動が変わります。また局所解にトラップされると最短経路を見つけることができません。
いろんな代償を払いますがより一般的な問題へ適用可能なはず。（うっかりマヌケな解を出すのが人間ぽくていい）
# http://okajima.air-nifty.com/b/2010/01/post-abc6.html
class Maze
@@directions = [{'x'=>-1,'y'=>0},{'x'=>1,'y'=>0},{'x'=>0,'y'=>-1},{'x'=>0,'y'=>1}]
@@trial_count = 1000
@@swinging = 1.0
@@positive = 1.05
@@negative = 0.99
@@base = 100.0
def run
load_map
@@trial_count.times {|i|
route = Array.new
solve_map(@s['y'],@s['x'], 0, route)
}
if select_route(@g['y'],@g['x']) then @map.each{|line| print line.to_s + "\n" } else print "fail!\n" end
end
def load_map
data = DATA.read
@map = []
data.each_line {|line| @map.push line.chomp.split(//) }
@cmap = []
@map.each{|m| @cmap.push Array.new(m.size, @@base)}
@map.each_with_index{|line,i| line.each_with_index{|c,j|
@s = {'x'=>j, 'y'=>i} if c == 'S'
@g = {'x'=>j, 'y'=>i} if c == 'G'
}}
end
def solve_map(y,x,c,route)
node = {'x'=>x,'y'=>y}
# check goal
if @map[y][x] == 'G'
route.each_with_index{|node,i|
@map[node['y']][node['x']] = ' '
@cmap[node['y']][node['x']] *= @@positive*(1.0+1.0/(c*c))
}
return
end
# new node
if @map[y][x] == ' '
@map[y][x] = '-'
route.push node
end
# check route
walkable = false
@@directions.each{|d| walkable |= @map[y+d['y']][x+d['x']] == ' '}
if walkable then
max_c = -10000.0
ny=-1
nx=-1
@@directions.each{|d|
rc = (rand(10000)/5000.0-1.0)*@@swinging
if @cmap[y+d['y']][x+d['x']]+rc > max_c && (@map[y+d['y']][x+d['x']] == ' ' || @map[y+d['y']][x+d['x']] == 'G')
max_c = @cmap[y+d['y']][x+d['x']]+rc
ny = y+d['y']
nx = x+d['x']
end
}
return solve_map(ny,nx,c+1,route) if nx != -1 && ny != -1
else
# abort
route.each_with_index{|node,i|
@map[node['y']][node['x']] = ' '
@cmap[node['y']][node['x']] *= @@negative
}
return
end
end
def select_route(y,x)
@map[y][x] = '$' if @map[y][x] == ' '
@@directions.each{|d| return true if @map[y+d['y']][x+d['x']] == 'S'}
max_c = -10000.0;
ny=-1
nx=-1
@@directions.each{|d|
if (@cmap[y+d['y']][x+d['x']] > max_c && @map[y+d['y']][x+d['x']] == ' ')
max_c = @cmap[y+d['y']][x+d['x']]
ny = y+d['y']
nx = x+d['x']
end
}
return select_route(ny,nx) if nx != -1 && ny != -1
return false
end
end
maze = Maze.new
maze.run
__END__
**************************
*S* * *
* * * * ************* *
* * * ************ *
* * *
************** ***********
* *
** ***********************
* * G *
* * *********** * *
* * ******* * *
* * *
**************************