Rubyで迷路探索を幅優先探索で解く

最近は仕事ができない感から完全脱却してみる｜牛尾剛｜noteに触発されて基本に戻ろうと思い、アルゴリズムの勉強をしている。今回は迷路の最短経路を幅優先探索で解くというのをやってみた。

やりたいこと

迷路を以下のような文字列で与えられたときに

.#....#G
.#.#....
...#.##.
#.##...#
...###.#
.#.....#
...#.#..
S.......

最短経路の手数と、その経路を出力する。

16
.#****#G
.#*#.***
.**#.##.
#*##...#
**.###.#
*#.....#
*..#.#..
S.......

実装

以下のように実装した。アルゴリズム理解のためなので再利用性や設計の綺麗さなどはあまり考えていない。

class SolveMaze
  VECTOR = [[0, 1], [0, -1], [1, 0], [-1, 0]]

  def initialize(maze_struct)
    @maze_struct = maze_struct
    @maze_width = @maze_struct.first.size
    @maze_height = @maze_struct.size

    # The distance between start to @maze_dist[x][y]
    @maze_dist = Array.new(@maze_height) { Array.new(@maze_width, nil) }
    # The previous position of @maze_dist[x][y]
    @maze_prev_links = Array.new(@maze_height) { Array.new(@maze_width, nil) }

    @search_queue = []
    @maze_struct.each_with_index do |row, x|
      row.each_with_index do |val, y|
        if val == 'S'
          @maze_start = [x, y]
          @search_queue.push([x, y])
          @maze_dist[x][y] = 0
        elsif val == 'G'
          @maze_goal = [x, y]
        end
      end
    end
  end

  def calc_by_bfs
    until @search_queue.empty?
      cur_x, cur_y = @search_queue.shift
      return @maze_dist[cur_x][cur_y] if @maze_struct[cur_x][cur_y] == 'G'

      VECTOR.each do |dx, dy|
        next_x = cur_x + dx
        next_y = cur_y + dy

        # outbound
        next if next_x < 0 || next_x >= @maze_width
        next if next_y < 0 || next_y >= @maze_height
        next if @maze_struct[next_x][next_y] == '#' # wall
        next if @maze_dist[next_x][next_y] # already visited

        @maze_dist[next_x][next_y] = @maze_dist[cur_x][cur_y] + 1
        @maze_prev_links[next_x][next_y] = [cur_x, cur_y]
        @search_queue.push([next_x, next_y])
      end
    end
  end

  def get_route
    route = []
    cur_x, cur_y = @maze_goal
    until cur_x == @maze_start[0] && cur_y == @maze_start[1]
      route.unshift([cur_x, cur_y])
      cur_x, cur_y = @maze_prev_links[cur_x][cur_y]
    end
    route.unshift(@maze_start)
    route
  end

  def print_route
    route = get_route
    maze_solved_struct = Marshal.load(Marshal.dump(@maze_struct))
    route[1..-2].each do |x, y|
      maze_solved_struct[x][y] = '*'
    end
    maze_solved_struct.each do |row|
      puts(row.join(''))
    end
  end
end

maze_str = <<~STR
  .#....#G
  .#.#....
  ...#.##.
  #.##...#
  ...###.#
  .#.....#
  ...#.#..
  S.......
STR
maze_struct = maze_str.split("\n").map { |line| line.split('') }
maze_solver = SolveMaze.new(maze_struct)
puts(maze_solver.calc_by_bfs)
maze_solver.print_route

maze_str2 = <<~STR
  S..#......
  .#...##.#.
  .##.#...#.
  ...#..##.#
  ##..#.#...
  ...#.#..#G
  .#....#..#
  ..#.#..#..
  .#.#.#..#.
  ......#...
STR
maze_struct2 = maze_str2.split("\n").map { |line| line.split('') }
maze_solver2 = SolveMaze.new(maze_struct2)
puts(maze_solver2.calc_by_bfs)
maze_solver2.print_route

実装してみての気づき

今いるマスから、上下左右の次のマスを計算し、それを探索キューに入れるというのが基本的な考え方
幅優先探索なら、一度経路を計算したマスはもう計算しなくて良いのはなるほどと思った
- 参考: BFS (幅優先探索) 超入門！〜キューを鮮やかに使いこなす〜 - Qiita
同じようなことをやっている記事を参考にしたのだが、動く方向をvectorとして表してループで処理するのはキレイに書ける手法として良い
- https://qiita.com/drken/items/0c7bab0384438f285f93
グラフ系の探索において経路を復元する時は、ひとつ前の要素が何かを記録しておくのが定石っぽい
- 以前Bellman-Ford法による最短経路発見の実装をしたときも同じ手法だった