Rubyで最短経路問題に挑戦してみた

人生を書き換える者すらいた。- 人材獲得作戦・４　試験問題ほかで採用に使ったという最短経路を求める問題にRubyで挑戦してみました。
というかこれはダイクストラ法を知ってるかどうかなような...
自分も中学からプログラミングやってたけどダイクストラ法を知ったのは大学生になってからだから、高校のときだったら解けなかったでしょう。
一般レベルのプログラマーを探すだけなら他の方もいろんなところでコメントしているように問題も選択式だったらいいかもしれませんね。
もちろんこの問題を所定の時間内に解ける人は一般以上の力量があると思いますが。
自分も数学的なアルゴリズムを組むのは苦手なので恥ずかしいですが...

マップデータはSerendip Web Studio - 最短経路探索プログラムの試験問題を解いてみたさんから拝借しちゃいました。

※追記: 以下のプログラムはダイクストラ法ではなく、単なる枝狩りありの深さ優先探索な気がしてきた
※さらに追記：ん〜やっぱり確定フラグを使ってないだけのダイクストラ法の亜種な感じもしてきた...

class Map

  attr_reader :start
  attr_reader :goal

  # map文字列から文字列の二次元配列としてマップをロードして返す
  def self.parse(str)
    map = self.new
    map.parse(str)
    return map
  end

  # コンストラクタ
  def initialize()
    @map = []
    @start = [nil, nil]
    @goal = [nil, nil]
    @cost = {} # [x,y] => [from_x, from_y, n] (@startからのコスト)
  end
  
  # map文字列から文字列の二次元配列としてマップをロード
  def parse(str)
    @map = []
    lines = str.split(/\n/)
    lines.each_with_index do |line, y|
      line.split(//).each_with_index do |char, x|
        @map[x] = [] if @map[x].nil?
        @map[x][y] = char
        @start = [x, y] if char == "S"
        @goal = [x, y] if char == "G" 
      end
    end
  end
  
  # 指定座標が壁かどうかを調べる
  def block?(x, y)
    return @map[x][y] == "*"
  end
  
  # 指定座標が道かどうかを調べる
  def path?(x, y)
    return (@map[x][y] == " " || @map[x][y] == "G")
  end
  
  # マップの幅
  def width
    return @map.size
  end
  
  # マップの高さ
  def height
    return @map[0].size
  end
  
  # スタート地点から, 全ての点への距離をダイクストラ法で求める
  def dijkstra!
    sx = @start[0]
    sy = @start[1]
    @cost[ [sx, sy] ] = [nil, nil, 0]
    nodes_around_start = available_around_nodes(sx, sy)
    dijkstra_from(sx, sy)
  end
  
  # @costに記録されている最短コストと, 
  # その場合の経路を逆にたどりひっくり返してstartからの経路にする
  def shortest_path_to_goal
    path = [ [@goal[0], @goal[1]] ]
    current_x = @goal[0]
    current_y = @goal[1]
    while (current_x != nil && current_y != nil)
      tmpx, tmpy, dummy_cost = @cost[ [current_x, current_y] ]
      path << [tmpx, tmpy]
      current_x = tmpx
      current_y = tmpy
    end
    path.pop # [nil, nil]をなくす
    return path.reverse
  end
  
  # 結果を表示する
  def draw_with_shortest_path
    copy_map = @map.dup
    s_path = shortest_path_to_goal
    s_path[1..-2].each do |(x, y)|
      copy_map[x][y] = "$"
    end
    (0..height-1).each do |draw_y|
      (0..width-1).each do |draw_x|
        print copy_map[draw_x][draw_y]
      end
      print "\n"
    end
  end
  
  protected
  
  # コスト表を元に再帰的にダイクストラしていく
  def dijkstra_from(x, y)
    nodes = available_around_nodes(x, y)
    dummy_x, dummy_y, my_cost = @cost[ [x, y] ]
    nodes.each do |(nx, ny)|
      dummy_x, dummy_y, node_cost = @cost[ [nx, ny] ]
      node_cost = width*height if node_cost.nil? # 一度もコストが計算されて設定されてない
      if my_cost+1 < node_cost then
        @cost[ [nx, ny] ] = [x, y, my_cost+1]
        dijkstra_from(nx, ny)
      end
    end
  end
  
  # 座標(x,y)の上下左右のノードのうち, ちゃんと道になってるやつを返す
  def available_around_nodes(x, y)
    return [ [x, y-1], [x, y+1], [x-1, y], [x+1, y] ].select{|(tx, ty)| path?(tx, ty) }
  end
  
end

$MAP1 = <<EOD
**********
*S*      *
* * ** * *
*   ** * *
***  *  G*
**********
EOD

$MAP2 = <<EOD
**************************
*S* *                    *
* * *  *  *************  *
* *   *    ************  *
*    *                   *
************** ***********
*                        *
** ***********************
*      *              G  *
*  *      *********** *  *
*    *        ******* *  *
*       *                *
**************************
EOD

# --- main program ---

#map = Map.parse($MAP1)
map = Map.parse($MAP2)
puts "map parsed: width=#{map.width}, height=#{map.height}"
puts "start=(#{map.start[0]}, #{map.start[1]}), goal=(#{map.goal[0]}, #{map.goal[1]})"
puts "running dijkstra!()"
map.dijkstra!
puts "dijkstra!() finished"
p map.shortest_path_to_goal
puts "--------------------------"
map.draw_with_shortest_path