深さ優先探索｜Python｜女子大生エンジニアの備忘録 #7
こんにちは、鈴です。
今回は、基本的なアルゴリズムの一つである深さ優先探索についての備忘録です。
アルゴリズムをご紹介した後、Pythonでの実装例を用いて解説を行っていきます。
前回の記事はこちらから↓
では早速行ってみましょう。
深さ優先探索とは
深さ優先探索は、グラフや木構造を探索するための基本的なアルゴリズムの一つです。
木の根にあたる部分からスタートし、それ以上進めない行き止まりの地点まで試行を繰り返し、行き止まりになったらまだ探索が完了していない地点まで戻って探索を行います。
「縦型探索」とも呼ばれています。
基本
深さ優先探索の基本は以下の通りです。
- 全箇所から全方位への移動を試し尽くす
- そのために、試し尽くしていない箇所を覚えておき、後で戻ってくる
実現方法には２種類あります。
再帰関数による探索
位置を引数にした再帰関数による探索で、自ら４方向への呼び出しを行います。
関数 search(x,y) {
if 位置(x,y)が範囲外
return
if 位置(x,y)がすでに探索済み
return
(x,y)に到達したことを記録
#４方向への探索
search(x+1,y) ＃右
search(x-1,y) ＃左
search(x,y+1) ＃下
search(x,y-1) ＃上
}
４方向への関数は再帰関数なので、１方向について全て試した後に帰ってきて次の方向を試すような仕様になっています。
これによって全方位試し尽くすことができます。
問題点としては、試行回数が多い問題の場合に、再帰関数が深くなりすぎることによって「スタックオーバーフロー」というエラーが発生する可能性があることがあげられます。
スタックによる探索
試すべき位置をスタックに保持しておく探索方法です。
再帰呼び出しの代わりに、位置をスタックにプッシュしていきます。
アルゴリスムは以下の通りです。
- 処理のスタート地点の位置をスタックにプッシュ
- スタックからポップ
- 隣にまだ訪れていない場所があればプッシュ
- スタックが空になるまで2.3を繰り返す
こちらの方法の場合、スタックオーバーフローを回避することができます。
Pythonによる実装例
実装例は以下の通りです。
今回は一つ目の探索方法、再帰関数による探索を実装しました。
位置の管理については真偽値を格納する二次元リストで行っています。
サイズは入力で受け取るようにしています。
本来はもう少し受け取る入力がありますが、今回は再帰関数の実装例なので省略しました。
また例として使えそうな問題があれば更新していきます。
まとめ
今回のまとめは以下の通りです。
- 深さ優先探索の基本は全箇所かた全方位への移動を試し尽くす探索
- ある方位について探索し尽くした後、試していない箇所まで戻ってくる
- 実現方法については二種類
- １つ目は、再帰関数による探索方法
- ２つ目は、スタックによる探索方法
- １つ目はスタックオーバーフローに注意
以上です。
余談
スタックオーバーフローのようなエラーは競技プログラミングをするまではあまりみたことがありませんでしたね。
ただやり方がわかってコードが書ければいいってわけじゃないのか！と絶望した記憶があります。
日々勉強ですね。。。
では。
鈴
