迷路の最短経路を求めるには？

雑記 Ruby

相当、出遅れた感はあるが、以下の試験問題をやってみた。（Rubyで）

　さて試験問題です。
　内容は、壁とスペースで構成された迷路が与えられたとき、スタート地点からゴール地点に至る最短経路を求めよ、というものです。
　たとえば、S:スタート　G:ゴール　*:壁　$:解答の経路　としたとき、

**************************
*S* *                    *
* * *  *  *************  *
* *   *    ************  *
*    *                   *
************** ***********
*                        *
** ***********************
*      *              G  *
*  *      *********** *  *
*    *        ******* *  *
*       *                *
**************************

という入力に対し、

**************************
*S* * $$$                *
*$* *$$*$ *************  *
*$* $$* $$$************  *
*$$$$*    $$$$$          *
**************$***********
* $$$$$$$$$$$$$          *
**$***********************
* $$$$$*$$$$$$$$$$$$$$G  *
*  *  $$$ *********** *  *
*    *        ******* *  *
*       *                *
**************************

　という出力が来ればOK、というわけです。（ブラウザだと見づらいかもしれないのでテキストエディタ等にコピーすれば見やすくなります）

　もうちょっと細かい条件としては、
●入出力はテキストデータを用いる
●一度に動けるのは上下左右のみ。斜めは不可
●最短経路が複数あるときはそのうちの１つが出力されていればOK
●入力データのバリデーション（長方形になっているか、スタート・ゴールが１つずつあるかどうか、等）は不要
●制限時間は３時間
●プログラム言語・OSは自由
　です。

人材獲得作戦・４ 試験問題ほか: 人生を書き換える者すらいた。

web検索なしの完全自力では、Lv2（最短性のチェックはせず、とにかく１本の到達経路を求めることまではできた）、あるいはLv3（不完全な最短性のチェックまでできた）だった...。どうやら、不合格っぽい。

その後、webで検索してみる。すると、ダイクストラとかA*（エースター）等の有名なアルゴリズムが一気に検索候補に挙がってくる。最短経路を探し出す部分で悩んでいたので、その解法さえ理解できれば、目指すコードは一気に完成した。参考にしたのは、以下のページ。（感謝です！とっても分かり易いアルゴリズムです。）


その方法は...

  • 迷路に対して、地図を作る。
  • 地図の初期状態は、S:スタート　G:ゴール　*:壁 以外がnilで埋まった配列。
  • 地図には、G:ゴールから各地点までの移動距離を記録していく。
    • まずは、G:ゴールの上下左右の移動可能な位置に1をセットする。
    • つぎに、上記で1をセットした位置それぞれの、上下左右の移動可能な位置に2をセットする。
    • さらに、上記で2をセットした位置それぞれの、上下左右の移動可能な位置に3をセットする。
    • 以上の操作をS:スタートに到達するまで繰り返す。
    • 途中、既に移動距離が記録されている位置では、何もしない。
  • 以上の地図が完成したら、S:スタートからより小さい移動距離を辿って行くと、G:ゴールまでの最短経路になる。


実にシンプルで、分かり易い仕組みだ。S:スタートではなく、逆のG:ゴールから辿って地図を作るところが賢い！その後は、S:スタートから迷うことなく一気にG:ゴールまでの最短経路を辿れるのだから。

      • 以下コード中の半角￥は、半角＼に置き換える必要あり。
