迷路を最短経路で脱出する問題

maze.rb

#!/usr/bin/ruby

# http://okajima.air-nifty.com/b/2010/01/post-abc6.html

# 【2010.1.25追記】
# #{RUBYLIB}/matrix.rb のコードを修正しないと動かないかもしれません。
# http://redmine.ruby-lang.org/issues/show/560

require 'set'
require 'matrix'

# 迷路に関するクラスなど
module Maze
  # 方向を表す定数
  DIRECTION = {
    :u => Vector[0, -1],
    :d => Vector[0, 1],
    :l => Vector[-1, 0],
    :r => Vector[1, 0]
  }
  
  # 迷路の地図を表すクラス
  class Map
    # コンストラクタ
    def initialize(filename)
      # ファイルを読み込む
      @data = File.readlines(filename).map{ |line| line.chomp }
      
      # スタート地点、ゴール地点を取得
      @data.each_with_index do |v, i|
        pos = v.index('S'); @start = Vector[pos, i] if pos
        pos = v.index('G'); @goal = Vector[pos, i] if pos
      end
    end
    
    # スタート地点、ゴール地点
    # いずれもVectorのインスタンスを返す
    attr_reader :start, :goal
    
    # 座標を指定し、その座標における（地図上の）文字を返す
    def [](vec)
      @data[vec[1]][vec[0],1]
    end
    
    # 経路を探索する
    def seek
      # スタックには、現時点の経路と、訪問済みの箇所を組にしたものを
      # 積んでおく
      stack = [{:route => [], :last_pos => @start, :visited => Set[@start]}]
      # 現時点での最良ルート
      shortest_path = nil
      shortest_length = @data.size * @data[0].length
      
      # 全探索
      until stack.empty?
        item = stack.pop
        
        # 経路が長くなりすぎた場合は終了
        next if item[:route].size >= shortest_length
        
        # ゴールした場合
        if item[:last_pos] == @goal
          if item[:route].size < shortest_length
            shortest_length = item[:route].size
            shortest_path = item[:route]
            
            puts "Length: #{shortest_length} (#{item[:route]})"
            puts show_map(item[:visited])
          end
          
          next
        end
        
        # 四方に進めてみて、進めるならそのルートをスタックに追加
        # ※ゴールに近づきそうな向きを優先的に試す
        get_priority(item[:last_pos]) do |dir_name|
          dir_vector = DIRECTION[dir_name]
          
          new_pos = item[:last_pos] + dir_vector
          
          # 進んだ先が、壁でも、既に通った場所でもない場合
          if self[new_pos] != '*' && !(item[:visited].include?(new_pos))
            stack << {
              :route => item[:route] + [dir_name],
              :last_pos => new_pos,
              :visited => item[:visited] + [new_pos]}
          end
        end
      end
    end
    
    # どの向きを優先的に探索するか決定する
    # 
    # 例えば現在地の座標が(1,2)でゴールの座標が(5,10)の場合、
    # 現在地からゴールへ向かうための移動数を上下左右の別に考えると
    # 「上に-4」「下に4」「左に-8」「右に8」となる。
    # 単純に考えれば、この値が大きい向きに進む方がゴールに
    # 到達しやすくなると予想されるので、この場合であれば
    # 「右→下→上→左」の順に探索を行う。
    def get_priority(current_pos)
      diff = current_pos - @goal
      {:u => -diff[1], :d => diff[1], :l => -diff[0], :r => diff[0]}.sort_by{ |k, v| -v }.each{ |k, v| yield k }
    end
    
    # 辿った結果の地図を文字列として表現する
    def show_map(visited)
      buf = Marshal.load(Marshal.dump(@data))
      visited.each do |vec|
        buf[vec[1]][vec[0],1] = '$'
      end
      
      buf.join("\n")
    end
  end
end

if $0 == __FILE__
  started = Time.now
  mm = Maze::Map.new(ARGV[0])
  mm.seek
  ended = Time.now
  
  puts "Calculation time: #{ended - started}"
end