幅優先、深さ優先(再帰あり&再帰無し)探索

いろんなところで使えそうなアルゴリズム
アルゴリズムの説明についてはせずに、単純にコードなどを書き記しておきます。
使用言語はPython3.10. match文を使います。

準備

import sys
sys.setrecursionlimit(10**6)
from collections import deque

迷路作成

開く

class Position:
    EMPTY = '.'
    BLOCK = '#'
    GOAL = 'G'
    START = 'S'
    CHECKED = 'o'

maze = """
    ############
    S.#...###..#
    #...#.#.#.##
    #.#.#...#.##
    ###.#.#.#.##
    #...###...##
    #.#.#...#.##
    ###.#.#.####
    #...#.###..G
    ###.#...#.##
    #...###.#.##
    ##.####...##
    ############
    """

def maze2list() -> list[list[str]]:
    return [list(line) for line in maze.split()]

def colored_maze(maze: list[list[str]]) -> str:
    colored_maze = ''
    for row in maze:
        colored_row = ''
        for cell in row:
            match cell:
                case Position.EMPTY:
                    c = f'\033[38;5;010m{cell}\033[0m'
                case Position.BLOCK:
                    c = f'\033[38;5;009m{cell}\033[0m'
                case Position.GOAL:
                    c = f'\033[38;5;011m{cell}\033[0m'
                case Position.START:
                    c = f'\033[38;5;012m{cell}\033[0m'
                case Position.CHECKED:
                    c = f'\033[38;5;014m{cell}\033[0m'
                case _:
                    c = str(cell)
            colored_row += c
        colored_row += '\n'
        colored_maze += colored_row
    return colored_maze

幅優先(Breadth First Search: BFS)

キューが空になるまでループを回す。
戻り値はゴールまでの経路のリストが入っている。

def bfs(maze: list[list[str]], start: list|tuple) -> list[list[int]]:
    # [position(y,x), [path(y,x)], counts]
    q = deque([[start, [list(start)], 0]])
    while q:
        p = q.popleft()
        y, x = p[0] # position(y,x)
        count = p[-1] # counts
        
        if maze[y][x] == Position.GOAL:
            print("DFS: found goal in {} steps".format(count))
            return p[1]

        maze[y][x] = Position.CHECKED
        pblock = [
            [y - 1, x],
            [y + 1, x],
            [y, x - 1],
            [y, x + 1]]
        for pb in pblock:
            # current position is outside of maze or is a block or is already checked
            if (
                not (0 <= pb[0] < len(maze)) or
                not (0 <= pb[1] < len(maze[0])) or
                maze[pb[0]][pb[1]] == Position.BLOCK or
                maze[pb[0]][pb[1]] == Position.CHECKED):
                continue
            # append to last element of queue
            q.append([pb, p[1] + [pb], count+1])
m = maze2list()
print(bfs(m, (1,0)))
print(colored_maze(m))

BFS: found goal in 59 steps
[[1, 0], [1, 1], [2, 1], [2, 2], [2, 3], [1, 3], [1, 4], [1, 5], [2, 5], [3, 5], [3, 6], [3, 7], [4, 7], [5, 7], [6, 7], [6, 6], [6, 5], [7, 5], [8, 5], [9, 5], [9, 6], [9, 7], [10, 7], [11, 7], [11, 8], [11, 9], [10, 9], [9, 9], [8, 9], [8, 10], [8, 11]]
############
oo#ooo###oo#
#ooo#o#o#o##
#o#o#ooo#o##
###o#o#o#o##
#ooo###ooo##
#o#o#ooo#o##
###o#o#o####
#ooo#o###ooG
###o#ooo#o##
#ooo###o#o##
##o####ooo##
############

深さ優先(Depth First Search: DFS)

再帰使う場合と使わない場合とで紹介。

再帰

実際に使う際は、sys.setrecursionlimitを大きな数に設定しておくこと。

GOAL = False
def dfs_recursive(maze: list[list], start: list, path: list, count: int):
    global GOAL
    if GOAL:
        return
    y, x = start
    if (
        not (0 <= y < len(maze)) or
        not (0 <= x < len(maze[0])) or
        maze[y][x] == Position.BLOCK or
        maze[y][x] == Position.CHECKED):
        return
    if maze[y][x] == Position.GOAL:
        print("DFS: found goal in {} steps".format(count))
        GOAL = True
        return path
    
    maze[y][x] = Position.CHECKED
    p = dfs_recursive(maze, (y-1, x), path + [[y-1,x]], count + 1)
    p = p or dfs_recursive(maze, (y+1, x), path + [[y+1,x]], count + 1)
    p = p or dfs_recursive(maze, (y, x-1), path + [[y,x-1]], count + 1)
    p = p or dfs_recursive(maze, (y, x+1), path + [[y,x+1]], count + 1)
    return p

m = maze2list()
print(dfs_recursive(m, (1,0), [[1,0]], 0))
print(colored_maze(m))

非再帰

BFSのコードと違う点は、while内のfor文で回す要素の順序とappendleftを使う点。逆順に回すこととで、先頭から[y-1,x], [y+1,x],[y,x-1],[y,x+1]とqに追加される。そうすることで、深さ順にどんどん追加されていくようになる。

def dfs(maze: list[list[str]], start: list|tuple) -> list[list[int]]:
    # [position(y,x), [path(y,x)], counts]
    q = deque([[start, [list(start)], 0]])
    while q:
        p = q.popleft()
        y, x = p[0] # position(y,x)
        count = p[-1] # counts
        
        if maze[y][x] == Position.GOAL:
            print("DFS: found goal in {} steps".format(count))
            return p[1]

        maze[y][x] = Position.CHECKED
        pblock = [
            [y - 1, x],
            [y + 1, x],
            [y, x - 1],
            [y, x + 1]]
        for pb in reversed(pblock):
            if (
                not (0 <= pb[0] < len(maze)) or
                not (0 <= pb[0] < len(maze[0])) or
                maze[pb[0]][pb[1]] == Position.BLOCK or
                maze[pb[0]][pb[1]] == Position.CHECKED):
                continue
            q.appendleft([pb, p[1] + [pb], count+1])

m = maze2list()
print(dfs(m, (1,0)))
print(colored_maze(m))

DFS: found goal in 30 steps
[[1, 0], [1, 1], [2, 1], [2, 2], [2, 3], [1, 3], [1, 4], [1, 5], [2, 5], [3, 5], [3, 6], [3, 7], [4, 7], [5, 7], [6, 7], [6, 6], [6, 5], [7, 5], [8, 5], [9, 5], [9, 6], [9, 7], [10, 7], [11, 7], [11, 8], [11, 9], [10, 9], [9, 9], [8, 9], [8, 10], [8, 11]]
############
oo#ooo###..#
#ooo#o#o#.##
#o#.#ooo#.##
###.#o#o#.##
#...###o..##
#.#.#ooo#.##
###.#o#o####
#...#o###ooG
###.#ooo#o##
#...###o#o##
##.####ooo##
############