第一回とありますが続かない可能性が高いです。
深さ優先探索とは
根から始まり、バックトラックするまで可能な限り探索を行う。(wiki引用)というアルゴリズムのことです。なんのことだかさっぱりわかりませんね。
例
ここではナンプレ(数独)の解法を例にやっていきます。数字を当てはめていって間違えたらその数字を変えていくという方法です。
この間違えたら数字を変えるというところがミソです。深さ優先探索は木構造をイメージするとわかりやすいです。ナンプレは9×9で合計81マスあって、それぞれに9通りの数字が入ります。つまり9の81乗で…とりあえず大きくなります(実際の問題は埋まっているマスがあるので実際は9の70乗ぐらいです)。
さて、では問題を解いて行きましょう。まずは右上の方から数字を埋めていきます。条件は縦、横、3×3のブロック内に同じ数字がないことです。これに合致する数字の中で一番小さい数字を埋めます。これを右上から左下に向かって繰り返します。もし、そこに数字が埋まらない場合は一つ前の数字を二番目に小さい数字に変えます。これを繰り返していきます。
私もなれてなくて1日かかってしまいましたが、できました。サンプルを置いておきます(注意:アクセスするとお同時に計算が始まります。計算対象は数学者が作った世界一難しいと言われているものです。ただし、軽量化などは一切やってないのでパソコンが熱くなる恐れがあります)。サンプル
まとめ
「根から始まり、バックトラックするまで可能な限り探索を行う。」ナンプレで言うと「右上から数字を埋めて矛盾するまで可能な限り探索を行う(そして矛盾したら一つ前の数字を変えて繰り返す)」ということです。
終わりに
このように置き換えるとわかりやすくなりますよね。次回は(あれば)幅優先探索を解説したいと思います。
