探索とは
探索とは、可能性を調べながら解を探す方法。
深さ優先探索とは
最も基礎的な探索の方法。
本記事で学ぶこと
- 深さ優先探索による「塗りつぶし」
- 深さ優先探索の再起関数による実装
- 深さ優先探索のスタックによる実装
問題
入力
- 図のような迷路
- .が通れる
出力
- sからgまでいけるか
塗りつぶし Flood-fill
問題の解き方
- sから行ける場所を全部調べる
- gに行ければ'yes', 行けれなかったら'no'
塗りつぶしは「sから行ける場所を全部調べる」方法であり、とてもよく使われる。
深さ優先探索による塗りつぶし
基本的な考え方
- 今いるところから隣に行こうとしてみる
- まだ行ってなかったらいく
ちゃんと塗りつぶすために
- 全箇所から4方向への移動をためし尽くす
- そのために、ためし尽くしてない場所を覚えておき、戻ってくる
- 戻ってきて別のところに行けたらそっちに行く
- スタート地点に戻ってきたら完了
なぜ深さ優先探索というか
まだ4方向を試し尽くしていない場所の中で、一番「深い」ばよから探索を広げるから
再帰関数による深さ優先探索
考え方
- 位置を引数にした再帰関数を使う
- 自分から4方向への呼び出しを行う
なぜこれで深さ優先探索になるか
- 再帰関数なので呼び出した後戻ってくる
- 戻ってきて違う方向へまた呼び出す
擬似コード
関数 search(x, y) {
if (場所 (x, y) が壁か迷路の外) return
if (既に (x, y) に一度到達している) return
(x, y) に到達したということを記録
//4方向を試す
//再帰関数なので1つの方向を試しおわた後帰ってきて次の方向を試す
search(x + 1, y)
search(x - 1, y)
search(x, y + 1)
search(x, y - 1)
}
スタックによる深さ優先探索
考え方
- 試すべき位置をスタックで管理
- 再帰呼び出しの代わりにスタックへpush
アルゴリズム
- 最初はスタート地点をスタックに投入
- 繰り返す：スタックから位置を取り出して、まだ訪れていない隣があればpush
再帰関数が深くなりすぎると「スタックオーバーフロー」が起こって実行時エラーになることがある。
スタックを用いる方法ならばこれを回避できる。
深さ優先探索のまとめ
深さ優先探索の他の出番
- 組み合わせ全てを試す全探索
- その高速化である枝刈り探索
深さ以外を優先する探索
- 幅優先探索
- 裁量優先探索 （→Dijkstra/Prim のアルゴリズム）
参考
A - 深さ優先探索