反復深化深さ優先探索（IDDFS；Iterative deepening depth-first search）やろうぜ（＾～＾）？

「　イテレーティブ　ディープニング　デプス　ファースト　サーチ　やろうぜ？」

「　何だぜ　それ？」

「　時間切れ負け　しないように　途中で　計算を投げ捨てる　探索よ」

「　どうやって　やるんだぜ？」

「　IDDFS のことか。
説明すると　お父んが寝てしまうので　手順を進めながら　やってみよう」

反復深化（Iterative deepening）とは

「　👆　反復深化探索は、よく　こんな絵で　説明されるな」

「　ぢごく　だ。　デザインがうまく機能していない建築だ」

「　将棋盤の前に座っている気分になってくれだぜ」

デプス（Depth）

「　👆　まず、　デプス（Depth）というのを　覚えてくれだぜ。
これから、上図を使って　デプス　を説明しよう」

「　数学に　毒されたみたいな図　わらう」

デプス1

「　👆　デプス１　というのは、最後の扉の　前にいるところだぜ」

「　麻雀の　テンパイ　みたいだな」

「　奥の扉を開けるのは、将棋で例えると　１手指すことだと思ってくれだぜ」

デプス0

「　👆　デプス 0　というのは、基本的には　指さない　ということだぜ」

「　わらう」

「　デプス 0　で何をやるかは　まあ　プログラマーが好きにしろだぜ」

「　何が　できんの？」

「　デプスをいったん忘れて、もうちょっと　深く読む、とか　そういうことだぜ」

「　👆　探索（たんさく；Search）　と呼ばれるものは、行ったっきり戻ってこないものと、
再び帰ってくるものがある。　コンピューター将棋で探索と言えば、　再び帰ってくると思っていい。
これを　再帰（さいき；Recursive）と呼ぶぜ」

「　おかえり」

「　開けた扉を閉めろだぜ」

「　絵を描くのが　めんどくさいので　省略するぜ。
頭の中で　バタン　バタン　してくれだぜ」

「　デプス０　って　Uターン　してくるとこなのね」

「　👆　イテレーションが　1回終わっているときの　デプス 0　もまた、基本的には　指さない　ということだぜ」

「　そこも　デプス０　かあ」

「　その　数えで１歳、　満０歳　みたいなの、どうにかなんないの？」

「　デプス0　と同じ呼ばれ方をしても、
イテレーションが　0回目、1回目、2回目　と増えていくたびに　デプス0　に着くまでに開けたドアの数が増えていることを
よく意識しておいてくれだぜ」

「　ここでクイズだぜ」

「　８年ぐらいブログを書いているが、クイズが出たのは　初めてだよな」

「　先ほどの図で、　イテレーションが　1回終わってるときの　デプス0　のすべての部屋に入ったとき、
それまでに開けた　ドアの数を答えなさい」

「　わざわざ　クイズにするんだから　6　とか答えたら　ハズレなんだろ。
同じ部屋に　何度も出たり入ったりすれば　答えは無限にあるんじゃないかだぜ？」

「　ブーッ。　正解は　８つだぜ。　数えろ」

「　んー、どこを　どう数えたら　８なんて言う　中途半端な数が　出てくるのかなあ？」

「　👆　納得できるまで　数えろだぜ」

「　なんか　何回も同じとこ　通ってる気がするな……」

「　開いているドアの数は　８つ　ねえ」

探索経路

「　👆　イテレーションが　2回終わっているときの　デプス 0　も、基本的には　指さない　ということだぜ」

「　そのドアは、横へ、横へ　開けてんの？」

「　いいや」

「　👆　まず　デプス１　で　深さ優先探索　をするぜ」

「　その　グネグネ　したやつよね」

「　👆　次に　デプス２　で　深さ優先探索　をするぜ」

「　ぜったい　わらう」

「　👆　次に　デプス３　で　深さ優先探索　をするぜ。　おっ、玉を発見」

「　超・大変じゃない？」

「　👆　目的のものを見つければ　すぐ帰ってきても　いいわけだしな」

「　👆　時間が切れる前に　すぐ帰るのも　同じ手順を踏まえろだぜ」

「　👆　時間切れになったら、途中まで探索していた分、全部　無駄になんの？」

「　そのイテレーションで　探索が途中だった分は　無駄になるな」

「　なんだか　もったいないわねえ」