解法の確立とは

例えば、二次方程式は

x=\frac{-b\pm\sqrt{b^2-4ac}}{2a}

のa,b,cに代入することで解を得ることができます。このように単純作業で解を得ることができる問題を、 解法が確立している と言います。
解法が確立していない問題の例として、

などがあります。
このような解法が確立されていない問題を解くには試行錯誤する必要があります。
今回はこのなかで、迷路を解く解法について説明します。

迷路の定義

迷路のいくつかの要素をまとめます。
迷路にはスタートとゴールがあります。
その途中に、節点（分かれ道）、行き止まり節点（行き止まり）があります。これはグラフを使って表すことができます。

こっちのほうがゴールに近そう とかそういうことを考えずに（知識に頼らずに）闇雲に探索する方法をブラインド探索と言います。

今回は、ブラインド探索のうち 深さ優先探索 （depth-first search）と 広さ優先探索 （breadth-first search）について説明します。

行き止まりまで探索し、ゴールが見つからなかったら戻って別の道を進む方法です。
LIFO（後入れ先出し）を使って実現することができます。

同じ深さの分かれ道をそれぞれ探し、ゴールが見つからなかったら次の深さの分かれ道を探す方法です。
分かれ道で影分身して並行して進んでいく みたいなイメージがあります。
これも、LIFOを使って実現可能です。

長くなったので実装はまた別にまとめます。