迷路*Python
覚えたてほやっほやのPythonを使ってみたくて書きました.
問題は,
人生を書き換える者すらいた。:人材獲得作戦・4 試験問題ほか
の最短経路探索問題から抜粋.
実際の問題の詳細については、リンクから.
簡単に説明すると,迷路のスタートからゴールまでの最短経路を返すプログラムを書いてくださいというものです.
出力はこんな感じにしました.(*:壁、S:スタート位置、G:ゴール位置、$:経路)
$ ipython meiro.py スタート地点:(1, 1) ゴール地点:(8, 22) 最短距離:60 ************************** *S* * $$$$ * *$* *$$* $************* * *$* $$* $$************ * *$$$$* $$$$$ * **************$*********** * $$$$$$$$$$$$$ * **$*********************** * $$$$$* $$$$$$$$$$$$$G * * * $$$$*********** * * * * ******* * * * * * **************************
コード全文を以下に晒します.
幅優先探索で,枝刈りしつつ,ゴールに行き着いたら探索終了,スタートから各位置の最小距離を繋げるとゴールまでの経路になります,という考え方です.
# -*-coding: utf-8 -*- #問題:S->Gまでの最短経路を求めたい.*は壁、上下左右にしか進めない. map = [ '**************************', '*S* * *', '* * * * ************* *', '* * * ************ *', '* * *', '************** ***********', '* *', '** ***********************', '* * G *', '* * *********** * *', '* * ******* * *', '* * *', '**************************' ]; def print_map(map): for l in map: print l def print_route(route): for l in route: print "".join(l) # mapから、'S'または'G'の位置を探して返す.無かったらNoneが返る def getLoc(map,SorG): t=0 for l in map: s=0 for n in l: if n == SorG: return (t,s) s=s+1 t=t+1 def search(map): s = getLoc(map,'S') # mapからSの位置を探す print 'スタート地点:'+str(s) if s == None: print 'スタート地点Sがないので、道はありません.' else: # s から'G'までの最短距離を返す search_from_s(map,s) # s から'G'までの最短距離を返す def search_from_s(map,s): mapi = len(map) mapj = len(map[0]) # distanceは、Sから(t,s)までの仮の最短距離を保存する distance=[[None for j in xrange(mapj)] for i in xrange(mapi)] distance[s[0]][s[1]]=0 #スタート地点は距離0 next=[(s,0)] #探索位置とその位置までのそのルートでの最短距離を保存するリスト型キュー while len(next) != 0: n = next.pop(0) a = n[0] # 探索位置 dis_a = n[1] # Sからa までの距離 # aの上下左右を見る. if 0<=a[0]-1 : # 上 next_a(a[0]-1,a[1],dis_a,map,distance,next) if a[0]+1<mapi : #下 next_a(a[0]+1,a[1],dis_a,map,distance,next) if 0<=a[1]-1 : #左 next_a(a[0],a[1]-1,dis_a,map,distance,next) if a[1]+1<mapj : #右 next_a(a[0],a[1]+1,dis_a,map,distance,next) #結果出力。ついでにGの位置も出力 g=getLoc(map,'G') print 'ゴール地点:'+str(g) print '最短距離:'+str(distance[g[0]][g[1]]) #SからGまでの最短経路を出力する search_route(map,distance) #aの上下左右を見る.壁(*)だったら何もしない. #壁でなければdistanceのその位置と同じ位置を見て、 #保存されている距離がdis_a+1よりも小さければ何もしない. #大きいか距離が保存されていなかったら、dis_a+1で置き換える #"G"だったら、dis_a+1を返し、探索終了. #"G"でなければ、nextにその位置とdis_a+1を保存する. def next_a(i,j,dis_a,map,distance,next): if map[i][j] == '*': return if distance[i][j] == None: distance[i][j]=dis_a+1 if map[i][j] != 'G': next.append(((i,j),dis_a+1)) else: del next[:] else: if distance[i][j] < dis_a+1: return else: distance[i][j] = dis_a+1 if map[i][j] != 'G': next.append(((i,j),dis_a+1)) else: del next [:] #distanceを辿って、最短経路をmap上に、$で書くだけ。 #最短経路がいくつもあれば、そのうちの一個だけ示す def search_route(map,distance): mapi = len(map) mapj = len(map[0]) route=[] for i in range(mapi): lst=[] for j in range(mapj): lst.append(map[i][j]) route.append(lst) s=getLoc(map,'S') g=getLoc(map,'G') a=g dis=distance[g[0]][g[1]] while s[0]!=a[0] or s[1]!=a[1]: dis=dis-1 if 0<=a[0]-1: # 上 if(distance[a[0]-1][a[1]]==dis): route[a[0]-1][a[1]]='$' a=(a[0]-1,a[1]) continue if a[0]+1<mapi : #下 if(distance[a[0]+1][a[1]]==dis): route[a[0]+1][a[1]]='$' a=(a[0]+1,a[1]) continue if 0<=a[1]-1 : #左 if(distance[a[0]][a[1]-1]==dis): route[a[0]][a[1]-1]='$' a=(a[0],a[1]-1) continue if a[1]+1<mapj : #右 if(distance[a[0]][a[1]+1]==dis): route[a[0]][a[1]+1]='$' a=(a[0],a[1]+1) route[s[0]][s[1]]='S' print_route(route) # 迷路を示す配列を渡すとSからGまでの最短距離を返す search(map)
ここまで作ってから気付いたんですが,真面目に解くなら,ファイルを読み込んでないと間違いだ...まぁ..mapは最初からリスト型にしておいたほうが良さそうとか、もっとシンプルに書けるところはあるなとかありますが、今回はPythonで書けて動いたので良し.