queueを用いた幅優先探索を今更実装・比較してみた

少しずつアルゴリズムとデータ構造の勉強をしていきます。
以前もやっていたのですが、割とテキトーに勉強していたので理解したところをきちんとアウトプットしていきます。
学問的にきちんと学んだわけではないので、雑なところもあるとは思いますがそこはご了承ください。

幅優先探索(BFS)

幅優先探索とは

wiki より引用

幅優先探索（はばゆうせんたんさく、英: breadth first search）はグラフ理論(Graph theory)において木構造(tree structure)やグラフ(graph)の探索に用いられるアルゴリズム。アルゴリズムは根ノードで始まり隣接した全てのノードを探索する。それからこれらの最も近いノードのそれぞれに対して同様のことを繰り返して探索対象ノードをみつける。「横型探索」とも言われる。

幅優先探索は解を探すために、グラフの全てのノードを網羅的に展開・検査する。最良優先探索とは異なり、ノード探索にヒューリスティクスを使わずに、グラフ全体を目的のノードがみつかるまで、目的のノードに接近しているかどうかなどは考慮せず探索する。

イメージは水を流すイメージでしょうか。まぁ幅優先探索の動き方？に関してはたくさん画像などが落ちてますので、このアルゴリズムがどのように動くか、というのはすぐにご確認いただけるかと思います。

queueとは

wiki より引用

キュー（英: queue）あるいは待ち行列は、コンピュータにおける基本的なデータ構造の一つ。データを先入れ先出し[1]のリスト構造で保持するものである。キューからデータを取り出すときには、先に入れられたデータから順に取り出される。キューにデータを入れることをエンキュー[2]、取り出すことをデキュー[3]という。

プリンターへの出力処理や、ウィンドウシステムにおけるイベントあるいはメッセージのハンドリング、プロセスの管理など、データを入力された順番通りに処理する必要があるケースに用いられる。また、個々のタスクの実行時間が予測できない、あるいは実行に時間がかかってしまい、即座に（同期的に）実行することができない場合、キューを使っていったんタスクを溜め込んでおき、後からタスクを取り出して非同期で実行する、というような目的で使用できる。

キューの変形として、先頭と末尾の両端から入出力を行えるものを両端キュー[4]という。

キューとは逆に後入れ先出し[5]のリスト構造を持つデータバッファをスタックと呼ぶ。

プログラミング言語によっては、キューを標準ライブラリとして実装していて、プログラマがキューそのもののプログラムを書かなくても利用できるようになっている。標準ライブラリとして用意されていない場合であっても、他のデータ構造、例えばリンクリストをキューと見立てて利用することも多い。

さて、早速次の迷路探索をするコードの実装に移ります。
左上から右下のゴールまでの最短経路を見つける問題を考えます。

S#...
...#.
.#...
..##G

まずqueueを用いない愚直な方法から。

bfs_notqueue.py

x = 0
y = 0
board = [['S','#','.','.','.'],
         ['.','.','.','#','.'],
         ['.','#','.','.','.'],
         ['.','.','#','#','G']]
#boardのサイズ
h = len(board)
w = len(board[0])

#boardのスタート地点を0に初期化します。
board[y][x] = 0

#移動可能な方向をチェックするためのリストを用意します。
d = [(1, 0), (-1, 0), (0, 1), (0, -1)]


def BFS(board):
    #cを探して、cが見つかればその周りをc+1で可能な限り埋めていくという形です。
    c = 0
    
    #Gが見つかるまで探索します。
    while True:
        for i in range(h):
            for j in range(w):
                if board[i][j] == c:
                    #4方向についてチェックします。
                    for dx, dy in d:
                        
                        #枠外判定
                        if i+dy >= h or i+dy < 0 or j+dx >= w or j+dx < 0:
                            continue
                        
                        #Gが見つかれば、終わりです。
                        if board[i+dy][j+dx] == 'G':
                            board[i+dy][j+dx] = c+1
                            return c + 1
                        
                        #数字または＃(壁)でないかをチェックします。
                        if board[i+dy][j+dx] != '.':
                            continue
                        
                        #上記のいずれでもない場合、c+1で埋めます。
                        board[i+dy][j+dx] = c + 1
        
        #一通り見終わったら次の数字へ
        c += 1
                        
                   
print(BFS(board))
for b in board:                        
    print(b) 
    

result

7
[0, '#', 4, 5, 6]
[1, 2, 3, '#', 7]
[2, '#', 4, 5, 6]
[3, 4, '#', '#', 7]

queueを用いない場合は、例えば上記のように何回も盤面を走査してあげる必要があります。
(queueを使っていない実装を見つけられなかったので、もしかしたらここまでひどくはならないものも存在するかもですが。)
一方でqueueを用いた場合、queueに探索したい場所(インデックス)をenqueまたはdequeしてあげることで、ピンポイントで探索を行い続けることができます。

queue_bfs.py

x = 0
y = 0
board = [['S','#','.','.','.'],
         ['.','.','.','#','.'],
         ['.','#','.','.','.'],
         ['.','.','#','#','G']]
#boardのサイズ
h = len(board)
w = len(board[0])

#boardのスタート地点を0に初期化します。
board[y][x] = 0

#移動可能な方向をチェックするためのリストを用意します。
d = [(1, 0), (-1, 0), (0, 1), (0, -1)]
queue = []

#queueとboardを初期化します
for dx, dy in d:
                        
    #枠外判定
    if y+dy >= h or y+dy < 0 or x+dx >= w or x+dx < 0:
        continue
    #数字または＃(壁)でないかをチェックします。
    if board[y+dy][x+dx] != '.':
        continue
                        
    #上記のいずれでもない場合、今の数字+1で埋めます
    board[y+dy][x+dx] = board[y][x] + 1
    queue.append((y+dy, x+dx))

def BFS(board):         
    #探索する場所がなくなるまで(＝queueの要素がなくなるまで)探索します。
    while queue:
        y, x = queue.pop(0)
        #4方向についてチェックします。
        for dx, dy in d:
                        
            #枠外判定
            if y+dy >= h or y+dy < 0 or x+dx >= w or x+dx < 0:
                continue
                        
            #Gが見つかれば、終わりです。
            if board[y+dy][x+dx] == 'G':
                board[y+dy][x+dx] = board[y][x]+1
                return board[y][x] + 1
                        
            #数字または＃(壁)でないかをチェックします。
            if board[y+dy][x+dx] != '.':
                continue
                        
            #上記のいずれでもない場合、今の場所の数字+1で埋めます
            board[y+dy][x+dx] = board[y][x]+1
        
            #queueに新しい場所を追加します
            queue.append((y+dy, x+dx)) 
                   
print(BFS(board))
for b in board:                        
    print(b) 

とりあえず、自分のための備忘録的な文章ですがこんな感じで理解しました。
何か間違い等あれば教えていただけると幸いです。