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

深さ優先探索を実際にpythonでプログラミングしていきます。

重要な部分をピックアップしつつ解説していきます。

初めて深さ優先探索をプログラミングする人でも、わかりやすく理解できるものを目指します！

深さ優先探索のアルゴリズム
事前準備
プログラムを作成していこう！
プログラムの完成形！
まとめ

深さ優先探索のアルゴリズム

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

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

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

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

こちらのアルゴリズムを参考にしながら作成していきましょう。

事前準備

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

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

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

こちらの迷路は幅優先探索でも使っていますので、違う探索ではどうなるのか比較したい場合は以下を参考にしてください。

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

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

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

プログラムを作成していこう！

まずは探索する迷路を作成していきます！

配列を使うことで迷路を実装していきます。

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

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

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

「s」にはオープンリストの先頭である一番最近に入れたものを代入します。

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

プログラムの完成形！

これまでのプログラムをまとめましょう。

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:
    t=len(openlist)-1
    s=openlist[t]
    closelist.append(s)
    if s==[7,7]:
        b=1
    else:
        x=s[0]
        y=s[1]
        a[x,y]=1
        openlist.pop(-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」を表示させて、探索した順番をみていきましょう。