組み合わせ爆発の問題を解こう その2 – 深さ優先探索(Depth-first Search, DFS)
2012-09-16Mathematics
では早速、スライドパズルを解いてみましょう。問題は、これまでの例題と同じです。
まずは「深さ優先探索」で解いてみます。深さ優先探索でスライドパズルを解くということは、とりあえず、どんどんスライドさせていき、それ以上スライドできなくなったら、1手戻って、別方向にスライドさせる…ということです。といっても、ちょっとわかりませんね。
もう一度、例題を見てみましょう。
一つここで決まりごとを決めます。「動かす方向を検討する順番は上→右→下→左とする」としましょう。例題の状態では…、
- 上には動かせない(壁があるから)
- 右には動かせない(壁があるから)
- 下には動かせる
ということで、下に動かしてみましょう。
下に動かした図は次のとおりです。
では、次の動かし方を検討しましょう。
- 上には動かせるが、初期状態と同じになるから動かさない。
- 右には動かせる。
ということで、右に動かしてみましょう。
右に動かした図は次のとおりです。
では、次の動かし方を検討しましょう。
- 上には動かせない(壁があるから)
- 右には動かせない(壁があるから)
- 下には動かせる
下に動かした図は次のとおりです。
では、次の動かし方を…、ということをどんどん続けていきます。
そうすると、どこかのタイミングで、どちらの方向にも動かせなくなる状態になります(どの方向に動かしても、壁がある、またはこれまで出てきた盤面と同じ状態となる)。その時は、これまで動きをさかのぼり、動かせるところから続ける、ということをします。
例題では、初期状態では下と左に動かせます。1手目に下で動かした場合の動かし方をすべて試したあとに、次に、1手目が左で動かした場合をすべて試します。1手目が左の場合をすべて試したあとは、1手目として取れるすべてのパターンを試したため、プログラムを終了させます。
スライドさせている途中で、完成状態になる場合もありますが、深さ優先探索の欠点は、その完成状態が、最適な動かし方で到達したものかどうかが、その場では判断できないことです。「動かす方向を検討する順番は上→右→下→左とする」という決まりで勝手に動かしたため、ものすごく動かしてからの完成なのかもしれません。どの動かし方が最も手順が少なかったかがわかるのは、すべてのパターンを試した後です。
一応参考までに、下に動かした履歴のうち、最初から100手までを掲載します。コロンより前が盤面の状態(=が壁、0が空白のマス、盤面のサイズが3×3なので、「40=215=86」のとき、1行目が「40=」、2行目が「215」、3行目が「=86」となります)、コロンより後が、その状態を作り出すために動かした空白マスの方向を示します(Uが上、Rが右、Dが下、Lが左)。
| 盤面の状態 | 動かし方 |
|---|---|
| 40=215=86 | |
| 41=205=86 | D |
| 41=250=86 | DR |
| 41=256=80 | DRD |
| 41=256=08 | DRDL |
| 41=206=58 | DRDLU |
| 40=216=58 | DRDLUU |
| 04=216=58 | DRDLUUL |
| 24=016=58 | DRDLUULD |
| 24=106=58 | DRDLUULDR |
| 20=146=58 | DRDLUULDRU |
| 02=146=58 | DRDLUULDRUL |
| 12=046=58 | DRDLUULDRULD |
| 12=406=58 | DRDLUULDRULDR |
| 10=426=58 | DRDLUULDRULDRU |
| 01=426=58 | DRDLUULDRULDRUL |
| 41=026=58 | DRDLUULDRULDRULD |
| 12=460=58 | DRDLUULDRULDRR |
| 12=468=50 | DRDLUULDRULDRRD |
| 12=468=05 | DRDLUULDRULDRRDL |
| 12=408=65 | DRDLUULDRULDRRDLU |
| 10=428=65 | DRDLUULDRULDRRDLUU |
| 01=428=65 | DRDLUULDRULDRRDLUUL |
| 41=028=65 | DRDLUULDRULDRRDLUULD |
| 41=208=65 | DRDLUULDRULDRRDLUULDR |
| 40=218=65 | DRDLUULDRULDRRDLUULDRU |
| 04=218=65 | DRDLUULDRULDRRDLUULDRUL |
| 24=018=65 | DRDLUULDRULDRRDLUULDRULD |
| 24=108=65 | DRDLUULDRULDRRDLUULDRULDR |
| 20=148=65 | DRDLUULDRULDRRDLUULDRULDRU |
| 02=148=65 | DRDLUULDRULDRRDLUULDRULDRUL |
| 12=048=65 | DRDLUULDRULDRRDLUULDRULDRULD |
| 24=180=65 | DRDLUULDRULDRRDLUULDRULDRR |
| 24=185=60 | DRDLUULDRULDRRDLUULDRULDRRD |
| 24=185=06 | DRDLUULDRULDRRDLUULDRULDRRDL |
| 24=105=86 | DRDLUULDRULDRRDLUULDRULDRRDLU |
| 20=145=86 | DRDLUULDRULDRRDLUULDRULDRRDLUU |
| 02=145=86 | DRDLUULDRULDRRDLUULDRULDRRDLUUL |
| 12=045=86 | DRDLUULDRULDRRDLUULDRULDRRDLUULD |
| 12=405=86 | DRDLUULDRULDRRDLUULDRULDRRDLUULDR |
| 10=425=86 | DRDLUULDRULDRRDLUULDRULDRRDLUULDRU |
| 01=425=86 | DRDLUULDRULDRRDLUULDRULDRRDLUULDRUL |
| 41=025=86 | DRDLUULDRULDRRDLUULDRULDRRDLUULDRULD |
| 12=450=86 | DRDLUULDRULDRRDLUULDRULDRRDLUULDRR |
| 12=456=80 | DRDLUULDRULDRRDLUULDRULDRRDLUULDRRD :Solved! |
| 12=485=06 | DRDLUULDRULDRRDLUULDRULDRRDLUULDRD |
| 12=485=60 | DRDLUULDRULDRRDLUULDRULDRRDLUULDRDR |
| 12=480=65 | DRDLUULDRULDRRDLUULDRULDRRDLUULDRDRU |
| 24=150=86 | DRDLUULDRULDRRDLUULDRULDRRDLUR |
| 24=156=80 | DRDLUULDRULDRRDLUULDRULDRRDLURD |
| 24=156=08 | DRDLUULDRULDRRDLUULDRULDRRDLURDL |
| 24=015=86 | DRDLUULDRULDRRDLUULDRULDRRDLUL |
| 04=215=86 | DRDLUULDRULDRRDLUULDRULDRRDLULU |
| 24=168=05 | DRDLUULDRULDRRDLUULDRULDRD |
| 24=168=50 | DRDLUULDRULDRRDLUULDRULDRDR |
| 24=160=58 | DRDLUULDRULDRRDLUULDRULDRDRU |
| 41=280=65 | DRDLUULDRULDRRDLUULDRR |
| 41=285=60 | DRDLUULDRULDRRDLUULDRRD |
| 41=285=06 | DRDLUULDRULDRRDLUULDRRDL |
| 41=268=05 | DRDLUULDRULDRRDLUULDRD |
| 41=268=50 | DRDLUULDRULDRRDLUULDRDR |
| 41=260=58 | DRDLUULDRULDRRDLUULDRDRU |
| 12=480=65 | DRDLUULDRULDRRDLUR |
| 12=485=60 | DRDLUULDRULDRRDLURD |
| 12=485=06 | DRDLUULDRULDRRDLURDL |
| 12=405=86 | DRDLUULDRULDRRDLURDLU |
| 10=425=86 | DRDLUULDRULDRRDLURDLUU |
| 01=425=86 | DRDLUULDRULDRRDLURDLUUL |
| 41=025=86 | DRDLUULDRULDRRDLURDLUULD |
| 12=450=86 | DRDLUULDRULDRRDLURDLUR |
| 12=456=80 | DRDLUULDRULDRRDLURDLURD :Solved! |
| 12=045=86 | DRDLUULDRULDRRDLURDLUL |
| 02=145=86 | DRDLUULDRULDRRDLURDLULU |
| 20=145=86 | DRDLUULDRULDRRDLURDLULUR |
| 24=105=86 | DRDLUULDRULDRRDLURDLULURD |
| 24=150=86 | DRDLUULDRULDRRDLURDLULURDR |
| 24=156=80 | DRDLUULDRULDRRDLURDLULURDRD |
| 24=156=08 | DRDLUULDRULDRRDLURDLULURDRDL |
| 24=185=06 | DRDLUULDRULDRRDLURDLULURDD |
| 24=185=60 | DRDLUULDRULDRRDLURDLULURDDR |
| 24=180=65 | DRDLUULDRULDRRDLURDLULURDDRU |
| 24=108=65 | DRDLUULDRULDRRDLURDLULURDDRUL |
| 20=148=65 | DRDLUULDRULDRRDLURDLULURDDRULU |
| 02=148=65 | DRDLUULDRULDRRDLURDLULURDDRULUL |
| 12=048=65 | DRDLUULDRULDRRDLURDLULURDDRULULD |
| 24=168=05 | DRDLUULDRULDRRDLURDLULURDDRULD |
| 24=168=50 | DRDLUULDRULDRRDLURDLULURDDRULDR |
| 24=160=58 | DRDLUULDRULDRRDLURDLULURDDRULDRU |
| 24=018=65 | DRDLUULDRULDRRDLURDLULURDDRULL |
| 04=218=65 | DRDLUULDRULDRRDLURDLULURDDRULLU |
| 40=218=65 | DRDLUULDRULDRRDLURDLULURDDRULLUR |
| 41=208=65 | DRDLUULDRULDRRDLURDLULURDDRULLURD |
| 41=280=65 | DRDLUULDRULDRRDLURDLULURDDRULLURDR |
| 41=285=60 | DRDLUULDRULDRRDLURDLULURDDRULLURDRD |
| 41=285=06 | DRDLUULDRULDRRDLURDLULURDDRULLURDRDL |
| 41=268=05 | DRDLUULDRULDRRDLURDLULURDDRULLURDD |
| 41=268=50 | DRDLUULDRULDRRDLURDLULURDDRULLURDDR |
| 41=260=58 | DRDLUULDRULDRRDLURDLULURDDRULLURDDRU |
| 41=028=65 | DRDLUULDRULDRRDLURDLULURDDRULLURDL |
| 01=428=65 | DRDLUULDRULDRRDLURDLULURDDRULLURDLU |
| 10=428=65 | DRDLUULDRULDRRDLURDLULURDDRULLURDLUR |
最初の100通りの動かすパターンのうち、2つのパターンが完成状態になっています。
- 12=456=80:DRDLUULDRULDRRDLUULDRULDRRDLUULDRRD:Solved
- 12=456=80:DRDLUULDRULDRRDLURDLURD:Solved
でも、どちらも、最適解(この問題では7手で完成状態になる動かし方があります)である動かし方ではありません。まだまだ、パターンの列挙が足りないのですね。
なお、プログラムを組んで検証すると、この問題では、動かせるパターンは9198通りありました。
深さ優先探索は、上の動かせるパターンを見るとわかりますが、どんどん空白マスを動かそうとするために、動かした履歴が長く長く、たまに短くなって、また、長く長くなっていくという動きになっています。
深さ優先探索でスライドパズルを解くときの特徴は次のとおりです。
- すべてのパターンを網羅するため、必ず最短の動かし方がわかる。
- 解法が見つかっても、その時点で最適なのかが判断できないため、すべての動かし方を試さないと、最適解が分からない。
- メモリの使用量が少ない。
ということで、次回は、幅優先探索で解いてみたいと思います。
Topic
- Mathematics (15)
- Natural Language Processing (1)