深さ優先探索・幅優先探索を使って、迷路を解きます。
今回使った迷路は、2次元配列で、壁が「#」、通路を「スペース」としたものです。
結果は次のようになりました。
このページで使った「スタック」、「キュー」、各探索の概要は前回触れているのでそちちを参照してください。
参考にしたページ
[Qiita]BFS (幅優先探索) 超入門！ 〜 キューを鮮やかに使いこなす 〜
Androidアプリを作成しました。
感情用のメモ帳です。
準備
実際に迷路を解く前に必要なものを準備します。
from collections import deque
from copy import deepcopy
maze = ['#################',
'# # # G',
'# # ### # # ### #',
'# # # # # # # #',
'# ### # # # # # #',
'# # # # # # # #',
'##### # # # # # #',
'# # # # #',
'# ####### # ### #',
'# # # # #',
'# # ####### # # #',
'# # # # # # #',
'# ### ### # # ###',
'S # # #',
'#################']
maze = [list(line) for line in maze]
WIDTH = 17
HEIGHT = 15
START = (13, 1)
GOAL = (1, 15)
def print_maze(maze_data, print_width=3):
for line in maze_data:
for char in line:
print(char.center(print_width), end='')
print()
キューを扱いたいので「deque」をインポート。
迷路のデータは文字列の入った1次元リストなので、list関数で変換して全体を2次元のリストにし、「maze」に再代入しました。
mazeの中で「'S'」の座標（ｙ軸, x軸）は、（13, 0）、「'G'」は（1, 16）ですが、変数に代入したスタートとゴールの座標は「START = (13, 1)」、「GOAL = (1, 15)」です。
print_maze関数の中で文字列のcenterメソッドを使い、出力のセンター寄せし、横幅が少し広がるようにしています。
設定しないとターミナルでは縦長で表示され、かなり見づらかったので。
設定しなかった場合。
################# # # # G # # ### # # ### # # # # # # # # # # ### # # # # # # # # # # # # # # ##### # # # # # # # # # # # # ####### # ### # # # # # # # # ####### # # # # # # # # # # # ### ### # # ### S # # # #################
設定した場合。
# # # # # # # # # # # # # # # # # # # # G # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # S # # # # # # # # # # # # # # # # # # # #
だいぶ見やすいです。
深さ優先探索
先に深さ優先探索をやります。
コードは前の項に追記した形です。
def dfsearch(maze_data):
maze = deepcopy(maze_data)
steps = 1
stack = [START]
while stack:
y, x = stack.pop()
maze[y][x] = str(steps)
if y == GOAL[0] and x == GOAL[1]:
break
for yi, xi in [(y, x-1), (y, x+1), (y-1, x), (y+1, x)]:
if maze[yi][xi] == ' ':
stack.append((yi, xi))
steps += 1
return maze
if __name__ == '__main__':
dfresult = dfsearch(maze)
print_maze(dfresult)
mazeの配列は幅優先探索でも使うので、標準ライブラリ「copy」のdeepcopyでデータを複製します。
[note.nkmk.me]Pythonの浅いコピーと深いコピー
ループの流れは、
- スタックから座標を取り出して現在地とし、迷路に歩数を書き込む
- もしその場所がゴール地点なら処理を抜ける
- 現在地から左、右、上、下のマスが「' '（半角スペース）」ならスタックに追加する
- 歩数の更新
迷路を直接書き換えているので、訪問済みかどうかの変数を用意する必要はありません。
ターミナルから実行してみましょう。
$ python3 maze_search.py # # # # # # # # # # # # # # # # # # 49 48 19 20 21 22 23 # 47 # 81 82 83 84 85 G # 50 # 18 # # # 24 # 46 # 80 # # # # # 51 # 17 16 15 # 25 # 45 # 79 # # # # 52 # # # 14 # 26 # 44 # 78 # # # # 53 54 55 # 13 # 27 # 43 # 77 # # # # # # # # 12 # 28 # 42 # 76 # # # # 7 8 9 10 11 # 29 30 31 # 75 # # # 6 # # # # # # # 32 # 74 # # # # # 5 # 39 38 37 36 35 34 33 # 73 # # # 4 # 40 # # # # # # # 72 # # # # 3 # 41 # 61 62 63 64 65 # 71 # # # # 2 # # # 60 # # # 66 # 70 # # # # S 1 56 57 58 59 # 67 68 69 # # # # # # # # # # # # # # # # # # #
この迷路は深さ優先探索で85歩かかりました。
幅優先探索
スタートからの距離を書き込み
次は幅優先探索です。
幅優先探索では最短経路が出せるので、mazeに探索した順を書き込むのではなく、スタート地点からの距離を書き込むようにします。
コードは前のコードに追記。
def bfsearch(maze_data):
maze = deepcopy(maze_data)
distance = [[-1]*WIDTH for _ in range(HEIGHT)]
distance[START[0]][START[1]] = 1
que = deque([START])
while que:
y, x = que.popleft()
maze[y][x] = str(distance[y][x])
if y == GOAL[0] and x == GOAL[1]:
break
for yi, xi in [(y, x-1), (y, x+1), (y-1, x), (y+1, x)]:
if maze[yi][xi] == ' ':
que.append((yi, xi))
distance[yi][xi] = distance[y][x] + 1
return maze
if __name__ == '__main__':
# dfresult = dfsearch(maze)
# print_maze(dfresult)
bfresult = bfsearch(maze)
print_maze(bfresult)
「distance」はmazeに対応し、スタート地点からの距離を保持させます。
すべてのマス目を「-1」で初期化し、スタート地点の座標のdistanceを「1」に設定。
ループの流れ
- キューから座標を取り出して現在地とし、迷路に直接距離を書き込む
- もしその場所がゴール地点なら処理を抜ける
- 現在地から左、右、上、下のマスが「' '」ならその座標をキューに追加
- その際、現在地のdistanceの値に1を足したものを、追加した座標のdistanceに書き込み
実行してみましょう。
$ python3 maze_search.py # # # # # # # # # # # # # # # # # # 21 20 19 20 21 22 23 # # 27 28 29 30 31 G # 22 # 18 # # # 24 # # 26 # # # # # 23 # 17 16 15 # 25 # # 25 # 27 # # # 24 # # # 14 # 26 # # 24 # 26 # # # 25 26 27 # 13 # 27 # # 23 # 25 # # # # # # # 12 # 28 # # 22 # 24 # # # 7 8 9 10 11 # 29 30 # 21 22 23 # # # 6 # # # # # # # # 20 # # # # # 5 # # 19 # # # 4 # # # # # # # # 18 # # # # 3 # # 7 8 9 10 11 # 17 # # # # 2 # # # 6 # # # 12 # 16 # # # # S 1 2 3 4 5 6 7 # 13 14 15 # # # # # # # # # # # # # # # # # # #
経路が分岐していますが、ちゃんとスタート地点からの距離になっています。
最短距離でいくと31歩でゴールですね。
最短経路の算出
bfsearch関数の結果を使い、ゴールから逆にたどっていって、最短経路を出すコードも書いてみました。
def shortest_distance(bfresult):
y, x = GOAL
count = int(bfresult[GOAL[0]][GOAL[1]])
shortest_list = [START, GOAL]
while count > 1:
count -= 1
for yi, xi in [(y, x-1), (y, x+1), (y-1, x), (y+1, x)]:
if bfresult[yi][xi] == str(count):
y, x = yi, xi
shortest_list.append((y, x))
break
maze_c = deepcopy(maze)
for yi, xi in shortest_list:
maze_c[yi][xi] = '.'
return maze_cリストにスタートとゴール座標を追加し、ゴールからカウントを逆にたどっていって、それぞれのカウントの座標を追加するものです。
最後にリストの座標のmazeを「'.'」に変換して返します。
$ python3 maze_search.py # # # # # # # # # # # # # # # # # # # # . . . . . G # # # # # # # . # # # # # # # # # . # # # # # # # # # # . # # # # # # # # . # # # # # # # # # # # . # # # # # # . # # # # # # # # # # # . # # # # # # # . # # # # # # # # # # # . # # # # # # . . . . . # . # # # # # # # . # # # . # . # # # # S . . . . . # . . . # # # # # # # # # # # # # # # # # # #
まとめ
これまでのコードをひとつにしたものです。
from collections import deque
from copy import deepcopy
maze = ['#################',
'# # # G',
'# # ### # # ### #',
'# # # # # # # #',
'# ### # # # # # #',
'# # # # # # # #',
'##### # # # # # #',
'# # # # #',
'# ####### # ### #',
'# # # # #',
'# # ####### # # #',
'# # # # # # #',
'# ### ### # # ###',
'S # # #',
'#################']
maze = [list(line) for line in maze]
WIDTH = 17
HEIGHT = 15
START = (13, 1)
GOAL = (1, 15)
def print_maze(maze_data, print_width=3):
for line in maze_data:
for char in line:
print(char.center(print_width), end='')
print()
def dfsearch(maze_data):
maze = deepcopy(maze_data)
steps = 1
stack = [START]
while stack:
y, x = stack.pop()
maze[y][x] = str(steps)
if y == GOAL[0] and x == GOAL[1]:
break
for yi, xi in [(y, x-1), (y, x+1), (y-1, x), (y+1, x)]:
if maze[yi][xi] == ' ':
stack.append((yi, xi))
steps += 1
return maze
def bfsearch(maze_data):
maze = deepcopy(maze_data)
distance = [[-1]*WIDTH for _ in range(HEIGHT)]
distance[START[0]][START[1]] = 1
que = deque([START])
while que:
y, x = que.popleft()
maze[y][x] = str(distance[y][x])
if y == GOAL[0] and x == GOAL[1]:
break
for yi, xi in [(y, x-1), (y, x+1), (y-1, x), (y+1, x)]:
if maze[yi][xi] == ' ':
que.append((yi, xi))
distance[yi][xi] = distance[y][x] + 1
return maze
def shortest_distance(bfresult):
y, x = GOAL
count = int(bfresult[GOAL[0]][GOAL[1]])
shortest_list = [START, GOAL]
while count > 1:
count -= 1
for yi, xi in [(y, x-1), (y, x+1), (y-1, x), (y+1, x)]:
if bfresult[yi][xi] == str(count):
y, x = yi, xi
shortest_list.append((y, x))
break
maze_c = deepcopy(maze)
for yi, xi in shortest_list:
maze_c[yi][xi] = '.'
return maze_c
if __name__ == '__main__':
# dfresult = dfsearch(maze)
bfresult = bfsearch(maze)
shresult = shortest_distance(bfresult)
# print_maze(maze)
# print_maze(dfresult)
# print_maze(bfresult)
print_maze(shresult)
他の迷路を使って実行した結果はこんな感じになりました。
実は探索をやるより前に、迷路を自動生成するコードを書いていたので、次はこっちをやっていこうかと思います。
迷路の生成と攻略を行うWebページを作成しました。
内部処理はRust。攻略に使ったアルゴリズムはこのページのものと同様です。