class Maze
  def initialize(str)
    @maze = str.split("\n")
    @s = find('S')
    @g = find('G')
    @map = @maze.map {|line| line.split('').map {|i| (/[\*SG]/ =~ i ? i : nil)}}
  end
  
  def find(str)
    @maze.each_with_index do |text, y|
      x = text.index(str)
      return [x, y] if x
    end
  end
  
  def map(x, y)
    @map[y][x]
  end
  
  def put_map(score, x, y)
    @map[y][x] = score
  end
  
  def maze(x, y)
    @maze[y][x,1]
  end
  
  def put_maze(str, x, y)
    @maze[y][x,1] = str
  end
  
  def next_locs(x, y)
    [[x, y-1], [x+1, y], [x, y+1], [x-1, y]]
  end
  
  def scores(x, y)
    next_locs(x, y).map {|loc| map(*loc)}
  end
  
  def show(item, interval=0.1)
    item.each {|line| p line}
    puts ''
    sleep interval
  end
  
  def mapping(locations=[@g], score=100)
    new_locations = []
    locations.each do |loc|
      next_locs(*loc).each do |next_loc|
        case map(*next_loc)
        when 'S'
          return score - 1
        when nil
          put_map(score, *next_loc)
          new_locations << next_loc
        end
      end
    end
    mapping(new_locations, score + 1)
  end
  
  def route
    score = mapping
    show(@map)
    x, y = @s
    until scores(x, y).include?('G') do
      #show(@maze)# 途中経過
      i = scores(x, y).index(score)
      x, y = next_locs(x, y)[i]
      put_maze('$', x, y)
      score -= 1
    end
    show(@maze)
  end
  
end



require 'benchmark'

Benchmark.bm do |x|
x.report{Maze.new(<<END).route}
**************************
*S* *                    *
* * *  *  *************  *
* *   *    ************  *
*    *                   *
************** ***********
*                        *
** ***********************
*      *              G  *
*  *      *********** *  *
*    *        ******* *  *
*       *                *
**************************
END

x.report{Maze.new(<<END).route}
**************************
*                        *
*                        *
*                        *
*                        *
*                        *
*            S           *
*                        *
*                    G   *
*                        *
*                        *
*                        *
**************************
END
end
  • score（移動距離）の初期値を100にしたのは、地図の配列を表示するとき、幅が揃って見易くなるので。


実行してみた。


$ ruby /Users/bebe/Desktop/meiro3.rb 
      user     system      total        real
["*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*"]
["*", "S", "*", 155, "*", 149, 148, 147, 146, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 153, 152, 151, 150, 149, 150, "*"]
["*", 158, "*", 154, "*", 150, 149, "*", 145, 144, "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", 148, 149, "*"]
["*", 157, "*", 153, 152, 151, "*", 145, 144, 143, 142, "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", 147, 148, "*"]
["*", 156, 155, 154, 153, "*", 145, 144, 143, 142, 141, 140, 139, 138, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, "*"]
["*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", 136, "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*"]
["*", 124, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, "*"]
["*", "*", 122, "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*"]
["*", 122, 121, 120, 119, 118, 117, "*", 113, 112, 111, 110, 109, 108, 107, 106, 105, 104, 103, 102, 101, 100, "G", 100, 101, "*"]
["*", 123, 122, "*", 118, 117, 116, 115, 114, 113, "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", 101, "*", 101, 102, "*"]
["*", 122, 121, 120, 119, "*", 117, 116, 115, 114, 115, 114, 113, 112, "*", "*", "*", "*", "*", "*", "*", 102, "*", 102, 103, "*"]
["*", 123, 122, 121, 120, 119, 118, 117, "*", 115, 114, 113, 112, 111, 110, 109, 108, 107, 106, 105, 104, 103, 104, 103, 104, "*"]
["*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*"]

"**************************"
"*S* *$$$$$               *"
"*$* *$ * $*************  *"
"*$*$$$*  $$************  *"
"*$$$ *    $$$$$          *"
"**************$***********"
"* $$$$$$$$$$$$$          *"
"**$***********************"
"* $$$$$*$$$$$$$$$$$$$$G  *"
"*  *  $$$ *********** *  *"
"*    *        ******* *  *"
"*       *                *"
"**************************"

  0.010000   0.000000   0.010000 (  0.210402)


