迷路の最短経路を求めるには?
相当、出遅れた感はあるが、以下の試験問題をやってみた。(Rubyで)
さて試験問題です。
内容は、壁とスペースで構成された迷路が与えられたとき、スタート地点からゴール地点に至る最短経路を求めよ、というものです。
たとえば、S:スタート G:ゴール *:壁 $:解答の経路 としたとき、************************** *S* * * * * * * ************* * * * * ************ * * * * ************** *********** * * ** *********************** * * G * * * *********** * * * * ******* * * * * * **************************という入力に対し、
************************** *S* * $$$ * *$* *$$*$ ************* * *$* $$* $$$************ * *$$$$* $$$$$ * **************$*********** * $$$$$$$$$$$$$ * **$*********************** * $$$$$*$$$$$$$$$$$$$$G * * * $$$ *********** * * * * ******* * * * * * **************************という出力が来ればOK、というわけです。(ブラウザだと見づらいかもしれないのでテキストエディタ等にコピーすれば見やすくなります)
もうちょっと細かい条件としては、
人材獲得作戦・4 試験問題ほか: 人生を書き換える者すらいた。
●入出力はテキストデータを用いる
●一度に動けるのは上下左右のみ。斜めは不可
●最短経路が複数あるときはそのうちの1つが出力されていればOK
●入力データのバリデーション(長方形になっているか、スタート・ゴールが1つずつあるかどうか、等)は不要
●制限時間は3時間
●プログラム言語・OSは自由
です。
web検索なしの完全自力では、Lv2(最短性のチェックはせず、とにかく1本の到達経路を求めることまではできた)、あるいは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それにしても、制限時間を気にしながら書いたコードは、まとまりがない...。