Pythonで幅優先探索で迷路を解き、経路を全て表示したい

Question

Pythonで迷路を幅優先探索で解き、全ての最短をルートを表示したいのですが、
最短距離をリストに格納するところまでは出来たのですがそれを元に
ルートを表示するところ(コード内のsearch_route関数)が上手く動作しません。
参考にしたサイト

具体的には次のようなマップな場合、(S:スタート G:ゴール $:ルート *:壁)

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

以下のように2つのルートを表示させたいのですが、

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

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

コードを実行すると、次の様に2個目のルートに1つ目のルートが重なって表示されます。

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

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

以下のコードのsearch_route関数の部分をどのように直せばよいでしょうか？

map = [
    '*****',
    '*   *',
    '*S*G*',
    '*   *',
    '*****'
    ];


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)
        return 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 range(mapj)] for i in range(mapi)]
    distance[s[0]][s[1]]=0 #スタート地点は距離０
    next.append((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]]))
    return 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:
        # 元のコード distance[i][j] < dis_a+1 となっていたが、距離が同じなら調べる必要は無い
        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 [:]

# nextをグローバル変数にしないと、next [:] と while len(next) != 0:
# が意味をなさず、ゴールに来ても他の探索ルートが探索を止めない。

"""
map:マップ
distance:スタートからの距離を記したリスト
route:ゴールからの探索ルートに＄を記したもの
dis:スタート、ゴール間の最短距離から1ずつ引いた値
s:スタートの座標
g:ゴールの座標
a:探索している座標
"""
def search_route(map, distance, route, dis, s, g, a):
    route = route.copy()
    a = a.copy()

    if a == s:
      # スタートとゴールも＄になっているので、SとGで上書き
      route[s[0]][s[1]]='S'  
      route[g[0]][g[1]]="G"

      print_route(route)
      print()
      
    # 枠外に行くと終了  
    if a[0]>=mapi or a[0]<0 or a[1]<0 or a[1]>=mapj:
      return 
    
    # 最短ルートでないと終了
    if distance[a[0]][a[1]]!=dis:
      return

    if distance[a[0]][a[1]]==dis:
      route[a[0]][a[1]]='$'

    dis=dis-1
     
    search_route(map,distance, route, dis,s, g, [a[0]+1,a[1]])
    search_route(map,distance, route, dis,s, g, [a[0]-1,a[1]])
    search_route(map,distance, route, dis,s, g, [a[0],a[1]-1])
    search_route(map,distance, route, dis,s, g, [a[0],a[1]+1])


next = []
# 迷路を示す配列を渡すとSからGまでの最短距離を返す
distance = search(map)

mapi = len(map)
mapj = len(map[0])

route = []

for i in range(mapi):
    lst=[]
    for j in range(mapj):
        lst.append(map[i][j])
    # print(lst)
    route.append(lst)

s=getLoc(map,'S')
s = list(s)
g=getLoc(map,'G')
g = list(g)
a=g

dis=distance[g[0]][g[1]]

search_route(map,distance, route, dis, s, g, a)

Comments

[meg_]

｢最短距離をリストに格納するところまでは出来た｣とのことですが、コードのどの部分で確認できましたか？

Answer 1

    route = route.copy()
    a = a.copy()

ここで「浅いコピー」を行っているからです。
二次元リストの複製を行いたい場合、「深いコピー」を行う必要があります。

「python deepcopy」等で検索してみてください。

なお、アルゴリズムの確認はしていません。

Comments

[pyxis]

ありがとうございました！
deepcopyすることにより別々のルートを表示できるようになりました。