["*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*"]
["*", nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, 109, 108, 107, 106, 107, 108, 109, "*"]
["*", nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, 109, 108, 107, 106, 105, 106, 107, 108, "*"]
["*", nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, 109, 108, 107, 106, 105, 104, 105, 106, 107, "*"]
["*", nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, 109, 108, 107, 106, 105, 104, 103, 104, 105, 106, "*"]
["*", nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, 109, 108, 107, 106, 105, 104, 103, 102, 103, 104, 105, "*"]
["*", nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, "S", 108, 107, 106, 105, 104, 103, 102, 101, 102, 103, 104, "*"]
["*", nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, 108, 107, 106, 105, 104, 103, 102, 101, 100, 101, 102, 103, "*"]
["*", nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, 108, 107, 106, 105, 104, 103, 102, 101, 100, "G", 100, 101, 102, "*"]
["*", nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, 108, 107, 106, 105, 104, 103, 102, 101, 100, 101, 102, 103, "*"]
["*", nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, 108, 107, 106, 105, 104, 103, 102, 101, 102, 103, 104, "*"]
["*", nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, 108, 107, 106, 105, 104, 103, 102, 103, 104, 105, "*"]
["*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*"]

"**************************"
"*                        *"
"*                        *"
"*                        *"
"*                        *"
"*                        *"
"*            S$$$$$$$$   *"
"*                    $   *"
"*                    G   *"
"*                        *"
"*                        *"
"*                        *"
"**************************"

  0.000000   0.000000   0.000000 (  0.205277)

面白かった。

最初のバージョン

ちなみに、web検索なしの完全自力の最初のバージョンは、以下のコード。途中経過も表示するようにして、行き止まりで戻りつつ、試行錯誤する様子が見れて、動きとしてはこっちの方が面白い。最短経路は求められないけど...。

  • G:ゴールまでの直線距離を求めて、より短い距離になる方向に舵を切っている。
  • しかし、急がば回れと言う諺もある通り、その瞬間は遠回りでも、結果的に近道になるケースもあり、最短経路を見つけられていない。
def maze_data
<<END.split("\n")
**************************
*S* *                    *
* * *  *  *************  *
* *   *    ************  *
*    *                   *
************** ***********
*                        *
** ***********************
*      *              G  *
*  *      *********** *  *
*    *        ******* *  *
*       *                *
**************************
END
end

def find(str)
  @maze.each_with_index do |text, y|
    x = text.index(str)
    return [x, y] if x
  end
end

def maze(x, y)
  @maze[y][x,1]
end

def put_maze(str, x, y)
  @maze[y][x,1] = str
end

def put?(x, y)
  true if maze(x, y) == " "
end

def loc_diff(from, to)
  [to[0] - from[0], to[1] - from[1]]
end

def distance(x, y)
  (x-@g[0])**2 + (y-@g[1])**2
end

def route(current_loc=@s, move_count=0)
  diff = loc_diff(current_loc, @g)
  
  if diff == [1, 0] || diff == [0, 1] || diff == [-1, 0] || diff == [0, -1]
    puts @maze
    return @maze
  else
    d = [nil, nil, nil, nil]
    d[0] = distance(current_loc[0],     current_loc[1] - 1) if put?(current_loc[0],     current_loc[1] - 1)
    d[1] = distance(current_loc[0] + 1, current_loc[1]    ) if put?(current_loc[0] + 1, current_loc[1]    )
    d[2] = distance(current_loc[0],     current_loc[1] + 1) if put?(current_loc[0],     current_loc[1] + 1)
    d[3] = distance(current_loc[0] - 1, current_loc[1]    ) if put?(current_loc[0] - 1, current_loc[1]    )
    
    puts @maze; sleep 0.1;
    
    while d != [nil, nil, nil, nil]
      new_loc = current_loc.clone
      min_value = d.min {|x, y| (x||999999) - (y||999999)}
      min_index = d.index(min_value)
      d[min_index] = nil
      case min_index
      when 0
        new_loc[1] = current_loc[1] - 1
      when 1
        new_loc[0] = current_loc[0] + 1
      when 2
        new_loc[1] = current_loc[1] + 1
      when 3
        new_loc[0] = current_loc[0] - 1
      end
      
      put_maze('$', *new_loc)
      if route(new_loc, move_count + 1)
        return @maze
      else
        put_maze(' ', *new_loc)
      end
    end #while
    return nil
  end
end



# S:スタートから辿る
@maze = maze_data
@s = find('S')
@g = find('G')
route

# G:ゴールから辿る
@maze = maze_data
@s = find('G')
@g = find('S')
route

それにしても、制限時間を気にしながら書いたコードは、まとまりがない...。