深さ優先探索とは、全探索アルゴリズムの一種です。木などのグラフやグラフと同一視できるものを探索する際に良く使われます。幅優先探索(BFS)と似ていますが、深さ優先探索は末端に到達するまで「深く」探索してから、他のノードの探索を始めます。DFSと略されることが多いです。DFSの状態遷移の順番アルゴリズム深さ優先探索は、「とりあえずこれ以上進めなくなるまで探索したら、戻って別のルートで探索し直す」ようなアルゴリズムです。再帰関数を用いた方法があります。深さ優先探索ではスタックを用いて実装することができます(類似のアルゴリズムに幅優先探索がありますが、これはキューを用いて実装できます)。今まで通った場所をスタックに保存しながら進み、末端に到達したらスタックからどこに戻るかの情報を取出します。一つの方法として、再帰関数を用いるやり方もあります。再帰関数を用いた全探索も、深さ優先探索の一種です。コンピュータ内部で関数を使う際に、スタックにデータを保存しておくため、このような動作になります。スタックを用いると幅優先探索と同様に書けるというメリットがあり、逆に再帰関数を用いると簡単に実装することができるというメリットがあります。状況に合わせて、もしくは自分の好みで、どちらで実装するかを決めれば良いでしょう。スタックを用いたアルゴリズム始めの状態から遷移可能な状態を、全てスタックに入れるスタックに要素がなければ終了する現在の状態から遷移可能な状態を、全てスタックに入れるスタックから1つ要素を取り出し、そこに状態を遷移させる2.に戻る幅優先探索のアルゴリズムのうち、キューをスタックに変更しただけで実装できます。途中の状態は以下のようになります。再帰関数を用いたアルゴリズム再帰関数を用いて深さ優先探索を実装できます。遷移可能な状態の個数分だけ、再帰関数を呼出して分岐させていきます。プログラムは上から下へ実行されるため、再帰関数の呼び出され方がスタックを用いた時と同じ様になります。遷移可能な状態が無くなる(末端)まで、戻って別のノードを探索することはありません。先程の図でいうと、状態1の時には、「状態2へ分岐する再帰関数」と「状態5へ分岐する再帰関数」を呼び出します。プログラムは上から下へ実行されるので、「状態2へ分岐する再帰関数」が先に実行され、これが終了するまで「状態5へ分岐する再帰関数」が呼び出されることはありません。具体例で試してみる以下のようなグラフについて深さ優先探索をしてみましょう。「OK」、たどり着けなければ「NO」を返すプログラムを幅優先探索で実装します。隣接行列・隣接リスト(グラフを参照)のどちらでグラフを表現するのか、スタック・再帰関数のどちらで深さ優先探索を実装するのかで、やり方が色々と変わってきます。隣接行列・スタックを用いた実装は以下のようになります。print("NO")出力は以下のようになります。隣接リスト表現を用いて、スタックで実装すると以下のようになります。0;}出力は先程と同じです。隣接リスト・再帰関数を用いたC++での実装例は以下のようになります。)で構成されたH行W列のマスについて、スタートから壁を通らずにゴールまでたどりつけるか判定してください。考え方スタートから深さ優先探索をすると、ゴールに到達するか判定することができます。グラフではなく、マス目でできた迷路上の探索なので、先程の例とプログラムの書き方が少し違いますが、基本的なアルゴリズムの考え方は変わりません。隣り合うマス目を、再帰関数で探索してください。このとき、既に探索したことのあるマス目は探索しないようにしないと、無限ループに陥ってしまいます。再帰関数での例を以下に示します。スタックを用いることでも同様に探索することができます。線形なデータ構造の1つです。...順列(n!)の全探索\(n!\)通りの全探索を行いたい時に順列が用いられます。コメントをキャンセルメールアドレスが公開されることはありません。*次回のコメントで使用するためブラウザーに自分の名前、メールアドレス、サイトを保存する。上に表示された文字を入力してください。