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

深さ優先探索

深さ優先探索（Depth First Search）は、グラフを始点から一番奥の末端まで一直線に調べて、答えが見つからない場合、今度は一番近い分かれ道に戻ってまた一番奥まで…、を繰り返す探索方法です。幅優先探索では、キューを使ったFIFOで探索を行いましたが、深さ優先探索では、スタックを使ったLIFOで探索を行います。

wikipedia 深さ優先探索

図でイメージすると分かりやすいですが、深さ優先探索は、一番深い階層まで一直線に潜ってしまうので、答えがいくつかある場合は、最初に見つかった答えが最短経路ではない可能性があります。

幅優先探索では、まずは水平方向に調べて、見つからない場合さらに一つ深い階層に潜ってその階層を水平方法に調べるので、答えがある場合は、必ず最短経路が見つかります。

以下の資料を参考にしています。

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

IKN Lab アルゴリズムとデータ構造木の巡回（なぞり）

競プロ覚書：深さ優先探索，幅優先探索まとめ

アルゴリズム

深さ優先探索は、以下のようなアルゴリズムになります。

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

幅優先探索のキューをスタックに変更するだけで、深さ優先探索になります。また、Pythonでは、リストを使うことで簡単にスタックを実現できます。

Python チュートリアルリストをスタックとして使う

今回は、再帰を使うことで、やることはスタックと同じなのですが、見た目がちょっと異なるように書きます。

Pythonで再帰を実装

import colorama
import termcolor

import maze

PATH = 0
WALL = 1
width = 29
height = 29

# mazeは、迷路の配列を作成する自作クラス。
# 壁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)


# ゴールを見つけたら処理を終えるためにフラグを置く。
found_goal = False
# 再帰関数　
# 何かを返すようにしないとnoneを返すため、
# 引数に空のリストを保持しゴールの座標を入れ常にreturnする。
def depth_first_search(x, y, count, ans=[]):
    global found_goal
    if found_goal:
        return ans
    # 座標xyを訪問済みにして、またスタートからの距離を保持する
    count += 1
    distance_visited[x][y] += count
    if maze[x][y] == 'G':
        found_goal = True
        ans = [x, y]
        return ans
    else:
        # 座標xyから上下左右に移動できる、かつまだ訪問済みでない。
        for i, j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            if found_goal:
                break
            else:
                new_x, new_y = x + i, y + j
                if maze[new_x][new_y] != WALL: 
                    if distance_visited[new_x][new_y] == -1:
                        ans = depth_first_search(new_x, new_y, count, ans=[])
    return ans
            

goal = depth_first_search(1, 1, 0)


# ゴールからスタートまでのルートをゴールから逆算する。
route = list()
route.append(goal)
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()