Panda Noir

JavaScript の限界を究めるブログです。

アルゴリズム勉強会 第一回 深さ優先探索

(本記事はリライト記事です。元の記事は削除しました)

第一回とありますが続かない可能性が高いです。

深さ優先探索とは

wikiによれば深さ優先探索とは

根から始まり、バックトラックするまで可能な限り探索を行う。

ことだそうです。なんのことだかさっぱりわかりませんね。具体例をみていきましょう。

ここではナンプレ(数独)の解法を例にやっていきます。ここでいうナンプレの解法とは、数字を左上から適当に当てはめていって、間違えていたら数字を変えていくという方法です。要するにゴリ押し

まずは右上の方から数字を埋めていきます。とりあえず「1」で埋めます。1を埋められない場合は2、ダメなら3…ととりあえず埋めてしまいます。埋めたら左にいき、また埋めていきます。

ここで「これを繰り返していたら、そのうちどの数字も入らないマスが出てくるんじゃないか?」と思ったあなた。そのとおりです。ほぼ100%埋まらないマスが出てきます。埋まらないマスが出た=間違えて埋めた数字がある、ということです。

ここであきらめてはいけません。間違えたのなら直前に戻り、違う数字で埋めてみるのです。もしそのマスも埋めることができなくなったらさらに前に戻っていきます。こうして「とりあえずズンズン埋めていって、間違えていたら直前に戻って埋めなおす」、つまり「深さ(=埋めた数)を優先する」探索を深さ優先探索といいます。

深さ優先探索のつかいどころ

これは次回の「幅優先探索」と比較したほうが早いですので、次回紹介します。

深さ優先探索を高速化する

実はさきほどのナンプレの解法も実は高速化してあります、本当の深さ優先探索の場合、以下のようになります。

  1. 右上より左下まで順に「1」で埋める
  2. 空欄がなくなったら、解答が条件を満たす(=それぞれの行、列、同じブロックで9種類すべて数字が使われている)か確認する
  3. 条件を満たしていない場合、直前に埋めたマスをほかの数字で埋めてチェックする
  4. 直前のマスにどの数字を入れても条件を満たせない場合は、さらにさかのぼって数字を変えていく

さすがにアホらしいですよね。ここで「枝切り」をします。枝切りとは、あらかじめ「これは絶対に解答じゃないだろ」というパターンを切り捨てることで探索回数を減らすテクニックです。

今回でいえば「同じ行、列、ブロックに存在しない数字」にしぼりこんで空欄を埋めていけばかなり探索を抑えられますよね。

もちろん、切ってはいけない枝を切るのは言語道断ですし、「切るべきか」判定するのにもコストがかかります。今回のようなケースは明らかに枝切りするべきですが、ほかのケースでは愚直に探索するほうが安全だったりします。

第二回へ続く