#解法の確立とは
例えば、二次方程式は
x=\frac{-b\pm\sqrt{b^2-4ac}}{2a}
のa,b,cに代入することで解を得ることができます。このように単純作業で解を得ることができる問題を、 解法が確立している と言います。
解法が確立していない問題の例として、
- 迷路
- パズル
- ゲーム
などがあります。
このような解法が確立されていない問題を解くには試行錯誤する必要があります。
今回はこのなかで、迷路を解く解法について説明します。
#迷路の定義
迷路のいくつかの要素をまとめます。
迷路にはスタートとゴールがあります。
その途中に、節点（分かれ道）、行き止まり節点（行き止まり）があります。これはグラフを使って表すことができます。
#ブラインド探索
こっちのほうがゴールに近そう とかそういうことを考えずに（知識に頼らずに）闇雲に探索する方法をブラインド探索と言います。
今回は、ブラインド探索のうち 深さ優先探索 （depth-first search）と 広さ優先探索 （breadth-first search）について説明します。
深さ優先探索
行き止まりまで探索し、ゴールが見つからなかったら戻って別の道を進む方法です。
LIFO（後入れ先出し）を使って実現することができます。
###長所と短所
####長所
- わかりやすい
- メモリ使用量が小さい 探索の深さに比例
####短所
- ゴールが近くにあるのに他の深い道に入ってしまうと時間がかかる
##広さ優先探索
同じ深さの分かれ道をそれぞれ探し、ゴールが見つからなかったら次の深さの分かれ道を探す方法です。
分かれ道で影分身して並行して進んでいく みたいなイメージがあります。
これも、LIFOを使って実現可能です。
###長所と短所
####長所
- 経路が最短となる解を見つけることができる
- 分散処理に強い
####短所
- 解が深いと処理時間が増える
- メモリ使用量が大きい 探索の深さに指数的
#ヒューリスティック探索
長くなったので実装はまた別にまとめます。