[Python] 幅優先探索で迷路を解く

幅優先探索

幅優先探索（Breadth First Search）とは、グラフを始点から近い順に1つずつ調べていく探索法です。キューを使うことにより、FIFOで全てを探索するというイメージで理解しています。

wikipedia 幅優先探索

迷路の幅優先探索、また深さ優先探索については、以下の資料が大変分かりやすいです。

京都産業大学　発展プログラミング演習I　演習資料迷路の経路探索

アルゴリズム

根ノードを空のキューに加える。
ノードをキューの先頭から取り出し、以下の処理を行う。
- ノードが探索対象であれば、探索をやめ結果を返す。
- そうでない場合、ノードの子で未探索のものを全てキューに追加する。
もしキューが空ならば、グラフ内の全てのノードに対して処理が行われたので、探索をやめ”not found”と結果を返す。
2に戻る。

ノードの展開により得られる子ノードはキューに追加される。訪問済みの管理は配列やセットなどでも行える。

迷路にアルゴリズムを当てはめる

スタート地点を空のキューに加える。
現在地をキューの先頭から取り出し、以下の処理を行う。
- 現在地がゴールであれば、探索をやめ結果を返す。
- そうでない場合、現在地の上下左右、未探索かつ通路を全てキューに追加する。
もしキューが空ならば、全ての通路を通ったがゴールにたどり着けなかったということなので、探索をやめ”ゴールが見つかりませんでした。”と結果を返す。今回は必ずゴールが見つかる迷路とする。
2に戻る。

今回は、未探索の地点をカウントアップしていくことで最短経路も求める。

pythonで実装

pythonには、queueを取り扱うのに便利なdeque オブジェクトがあるので、こちらを使います。

Python チュートリアルリストをキューとして使う

Python 標準ライブラリdeque オブジェクト

from collections import deque

import colorama
import termcolor

import maze

PATH = 0
WALL = 1

width = 29
height = 29

# 迷路の配列を作成する。
# 壁1、通路0、スタート[1, 1]、ゴール[height-1, widht-1]として、
# 迷路をランダムに作成して二次元のリストを返す。
maze = maze.MazeByMakingWall(width, height).make_maze()

# 地図上の未訪問地点を-1とする。
# また、移動するごとに+1することで、スタート地点からの移動距離を保持する。
distance_visited = list() 
for x in range(height):
    distance_visited.append([-1] * width)

# スタート地点を登録する。
queue = deque([[1, 1]])
distance_visited[1][1] = 0

while True:
    x, y = queue.popleft()
    # ゴールの場合は終了する。
    if maze[x][y] == 'G':
        goal_x, goal_y = x, y
        break
    # 現在地点の上下左右のマスを確認する。
    for i, j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
        new_x, new_y = x + i, y + j
        # それぞれのマスが移動できる場合、かつまだ移動したことが無い場合
        if maze[new_x][new_y] != WALL and distance_visited[new_x][new_y] == -1:
            # そのマスのスタートからの移動距離を設定し、またキューに登録する。
            distance_visited[new_x][new_y] = distance_visited[x][y] + 1
            queue.append([new_x, new_y])


# ゴールからスタートまでのルートをゴールから逆算する。
route = list()
route.append([goal_x, goal_y])
while True:
    x, y = route[-1]
    distance = distance_visited[x][y]
    if distance == 0:
        break
    for i, j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
        before_x, before_y = x + i, y + j
        if distance_visited[before_x][before_y] == distance-1:
            route.append([before_x, before_y])
            break

for x, y in route:
    if maze[x][y] == 'S' or maze[x][y] == 'G':
        continue
    else:
        maze[x][y] = 'R'

# 色付きで出力する。
colorama.init()
for row in maze:
    for cell in row:
        if cell == PATH:
            print('   ', end='')
        elif cell == WALL:
            print(termcolor.colored('   ', 'green', 'on_green'), end='')
        elif cell == 'R':
            print(termcolor.colored('   ', 'yellow', 'on_yellow'), end='')
        elif cell == 'S':
            print(termcolor.colored('STA', 'red'), end='')
        elif cell == 'G':
            print(termcolor.colored('GOA', 'red'), end='')
    print()