迷路の最短経路
ここにある迷路の最短経路を調べる問題をやってみた。これはまた要するに動的計画法でいいんでしょ、とハンマーの使い方を覚えたもんだからすべてが釘に見える感じで、同じ方法論でやってみようとしてみたり。ダイクストラ法がうんたらという話も聞こえてきたけど、ちょっと大げさっぽい。
で、ともかく書いてみて1時間ほど試行錯誤したのち、うまく行かずに放置していたのだけど、スタートとゴールは実は対象なのだよ、どっちからはじめても同じだよ、という神の声が聞こえて、別の方針でやってみることにした。
スタートから隣接するセルを1つずつ辿っていき、適当に埋めていく。すでに誰かがそのセルに来たことがあれば、その経路は調べる必要がない。
この方針自体は上手くいきそうだとすぐにわかったけど、実際に動くコードに落とし込むのにえらい時間がかかってしまった。いろいろ思うところはあるけど、動いて良かった。
=begin example maze: ************************** *S* * * * * * * ************* * * * * ************ * * * * ************** *********** * * ** *********************** * * G * * * *********** * * * * ******* * * * * * ************************** output(shortest path): ************************** *S* *#### * *#* *# *# ************* * *#*###* # ************ * *### * ####### * **************#*********** * ############# * **#*********************** * ### *##############G * * *##### *********** * * * * ******* * * * * * ************************** =end Point = Struct.new(:y, :x) def read_maze maze = [] while line = gets line.chomp! maze << line.split(//) end maze end def find_postion(maze, c) line = maze.find {|l| l.index(c)} y = maze.index(line) x = line.index(c) return Point.new(y, x) end def next_cell(paths, maze, table) new_paths = [] paths.each do |path| [[-1, 0], [1, 0], [0, -1], [0, 1]].each do |move| p = path.last y2 = p.y + move[0] x2 = p.x + move[1] if (table[y2][x2] == nil && (maze[y2][x2] == " " || maze[y2][x2] == "G")) then table[y2][x2] = table[p.y][p.x] + 1 new_path = Marshal.load(Marshal.dump(path)) new_path << Point.new(y2, x2) new_path << "goal" if maze[y2][x2] == "G" new_paths << new_path end end end new_paths end # initialize maze = read_maze # maze = [["*", "*", "*", "*", "*"], ["*", "S", " ", " ", "*"], ["*", " ", " ", "G", "*"], ["*", "*", "*", "*", "*"]] table = Array.new(maze.size) do Array.new(maze[0].size, nil) end # table = [[nil, nil, nil, nil, nil], [nil, nil, nil, nil, nil], [nil, nil, nil, nil, nil], [nil, nil, nil, nil, nil]] start = find_postion(maze, "S") table[start.y][start.x] = 0 paths = [[start]] # [[start,p1],[start,p2]] -> [[start,p1,p3],[start,p2,p4]] # search cell by cell while true do paths = next_cell(paths, maze, table) # if some path hits the goal then. paths.each do |path| if path.last == "goal" then path.pop # need to delete the "goal" path.pop; path.shift # just to output S and G path.each do |p| maze[p.y][p.x] = "#" end maze.each do |line| print line.join,"\n" end exit end end end