幅優先探索をpythonで実装してみよう！

幅優先探索をpythonで実際にプログラミングしていきたいと思います。

重要な部分をピックアップしながら解説していきます！

初心者でもわかりやすく理解できるものを目標としています！！

幅優先探索のアルゴリズム
事前準備
プログラムを作成！
プログラムの完成形！
まとめ

幅優先探索のアルゴリズム

まず簡単に、幅優先探索のアルゴリズムについて確認していきます。

初期状態をオープンリストに入れる。
オープンリストが空でない間、以下[3~5]を実行する。
オープンリストから先頭の要素aを取り出す。クローズドリストにaを追加することで参照をする。
aが目標状態であれば達成したということで終了する。
aから接続していて、まだ追加していない状態を全てオープンリストの末尾に追加する。

幅優先探索について復習したい方はこちら！

幅優先探索(BFS)とは？わかりやすく図を用いて解説！

このアルゴリズムを元にプログラムを作っていきましょう！！

事前準備

今回は定番の「迷路を探索する」ことを想定したプログラムを作っていきます。

迷路は見やすく、簡単すぎない程度の大きさである9×9マスにします。

左上の白い枠をスタート地点として、ゴールである右下を探索することができたら終了とします。

プログラムでは、座標を指定することでどの位置を探索しているのかをわかるようにします。

また、通れる道とそうでない道の区別を座標に数値を入れることで判断できるようにします。

プログラムを作成！

それでは早速プログラムを作成していきます！

まずは、探索する迷路を決めます。

先ほどの図にある迷路を配列として作ります。

import numpy as np
a=np.array([[1,1,1,1,1,1,1,1,1],
            [1,0,1,1,1,0,1,1,1],
            [1,0,0,0,0,0,1,0,1],
            [1,0,1,1,1,0,1,1,1],
            [1,0,1,1,1,0,0,0,1],
            [1,0,1,1,1,1,1,1,1],
            [1,0,1,0,0,0,1,1,1],
            [1,0,0,0,1,0,0,0,1],
            [1,1,1,1,1,1,1,1,1]])

スタート地点が配列aの(1,1)にくるようにします。

通れないエリアを数字の「１」を入れ、通れるエリアを「0」としました。

（数字にしたのは後の処理で代入するのを楽にするためです。）

次は探索する方法を考えます。

何度も参照を行うことから繰り返し文を使う方が楽だとわかります。

ただし、一度参照した場所は参照できないようにする必要があることに注意します。

その結果、「while文」を利用して何度も処理を行うことにしました。

また「0」である場所を参照する条件にした場合、参照したときにその場所を「１」に変えればこれ以上参照されることがなくなります。

while b==0:
    s=openlist.pop(0)
    closelist.append(s)
    if s==[7,7]:
        b=1
    else:
        x=s[0]
        y=s[1]
        a[x,y]=1
        if a[x-1,y]==0:#上
            openlist.append([x-1,y])
        if a[x,y-1]==0:#左
            openlist.append([x,y-1])
        if a[x+1,y]==0:#下
            openlist.append([x+1,y])
        if a[x,y+1]==0:#右
            openlist.append([x,y+1])
#分かれ道は右が一番最後、次に下、左、上

コメントに書いてあるように、参照する順番を同時にすることはできないので、

今回は、左と右にいけた場合は先に左を参照することとします。

最後は「b」の変数や「openlist」と勝手に書いたリストを宣言すれば完成です。

プログラムの完成形！

先ほど考えて書いたプログラムをまとめると以下になります。

import matplotlib.pyplot as plt
import numpy as np
a=np.array([[1,1,1,1,1,1,1,1,1],
 [1,0,1,1,1,0,1,1,1],
 [1,0,0,0,0,0,1,0,1],
 [1,0,1,1,1,0,1,1,1],
 [1,0,1,1,1,0,0,0,1],
 [1,0,1,1,1,1,1,1,1],
 [1,0,1,0,0,0,1,1,1],
 [1,0,0,0,1,0,0,0,1],
 [1,1,1,1,1,1,1,1,1]])

b=0
x=1
y=1

openlist=list()
closelist=list()
openlist.append([x,y])

while b==0:
    s=openlist.pop(0)
    closelist.append(s)
    if s==[7,7]:
        b=1
    else:
        x=s[0]
        y=s[1]
        a[x,y]=1
        if a[x-1,y]==0:#上
            openlist.append([x-1,y])
        if a[x,y-1]==0:#左
            openlist.append([x,y-1])
        if a[x+1,y]==0:#下
            openlist.append([x+1,y])
        if a[x,y+1]==0:#右
            openlist.append([x,y+1])
#分かれ道は右が一番優先、次に下、左、上

これで完成しましたが、うまくできているか確認しておきましょう。

「closelist」に探索した座標が順番に入っているので表示させてみます。